Block LU decomposition explained
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
\begin{pmatrix}
A&B\\
C&D\end{pmatrix}
=
\begin{pmatrix}
I&0\\
CA-1&I
\end{pmatrix}
\begin{pmatrix}
A&0\\
0&D-CA-1B
\end{pmatrix}
\begin{pmatrix}
I&A-1B\\
0&I
\end{pmatrix}
Block Cholesky decomposition
Consider a block matrix:
\begin{pmatrix}
A&B\\
C&D\end{pmatrix}
=
\begin{pmatrix}
I\\
CA-1\end{pmatrix}
A
\begin{pmatrix}
I&A-1B
\end{pmatrix}
+
\begin{pmatrix}
0&0\\
0&D-CA-1B
\end{pmatrix},
where the matrix
\begin{matrix}A\end{matrix}
is assumed to be non-singular,
\begin{matrix}I\end{matrix}
is an identity matrix with proper dimension, and
\begin{matrix}0\end{matrix}
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 | |
\\
C
| |
| \end{pmatrix}
\begin{pmatrix}
A | |
&
B
\end{pmatrix}
+
\begin{pmatrix}
0&0\\
0&
\end{pmatrix}
\begin{pmatrix}
0&0\\
0&
\end{pmatrix}
,
where the
Schur complement of
\begin{matrix}A\end{matrix}
in the block matrix is defined by
\begin{matrix}
Q=D-CA-1B
\end{matrix}
and the half matrices can be calculated by means of
Cholesky decomposition or LDL decomposition.The half matrices satisfy that
| |
| =A;
\end{matrix}
\begin{matrix}
A | |
| |
| =I;
\end{matrix}
\begin{matrix}
A | |
| |
| =I;
\end{matrix}
\begin{matrix}
Q | |
=Q.
\end{matrix}
Thus, we have
\begin{pmatrix}
A&B\\
C&D\end{pmatrix}
=
LU,
where
LU
&0\\
C
&
| |
| 0
\end{pmatrix}
\begin{pmatrix}
A | |
&
B\\
0&0
\end{pmatrix}
+
\begin{pmatrix}
0&0\\
0&
\end{pmatrix}
\begin{pmatrix}
0&0\\
0&
\end{pmatrix}.
The matrix
\begin{matrix}LU\end{matrix}
can be decomposed in an algebraic manner into
L=
&0\\
C
&
\end{pmatrix}
~~and~~
U
&
B\\
0&
\end{pmatrix}.
See also
