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

$\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)=\left(\begin{array}{cc}I& 0\\ C{A}^{-1}& I\end{array}\right)\left(\begin{array}{cc}A& 0\\ 0& D-C{A}^{-1}B\end{array}\right)\left(\begin{array}{cc}I& A^{-1}B\\ 0& I\end{array}\right)$

Block Cholesky decomposition

Consider a block matrix:

$\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)=\left(\begin{array}{c}I\\ C{A}^{-1}\end{array}\right)A\left(\begin{array}{cc}I& A^{-1}B\end{array}\right)+\left(\begin{array}{cc}0& 0\\ 0& D-C{A}^{-1}B\end{array}\right),$

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

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

$\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)=\left(\begin{array}{c}{A}^{\frac{1}{2}}\\ C{A}^{-\frac{*}{2}}\end{array}\right)\left(\begin{array}{cc}{A}^{\frac{*}{2}}& A^{-\frac{1}{2}}B\end{array}\right)+\left(\begin{array}{cc}0& 0\\ 0& Q^{\frac{1}{2}}\end{array}\right)\left(\begin{array}{cc}0& 0\\ 0& Q^{\frac{*}{2}}\end{array}\right),$

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

$\begin{array}{c}Q=D-C{A}^{-1}B\end{array}$

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

$\begin{array}{c}{A}^{\frac{1}{2}}{A}^{\frac{*}{2}}=A;\end{array}\begin{array}{c}{A}^{\frac{1}{2}}{A}^{-\frac{1}{2}}=I;\end{array}\begin{array}{c}{A}^{-\frac{*}{2}}{A}^{\frac{*}{2}}=I;\end{array}\begin{array}{c}{Q}^{\frac{1}{2}}{Q}^{\frac{*}{2}}=Q.\end{array}$

Thus, we have

$\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)=LU,$

where

$LU=\left(\begin{array}{cc}{A}^{\frac{1}{2}}& 0\\ C{A}^{-\frac{*}{2}}& 0\end{array}\right)\left(\begin{array}{cc}{A}^{\frac{*}{2}}& A^{-\frac{1}{2}}B\\ 0& 0\end{array}\right)+\left(\begin{array}{cc}0& 0\\ 0& Q^{\frac{1}{2}}\end{array}\right)\left(\begin{array}{cc}0& 0\\ 0& Q^{\frac{*}{2}}\end{array}\right).$

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

$L=\left(\begin{array}{cc}{A}^{\frac{1}{2}}& 0\\ C{A}^{-\frac{*}{2}}& Q^{\frac{1}{2}}\end{array}\right)\mathrm{a}\mathrm{n}\mathrm{d}U=\left(\begin{array}{cc}{A}^{\frac{*}{2}}& A^{-\frac{1}{2}}B\\ 0& Q^{\frac{*}{2}}\end{array}\right).$

See also

• Matrix decomposition