Block LU decomposition

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::egin{pmatrix} A & B \ C & D end{pmatrix}=egin{pmatrix}I \C A^{-1}end{pmatrix},A,egin{pmatrix}I & A^{-1}Bend{pmatrix}+egin{pmatrix}0 & 0 \0 & D-C A^{-1} Bend{pmatrix},where the matrix egin{matrix}Aend{matrix} is assumed to be non-singular,egin{matrix}Iend{matrix} is an identity matrix with proper dimension, and egin{matrix}0end{matrix} is a matrix whose elements are all zero.

We can also rewrite the above equation using the half matrices::egin{pmatrix} A & B \ C & D end{pmatrix}=egin{pmatrix}A^{frac{1}{2 \C A^{-frac{*}{2end{pmatrix}egin{pmatrix}A^{frac{*}{2 & A^{-frac{1}{2Bend{pmatrix}+egin{pmatrix}0 & 0 \0 & Q^{frac{1}{2end{pmatrix}egin{pmatrix}0 & 0 \0 & Q^{frac{*}{2end{pmatrix},where the Schur complement of egin{matrix}Aend{matrix}in the block matrix is defined by:egin{matrix}Q = D - C A^{-1} Bend{matrix} and the half matrices can be calculated by means of Cholesky decomposition or LDL decomposition.The half matrices satisfy that:egin{matrix}A^{frac{1}{2,A^{frac{*}{2=A;end{matrix}qquadegin{matrix}A^{frac{1}{2,A^{-frac{1}{2=I;end{matrix}qquadegin{matrix}A^{-frac{*}{2,A^{frac{*}{2=I;end{matrix}qquadegin{matrix}Q^{frac{1}{2,Q^{frac{*}{2=Q.end{matrix}

Thus, we have:egin{pmatrix} A & B \ C & D end{pmatrix}=LU,where:LU =egin{pmatrix}A^{frac{1}{2 & 0 \C A^{-frac{*}{2 & 0end{pmatrix}egin{pmatrix}A^{frac{*}{2 & A^{-frac{1}{2B \0 & 0end{pmatrix}+egin{pmatrix}0 & 0 \0 & Q^{frac{1}{2end{pmatrix}egin{pmatrix}0 & 0 \0 & Q^{frac{*}{2end{pmatrix}.

The matrix egin{matrix}LUend{matrix} can be decomposed in an algebraic manner into::L = egin{pmatrix}A^{frac{1}{2 & 0 \C A^{-frac{*}{2 & Q^{frac{1}{2end{pmatrix}mathrm{~~and~~}U =egin{pmatrix}A^{frac{*}{2 & A^{-frac{1}{2B \0 & Q^{frac{*}{2end{pmatrix}.

ee also

*Matrix decomposition


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Block matrix — In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices.[1] We group the rows and… …   Wikipedia

  • Block matrix pseudoinverse — is a formula of pseudoinverse of a partitioned matrix. This is useful for decomposing or approximating many algorithms updating parameters in signal processing, which are based on least squares method. Derivation Consider a column wise… …   Wikipedia

  • Matrix decomposition — In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. There are many different matrix decompositions; each finds use among a particular class of problems. Contents 1… …   Wikipedia

  • LU decomposition — In linear algebra, LU decomposition (also called LU factorization) is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as… …   Wikipedia

  • Functional decomposition — refers broadly to the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by function composition. In general, this process of …   Wikipedia

  • Schur decomposition — In the mathematical discipline of linear algebra, the Schur decomposition or Schur triangulation (named after Issai Schur) is an important matrix decomposition. Statement The Schur decomposition reads as follows: if A is a n times; n square… …   Wikipedia

  • Jordan–Chevalley decomposition — In mathematics, the Jordan–Chevalley decomposition, named after Camille Jordan and Claude Chevalley (also known as Dunford decomposition, named after Nelson Dunford, as well as SN decomposition), expresses a linear operator as the sum of its… …   Wikipedia

  • Dantzig–Wolfe decomposition — is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Phil Wolfe and initially published in 1960[1]. Many texts on linear programming have sections dedicated to… …   Wikipedia

  • Randomized block design — In the statistical theory of the design of experiments, blocking is the arranging of experimental units in groups (blocks) that are similar to one another. Typically, a blocking factor is a source of variability that is not of primary interest to …   Wikipedia

  • Time-evolving block decimation — The time evolving block decimation (TEBD) algorithm is a numerical scheme used to simulate one dimensional quantum many body systems, characterized by at most nearest neighbour interactions.It is dubbed Time evolving Block Decimation because it… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”