linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...

, a Block LU decomposition is a

matrix decomposition In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...

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 Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...

to reduce the complexity of the block matrix formula.

Block LDU decomposition

\begin
 A & B \\
 C & D 
\end
=
\begin
I & 0 \\
C A^ & I
\end
\begin
A & 0 \\
0 & D-C A^ B
\end
\begin
I & A^ B \\
0 & I
\end

Block Cholesky decomposition

Consider a block matrix: :

\begin
 A & B \\
 C & D 
\end
=
\begin
I \\
C A^
\end
\,A\,
\begin
I & A^B
\end
+
\begin
0 & 0 \\
0 & D-C A^ B
\end,

where the matrix

\beginA\end

is assumed to be non-singular,

\beginI\end

is an identity matrix with proper dimension, and

\begin0\end

is a matrix whose elements are all zero. We can also rewrite the above equation using the half matrices: :

\begin
 A & B \\
 C & D 
\end
=
\begin
A^ \\
C A^
\end
\begin
A^ & A^B
\end
+
\begin
0 & 0 \\
0 & Q^
\end
\begin
0 & 0 \\
0 & Q^
\end
,

where the Schur complement of

\beginA\end

in the block matrix is defined by :

\begin
Q = D - C A^ B
\end

and the half matrices can be calculated by means of

Cholesky decomposition In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for effici ...

LDL decomposition In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for effici ...

. The half matrices satisfy that :

\begin
A^\,A^=A;
\end
\qquad
\begin
A^\,A^=I;
\end
\qquad
\begin
A^\,A^=I;
\end
\qquad
\begin
Q^\,Q^=Q.
\end

Thus, we have :

\begin
 A & B \\
 C & D 
\end
=
LU,

where :

LU =
\begin
A^    & 0 \\
C A^ & 0
\end
\begin
A^ & A^B \\
0               & 0
\end
+
\begin
0 & 0 \\
0 & Q^
\end
\begin
0 & 0 \\
0 & Q^
\end.

The matrix

\beginLU\end

can be decomposed in an algebraic manner into ::

L = 
\begin
A^    & 0 \\
C A^ & Q^
\end
\mathrm
U =
\begin
A^ & A^B \\
0               & Q^
\end.

Block LDU decomposition

Block Cholesky decomposition

See also