Sparse direct elimination and ordering — Examples

Write a vector as $x=(x_0,y_1,\dots ,y_m)$. The quadratic form is $x^{T}Ax=x_0^2+{\sum }_i{y}_i^2+2t{x}_0{\sum }_i{y}_i$. Since $m{\sum }_i{y}_i^2-({\sum }_i{y}_i{)}^2={\sum }_{i<j}(y_i-y_j{)}^2\ge 0$, we have $\mathrm{\mid }{\sum }_i{y}_i\mathrm{\mid }\le \sqrt{m}\mathrm{\parallel }y{\mathrm{\parallel }}_2$. Therefore $2t\mathrm{\mid }{x}_0\mathrm{\mid }\mid {\sum }_i{y}_i\mid \le 2t\sqrt{m}\mathrm{\mid }{x}_0\mathrm{\mid }\mathrm{\parallel }y{\mathrm{\parallel }}_2\le t\sqrt{m}(x_0^2+\mathrm{\parallel }y{\mathrm{\parallel }}_2^2)=\frac{1}{2}\mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{.}$ It follows that $x^{T}Ax\ge \frac{1}{2}\mathrm{\parallel }x{\mathrm{\parallel }}_2^2>0$ for $x\mathrm{\ne }0$, so $A$ is positive definite.

In leaf-first order, each leaf has exactly one later neighbor, the center. By [F1] no pair of distinct remaining neighbors exists, so eliminating that leaf adds no edge. This holds for every leaf; eliminating the last center also adds no edge.

In center-first order, the center's later-neighbor set is all $m$ leaves. By [F1], the graph update inserts every pair of distinct leaves, so it has $\left(\genfrac{}{}{0px}{}{m}{2}\right)$ leaf-to-leaf fill edges not in the original star.

The pivot at the center is $1$. Its Schur complement on the leaves is $I_m-t^2{\mathbf{11}}^T$, whose off-diagonal entries are $-t^2\mathrm{\ne }0$. Thus the symbolic fill edges from step 1.3 are also numerical nonzeros for this matrix, while step 1.2 gives no fill in the other order.

Steps 1.2 and 2.1 exhibit respectively $0$ and $\left(\genfrac{}{}{0px}{}{m}{2}\right)$ fill edges for two orderings of the same positive-definite sparse matrix.

The determinant of $A$ is $-1$, so $A$ is nonsingular. Its eigenvectors $(1,1{)}^T$ and $(1,-1{)}^T$ have eigenvalues $1$ and $-1$, respectively; therefore $A$ is indefinite.

Both diagonal candidates have pivot $0$, while the other entry in each column has modulus $1$. Since ${\theta }^{-1}\mathrm{\mid }0\mathrm{\mid }=0$, neither one-by-one test in [F1] passes.

For the declared block $D=A$, $\det D=-1\mathrm{\ne }0$ and $D^{-1}=A$. There are no external indices, so $c_1=c_2=0$ and the two-by-two threshold left side is zero; the test in [F1] passes.

The algorithm therefore returns $P=I$, $L=I$, and $D_{\mathrm{b}\mathrm{l}\mathrm{k}}=A$. Direct multiplication gives $A=L{D}_{\mathrm{b}\mathrm{l}\mathrm{k}}{L}^{\ast }$. Thus the block pivot succeeds where every one-by-one diagonal pivot fails.

For every grid vertex $v$, let $b(v)=4-{\mathrm{deg}}_{G_k}(v)$ be its number of missing boundary neighbors. Expanding squares gives $x^T{A}_{k}x={\sum }_{\{v,w\}\in E(G_k)}(x_v-x_w{)}^2+{\sum }_{v\in G_k}b(v)x_v^2\mathrm{.}$ The right side is nonnegative. If it is zero, every adjacent pair has equal coordinates and every boundary vertex with $b(v)>0$ has value zero. The grid is connected and has a boundary vertex, so all coordinates are equal to zero. Hence $A_k$ is positive definite.

By [F1], the order is the coordinate nested-dissection order on the five-point grid. The matrix is symmetric positive definite by step 1.1 and its off-diagonal pattern is exactly $G_k$. For $k\ge 2$, applying [F2] with $n=k^2$ to exact scalar multifrontal Cholesky gives arithmetic work $O((k^2{)}^{3\mathrm{/}2})=O(k^3)$ and symbolic factor storage $O(k^2\log (k^2))=O(k^2\log k)$, with the allocation convention of [F2]. For $k=1$, the matrix and factor each have one entry.

Step 1.1 verifies the matrix hypothesis and step 2.1 gives the nested-dissection cost specialization.