Math 2.0

Numerical analysis Definition

Incomplete Cholesky factorization

Builds on Positive definite matrixSparse matrixTriangular matrixCholesky decompositionM-matrix

Definition

Let AA be a real symmetric positive definite n×nn \times n sparse matrix. Let S⊆{(i,j):1≤j≤i≤n}S \subseteq \set{(i, j) : 1 \le j \le i \le n} be a set of positions that contains every diagonal position (i,i)(i, i). An incomplete Cholesky factorization of AA with pattern SS is a lower triangular matrix LL with positive diagonal such that:

  1. lij=0l_{ij} = 0 for every i≥ji \ge j with (i,j)∉S(i, j) \notin S;
  2. (LLT)ij=aij(L L^T)_{ij} = a_{ij} for every (i,j)∈S(i, j) \in S.

When SS is the set of positions (i,j)(i, j) with i≥ji \ge j and aij≠0a_{ij} \ne 0, the factorization is called IC(0).

Remarks

If SS contains all positions with i≥ji \ge j, the incomplete factor is the exact Cholesky factor. Example: let AA be tridiagonal and symmetric positive definite. Its exact Cholesky factor is lower bidiagonal, so it vanishes outside the pattern of AA. Hence the IC(0) factor exists and is the exact factor. Non-example: for the 2×22 \times 2 identity matrix, the matrix LL with rows (1,0)(1, 0) and (1,1)(1, 1) and the pattern of all positions satisfies clause 1. It fails clause 2, since (LLT)21=1≠0=a21(L L^T)_{21} = 1 \ne 0 = a_{21}. The factor is computed by the Cholesky recurrences with each update outside SS discarded. For a general symmetric positive definite AA, the process can meet a nonpositive pivot, and then no such LL is produced. It exists for every pattern when AA is a symmetric M-matrix, a result of Meijerink and van der Vorst. Variants choose SS by levels of fill or drop entries below a threshold.

Reading path

To understand this page from the ground up, read these 14 pages in order. The foundations come first.

Show the path as a graph
M-matrix, concept, no evidence levelM-matrixconceptMatrix, definition, no evidence levelMatrixdefinitionPositive definite matrix, concept, no evidence levelPositive definite mat…conceptSparse matrix, concept, no evidence levelSparse matrixconceptTriangular matrix, concept, no evidence levelTriangular matrixconceptSquare matrix, definition, no evidence levelSquare matrixdefinitionTranspose, definition, no evidence levelTransposedefinitionLower triangular matrix, definition, no evidence levelLower triangular matr…definitionSymmetric matrix, definition, no evidence levelSymmetric matrixdefinitionConjugate transpose, definition, no evidence levelConjugate transposedefinitionHermitian matrix, definition, no evidence levelHermitian matrixdefinitionPositive definite matrix, definition, no evidence levelPositive definite mat…definitionCholesky decomposition, statement, no evidence levelCholesky decompositionstatementIncomplete Cholesky factorization, definition, no evidence levelIncomplete Cholesky f…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. M-matrix concept
  2. Matrix definition
  3. Positive definite matrix concept
  4. Sparse matrix concept
  5. Triangular matrix concept
  6. Square matrix definition
  7. Transpose definition
  8. Lower triangular matrix definition
  9. Symmetric matrix definition
  10. Conjugate transpose definition
  11. Hermitian matrix definition
  12. Positive definite matrix definition
  13. Cholesky decomposition statement
  14. Incomplete Cholesky factorization definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Incomplete_Cholesky_factorization
About this page
Tag7V24BPCQTZ
URIm2://7V24BPCQTZ
Kinddefinition
WritingW0 stub
MSC65F08, 65F50, 65F10
DefinesIncomplete Cholesky factorization
UsesPositive definite matrix, Sparse matrix, Triangular matrix, Cholesky decomposition, M-matrix

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.