Block LU decomposition
{{More citations needed|date=June 2025}}
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.{{cite journal |last1=Gallivan |first1=K. A. |last2=Plemmons |first2=R. J. |last3=Sameh |first3=A. H. |title=Parallel Algorithms for Dense Linear Algebra Computations |journal=SIAM Review |date=1990 |volume=32 |issue=1 |pages=94–95 |url=https://www.jstor.org/stable/2030382 |access-date=24 June 2025 |issn=0036-1445}}
Block LDU decomposition
:
\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}
Block Cholesky decomposition
Consider a block matrix:
:
\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},
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:
:
\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}{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
in the block matrix is defined by
:
\begin{matrix}
Q = D - C A^{-1} B
\end{matrix}
and the half matrices can be calculated by means of Cholesky decomposition or LDL decomposition.
The half matrices satisfy that
:
\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
:
\begin{pmatrix}
A & B \\
C & D
\end{pmatrix}
=
LU,
where
:
LU =
\begin{pmatrix}
A^{\frac{1}{2}} & 0 \\
C A^{-\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 can be decomposed in an algebraic manner into
::
\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}{2}}B \\
0 & Q^{\frac{*}{2}}
\end{pmatrix}.