A node-addition model for symbolic factorization

ABSTRACT

A symbolic node-addition model for matrix factorization of symmetric positive definite matrices is described. In this model, the nodes are added onto the filled graph one at a time. The advantage of the node-addition model is its simplicity and flexibility. The model can be immediately incorporated into finite element analysis programs. The model can also be extended to determine modification patterns in the matrix factors due to changes in the original matrix. For a given matrix K(=LDLt), the time complexity of the algorithm for constructing the structure of the lower triangular matrix factor L is O(&eegr;(L)) where &eegr;(L) is the number of nonzero entries in L.

REFERENCES

• 1: AKIN, J. E., AND PARDUE, R.M. Element resequencing for frontal solutions. In The Mathematics of Finite Element and Applications II, J. R. Whitman, Ed., Academic Press, New York, 1976, pp. 535-541.
• 2: BATHE, K. Finite Element Procedures in Engineering Analysis. Prentice Hall, New York, 1982.
• 3: BYKAT, A. A note on an element ordering scheme. Int. J. Numer. Meth. Eng. 11, (1977), 194-198.
• 4: EISENSTAT, S. C., GURSKY, M. C., SCHULTZ, M. H., AND SHERMAN, A.M. Yale sparse matrix package I. The symmetric codes. Res. Rep. 112, Department of Computer Science, Yale Univ., New Haven, Conn., July 1977.
• 5: FELIPPA, C. A. Solution of linear equations with skyline-stored symmetric matrix. Comput. Struct. 5, (1975), 13-19.
• 6: FUCHS, G. YON, RoY, J. R., AND SCHREM, E. Hypermatrix solution of large sets of symmetric positive-definite linear equations. Comput. Meth. Appl. Mech. Eng. 1, 1 (1972), 197-216.
• 7: GEORGE, A., AND LIU, J. W.H. User guide for SPARSPAK: Waterloo sparse linear equations package. Res. Rep. CS-78-30, Univ. of Waterloo, Waterloo, Ont., 1978.
• 8: GEORGE, A., AND LIU, J. W.H. An optimal algorithm for symbolic factorization of symmetric matrices. SIAM Comput., 9, 3 (1980), 583-593.
• 9: John Alan George, Computer implementation of the finite element method, 1971
• 10: GEORGE A., AND LIU, J. W. 14. An automatic nested dissection algorithm for irregular finite element problems. SIAM J. Numer. Anal., 15, (1978), 1053-1069.
• 11: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 12: GEORGE, A., AND MC}NTYRE, D.R. On the application of the minimum degree algorithm to finite element systems. SIAM J. Numerical Analysis, 15, 1 (1978), 90-112.
• 13: IRONS, B.M. A frontal solution program for finite element analysis. Int. J. Numer. Meth. Eng. 2, (1970), 5-32.
• 14: LAW, K. H., AND FENVES, S.J. A two-step approach to finite element ordering. Int. J. Numer. Meth. Eng. 19, (1983), 891-911.
• 15: LAW, K. H., AND FENVES, S.J. A Physical interpretation of factorization and factor modification in structural analysis. J. Franklin Institute 316, 5 (1983), 385-404.
• 16: LAW, K.H. Sparse matrix factor modification in structural reanalysis. Int. J. Numer. Meth. Eng. 21, (1985), 37-63.
• 17: LIu, J. W.H. A compact row storage scheme for cholesky factors using elimination trees. Tech. Rep. No. CS-84-02, Dept. of Computer Science, York University, 1984.
• 18: RAZZAGUE, A. Automatic reduction of frontwidth for finite element analysis, int. J. Numer. Meth. Eng. I5, (1980), 1315-1324.
• 19: ROSE, D.J. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equation. In Graph Theory Comput., R. C. Read, Ed., Academic Press, New York (1972), pp. 183-217.
• 20: ROSE, D. J., TARJAN, R. E., AND LUEKER, G.E. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 2 (1976), 266-283.
• 21: Row, D. G., POWELL, G. H., AND MONDKAR, D.P. Solution of progressively changing equilibrium equations for nonlinear structures. Comput. Struct. 7, (1977), 659-665.
• 22: Andrew Harry Sherman, On the efficient solution of sparse systems of linear and nonlinear equations., 1975
• 23: ZIENKIEWICZ, O. C., GAGO, J. P. DE S. R., AND KELLY, D.W. The hierarchical concept in finite element analysis. Comput. Struct. 16, 1-4 (1983), 53-65.

INDEX TERMS

Classification:
  E. Data

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Measurement, Performance, Theory, Verification