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
( A B C D ) = ( I 0 C A − 1 I ) ( A 0 0 D − C A − 1 B ) ( I A − 1 B 0 I ) {\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}}}Block Cholesky decomposition
Consider a block matrix:
( A B C D ) = ( I C A − 1 ) A ( I A − 1 B ) + ( 0 0 0 D − C A − 1 B ) , {\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 A {\displaystyle {\begin{matrix}A\end{matrix}}} is assumed to be non-singular, I {\displaystyle {\begin{matrix}I\end{matrix}}} is an identity matrix with proper dimension, and 0 {\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:
( A B C D ) = ( A 1 2 C A − ∗ 2 ) ( A ∗ 2 A − 1 2 B ) + ( 0 0 0 Q 1 2 ) ( 0 0 0 Q ∗ 2 ) , {\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 A {\displaystyle {\begin{matrix}A\end{matrix}}} in the block matrix is defined by
Q = D − C A − 1 B {\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
A 1 2 A ∗ 2 = A ; A 1 2 A − 1 2 = I ; A − ∗ 2 A ∗ 2 = I ; Q 1 2 Q ∗ 2 = Q . {\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
( A B C D ) = L U , {\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}=LU,}where
L U = ( A 1 2 0 C A − ∗ 2 0 ) ( A ∗ 2 A − 1 2 B 0 0 ) + ( 0 0 0 Q 1 2 ) ( 0 0 0 Q ∗ 2 ) . {\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 L U {\displaystyle {\begin{matrix}LU\end{matrix}}} can be decomposed in an algebraic manner into
L = ( A 1 2 0 C A − ∗ 2 Q 1 2 ) a n d U = ( A ∗ 2 A − 1 2 B 0 Q ∗ 2 ) . {\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}}.}