Main Content

dissect

Nested dissection permutation

collapse all in page

Syntax

p = dissect(A)
p = dissect(A,Name,Value)

Description

p = dissect(A) returns a permutation vector computed using nested dissection of the sparsity structure of A.

example

p = dissect(A,Name,Value) specifies additional options using one or more name-value pair arguments. For example, dissect(A,'NumIterations',15) uses 15 refinement iterations in the nested dissection algorithm instead of 10.

example

Examples

collapse all

Open Live Script

Reorder a sparse matrix with several methods and compare the fill-in incurred by the LU decomposition of the reordered matrices.

Load the west0479 matrix, which is a real-valued 479-by-479 sparse matrix with both real and complex pairs of conjugate eigenvalues. View the sparsity structure.

load west0479.mat
A = west0479;
spy(A)

Figure contains an axes object. The axes object with xlabel nz = 1887 contains a line object which displays its values using only markers.

Calculate several different permutations of the matrix columns, including the nested dissection ordering.

p1 = dissect(A);
p2 = amd(A);
p3 = symrcm(A);

Compare the sparsity structures of the LU decomposition of A using the different ordering methods. The dissect function produces the reordering that incurs the least amount of fill-in.

subplot(1,2,1)
spy(A)
title('Original Matrix')
subplot(1,2,2)
spy(lu(A))
title('LU Decomposition')

Figure contains 2 axes objects. Axes object 1 with title Original Matrix, xlabel nz = 1887 contains a line object which displays its values using only markers. Axes object 2 with title LU Decomposition, xlabel nz = 15918 contains a line object which displays its values using only markers.

figure
subplot(1,2,1)
spy(A(p3,p3))
title('Reverse Cuthill-McKee')
subplot(1,2,2)
spy(lu(A(p3,p3)))
title('LU Decomposition')

Figure contains 2 axes objects. Axes object 1 with title Reverse Cuthill-McKee, xlabel nz = 1887 contains a line object which displays its values using only markers. Axes object 2 with title LU Decomposition, xlabel nz = 13654 contains a line object which displays its values using only markers.

figure
subplot(1,2,1)
spy(A(p2,p2))
title('Approximate Minimum Degree')
subplot(1,2,2)
spy(lu(A(p2,p2)))
title('LU Decomposition')

Figure contains 2 axes objects. Axes object 1 with title Approximate Minimum Degree, xlabel nz = 1887 contains a line object which displays its values using only markers. Axes object 2 with title LU Decomposition, xlabel nz = 13316 contains a line object which displays its values using only markers.

figure
subplot(1,2,1)
spy(A(p1,p1))
title('Nested Dissection')
subplot(1,2,2)
spy(lu(A(p1,p1)))
title('LU Decomposition')

Figure contains 2 axes objects. Axes object 1 with title Nested Dissection, xlabel nz = 1887 contains a line object which displays its values using only markers. Axes object 2 with title LU Decomposition, xlabel nz = 12216 contains a line object which displays its values using only markers.

Open Live Script

An arrowhead matrix is a sparse matrix that has a few dense columns. Use the 'MaxDegreeThreshold' name-value pair to filter the dense columns to the end of the reordered matrix.

Create an arrowhead sparse matrix and view the sparsity pattern.

A = speye(100) + diag(ones(1,99),1) + diag(ones(1,98),2);
A(1:5,:) = ones(5,100);
A = A + A';
spy(A)

Figure contains an axes object. The axes object with xlabel nz = 1444 contains a line object which displays its values using only markers.

Calculate the nested dissection ordering, and filter out the columns that have more than 10 nonzero elements.

p = dissect(A,'MaxDegreeThreshold',10);

View the sparsity pattern of the reordered matrix. dissect places the dense columns at the end of the reordered matrix.

spy(A(p,p))

Figure contains an axes object. The axes object with xlabel nz = 1444 contains a line object which displays its values using only markers.

Input Arguments

collapse all

Input matrix, specified as a square matrix. A can be either full or sparse. If A is nonsymmetric, then dissect symmetrizes it.

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | logical
Complex Number Support: Yes

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose Name in quotes.

Example: p = dissect(A,'NumIterations',15,'NumSeparators',2) uses 15 refinement iterations and 2 separators in the nested dissection algorithm.

Vertex weights, specified as the comma-separated pair consisting of 'VertexWeights' and a vector. The vector of weights must have length equal to size(A,1) so that a weight is specified for each vertex. Use this option to specify how the graph vertices (matrix columns) are weighted, which affects how the algorithm computes the balance between partitions.

By default, the nested dissection algorithm weights all vertices equally.

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Number of separators, specified as the comma-separated pair consisting of 'NumSeparators' and a positive integer. Use this option to specify how many partitions the graph is split into during each partitioning step. Increasing the number of separators in the nested dissection algorithm can result in a higher quality permutation at the cost of additional execution time.

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Number of refinement iterations, specified as the comma-separated pair consisting of 'NumIterations' and a positive integer. More refinement iterations can result in a higher quality permutation at the cost of increased execution time.

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Threshold for partition imbalance, specified as the comma-separated pair consisting of 'MaxImbalance' and a scalar value that is an integer multiple of 0.001 greater than or equal to 1.001 and less than or equal to 1.999. Larger threshold values might reduce execution time by allowing the algorithm to accept a worse permutation.

Data Types: single | double

Threshold for vertex degree, specified as the comma-separated pair consisting of 'MaxDegreeThreshold' and a nonnegative integer. The nested dissection algorithm ignores vertices with degree larger than threshold*(avg degree)/10 during ordering. dissect places vertices ignored in this way at the end of the permutation. This effectively places any vertices with degree greater than the threshold in the first, top-level separator. Filtering out highly connected vertices can sometimes improve the speed and accuracy of the ordering.

The default value of 0 means that all vertices are ordered.

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Output Arguments

collapse all

Permutation vector, returned as a vector. Use the permutation vector to reorder the columns of A using the indexing expression A(p,p). For example, the Cholesky factorization chol(A(p,p)) tends to be sparser than that of A.

Algorithms

The nested dissection ordering algorithm described in [1] is a multilevel graph partitioning algorithm that is used to produce fill-reducing orderings of sparse matrices. The input matrix is treated as the adjacency matrix of a graph. The algorithm coarsens the graph by collapsing vertices and edges, reorders the smaller graph, and then uses refinement steps to uncoarsen the small graph and produce a reordering of the original graph.

The name-value pairs for dissect enable you to control various stages of the algorithm:

  • Coarsening

    In this phase, the algorithm creates successively smaller graphs from the original graph by collapsing together adjacent pairs of vertices. 'MaxDegreeThreshold' enables you to filter out highly connected graph vertices (which are dense columns in the matrix) by ordering them last.

  • Partitioning

    After the graph is coarsened, the algorithm completely reorders the smaller graph. At each partitioning step, the algorithm attempts to partition the graph into equal parts: 'NumSeparators' specifies how many parts to partition the graph into, 'VertexWeights' optionally assigns weights to the vertices, and 'MaxImbalance' specifies the threshold for the difference in weight between the different partitions.

  • Refinement

    After the smallest graph is reordered, the algorithm makes projections to enlarge the graph back to the original size by expanding the vertices that were previously combined. After each projection step, a refinement step is performed that moves vertices between partitions to improve the quality of the solution. 'NumIterations' controls how many refinement steps are used during this uncoarsening phase.

References

[1] Karypis, George and Vipin Kumar. "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs." SIAM Journal on Scientific Computing. Vol. 20, Number 1, 1999, pp. 359–392.

Extended Capabilities

Version History

Introduced in R2017b

See Also

| | | |

Topics