The goal of symbolic factorization is to define the sparsity pattern of the LU decomposition of a sparse matrix A. Recall that
| $$\mathbf{LU=PAQ}$$ | (93) |
where P and Q are row and column permutations that reflect the pivot strategy associated with the factorization process.
The goal of the current section is somewhat more specific. It describes a symbolic factorization algorithm that simulates the decomposition of A when a minimum degree pivot strategy is applied. The algorithm operates on an undirected graph G = ( V, E ) whose vertices V are labeled from 1 to $\left|V\right|.$ G is defined by its adjacency list A. The algorithm arrives at a symbolic factorization by eliminating vertices from G. Each stage of the process creates a reduced graph G $^{\prime}$ = ( V $^{\prime}$, E $^{\prime}$ ). The vertex v with the minimum degree in G $^{\prime}$ is chosen as the next elimination candidate. The algorithm describes the structure of L, U, P, and Q in the following manner:
The adjacency list A is augmented to account for fill-ups that will occur during numeric factorization.
A list L is created. The list orders the vertices in V according to a minimum degree pivot strategy. If the vertices of V are labeled according to their position in LU, a minimum degree ordering of V is generated.
A mapping $\psi$ is created. The domain of $\psi$ is the initial label of vertex v. The range of $\psi$ is the minimum degree label of v. That is, $\psi(v)$ is the minimum degree label of v.
A mapping $\tau$ is created. The domain of $\tau$ is the the minimum degree label of vertex v. The range of $\tau$ is the initial label of v. That is, if $\overline{v}$ is the minimum degree label of a vertex, $\tau(\overline{v})$ is the initial label of the vertex.
One field associated with edge eij in the adjacency list contains a binary variable indicating whether edge (i,j) is a fill-up or not. The fill-up indicator is communicated through the buffer e in the normal manner.
Algorithm 22 computes a symbolic factorization of G that consists of these four data structures.
| for $i=1,\cdots,|V|$ |
| $v=$ minimum_degree( $V^{\prime}$ ) |
| while[ $w=$ iterate( $A$, vertex $v,1,|V|,e$ ) ] $\neq$ finished |
| if in_graph( $V^{\prime},w$ ) |
| decrease_degree( $V^{\prime},w$ ) |
| push_iteration |
| while[ $z=$iterate( $A$,vertex $v,w+1,|V|,e$ ) ] $\neq$ finished |
| $e.fillup=$ true |
| if insert( $A,z,w,e$ ) |
| increase_degree( $V^{\prime},z$ ) |
| insert( $A,w,z,e$ ) |
| increase_degree( $V^{\prime},w$ ) |
| pop_iteration |
| remove( $V^{\prime},v$ ) |
| map( $\psi,v,i$ ) |
| map( $\tau,i,v$ ) |
| link( $L,v$ ) |
| $^\dagger$ Operations and data types are defined in Sections 8.2.2 - 8.2.5. |
A few observations concerning the factorization procedure:
The reduced graph G$^{\prime}$ is tracked in data structures designed to model vertex elimination – see Section 8.2.3 of this monograph and Section 8 (Vertex Elimination) of its companion Graph Algorithms for implementation details.
The adjacency list A is augmented to log fill-ups but it is never diminished to reflect graph reduction.
If the algorithm is efficiently implemented, $\psi$, $\tau$, and l can occupy space that is vacated as G$^{\prime}$ shrinks.
The complexity of the symbolic factorization is determined by the size of the adjacency list. One iteration of the main loop requires $\frac{{e}^{2}-e}{2}$ adjacency list accesses, where e is the number of edges incident upon vertex v. If all vertices in V have the same number of incident edges, the total operation count is $\left|V\right|\frac{{e}^{2}-e}{2}$. In this case, the time complexity of symbolic factorization is $O\left(\left|V\right|{e}^{2}\right)$ if all operations on the data structures are O(1).
Consider the following comparison of symbolic factorization operation counts to those associated with the LU decomposition of a dense matrix. If a graph has 100 vertices each of which has 5 incident edges, computing the symbolic factorization requires 1000 operations. Computing the dense factorization requires 661,650 operations. If the number of vertices increases to 1000 while the incident edges per vertex remains constant (the typical scenario in network analysis problems associated with electric power systems), symbolic factorization requires 1 × 104 operations and dense matrix decomposition requires 6 × 108 operations.