etree

Elimination tree of a sparse symmetric matrix.

Category: Mathematics > Sparse Matrices

Syntax

p = etree(A)

Description

The elimination tree describes the dependencies of a Cholesky factorization: column j of the factor affects only its ancestors in the tree. Its shape tells how much of the computation can run independently, and its height bounds the number of sequential steps.

The tree depends only on the nonzero pattern of A, not on the values. A matrix with several diagonal blocks gives a forest, with one root for each block.

Input arguments

A

Sparse square matrix. Only its nonzero pattern in the upper triangle is used.

Output arguments

p

Row vector with p(j) the parent of column j, or 0 for a root.

Example

Tree of a tridiagonal matrix

A = sparse(diag(4*ones(4,1)) + diag(ones(3,1),1) + diag(ones(3,1),-1));
p = etree(A)

p = 1×4

     2     3     4     0

See also

etreeplot treeplot symbfact symrcm