8.5 Creating PAPT from a Symbolic Factorization

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, ψ(v)\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.

Algorithm 23: Construct PAPT of a Sparse Matrix
v= v=\text{ }first(LL)
for i=1,,|V|i=1,\cdots,|V|
    while[w=w=iterate(AA,vertex v,1,|V|,ev,1,|V|,e)] \neq finished
        if e.fillupe.fillup is true
            a=0a=0
        else
            make_element(𝐀,v,w,a\mathbf{A},v,w,a)
        j=ψj=\psi(ww)
        insert(𝐏𝐀𝐏𝐓,i,j,a\mathbf{PAP^{T}},i,j,a)
    make_element(𝐀,v,v,a\mathbf{A},v,v,a)
    insert(𝐏𝐀𝐏𝐓,i,i,a\mathbf{PAP^{T}},i,i,a)
    a=a= row header
    insert(𝐏𝐀𝐏𝐓,i,0,a\mathbf{PAP^{T}},i,0,a)
    v= v=\text{ }next(L,vL,v)
† 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 upduring LU decomposition.

Algorithm 24: Construct PAPT of a Sparse Symmetric Matrix
v= v=\text{ }first(LL)
for i=1,,|V|i=1,\cdots,|V|
    while[w=w=iterate(AA,vertex v,1,|V|,ev,1,|V|,e)] \neq finished
        j=ψj=\psi(ww)
        if j>ij>i
            if e.fillupe.fillup is true
                a=0a=0
            else
                make_element(𝐀,v,w,a\mathbf{A},v,w,a)
            insert(𝐏𝐀𝐏𝐓,i,j,a\mathbf{PAP^{T}},i,j,a)
    make_element(𝐀,v,v,a\mathbf{A},v,v,a)
    insert(𝐏𝐀𝐏𝐓,i,i,a\mathbf{PAP^{T}},i,i,a)
    v= v=\text{ }next(L,vL,v)
† Operations and data types are defined in Section 8.2.