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 Cholesky decomposition

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}},}$

where the matrix ${\displaystyle {\begin{matrix}A\end{matrix}}}$ is assumed to be non-singular, ${\displaystyle {\begin{matrix}I\end{matrix}}}$ is an identity matrix with proper dimension, and ${\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 {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 ${\displaystyle {\begin{matrix}A\end{matrix}}}$ in the block matrix is defined by

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

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

where

${\displaystyle 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 ${\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 {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}}.}$

Block LDU decomposition

An alternative to LU decomposition is LDU (Lower-Diagonal-Upper) decomposition if ${\textstyle A}$ is non-singular, which may be simpler to implement:

${\displaystyle {\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}$ is non-singular:

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

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

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

See also

• Matrix decomposition
• Schur complement