Symbolic factorization determines the structure of L and U when the product PAQ is decomposed. The current section examines a procedure for creating this product directly when A does not exist. Pivoting down the diagonal of the resulting matrix creates the LU decomposition predicted by symbolic factorization.
More specifically, the current section describes an algorithm which acts on the adjacency list A of an undirected graph G = ( V, E ) to create a matrix with symmetric sparsity pattern that represents the product
| $$\mathbf{PA{P}^{T}}$$ |
where
A is the sparse matrix that corresponds to the graph G.
P is the row permutation matrix corresponding to the minimum degree labeling of V.
It is assumed that A has been expanded to accommodate fill-ups that will occur during LU decomposition and that the permutation matrix P is implemented as
A list L which traverses V in minimum degree order, and
A mapping $\psi$ whose domain is the initial label of a vertex v from V(G) and whose range is the minimum degree label of v. That is, $\psi(v)$ returns the minimum degree label of v.
Section 8.4.1 describes a procedure that creates the augmented adjacency list A and the permutation matrix P in the desired form.
It is further assumed that both the adjacency list A and the matrix PAPT are maintained in sparse data structures that support the scan and insert operators. The operation make_element initializes element aij of sparse matrix A when its row and column indices, i and j, are specified. Communication with the data structures is maintained through buffers e and a in the normal manner.
Algorithm 23 constructs the full, asymmetric matrix PAPT based on these assumptions. Zero valued entries are created for elements that will fill up during LU decomposition.
| $v=$ first( $L$ ) |
| for $i=1,\cdots,|V|$ |
| while[ $w=$ iterate( $v,1,|V|,e$ ) ] $\neq$ finished |
| if $e.fillup$ is true |
| $a=0$ |
| else |
| make_element( $\mathbf{A},v,w,a$ ) |
| $j=\psi$( $w$ ) |
| insert( $\mathbf{PAP^{T}},i,j,a$ ) |
| make_element( $\mathbf{A},v,v,a$ ) |
| insert( $\mathbf{PAP^{T}},i,i,a$ ) |
| $a=$ row header |
| insert( $\mathbf{PAP^{T}},i,0,a$ ) |
| $v=$ next( $L,v$ ) |
| $^\dagger$ Operations and data types are defined in Section 8.2. |
Algorithm 24 constructs the symmetric matrix PAPT. Zero valued entries are created for elements that will fill up during LU decomposition.
| $v=$ first( $L$ ) |
| for $i=1,\cdots,|V|$ |
| while[ $w=$ iterate( $A$,vertex $v,1,|V|,e$ ) ] $\neq$ finished |
| $j=\psi$( $w$ ) |
| if $j>i$ |
| if $e.fillup$ is true |
| $a=0$ |
| else |
| make_element( $\mathbf{A},v,w,a$ ) |
| insert( $\mathbf{PAP^{T}},i,j,a$ ) |
| make_element( $\mathbf{A},v,v,a$ ) |
| insert( $\mathbf{PAP^{T}},i,i,a$ ) |
| $v=$ next( $L,v$ ) |
| $^\dagger$ Operations and data types are defined in Section 8.2. |