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
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/064bf58095d9594d8b4300a7e5da6a876c6835bb)
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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f5a602816cc31f8dac80d1cba84f72e477b9e08)
where the matrix
is assumed to be non-singular,
is an identity matrix with proper dimension, and
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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/720913e757f140144bbb9dd18ad3a2b4d1c0309f)
where the Schur complement of
in the block matrix is defined by
![{\displaystyle {\begin{matrix}Q=D-CA^{-1}B\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7c2c67586bb208b3f675087fb6d0582fbc45a32)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48d56884218aca3ef4521aa2e4dc5d2ac7db80d8)
Thus, we have
![{\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}=LU,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91454e4b2c3c6b7bb4f67fb5b21994a3d0d051ff)
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae053d35aaba19e1ca7f1a10395f26f8f34b323a)
The 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6538efdcb61116f1b992a5c419c9f315c217aac6)
See also
References