Related Searches
Definitions

# Block LU decomposition

In linear algebra, a Block LU decomposition is a 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.

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 $begin\left\{matrix\right\}Aend\left\{matrix\right\}$ is assumed to be non-singular, $begin\left\{matrix\right\}Iend\left\{matrix\right\}$ is an identity matrix with proper dimension, and $begin\left\{matrix\right\}0end\left\{matrix\right\}$ 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 $begin\left\{matrix\right\}Aend\left\{matrix\right\}$ 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


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 $begin\left\{matrix\right\}LUend\left\{matrix\right\}$ can be decomposed in an algebraic manner into

$L =$
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}.