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.

Block LDU decomposition

An LU decomposition is LDU (Lower-Diagonal-Upper) decomposition may be performed if ${\textstyle A}$ is non-singular. Consider a block matrix:

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

This may be useful for inversion if also ${\textstyle D-CA^{-1}B}$ (the Schur complement) is non-singular:

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

An equivalent UDL decomposition exists if ${\textstyle D}$ is non-singular:

${\begin{bmatrix}A&B\\C&D\end{bmatrix}}={\begin{bmatrix}I&BD^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}{\begin{bmatrix}I&0\\D^{-1}C&I\end{bmatrix}}$

This may be useful for inversion if ${\textstyle A-BD^{-1}C}$ is non-singular:

${\begin{bmatrix}A&B\\C&D\end{bmatrix}}^{-1}={\begin{bmatrix}I&0\\D^{-1}C&I\end{bmatrix}}^{-1}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}^{-1}{\begin{bmatrix}I&BD^{-1}\\0&I\end{bmatrix}}^{-1}={\begin{bmatrix}I&0\\-D^{-1}C&I\end{bmatrix}}{\begin{bmatrix}A-BD^{-1}C&0\\0&D\end{bmatrix}}^{-1}{\begin{bmatrix}I&-BD^{-1}\\0&I\end{bmatrix}}$

Block Cholesky decomposition

If the matrix is symmetric, then an alternative simplification is as follows:

${\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 ${\begin{matrix}A\end{matrix}}$ is assumed to be non-singular, ${\begin{matrix}I\end{matrix}}$ is an identity matrix with proper dimension, and ${\begin{matrix}0\end{matrix}}$ is a matrix whose elements are all zero.

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

${\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}A^{\frac {1}{2}}\\CA^{-{\frac {1}{2}}}\end{pmatrix}}{\begin{pmatrix}A^{\frac {1}{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 {1}{2}}\end{pmatrix}},$

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

${\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

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

Thus, we have

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

where

$LU={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\frac {1}{2}}}&0\end{pmatrix}}{\begin{pmatrix}A^{\frac {1}{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 {1}{2}}\end{pmatrix}}.$

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

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

See also

• Matrix decomposition
• Schur complement