RCM Numberer: Difference between revisions

From OpenSeesWiki
Jump to navigation Jump to search
(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
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
Given a symmetric ''n''×''n'' matrix we visualize the matrix as the [[adjacency matrix]] of a [[graph (mathematics)|graph]]. The Cuthill-McKee algorithm is then a relabeling of the [[vertex (graph theory)|vertices]] of the graph to reduce the bandwidth of the adjacency matrix.
{{CommandManualMenu}}


The algorithm produces an ordered [[n-tuple]] ''R'' of vertices which is the new order of the vertices.  
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:


First we choose a [[peripheral vertex]] ''x'' and set ''R'':= ({''x''}).


Then for i=1,2,... we iterate the following steps while |''R''| < ''n''  
{|
| style="background:lime; color:black; width:800px" | '''numberer RCM'''
|}


*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|breadth-first traversal]] where neighboring vertices are visited in order from lowest to highest vertex order.
-----
 
 
REFERENCES:


==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.
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.
----
Code Developed by: <span style="color:blue"> fmk </span>

Latest revision as of 00:48, 1 June 2013



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.


Code Developed by: fmk

Retrieved from "https://opensees.ist.berkeley.edu/wiki/index.php?title=RCM_Numberer&oldid=10577"