In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
subfield of
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
the symbolic Cholesky decomposition is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
used to determine the non-zero pattern for the
factors of a
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
when applying the
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for effici ...
or variants.
Algorithm
Let
be a sparse symmetric positive definite matrix with elements from a field
, which we wish to factorize as
.
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. To write the algorithm down we use the following notation:
* Let
and
be sets representing the non-zero patterns of columns and (below the diagonal only, and including diagonal elements) of matrices and respectively.
* Take
to mean the smallest element of
.
* Use a parent function
to define the elimination tree within the matrix.
The following algorithm gives an efficient
symbolic factorization of :
:
{{DEFAULTSORT:Symbolic Cholesky Decomposition
Articles with example pseudocode
Matrix decompositions