As Gaussian elimination is applied to a sparse matrix A, row operations tend to introduce nonzero elements into L and U that have no counterpart in A. These nonzero entries in L and U that are induced by the factorization process are referred to as fill-ups. A fact central to sparse matrix techniques is that changes in the pivot strategy change the number fill-ups that occur during factorization.
This being the case, an important goal of sparse matrix algorithms is to find a pivot strategy that minimizes the number of fill-ups during LU decomposition. For the asymmetric case, Rose and Tarjan[15] have shown that this minimization problem is NP complete. For the symmetric case, no optimal solution exists to date. Therefore, existing fill-up reduction algorithms are heuristic in nature.
Among the most successful heuristics are those based on the work of Markowitz [1957]. A Markowitz pivot strategy involves choosing a pivot element aij which minimizes a quantity called the Markowitz count at each elimination step. The Markowitz count is the product
| $$(r_{i}-1)(c_{j}-1)$$ | (91) |
where
ri is the number of entries in row i of the reduced matrix, and
cj is the number of entries in column j of the reduced matrix.
Stability considerations are introduced into Markowitz pivoting strategies by defining numerical thresholds that also apply to pivot candidates. In effect, these thresholds temper sparsity considerations to preserve numerical stability. Typical threshold considerations require that the successful pivot candidate satisfy the following conditions:
| $$|a_{ij}^{\left(k\right)}|\geq u\max_{l\geq k}|a_{ij}^{\left(k\right)}|$$ | (92) |
where u is a number falling in the range $0<u\leq 1$.
Duff
If aji is nonzero whenever aij is nonzero, matrix A has a symmetric sparsity structure. If A is diagonally dominant and has a symmetric sparsity structure, the minimum degree pivot strategy is commonly used to reduce fill-ups during LU decomposition. Minimum degree pivoting is a special case of Markowitz pivoting that ignores the numerical values of aij and concentrates on the structure of A.
The most straightforward motivation of minimum degree pivoting is based on the following observations:
Any matrix A with symmetric sparsity structure can be represented by an undirected, ordered graph G = ( V, E ).
The effect of Gaussian elimination on the sparsity structure of A is modeled by the impact of eliminating vertices from G.
Vertex elimination is examined elsewhere in this series of monographs–see the discussion in Section 8 (Vertex Elimination) of Graph Algorithms for more information. At this point, it suffices to say that a vertex v is eliminated from the graph G = ( V, E ) by
Removing vertex v from V(G).
Removing all edges that were incident upon v from E(G).
Adding edges to E(G) that connect all the vertices that were adjacent to v.
The edges that are added to G when vertex v is eliminated correspond to the fill-ups that occur in A when row v is eliminated.
The minimum degree pivot strategy is just the order in which the following algorithm eliminates the vertices of G.
| for $i=1,\cdots,|V|$ |
| Choose the vertex v from V that has the minimum degree |
| Eliminate vertex v from G |
You should recall that the degree of vertex v is the number of vertices that are adjacent to v. The algorithm has an arbitrary tie-breaking rule. If more than one vertex is of minimum degree at the beginning of an elimination step, any vertex from the group may be eliminated. Gomez and Franquelo in [16] and [17] examine the impact of alternate tie-breaking schemes on minimum degree pivoting strategies.