# etree

Elimination tree

## Syntax

``p = etree(A)``
``p = etree(A,type)``
``[p,q] = etree(___)``

## Description

example

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

example

````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

collapse all

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 ```

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")```

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

collapse all

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 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

collapse all

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.

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.

collapse all

### 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

## Version History

Introduced before R2006a