The DOI matches its Crossref record; 104 of the 104 references it cites were found in a registry or an index.
A survey of sparse matrix research
Abstract
This paper surveys the state of the art in sparse matrix research in January 1976. Much of the survey deals with the solution of sparse simultaneous linear equations, including the storage of such matrices and the effect of paging on sparse matrix algorithms. In the symmetric case, relevant terms from graph theory are defined. Band systems and matrices arising from the discretization of partial differential equations are treated as separate cases. Preordering techniques are surveyed with particular emphasis on partitioning (to block triangular form) and tearing (to bordered block triangular form). Methods for solving the least squares problem and for sparse linear programming are also reviewed. The sparse eigenproblem is discussed with particular reference to some fairly recent iterative methods. There is a short discussion of general iterative techniques, and reference is made to good standard texts in this field. Design considerations when implementing sparse matrix algorithms are examined and finally comments are made concerning the availability of codes in this area.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Harary, F. (1969) · Cited by 10,739
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Methods of conjugate gradients for solving linear systems
Hestenes, M. R., & Stiefel, E. (1952) · Journal of Research of the National Bureau of Standards · doi:10.6028/jres.049.044 · Cited by 8,132
Depth-First Search and Linear Graph Algorithms
Tarjan, R. (1972) · SIAM Journal on Computing · doi:10.1137/0201010 · Cited by 6,081
Varga, R. S. (2000) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-05156-2 · Cited by 5,811
Linear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
The Algebraic Eigenvalue Problem
I., E., & Wilkinson, J. H. (1966) · Mathematics of Computation · doi:10.2307/2003558 · Cited by 5,140
Lanczos, C. (1950) · Journal of Research of the National Bureau of Standards · doi:10.6028/jres.045.026 · Cited by 4,391
The finite element method in engineering science
Zienkiewicz, O. C. (1971) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,376
Bramble, J. H., & Varga, R. S. (1963) · Mathematics of Computation · doi:10.2307/2003862 · Cited by 4,091
Algorithms for the Assignment and Transportation Problems
Munkres, J. (1957) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0105003 · Cited by 3,986
Numerical Initial Value Problems in Ordinary Differential Equations
Watt, J. M. (1972) · The Computer Journal · doi:10.1093/comjnl/15.2.155 · Cited by 3,518
An Analysis of the Finite Element Method
I., E., Strang, G., & Fix, G. J. (1974) · Mathematics of Computation · doi:10.2307/2005716 · Cited by 3,484
The Numerical Solution of Parabolic and Elliptic Differential Equations
Peaceman, D. W., & Rachford, Jr. (1955) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0103003 · Cited by 3,255
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Hopcroft, J. E., & Karp, R. M. (1973) · SIAM Journal on Computing · doi:10.1137/0202019 · Cited by 2,802
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Introduction to matrix computations
Stewart, G. W. (1973) · International Linear Collider · Cited by 2,381
Hall, P. (1935) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-10.37.26 · Cited by 1,954
(2016) · The SAGE Encyclopedia of Theory in Psychology · doi:10.4135/9781483346274.n148 · Cited by 1,815
Calculating the Singular Values and Pseudo-Inverse of a Matrix
Golub, G., & Kahan, W. (1965) · Journal of the Society for Industrial and Applied Mathematics Series B Numerical Analysis · doi:10.1137/0702016 · Cited by 1,786
Iterative Solution of Large Linear Systems
(1971) · Elsevier eBooks · doi:10.1016/c2013-0-11733-3 · Cited by 1,734
Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations
Stone, H. L. (1968) · SIAM Journal on Numerical Analysis · doi:10.1137/0705044 · Cited by 1,692
Warshall, S. (1962) · Journal of the ACM · doi:10.1145/321105.321107 · Cited by 1,683
A study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
Solution of Sparse Indefinite Systems of Linear Equations
Paige, C. C., & Saunders, M. A. (1975) · SIAM Journal on Numerical Analysis · doi:10.1137/0712047 · Cited by 1,620
Reducing the bandwidth of sparse symmetric matrices
Cuthill, E., & McKee, J. (1969) · Proceedings of the 1969 24th national conference on - · doi:10.1145/800195.805928 · Cited by 1,457
Rounding errors in algebraic processes
(1964) · Journal of the Franklin Institute · doi:10.1016/0016-0032(64)90390-4 · Cited by 1,315
Incidence matrices and interval graphs
Fulkerson, D., & Gross, O. (1965) · Pacific Journal of Mathematics · doi:10.2140/pjm.1965.15.835 · Cited by 1,262
Power Flow Solution by Newton's Method
Tinney, W., & Hart, C. (1967) · IEEE Transactions on Power Apparatus and Systems · doi:10.1109/tpas.1967.291823 · Cited by 1,215
THE THEORY OF MATRICES IN NUMERICAL ANALYSIS
Mirsky, L. (1965) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-40.1.378b · Cited by 1,148
Iverson, K. E. (1962) · Proceedings of the May 1-3, 1962, spring joint computer conference on - AIEE-IRE '62 (Spring) · doi:10.1145/1460833.1460872 · Cited by 1,067
Nested Dissection of a Regular Finite Element Mesh
George, A. (1973) · SIAM Journal on Numerical Analysis · doi:10.1137/0710032 · Cited by 1,064
Numerical methods for solving linear least squares problems
Golub, G. (1965) · Numerische Mathematik · doi:10.1007/bf01436075 · Cited by 849
Direct solutions of sparse network equations by optimally ordered triangular factorization
Tinney, W. F., & Walker, J. (1967) · Proceedings of the IEEE · doi:10.1109/proc.1967.6011 · Cited by 811
The art of computer programming. Vol.1: Fundamental algorithms
Knuth, D. E. (1978) · Virtual Defense Library (Ministerio de Defensa) · Cited by 801
Meijerink, J. A., & van der Vorst, H. A. (1977) · Mathematics of Computation · doi:10.2307/2005786 · Cited by 794
On Direct Methods for Solving Poisson’s Equations
Buzbee, B. L., Golub, G. H., & Nielson, C. W. (1970) · SIAM Journal on Numerical Analysis · doi:10.1137/0707049 · Cited by 734
The Transitive Reduction of a Directed Graph
Aho, A. V., Garey, M. R., & Ullman, J. D. (1972) · SIAM Journal on Computing · doi:10.1137/0201008 · Cited by 718
The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
Francis, J. G. F. (1961) · The Computer Journal · doi:10.1093/comjnl/4.3.265 · Cited by 710
A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
Hockney, R. W. (1965) · Journal of the ACM · doi:10.1145/321250.321259 · Cited by 683
An empirical study of FORTRAN programs
Knuth, D. E. (1971) · Software: Practice and Experience · doi:10.1002/spe.4380010203 · Cited by 680
The potential calculation and some applications
Hockney, R. W. (1970) · Methods in computational physics · Cited by 650
Graph theory and theoretical physics
Harary, F. (1967) · Cited by 630
Unitary Triangularization of a Nonsymmetric Matrix
Householder, A. S. (1958) · Journal of the ACM · doi:10.1145/320941.320947 · Cited by 629
An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
Gibbs, N. E., Poole, W. G., & Stockmeyer, P. K. (1976) · SIAM Journal on Numerical Analysis · doi:10.1137/0713023 · Cited by 595
Methods for modifying matrix factorizations
Gill, P. E., Golub, G. H., Murray, W., & Saunders, M. A. (1974) · Mathematics of Computation · doi:10.1090/s0025-5718-1974-0343558-6 · Cited by 590
Handbook for Automatic Computation
Wilkinson, J. H., & Reinsch, C. (1971) · Springer eBooks · doi:10.1007/978-3-642-86940-2 · Cited by 545
The Elimination form of the Inverse and its Application to Linear Programming
Markowitz, H. M. (1957) · Management Science · doi:10.1287/mnsc.3.3.255 · Cited by 512
Triangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 500
Least Squares Computations by Givens Transformations Without Square Roots
GENTLEMAN, W. M. (1973) · IMA Journal of Applied Mathematics · doi:10.1093/imamat/12.3.329 · Cited by 479
Solving linear least squares problems by Gram-Schmidt orthogonalization
Björck, Å. (1967) · BIT · doi:10.1007/bf01934122 · Cited by 470
Rounding Errors in Algebraic Processes
(1964) · Nature · doi:10.1038/202016a0 · Cited by 456
Rose, D. J. (1972) · Elsevier eBooks · doi:10.1016/b978-1-4832-3187-7.50018-0 · Cited by 449
Concus, P., Golub, G. H., & O'Leary, D. P. (1976) · Sparse Matrix Computations · doi:10.1016/b978-0-12-141050-6.50023-4 · Cited by 433
Computational Variants of the Lanczos Method for the Eigenproblem
PAIGE, C. C. (1972) · IMA Journal of Applied Mathematics · doi:10.1093/imamat/10.3.373 · Cited by 408
Denning, P. J. (1970) · ACM Computing Surveys · doi:10.1145/356571.356573 · Cited by 407
Variants of the hungarian method for assignment problems
Kuhn, H. W. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030404 · Cited by 386
Handbook for Automatic Computation
Rutishauser, H. (1967) · Springer eBooks · doi:10.1007/978-3-642-86934-1 · Cited by 383
Francis, J. G. F. (1962) · The Computer Journal · doi:10.1093/comjnl/4.4.332 · Cited by 382
(1976) · Elsevier eBooks · doi:10.1016/c2013-0-10439-4 · Cited by 354
Triangular Factorization and Inversion by Fast Matrix Multiplication
Bunch, J. R., & Hopcroft, J. E. (1974) · Mathematics of Computation · doi:10.1090/s0025-5718-1974-0331751-8 · Cited by 353
Liu, W.-H., & Sherman, A. H. (1976) · SIAM Journal on Numerical Analysis · doi:10.1137/0713020 · Cited by 294
The Use of Linear Graphs in Gauss Elimination
Parter, S. (1961) · SIAM Review · doi:10.1137/1003021 · Cited by 290
An O (N2.5) algorithm for maximum matching in general graphs
Even, S., & Kariv, O. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.5 · Cited by 287
A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
Ford, L. R., & Fulkerson, D. R. (1957) · Canadian Journal of Mathematics · doi:10.4153/cjm-1957-024-0 · Cited by 286
The Determinant of the Adjacency Matrix of a Graph
Harary, F. (1962) · SIAM Review · doi:10.1137/1004057 · Cited by 236
The Direct Solution of the Discrete Poisson Equation on a Rectangle
Dorr, F. W. (1970) · SIAM Review · doi:10.1137/1012045 · Cited by 219
Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian
Schubert, L. K. (1970) · Mathematics of Computation · doi:10.1090/s0025-5718-1970-0258276-9 · Cited by 205
On Algorithms for Obtaining a Maximum Transversal
Duff, I. S. (1981) · ACM Transactions on Mathematical Software · doi:10.1145/355958.355963 · Cited by 203
Self-citationComputational aspects of F. L. Bauer's simultaneous iteration method
Rutishauser, H. (1969) · Numerische Mathematik · doi:10.1007/bf02165269 · Cited by 196
Efficient determination of the transitive closure of a directed graph
Munro, I. (1971) · Information Processing Letters · doi:10.1016/0020-0190(71)90006-8 · Cited by 195
PROCESS ANALYSIS AND SIMULATION
Micet, U. (2015) · Cited by 188
Organizing matrices and matrix operations for paged memory systems
McKellar, A. C., & Coffman, E. G. (1969) · Communications of the ACM · doi:10.1145/362875.362879 · Cited by 175
Algorithmic Aspects of Vertex Elimination on Directed Graphs
Rose, D. J., & Tarjan, R. E. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0134014 · Cited by 160
Phillips, G. M. (1974) · The Computer Journal · doi:10.1093/comjnl/17.4.370 · Cited by 159
Simultaneous iteration method for symmetric matrices
Rutishauser, H. (1970) · Numerische Mathematik · doi:10.1007/bf02219773 · Cited by 157
2P1,3 , 3P1,3 , and 4P1,3 States of He and the 2P1 State of Li+
Schiff, B., Lifson, H., Pekeris, C. L., & Rabinowitz, P. (1965) · Physical Review · doi:10.1103/physrev.140.a1104 · Cited by 147
Bauer, F. L. (1957) · Zeitschrift für angewandte Mathematik und Physik · doi:10.1007/bf01600502 · Cited by 146
A Set of Principles to Interconnect the Solutions of Physical Systems
Kron, G. (1953) · Journal of Applied Physics · doi:10.1063/1.1721447 · Cited by 132
Some Basic Techniques for Solving Sparse Systems of Linear Equations
Gustavson, F. G. (1972) · Springer eBooks · doi:10.1007/978-1-4615-8675-3_4 · Cited by 131
Large Sparse Sets of Linear Equations
H., A. S., & Reid, J. K. (1973) · Mathematics of Computation · doi:10.2307/2005268 · Cited by 126
An automatic reordering scheme for simultaneous equations derived from network systems
King, I. P. (1970) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.1620020406 · Cited by 124
Computer methods of network analysis
Branin, F. H. (1967) · Proceedings of the IEEE · doi:10.1109/proc.1967.6010 · Cited by 124
A Note on Modifications to the Givens Plane Rotation
Hammarling, S. J. (1974) · IMA Journal of Applied Mathematics · doi:10.1093/imamat/13.2.215 · Cited by 118
An algorithm for a minimum cover of a graph
Norman, R. Z., & Rabin, M. O. (1959) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1959-0106853-5 · Cited by 115
A transitive closure algorithm
Purdom, P. W. (1970) · BIT Numerical Mathematics · doi:10.1007/bf01940892 · Cited by 114
Gaylord, J. (2020) · CRC Press eBooks · doi:10.1201/9781003065418-3 · Cited by 113
Note on the iterative refinement of least squares solution
Golub, G. H., & Wilkinson, J. H. (1966) · Numerische Mathematik · doi:10.1007/bf02166032 · Cited by 112
Bidiagonalization of Matrices and Solution of Linear Equations
Paige, C. C. (1974) · SIAM Journal on Numerical Analysis · doi:10.1137/0711019 · Cited by 112
Tridiagonalization of a symetric band matrix
Schwarz, H. R. (1968) · Numerische Mathematik · doi:10.1007/bf02162505 · Cited by 99
A Generalized Cyclic Reduction Algorithm
Sweet, R. A. (1974) · SIAM Journal on Numerical Analysis · doi:10.1137/0711042 · Cited by 98
Primal partition programming for block diagonal matrices
Rosen, J. B. (1964) · Numerische Mathematik · doi:10.1007/bf01386073 · Cited by 91
An Algorithm for Distinct Representatives
Hall, M. (1956) · American Mathematical Monthly · doi:10.2307/2309562 · Cited by 90
An iterative block lanczos method for the solution of large sparse symmetric eigenproblems.
Underwood, R. (1975) · Cited by 86
The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration
Clint, M. (1970) · The Computer Journal · doi:10.1093/comjnl/13.1.76 · Cited by 86
A Survey of Indexing Techniques for Sparse Matrices
Pooch, U. W., & Nieder, A. (1973) · ACM Computing Surveys · doi:10.1145/356616.356618 · Cited by 83
GRAPH THEORY AND GAUSSIAN ELIMINATION
Tarjan, R. E. (1976) · Elsevier eBooks · doi:10.1016/b978-0-12-141050-6.50006-4 · Cited by 66
On the Complexity of Sparse Elimination
Emiris, I. Z. (1996) · Journal of Complexity · doi:10.1006/jcom.1996.0010 · Cited by 60
Eigenproblems for Matrices Associated with Periodic Boundary Conditions
Björck, Å., & Golub, G. H. (1977) · SIAM Review · doi:10.1137/1019002 · Cited by 34
The solution of natural frequency equations by relaxation methods
Cooper, J. L. B. (1948) · Quarterly of Applied Mathematics · doi:10.1090/qam/25816 · Cited by 21
An operating environment for dynamic-recursive computer programming systems
Brown, W. S. (1965) · Communications of the ACM · doi:10.1145/364955.364966 · Cited by 17
On Finding a Maximal Assignment
Yaspan, A. (1966) · Operations Research · doi:10.1287/opre.14.4.646 · Cited by 14
Cited by
The university of Florida sparse matrix collection
Davis, T. A., & Hu, Y. (2011) · ACM Transactions on Mathematical Software · doi:10.1145/2049662.2049663 · Cited by 3,630
Updating the Inverse of a Matrix
Hager, W. W. (1989) · SIAM Review · doi:10.1137/1031049 · Cited by 1,103
An iterative pruning algorithm for feedforward neural networks
Castellano, G., Fanelli, A. M., & Pelillo, M. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.572092 · Cited by 295
DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks
Wiedemann, S., Kirchhoffer, H., Matlage, S., Haase, P., Marban, A., Marinc, T., Neumann, D., Nguyen, T., Schwarz, H., Wiegand, T., et al. (2020) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2020.2969554 · Cited by 113
Metadata
- Authors
- Duff, I. S.
- Venue
- Proceedings of the IEEE
- Published
- 1977
- Volume
- 65
- Issue
- 4
- Pages
- 500-535
- ISSN
- 0018-9219 (ISSN-L)
- OpenAlex
- W2128676746
- Cited by
- 262
- References
- 104
- FWCI
- 21.78
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.