Reducing the bandwidth of sparse symmetric matrices

ABSTRACT

The finite element displacement method of analyzing structures involves the solution of large systems of linear algebraic equations with sparse, structured, symmetric coefficient matrices. There is a direct correspondence between the structure of the coefficient matrix, called the stiffness matrix in this case, and the structure of the spatial network delineating the element layout. For the efficient solution of these systems of equations, it is desirable to have an automatic nodal numbering (or renumbering) scheme to ensure that the corresponding coefficient matrix will have a narrow bandwidth. This is the problem considered by R. Rosen1. A direct method of obtaining such a numbering scheme is presented. In addition several methods are reviewed and compared.

REFERENCES

• 1: Richard Rosen, Matrix bandwidth minimization, Proceedings of the 1968 23rd ACM national conference, p.585-595, August 27-29, 1968 [doi>10.1145/800186.810622]
• 2: R. S. Varga, "Matrix Iterative Analysis." Prentice-Hall, Inc., New York (1962).
• 3: B. A. Carré, "The partitioning of network problems for block iteration." Computer Journal 9, (1966), pp. 84-97.
• 4: S. Parter, "The use of linear graphs in Gauss elimination." SIAM Review 3, (1961), pp. 119-130.
• 5: N. Sato and W. F. Tinney, "Techniques for exploiting the sparsity of the network admittance matrix." IEEE Transactions on Power Apparatus and Systems, 82, (1963), pp. 944-950.
• 6: R. P. Tewarson, "Solution of a system of simultaneous linear equations with a sparse coefficient matrix by elimination methods." BIT 7, (1967), pp. 226-239.
• 7: A. Nathan and R. K. Even, "The inversion of sparse matrices by a strategy derived from their graphs." Computer Journal 9, (1966), pp. 190-194.
• 8: D. V. Steward, "On an approach to techniques for the analysis of the structure of large systems of equations." SIAM Review 4, (1962), pp. 321-342.
• 9: R. P. Tewarson, "Row-Column permutation of sparse matrices." Computer Journal 10, (1967), pp. 300-305.
• 10: F. A. Akyuz and S. Utku, "An automatic relabeling scheme for bandwidth minimization of stiffness matrices." AIAA Journal, 6, (1968), pp. 728-730.
• 11: G. G. Alway and D. W. Martin, "An algorithm for reducing the bandwidth of a matrix of symmetrical configuration." Computer Journal 8, (1965), pp. 264-272.
• 12: A. Jennings, "A compact storage scheme for the solution of symmetric linear simultaneous equations." Computer Journal 9, (1966), pp.281-285
• 13: F. Harary, "A graph theoretic approach to matrix inversion by partitioning." Numerische Mathematik, 4, (1962), pp. 128-135.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Theory