More Web Proxy on the site http://driver.im/

article

Algorithms and Data Structures for Sparse Symmetric Gaussian Elimination

Authors:

Stanley C. Eisenstat,

Martin H. Schultz,

Andrew H. ShermanAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 2, Issue 2

Pages 225 - 237

https://doi.org/10.1137/0902019

Published: 01 June 1981 Publication History

Abstract

In this paper we present algorithms and data structures that may be used in the efficient implementation of symmetric Gaussian elimination for sparse systems of linear equations with positive definite coefficient matrices. The techniques described here serve as the basis for the symmetric codes in the Yale Sparse Matrix Package.

References

[1]

A. AHO, J. E. HOPCROFT AND J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

[2]

A. CHANG, Application of sparse matrix methods in electric power system analysis, in Sparse Matrix Proceedings, R. A. Willoughby, ed., Rep. RA1, IBM Research, Yorktown Heights, NY, 1968, pp. 113-122.

[3]

A. R. CURTIS AND J. K. REID, Fortran subroutines tor the solution of sparse sets of linear equations, AERE rep. R.6844, HMSO, London, 1971.

[4]

S. C. EISENSTAT, J. A. GEORGE, R. GRIMES, D. R. KINCAID AND A. H. SHERMAN, Some comparisons of software packages for large sparse linear systems, in Advances in Computer Methods for Partial Differential Equations--III, R. Vichnevetsky and R. S. Stepleman, eds., IMACS, New Brunswick, NJ, 1979, pp. 98-106.

[5]

S. C. EISENSTAT, M. C. GURSKY, M. H. SCHULTZ AND A. H. SHERMAN, The Yale sparse matrix package I: Symmetric matrices, Rep. 112, Dept. of Computer Science, Yale University, New Haven, CT, 1977.

[6]

S. C. EISENSTAT, M. H. SCHULTZ AND A. H. SHERMAN, Application of sparse matrix methods to partial differential equations, in Advances in Computer Methods for Partial Differential Equations-- I, R. Vichnevetsky, ed., AICA, New Brunswick, NJ, 1975, pp. 40-45.

[7]

S. C. EISENSTAT, M. H. SCHULTZ AND A. H. SHERMAN, Considerations in the design of software for sparse Gaussian elimination, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, New York, 1976, pp. 263-274.

[8]

G. E. FORSYTHE AND C. B. MOLER, Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, NJ, 1967.

[9]

J. A. GEORGE AND J. W.-H. LIU, An optimal algorithm for symbolic factorization of symmetric matrices, Res. rep. CS-78-11, Department of Computer Science, University of Waterloo, Ontario, 1978.

[10]

J. A. GEORGE AND J. W.-H. LIU, User guide for SPARSPAK: Waterloo sparse linear equations package, Res. rep. CS-78-30, Dept. of Computer Science, University of Waterloo, Ontario, 1978.

[11]

F. G. GUSTAVSON, Some basic techniques for solving sparse systems of linear equations, in Sparse Matrices and Their Applications, D. J. Rose and R. A. Willoughby, eds., Plenum Press, New York, 1972, pp. 41-52.

[12]

N. MUNSGAARD, New factorization codes for sparse, symmetric and positive definite matrices, BIT 19 (1979), pp. 43-52.

[13]

D. J. ROSE, A. H. SHERMAN, R. E. TARJAN AND G. F. WHITTEN, Algorithms and software for in-core factorization of sparse symmetric positive definite matrices. Comput. & Structures 11 (1980), pp. 597-608.

[14]

D. J. ROSE, R. E. TARJAN AND G. S. LUEKER, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (1976), pp. 266-283.

[15]

D. J. ROSE AND G. F. WHITTEN, private communication.

[16]

A. H. SHERMAN, On the efficient solution of sparse systems of linear and nonlinear equations, doctoral dissertation, Department of Computer Science, Yale University, New Haven, CT, 1975.

[17]

P. T. WOO, S. C. EISENSTAT, M. H. SCHULTZ AND A. H. SHERMAN, Application of sparse matrix techniques to reservoir simulation, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, New York, 1976, pp. 427-438.

Cited By

Fazli EEbnenasir A(2023)TPGen: A Self-stabilizing GPU-Based Method for Test and Prime Paths GenerationFundamentals of Software Engineering10.1007/978-3-031-42441-0_4(40-54)Online publication date: 4-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-42441-0_4
Chen QJiao X(2022)HIFIR: Hybrid Incomplete Factorization with Iterative Refinement for Preconditioning Ill-Conditioned and Singular SystemsACM Transactions on Mathematical Software10.1145/353616548:3(1-33)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1145/3536165
Tian MWang JZhang ZDu WPan JLiu T(2022)swSuperLU: A highly scalable sparse direct solver on Sunway manycore architectureThe Journal of Supercomputing10.1007/s11227-021-04270-w78:9(11441-11463)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11227-021-04270-w
Show More Cited By

Recommendations

An Implementation of Gaussian Elimination with Partial Pivoting for Sparse Systems

In this paper, we consider the problem of solving a sparse nonsingular system of linear equations. We show that the structures of the triangular matrices obtained in the $LU$-decomposition of a sparse nonsingular matrix A using Gaussian elimination with ...
A sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of an SPD matrix

In this paper, a method via sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix is proposed. The resulting factorized sparse approximate inverse is used as a preconditioner for ...
Multiprocessor sparse SVD algorithms and applications

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific and Statistical Computing

SIAM Journal on Scientific and Statistical Computing Volume 2, Issue 2

1981

136 pages

ISSN:0196-5204

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 June 1981

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fazli EEbnenasir A(2023)TPGen: A Self-stabilizing GPU-Based Method for Test and Prime Paths GenerationFundamentals of Software Engineering10.1007/978-3-031-42441-0_4(40-54)Online publication date: 4-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-42441-0_4
Chen QJiao X(2022)HIFIR: Hybrid Incomplete Factorization with Iterative Refinement for Preconditioning Ill-Conditioned and Singular SystemsACM Transactions on Mathematical Software10.1145/353616548:3(1-33)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1145/3536165
Tian MWang JZhang ZDu WPan JLiu T(2022)swSuperLU: A highly scalable sparse direct solver on Sunway manycore architectureThe Journal of Supercomputing10.1007/s11227-021-04270-w78:9(11441-11463)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11227-021-04270-w
Bank R(2019)A two level solver for $$h{-}p$$ adaptive finite element equationsComputing and Visualization in Science10.1007/s00791-017-0280-z20:3-6(51-57)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s00791-017-0280-z
Jacquelin MLin LJia WZhao YYang C(2018)A Left-Looking Selected Inversion Algorithm and Task Parallelism on Shared Memory SystemsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3149457.3149472(54-63)Online publication date: 28-Jan-2018
https://dl.acm.org/doi/10.1145/3149457.3149472
Greif CHe SLiu P(2017)SYM-ILDLACM Transactions on Mathematical Software10.1145/305494844:1(1-21)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3054948
Hagemann MSchenk O(2006)Weighted Matchings for Preconditioning Symmetric Indefinite Linear SystemsSIAM Journal on Scientific Computing10.1137/04061561428:2(403-420)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1137/040615614
Xie D(2004)An effective compressed sparse preconditioner for large scale biomolecular simulationsProceedings of the First international conference on Computational and Information Science10.1007/978-3-540-30497-5_11(64-70)Online publication date: 16-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30497-5_11
Li NSaad YChow E(2003)Crout Versions of ILU for General Sparse MatricesSIAM Journal on Scientific Computing10.1137/S106482750240509425:2(716-728)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1137/S1064827502405094
Bank RSmith R(2002)An Algebraic Multilevel Multigraph AlgorithmSIAM Journal on Scientific Computing10.1137/S106482750038104523:5(1572-1592)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.1137/S1064827500381045
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents