etree

Elimination tree

Syntax

p = etree(A)

p = etree(A,type)

[p,q] = etree(___)

Description

p = etree(A) returns an elimination tree of the square symmetric matrix whose upper triangle is that of A.

p = etree(A,type) specifies the type of elimination tree. For example, if type is "lo", then etree uses the lower triangle of A to construct the square symmetric matrix.

[p,q] = etree(___) also returns the postorder permutation q of the elimination tree. You can specify two outputs with any of the input argument combinations in the previous syntaxes.

Examples

Elimination Trees of Matrices

Create a 7-by-7 tridiagonal matrix of zeros and ones.

A = diag(ones(1,7)) + diag(ones(1,6),1) + diag(ones(1,6),-1)

A = 7×7

     1     1     0     0     0     0     0
     1     1     1     0     0     0     0
     0     1     1     1     0     0     0
     0     0     1     1     1     0     0
     0     0     0     1     1     1     0
     0     0     0     0     1     1     1
     0     0     0     0     0     1     1

Calculate an elimination tree of A. Each element p(i) of the elimination tree represents the parent of node i. p(7) is 0 because node 7 is the root of the tree.

p = etree(A)

p = 1×7

     2     3     4     5     6     7     0

Create a 6-by-6 block diagonal matrix of zeros and ones.

a = ones(3);
b = zeros(3);
B = [a b; b a]

B = 6×6

     1     1     1     0     0     0
     1     1     1     0     0     0
     1     1     1     0     0     0
     0     0     0     1     1     1
     0     0     0     1     1     1
     0     0     0     1     1     1

Calculate an elimination tree of B. etree returns a forest with two elimination trees, indicated by the root nodes at indices 3 and 6.

r = etree(B)

r = 1×6

     2     3     0     5     6     0

Specify Type of Elimination Tree

Calculate two different elimination trees of the bucky sparse matrix. The "lo" elimination tree uses the lower triangle of A, while the "col" elimination tree uses the matrix A'*A.

A = bucky;
p1 = etree(A,"lo");
p2 = etree(A,"col");

Plot the elimination trees using treeplot.

treeplot(p1)
title("Lower Triangle Elimination Tree")

treeplot(p2)
title("Column Elimination Tree")

Elimination Trees of Different Sparsity Patterns

Calculate elimination trees of two permutations of the bucky sparse matrix. Use symrcm to create the symmetric reverse Cuthill-McKee ordering, and use symamd to create the symmetric approximate minimum degree ordering.

A = bucky;
r = symrcm(A);
p1 = etree(A(r,r));
m = symamd(A);
p2 = etree(A(m,m));

Plot the elimination trees using treeplot. The reverse Cuthill-McKee elimination tree is a line of nodes, while the minimum degree elimination tree has multiple disjoint branches.

treeplot(p1)
title("Reverse Cuthill-McKee Elimination Tree")

treeplot(p2)
title("Minimum Degree Elimination Tree")

Plot the sparsity patterns using spy. The elimination tree of a matrix depends on its sparsity pattern, so the different sparsity patterns result in different elimination trees.

spy(A(r,r))
title("Reverse Cuthill-McKee Sparsity Pattern")

spy(A(m,m))
title("Minimum Degree Sparsity Pattern")

Input Arguments

A — Input matrix

matrix

Input matrix. A can be either full or sparse. If the elimination tree type is "sym" or "lo", then A must be a square matrix. etree uses the sparsity structure of A to calculate the elimination tree.

Data Types: double | logical
Complex Number Support: Yes

type — Type of elimination tree

"sym" (default) | "lo" | "col" | "row"

Type of elimination tree, specified as "sym", "lo", "col", or "row". Use this argument to specify what matrix etree uses to compute the elimination tree.

• If type is "sym", then etree constructs a square symmetric matrix using the upper triangle of A and returns the elimination tree of that matrix.

• If type is "lo", then etree constructs a square symmetric matrix using the lower triangle of A and returns the elimination tree of that matrix.

• If type is "col", then etree constructs the matrix A'*A and returns the elimination tree of that matrix, which is the column elimination tree of A.

• If type is "row", then etree constructs the matrix A*A' and returns the elimination tree of that matrix, which is the row elimination tree of A.

Output Arguments

p — Elimination tree

numeric vector

Elimination tree, returned as a numeric vector. p(i) represents the parent of node i in the tree, or 0 if i is a root.

q — Postorder permutation

numeric vector

Postorder permutation of elimination tree p, returned as a numeric vector.

You can use the postorder permutation of an elimination tree when computing the columns of a Cholesky factorization by hand. For a node i and its parent node j in an elimination tree p, column i must be completely computed before column j in the Cholesky factorization. The postorder permutation of p specifies an order in which to compute these columns that is consistent with this requirement. Use chol to compute the factorization directly.

More About

Elimination Tree

An elimination tree is a data structure that captures row and column dependencies of a Cholesky factorization and describes the operations that can be performed at the same time. Disjoint branches of an elimination tree can be calculated in parallel, so factorizations of matrices that have elimination trees with branching can be computed faster. You can reorder a sparse matrix to change the amount of fill-in and compute a different elimination tree.

References

[1] Chen, Yanqing, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. “Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate.” ACM Transactions on Mathematical Software 35, no. 3 (October 2008): 1–14. https://doi.org/10.1145/1391989.1391995.

[2] Pothen, Alex, and Sivan Toledo. "Elimination Structures in Scientific Computing." In Handbook of Data Structures and Applications, edited by Dinesh P. Mehta and Sartaj Sahni, 945–965. New York: Chapman and Hall/CRC, 2017. https://doi.org/10.1201/9781315119335

Extended Capabilities

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

Version History

Introduced before R2006a