Symbolic Cholesky decomposition

Symbolic Cholesky decomposition

In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used to determine the non-zero pattern for the L factors of a symmetric sparse matrix when applying the Cholesky decomposition or variants.

Algorithm

Let:A=(a_{ u,mu}) in mathbb{K}^{n imes n}

be a sparse symmetric positive definite matrix, which we wish to factorize as:A = LL^T,

In order to implement an efficient sparse factorization it has been found to be necessary to determine the non zero structure of the factors before doing any numerical work.

Let mathcal{A}_i and mathcal{L}_j be sets representing the non-zero patterns of columns i and j (below the diagonal only) of matrices A and L respectively.

Take minmathcal{L}_j to mean the least element of mathcal{L}_j.

Define the elimination tree on the matrix by use of a parent function pi(i),!.

Then the following algorithm will give an efficient symbolic factorization of A,

:mbox{For}~i=1, n::mathcal{L}_i = mathcal{A}_i::mbox{For}~j~mbox{such that}~pi(j) = i:::mathcal{L}_i = mathcal{L}_i cup mathcal{L}_jsetminus{j}::pi(i) = minmathcal{L}_isetminus{i}


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Cholesky decomposition — In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André Louis Cholesky… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Sparse matrix — A sparse matrix obtained when solving a finite element problem in two dimensions. The non zero elements are shown in black. In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros (Stoer Bulirsch 2002,… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Matrice Creuse — Une matrice creuse obtenue lors de la résolution d un problème éléments finis. Les éléments non nuls sont représentés en noir. Dans la discipline de l analyse numérique des mathématiques, une matrice creuse est une matrice contenant beaucoup de… …   Wikipédia en Français

  • Matrice clairsemée — Matrice creuse Une matrice creuse obtenue lors de la résolution d un problème éléments finis. Les éléments non nuls sont représentés en noir. Dans la discipline de l analyse numérique des mathématiques, une matrice creuse est une matrice… …   Wikipédia en Français

  • Matrice creuse — Une matrice creuse obtenue lors de la résolution d un problème éléments finis. Les éléments non nuls sont représentés en noir. Dans la discipline de l analyse numérique des mathématiques, une matrice creuse est une matrice contenant beaucoup de… …   Wikipédia en Français

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Pidgin code — In computer programming, pidgin code is a mixture of several programming languages in the same program, or pseudocode that is a mixture of a programming language with natural language descriptions. Hence the name: the mixture is a programming… …   Wikipedia

  • Numerical analysis — Babylonian clay tablet BC 7289 (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 is four sexagesimal figures, which is about six decimal figures. 1 + 24/60 + 51/602 + 10/603 = 1.41421296...[1] Numerical analysis is the …   Wikipedia

Share the article and excerpts

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