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
:<math>
\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}
=
\begin{pmatrix}
I & 0 \\
C A^{-1} & I
\end{pmatrix}
\begin{pmatrix}
A & 0 \\
0 & D-C A^{-1} B
\end{pmatrix}
\begin{pmatrix}
I & A^{-1} B \\
0 & I
\end{pmatrix}
</math>
Block Cholesky decomposition
Consider a block matrix:
:<math>
\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}
=
\begin{pmatrix}
I \\
C A^{-1}
\end{pmatrix}
\,A\,
\begin{pmatrix}
I & A^{-1}B
\end{pmatrix}
+
\begin{pmatrix}
0 & 0 \\
0 & D-C A^{-1} B
\end{pmatrix},
</math>
where the matrix <math>\begin{matrix}A\end{matrix}</math> is assumed to be non-singular,
<math>\begin{matrix}I\end{matrix}</math> is an identity matrix with proper dimension, and <math>\begin{matrix}0\end{matrix}</math> is a matrix whose elements are all zero.
We can also rewrite the above equation using the half matrices:
:<math>
\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}
=
\begin{pmatrix}
A^{\frac{1}{2 \\
C A^{-\frac{*}{2
\end{pmatrix}
\begin{pmatrix}
A^{\frac{*}{2 & A^{-\frac{1}{2B
\end{pmatrix}
+
\begin{pmatrix}
0 & 0 \\
0 & Q^{\frac{1}{2
\end{pmatrix}
\begin{pmatrix}
0 & 0 \\
0 & Q^{\frac{*}{2
\end{pmatrix}
,</math>
where the Schur complement of <math>\begin{matrix}A\end{matrix}</math>
in the block matrix is defined by
:<math>
\begin{matrix}
Q = D - C A^{-1} B
\end{matrix}
</math>
and the half matrices can be calculated by means of Cholesky decomposition or LDL decomposition.
The half matrices satisfy that
:<math>
\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}</math>
Thus, we have
:<math>
\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}
=
LU,
</math>
where
:<math>
LU =
\begin{pmatrix}
A^{\frac{1}{2 & 0 \\
C A^{-\frac{*}{2 & 0
\end{pmatrix}
\begin{pmatrix}
A^{\frac{*}{2 & A^{-\frac{1}{2B \\
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}.
</math>
The matrix <math>\begin{matrix}LU\end{matrix}</math> can be decomposed in an algebraic manner into
::<math>L =
\begin{pmatrix}
A^{\frac{1}{2 & 0 \\
C A^{-\frac{*}{2 & Q^{\frac{1}{2
\end{pmatrix}
\mathrm{~~and~~}
U =
\begin{pmatrix}
A^{\frac{*}{2 & A^{-\frac{1}{2B \\
0 & Q^{\frac{*}{2
\end{pmatrix}.
</math>
See also
- Matrix decomposition