- Source: 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
(
A
B
C
D
)
=
(
I
0
C
A
−
1
I
)
(
A
0
0
D
−
C
A
−
1
B
)
(
I
A
−
1
B
0
I
)
{\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix}}{\begin{pmatrix}A&0\\0&D-CA^{-1}B\end{pmatrix}}{\begin{pmatrix}I&A^{-1}B\\0&I\end{pmatrix}}}
Block Cholesky decomposition
Consider a block matrix:
(
A
B
C
D
)
=
(
I
C
A
−
1
)
A
(
I
A
−
1
B
)
+
(
0
0
0
D
−
C
A
−
1
B
)
,
{\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}I\\CA^{-1}\end{pmatrix}}\,A\,{\begin{pmatrix}I&A^{-1}B\end{pmatrix}}+{\begin{pmatrix}0&0\\0&D-CA^{-1}B\end{pmatrix}},}
where the matrix
A
{\displaystyle {\begin{matrix}A\end{matrix}}}
is assumed to be non-singular,
I
{\displaystyle {\begin{matrix}I\end{matrix}}}
is an identity matrix with proper dimension, and
0
{\displaystyle {\begin{matrix}0\end{matrix}}}
is a matrix whose elements are all zero.
We can also rewrite the above equation using the half matrices:
(
A
B
C
D
)
=
(
A
1
2
C
A
−
∗
2
)
(
A
∗
2
A
−
1
2
B
)
+
(
0
0
0
Q
1
2
)
(
0
0
0
Q
∗
2
)
,
{\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}={\begin{pmatrix}A^{\frac {1}{2}}\\CA^{-{\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
A
{\displaystyle {\begin{matrix}A\end{matrix}}}
in the block matrix is defined by
Q
=
D
−
C
A
−
1
B
{\displaystyle {\begin{matrix}Q=D-CA^{-1}B\end{matrix}}}
and the half matrices can be calculated by means of Cholesky decomposition or LDL decomposition.
The half matrices satisfy that
A
1
2
A
∗
2
=
A
;
A
1
2
A
−
1
2
=
I
;
A
−
∗
2
A
∗
2
=
I
;
Q
1
2
Q
∗
2
=
Q
.
{\displaystyle {\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
(
A
B
C
D
)
=
L
U
,
{\displaystyle {\begin{pmatrix}A&B\\C&D\end{pmatrix}}=LU,}
where
L
U
=
(
A
1
2
0
C
A
−
∗
2
0
)
(
A
∗
2
A
−
1
2
B
0
0
)
+
(
0
0
0
Q
1
2
)
(
0
0
0
Q
∗
2
)
.
{\displaystyle LU={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\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
L
U
{\displaystyle {\begin{matrix}LU\end{matrix}}}
can be decomposed in an algebraic manner into
L
=
(
A
1
2
0
C
A
−
∗
2
Q
1
2
)
a
n
d
U
=
(
A
∗
2
A
−
1
2
B
0
Q
∗
2
)
.
{\displaystyle L={\begin{pmatrix}A^{\frac {1}{2}}&0\\CA^{-{\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}}.}
See also
Matrix decomposition
References
Kata Kunci Pencarian:
- Logam alkali
- Determinan
- Nitrogen
- Boron
- Block LU decomposition
- LU decomposition
- Matrix decomposition
- Cholesky decomposition
- Block matrix
- Computational complexity of matrix multiplication
- List of numerical analysis topics
- Outline of linear algebra
- Cuneiform (Unicode block)
- Symplectic matrix
