RCM Numberer: Difference between revisions
(Created page with 'Given a symmetric ''n''×''n'' matrix we visualize the matrix as the adjacency matrix of a graph. The Cuthill-McKee algorithm is then a relabelin...') |
No edit summary |
||
| Line 1: | Line 1: | ||
Given a symmetric ''n'' | {{CommandManualMenu}} | ||
This command is used to construct an RCM degree-of-freedom numbering object to provide the mapping between the degrees-of-freedom at the nodes and the | |||
equation numbers. An RCM numberer uses the reverse Cuthill-McKee scheme to order the matrix equations. The command to construct an RCM numberer is a follows: | |||
{| | |||
| style="background:yellow; color:black; width:800px" | '''numberer RCM''' | |||
|} | |||
----- | |||
REFERENCES: | |||
E. Cuthill and J. McKee. [http://portal.acm.org/citation.cfm?id=805928''Reducing the bandwidth of sparse symmetric matrices''] In Proc. 24th Nat. Conf. [[Association for Computing Machinery|ACM]], pages 157-172, 1969. | |||
---- | |||
THEORY: | |||
Given a symmetric (in structure) ''n''-by-''n'' matrix we create a graph of the matrix, where the vertices correspond to the equation numbers and the edges of the graph correspond to non-zero (in structure, not necessarily value) <math> a_{ij} </math> matrix terms. | |||
The reverse Cuthill-McKee algorithm is a relabeling of the vertices of the graph to reduce the bandwidth of the matrix. | |||
The algorithm produces an ordered [[n-tuple]] ''R'' of vertices which is the new order of the vertices. | The algorithm produces an ordered [[n-tuple]] ''R'' of vertices which is the new order of the vertices. | ||
| Line 12: | Line 34: | ||
*Append <math>A_i</math> to the Result set ''R''. | *Append <math>A_i</math> to the Result set ''R''. | ||
In other words, number the vertices according to a particular | In other words, number the vertices according to a particular breadth-first search, where neighboring vertices are visited in order from lowest to highest vertex order. | ||
= | ---- | ||
Code Developed by: <span style="color:blue"> fmk </span> | |||
Revision as of 01:04, 2 March 2010
- Command_Manual
- Tcl Commands
- Modeling_Commands
- model
- uniaxialMaterial
- ndMaterial
- frictionModel
- section
- geometricTransf
- element
- node
- sp commands
- mp commands
- timeSeries
- pattern
- mass
- block commands
- region
- rayleigh
- Analysis Commands
- Output Commands
- Misc Commands
- DataBase Commands
This command is used to construct an RCM degree-of-freedom numbering object to provide the mapping between the degrees-of-freedom at the nodes and the equation numbers. An RCM numberer uses the reverse Cuthill-McKee scheme to order the matrix equations. The command to construct an RCM numberer is a follows:
| numberer RCM |
REFERENCES:
E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.
THEORY:
Given a symmetric (in structure) n-by-n matrix we create a graph of the matrix, where the vertices correspond to the equation numbers and the edges of the graph correspond to non-zero (in structure, not necessarily value) <math> a_{ij} </math> matrix terms. The reverse Cuthill-McKee algorithm is a relabeling of the vertices of the graph to reduce the bandwidth of the matrix.
The algorithm produces an ordered n-tuple R of vertices which is the new order of the vertices.
First we choose a peripheral vertex x and set R:= ({x}).
Then for i=1,2,... we iterate the following steps while |R| < n
- Construct the adjacency set <math>A_i</math> of <math>R_i</math> (with <math>R_i</math> the i-th component of R) and exclude the vertices we already have in R
- <math>A_i := \operatorname{Adj}(R_i) \setminus R</math>
- Sort <math>A_i</math> with ascending vertex order.
- Append <math>A_i</math> to the Result set R.
In other words, number the vertices according to a particular breadth-first search, where neighboring vertices are visited in order from lowest to highest vertex order.
Code Developed by: fmk