Main Content

symrcm

Sparse reverse Cuthill-McKee ordering

所有的页面崩溃

Syntax

r = symrcm(S)

Description

r = symrcm(S)returns the symmetric reverse Cuthill-McKee ordering ofS. This is a permutationrsuch thatS(r,r)tends to have its nonzero elements closer to the diagonal. This is a good preordering for LU or Cholesky factorization of matrices that come from long, skinny problems. The ordering works for both symmetric and nonsymmetricS.

For a real, symmetric sparse matrix,S，特征值S(r,r)are the same as those ofS, buteig(S(r,r))计算的时间可能比eig(S).

Examples

collapse all

Open Live Script

The statement

B = bucky;

uses a function in thedemostoolbox to generate the adjacency graph of a truncated icosahedron. This is better known as a soccer ball, a Buckminster Fuller geodesic dome (hence the namebucky), or, more recently, as a 60-atom carbon molecule. There are 60 vertices. The vertices have been ordered by numbering half of them from one hemisphere, pentagon by pentagon; then reflecting into the other hemisphere and gluing the two halves together.

使用此编号，矩阵没有特别狭窄的带宽，正如第一个间谍图所示：

figure(); subplot(1,2,1),spy(B),title('B')

图包含一个轴对象。带标题B的轴对象包含一个类型行的对象。

The reverse Cuthill-McKee ordering is obtained with:

p = symrcm(B); R = B(p,p);

Thespyplot shows a much narrower bandwidth.

subplot(1,2,2),spy(R),title('B(p,p)')

Figure contains 2 axes objects. Axes object 1 with title B contains an object of type line. Axes object 2 with title B(p,p) contains an object of type line.

This example is continued in the reference page forsymamd.

The bandwidth can also be computed with:

[i,j] = find(B); bw = max(i-j) + 1;

带宽的BandRare 35 and 12, respectively.

Algorithms

The algorithm first finds a pseudoperipheral vertex of the graph of the matrix. It then generates a level structure by breadth-first search and orders the vertices by decreasing distance from the pseudoperipheral vertex. The implementation is based closely on the SPARSPAK implementation described by George and Liu.

参考

[1] George, Alan and Joseph Liu,Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981.

[2] Gilbert, John R., Cleve Moler, and Robert Schreiber, “Sparse Matrices in MATLAB: Design and Implementation,”SIAM Journal on Matrix Analysis, 1992. A slightly expanded version is also available as a technical report from the Xerox Palo Alto Research Center.

Extended Capabilities

版本历史

Introduced before R2006a

See Also

|||