Block LU decomposition

In linear algebra, a Block LU decomposition is a matrix decomposition of a block matrix into a lower block triangular matrix L and an upper block triangular matrix U. This decomposition is used in numerical analysis to reduce the complexity of the block matrix formula.^[1]

${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix}}{\begin{pmatrix}A&0\0円&D-CA^{-1}B\end{pmatrix}}{\begin{pmatrix}I&A^{-1}B\0円&I\end{pmatrix}}}${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix}}{\begin{pmatrix}A&0\0円&D-CA^{-1}B\end{pmatrix}}{\begin{pmatrix}I&A^{-1}B\0円&I\end{pmatrix}}}

Consider a block matrix:

${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I\\CA^{-1}\end{pmatrix}},円A,円{\begin{pmatrix}I&A^{-1}B\end{pmatrix}}+{\begin{pmatrix}0&0\0円&D-CA^{-1}B\end{pmatrix}},}${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I\\CA^{-1}\end{pmatrix}},円A,円{\begin{pmatrix}I&A^{-1}B\end{pmatrix}}+{\begin{pmatrix}0&0\0円&D-CA^{-1}B\end{pmatrix}},}

where the matrix ${\displaystyle {\begin{matrix}A\end{matrix}}}${\displaystyle {\begin{matrix}A\end{matrix}}} is assumed to be non-singular, ${\displaystyle {\begin{matrix}I\end{matrix}}}${\displaystyle {\begin{matrix}I\end{matrix}}} is an identity matrix with proper dimension, and ${\displaystyle {\begin{matrix}0\end{matrix}}}${\displaystyle {\begin{matrix}0\end{matrix}}} is a matrix whose elements are all zero.

We can also rewrite the above equation using the half matrices:

${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}A^{\frac {1}{2}}\\CA^{-{\frac {*}{2}}}\end{pmatrix}}{\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\end{pmatrix}}+{\begin{pmatrix}0&0\0円&Q^{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&0\0円&Q^{\frac {*}{2}}\end{pmatrix}},}${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}A^{\frac {1}{2}}\\CA^{-{\frac {*}{2}}}\end{pmatrix}}{\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\end{pmatrix}}+{\begin{pmatrix}0&0\0円&Q^{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&0\0円&Q^{\frac {*}{2}}\end{pmatrix}},}

where the Schur complement of ${\displaystyle {\begin{matrix}A\end{matrix}}}${\displaystyle {\begin{matrix}A\end{matrix}}} in the block matrix is defined by

${\displaystyle {\begin{matrix}Q=D-CA^{-1}B\end{matrix}}}${\displaystyle {\begin{matrix}Q=D-CA^{-1}B\end{matrix}}}

and the half matrices can be calculated by means of Cholesky decomposition or LDL decomposition. The half matrices satisfy that

${\displaystyle {\begin{matrix}A^{\frac {1}{2}},円A^{\frac {*}{2}}=A;\end{matrix}}\qquad {\begin{matrix}A^{\frac {1}{2}},円A^{-{\frac {1}{2}}}=I;\end{matrix}}\qquad {\begin{matrix}A^{-{\frac {*}{2}}},円A^{\frac {*}{2}}=I;\end{matrix}}\qquad {\begin{matrix}Q^{\frac {1}{2}},円Q^{\frac {*}{2}}=Q.\end{matrix}}}${\displaystyle {\begin{matrix}A^{\frac {1}{2}},円A^{\frac {*}{2}}=A;\end{matrix}}\qquad {\begin{matrix}A^{\frac {1}{2}},円A^{-{\frac {1}{2}}}=I;\end{matrix}}\qquad {\begin{matrix}A^{-{\frac {*}{2}}},円A^{\frac {*}{2}}=I;\end{matrix}}\qquad {\begin{matrix}Q^{\frac {1}{2}},円Q^{\frac {*}{2}}=Q.\end{matrix}}}

Thus, we have

${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}=LU,}${\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}=LU,}

where

${\displaystyle LU={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\frac {*}{2}}}&0\end{pmatrix}}{\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\0円&0\end{pmatrix}}+{\begin{pmatrix}0&0\0円&Q^{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&0\0円&Q^{\frac {*}{2}}\end{pmatrix}}.}${\displaystyle LU={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\frac {*}{2}}}&0\end{pmatrix}}{\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\0円&0\end{pmatrix}}+{\begin{pmatrix}0&0\0円&Q^{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&0\0円&Q^{\frac {*}{2}}\end{pmatrix}}.}

The matrix ${\displaystyle {\begin{matrix}LU\end{matrix}}}${\displaystyle {\begin{matrix}LU\end{matrix}}} can be decomposed in an algebraic manner into

${\displaystyle L={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\frac {*}{2}}}&Q^{\frac {1}{2}}\end{pmatrix}}\mathrm {~~and~~} U={\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\0円&Q^{\frac {*}{2}}\end{pmatrix}}.}${\displaystyle L={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\frac {*}{2}}}&Q^{\frac {1}{2}}\end{pmatrix}}\mathrm {~~and~~} U={\begin{pmatrix}A^{\frac {*}{2}}&A^{-{\frac {1}{2}}}B\0円&Q^{\frac {*}{2}}\end{pmatrix}}.}

• Matrix decomposition

• Matrix decompositions
• Linear algebra

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from June 2025
• All articles needing additional references