Sparse matrix models and kernel costs — Examples

The row-pointer array has length $5$, starts at $0$, ends at $10$, and is nondecreasing. Every listed column index lies in $\{0,1,2,3\}$, so the data satisfy the CSR invariants for a $4$ by $4$ matrix.

Row $0$ uses columns $0,1$ with values $2,-1$; row $1$ uses columns $0,1,2$ with values $-1,2,-1$; row $2$ uses columns $1,2,3$ with values $-1,2,-1$; row $3$ uses columns $2,3$ with values $-1,2$. These rational sums are the specified entries of $T$, so the record represents $T$.

The row formulas give $y_0=2(1)-1(2)=0$, $y_1=-1(1)+2(2)-1(3)=0$, $y_2=-1(2)+2(3)-1(4)=0$, and $y_3=-1(3)+2(4)=5$ in $\mathbb{Q}$.

By [L3], these row values are the exact matrix-vector output, so the algorithm returns $(0,0,0,5)$.

The CSR has $s=10$ entries and $m=4$ rows. [L4] gives $10$ multiplications, $10$ additions, $4$ initializations, and $2(10)+4+1=25$ input slots.

The off-diagonal nonzero entries of $A$ are exactly $A_{01}=A_{10}=-1$ and $A_{12}=A_{21}=-1$, so the initial structural graph is the path with edges $\{0,1\}$ and $\{1,2\}$. The first pivot is $p_0=A_{11}=2\mathrm{\ne }0$, so [A1] defines $S^1=\left(\begin{array}{cc}3\mathrm{/}2& -1\mathrm{/}2\\ -1\mathrm{/}2& 3\mathrm{/}2\end{array}\right)$ on the remaining labels $(0,2)$. Now $p_1=S_{00}^1=3\mathrm{/}2\mathrm{\ne }0$, so the next update is defined and gives $S_{22}^2=3\mathrm{/}2-(-1\mathrm{/}2{)}^2\mathrm{/}(3\mathrm{/}2)=4\mathrm{/}3$. Hence $p_2=4\mathrm{/}3\mathrm{\ne }0$, and its update leaves the empty matrix. Thus all three pivots are nonzero and every stage is defined.

The first eliminated vertex is $v_0=1$, whose later-neighbor set is $\{0,2\}$. By [L1] its elimination adds the previously absent edge $\{0,2\}$; the computed $S_{02}^1=-1\mathrm{/}2$ is nonzero. Since $A$ is symmetric over the field $\mathbb{Q}$ and step 1.1 verifies all pivots, [L4] applies to these Schur complements. After the first elimination only two vertices remain, so later eliminations cannot join a new pair. Thus this ordering creates exactly one fill edge, realized by a numerical nonzero.

This ordering creates one structural fill edge. The computation gives a finite example only and supplies no general fill bound.

All three off-diagonal positions of $A$ are nonzero, so the initial graph has edges $\{0,1\}$, $\{0,2\}$, and $\{1,2\}$. Eliminating vertex $1$ leaves $\{0,2\}$ as a later-neighbor pair, and [L1] retains its edge in the filled graph.

The first pivot is $2$, and the update in [L3] gives $S_{02}^1=1\mathrm{/}2-(1)(1)\mathrm{/}2=0$. The two remaining diagonal entries are $3-1\mathrm{/}2=5\mathrm{/}2$, so the last two pivots are both $5\mathrm{/}2$ and are nonzero. Thus all pivots are nonzero while the numerical support loses $\{0,2\}$.

By [L4], the filled graph contains the numerical support; step 1.1 shows its edge $\{0,2\}$ remains, while step 2.1 shows the corresponding numerical entry is zero. Thus the inclusion is strict in this example.

The pointers $0,2,3$ delimit two entries in row $0$ and one in row $1$; all column indices lie in $\{0,1,2\}$. Row $0$ contributes $2+(-2)=0$ to column $1$, and row $1$ contributes $0$ to column $0$. Thus every matrix entry is zero, while all three values are stored.

The products in row $0$ are $2(5)$ and $(-2)(5)$, which sum to $0$; the row $1$ product is $0(4)=0$. By [L3], the algorithm returns $(0,0)$.

There are three stored entries and two rows, so [L4] gives $3$ multiplications, $3$ additions, $2$ initializations, and $2(3)+2+1=9$ CSR input slots. This noncanonical record has $s=3\mathrm{\ne }\mathrm{nnz}(A)=0$.