dissect

Nested dissection permutation

Description

example

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.

Examples

collapse all

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.

A = west0479;
spy(A) 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
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
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
subplot(1,2,1)
spy(A(p1,p1))
title('Nested Dissection')
subplot(1,2,2)
spy(lu(A(p1,p1)))
title('LU Decomposition') 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) 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)) 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 comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside quotes. You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

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

 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.