OpenSees Cloud

OpenSees AMI

Reduce Your Bandwidth

Original Post - 23 Nov 2020 - Michael H. Scott

Visit Structural Analysis Is Simple on Substack.

For large structural models, the solution to \({\bf K}_T\Delta {\bf U}={\bf R}\) can be the computational bottleneck during an analysis. Although computing speed and algorithms to solve \({\bf K}_T\Delta {\bf U}={\bf R}\) are very good, you still want to make sure the solution happens as quickly as possible, particularly when inside the double nested time integration/equilibrium solution loop of nonlinear dynamic analysis. Pennies in the change jar add up.

The computational cost of solving simultaneous linear equations is proportional to \(bN^2\), where N is the number of equations and b is the bandwidth of \({\bf K}_T\). The bandwidth of a matrix is the largest distance, over all rows of the matrix, from the diagonal entry to the farthest column with a known non-zero entry. You know a priori where the non-zero entries in a stiffness matrix will be based on the element connectivity and the equation numbers assigned to each node.

Generally, linear equation solvers will solve faster when the matrix bandwidth is reduced, i.e., when the off-diagonal non-zeros are close to the diagonal. You can’t change N, but you can change b, which is where equation numbering comes in to play. Reducing the bandwidth also decreases the amount of memory allocated for banded and profile matrix storage schemes.

There are three approaches to equation numbering in OpenSees–Plain, AMD, and RCM. I will demonstrate the numbering approaches using the frame with node tags shown below. There are N=22 simultaneous equations of nodal equilibrium.

The Plain numberer assigns equation numbers in ascending order of node tags input by the user, i.e., start at node 1, number the DOFs, then go to node 2, node 3, etc. The node tags don’t have to be sequential, or all positive–the Plain numberer will go from low to high.

For the example frame, the Plain numberer gives the following stiffness matrix topology based on numbering equations in nodal order 1,2,3,…,9,10. The off-diagonals are spread out quite a bit, with matrix bandwidth b=21.

The AMD numberer uses approximate minimum degree ordering to number the equations. Applying AMD to the frame example, the equations are numbered in the sequence of nodes 1,10,5,6,8,2,9,3,7,4. Compared to the Plain numberer, the off-diagonals are packed tighter with matrix bandwidth b=16.

The RCM numberer numbers equations using the reverse Cuthill-McKee algorithm. For the frame example, the order of nodes is 10,6,5,8,3,2,7,4,9,1. Compared to the AMD numberer, the off-diagonals are packed more tightly around the diagonal and the matrix bandwidth is b=13.

Both AMD and RCM can clean up poor choices of node numbering, either input by a user or generated by an automated meshing routine. Unless you want to control the equation numbers, e.g., for demonstration or instructional purposes, there’s no reason not to use AMD or RCM. Although RCM is the default option for equation numbering in OpenSees, RCM is not categorically better than AMD for all problems.