From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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.[ 1]
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}}}
I
{\displaystyle {\begin{matrix}I\end{matrix}}}
0
{\displaystyle {\begin{matrix}0\end{matrix}}}
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}}}
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}}}
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
References
