7.2 LU Decomposition of Symmetric Matrices

Given the symmetric structure of the LDU factors of a symmetric matrix (see Section 7.1) and the common use of LU factorization in the analysis of linear systems, it is constructive to develop expressions that relate an explicit LU decomposition to an implicit LDU factorization. In subsequent sections of this document, they will prove useful in deriving symmetric variants of the algorithms discussed in Section 4 and Section 5.

In other words, the symmetric factorization algorithms discussed in this document assume an LU decomposition exists (or is to be computed) such that

  • Its existing (explicit) factorization (either L or U) is triangular, and

  • The desired (implicit) factorization is unit triangular.

This implies that algorithms which deal with an explicit set of lower triangular factors, call them 𝐋¯\mathbf{\overline{L}}, will associate the factors of an implicit LDU decomposition as follows

𝐋¯=𝐋𝐃\mathbf{\overline{L}=LD} (77)

or

𝐋=𝐋¯𝐃-𝟏\mathbf{L=\overline{L}{D}^{-1}}

Substituting for L based on Equation 74 yields

𝐔𝐓=𝐋¯𝐃-𝟏\mathbf{{U}^{T}=\overline{L}{D}^{-1}} (78)

Recalling that the inverse of a diagonal matrix is the arithmetic inverse of each element and taking the product yields

uji=l¯ijdii{u}_{ji}=\frac{{\overline{l}}_{ij}}{{d}_{ii}}

Since dii=l¯ii{d}_{ii}={\overline{l}}_{ii},

uij=l¯jil¯jj{u}_{ij}=\frac{{\overline{l}}_{ji}}{{\overline{l}}_{jj}} (79)

In a similar vein, algorithms that deal with an explicit set of upper triangular factors, call them 𝐔¯\mathbf{\overline{U}}, will associate the factors of an LDU decomposition as follows.

𝐔¯=𝐃𝐔\mathbf{\overline{U}=DU} (80)

This association yields the following relationship between the explicit factors 𝐔¯\mathbf{\overline{U}} and implicit factors L.

lij=u¯jiu¯jj{l}_{ij}=\frac{{\overline{u}}_{ji}}{{\overline{u}}_{jj}} (81)

These observations show that it is only necessary to compute and store 𝐋¯\mathbf{\overline{L}} or 𝐔¯\mathbf{\overline{U}} during the LU factorization of a symmetric matrix. This halves the arithmetic required during the factorization procedure. However, symmetry does not reduce the work required during forward and backward substitution.