Computations with Sparse Matrices
Reginald P. Tewarson · SIAM Review · 1970
Previous article Next article Computations with Sparse MatricesR. P. TewarsonR. P. Tewarsonhttps://doi.org/10.1137/1012103PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] F. A. Akyuz and , S. Utku, An automatic relabeling scheme for bandwidth minimization of stiffness matrices, AIAA J., 6 (1968), 728–730 CrossrefGoogle Scholar[2] G. G. Alway and , D. W. Martin, An algorithm for reducing the bandwidth of a matrix of symmetrical configuration, Comput. J., 8 (1965), 264–272 10.1093/comjnl/8.3.264 0147.13103 CrossrefISIGoogle Scholar[3] F. L. Bauer, Optimally scaled matrices, Numer. Math., 5 (1963), 73–87 10.1007/BF01385880 MR0159412 0107.10501 CrossrefGoogle Scholar[4] A. Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, Nordisk Tidskr. Informations-Behandling, 7 (1967), 1–21, BIT MR0214275 0183.17802 CrossrefGoogle Scholar[5] F. H. Branin, The relation between Kron's method and the classical methods of network analyses, The WESCON Convention Record, (1959), 1–29, Part 2 Google Scholar[6] R. K. Brayton, , F. G. Gustavson and , R. A. Willoughby, Some results on sparse matrices, Rep., RC 2332(11451), IBM, Yorktown Heights, N.Y., 1969 Google Scholar[7] Robert G. Busacker and , Thomas L. Saaty, Finite graphs and networks: An introduction with applications, McGraw-Hill Book Co., New York, 1965xiv+294 MR0209176 0146.20104 Google Scholar[8] B. A. Carré, The partitioning of network equations for block iteration, Comput. J., 9 (1966), 84–97 MR0195242 0229.65035 CrossrefISIGoogle Scholar[9] A. Chang, R. A. Willoughby, Application of sparse matrix methods in electric power system analysis, Proc. Symposium on Sparse Matrices and Their Applications, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969, 113–121 Google Scholar[10] E. Cuthill and , J. Mckee, Reducing the bandwidth of sparse symmetric matrices, Tech. Note, AML-40-69, Applied Mathematics Laboratory, Naval Ship Research and Development Center, Washington, D.C., 1969 Google Scholar[11] Philip Wolfe and , Leola Cutler, R. L. Graves and , P. Wolfe, Experiments in linear programmingRecent advances in mathematical programming, McGraw-Hill, New York, 1963, 177–200 MR0155682 0223.90001 Google Scholar[12] George B. Dantzig and , Wm. Orchard-Hays, The product form for the inverse in the simplex method, Math. Tables and Other Aids to Computation, 8 (1954), 64–67 MR0061469 0055.35103 CrossrefGoogle Scholar[13] G. B. Dantzig, , R. P. Harvey, , R. D. McKnight and , S. S. Smith, R. A. Willoughby, Sparse matrix techniques in two mathematical programming codes, Proc. Symposium on Sparse Matrices and Their Applications, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969, 9–10 Google Scholar[14] J. C. Dickson, Finding permutation operations to produce a large triangular sub-matrix, OR Society of America 28th national meeting, Houston, Texas, 1965 Google Scholar[15] A. L. Dulmage and , N. S. Mendelsohn, On the inversion of sparse matrices, Math. Comp., 16 (1962), 494–496 MR0156452 0115.11301 CrossrefGoogle Scholar[16] A. L. Dulmage and , N. S. Mendelsohn, F. Harary, Graphs and matricesGraph Theory and Theoretical Physics, Academic Press, London, 1967, 167–227. (loose errata) MR0252247 0204.24402 Google Scholar[17] H. Edelman, Massnahmen zur Reduction des Rechenaufwands bei der berechnung grosser elektrischer Netz, Electronic Rechenanlagen, 10 (1968), 118–123 Google Scholar[18] George E. Forsythe and , Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall Inc., Englewood Cliffs, N.J., 1967xi+148 MR0219223 0154.40401 Google Scholar[19] D. R. Fulkerson and , P. Wolfe, An algorithm for scaling matrices, SIAM Rev., 4 (1962), 142–146 10.1137/1004032 MR0137587 0108.12401 LinkISIGoogle Scholar[20] D. R. Fulkerson and , O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15 (1965), 835–855 MR0186421 0132.21001 CrossrefISIGoogle Scholar[21] F. Gustavson, , W. Liniger and , R. A. Willoughby, Symbolic generation of an optimal Crout algorithm for sparse system of equations, Rep., RC-1852, IBM, Yorktown Heights, N.Y., 1967 Google Scholar[22] Frank Harary, On the consistency of precedence matrices, J. Assoc. Comput. Mach., 7 (1960), 255–259 MR0131997 0097.12402 CrossrefISIGoogle Scholar[23] Frank Harary, A graph theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues, J. Math. Phys., 38 (1959/1960), 104–111 MR0109793 0087.01701 CrossrefGoogle Scholar[24] Frank Harary, A graph theoretic approach to matrix inversion by partitioning, Numer. Math., 4 (1962), 128–135 10.1007/BF01386304 MR0139545 0109.09003 CrossrefGoogle Scholar[25] Frank Harary, Graphs and matrices, SIAM Rev., 9 (1967), 83–90 10.1137/1009003 MR0210615 0146.45803 LinkISIGoogle Scholar[26] B. R. Heap, Random matrices and graphs, Numer. Math., 8 (1966), 114–122 10.1007/BF02163181 MR0194355 0139.33304 CrossrefISIGoogle Scholar[27] F. B. Hildebrand, Introduction to numerical analysis, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1956x+511 MR0075670 0070.12401 Google Scholar[28] A. Jennings, A compact storage scheme for the solution of symmetric linear simultaneous equations, Comput. J., 9 (1966), 281–285 0142.13401 CrossrefISIGoogle Scholar[29] A. Jennings, A sparse matrix scheme for the computer analysis of structures, Internat. J. Comput. Math., 2 (1968), 1–21 0164.18803 CrossrefISIGoogle Scholar[30] G. Kron, Diakoptics, McDonald, London, 1963 Google Scholar[31] L. J. Larson, A modified inversion procedure for product form of inverse in linear programming codes, Comm. ACM, 5 (1962), 382–383 10.1145/368273.368283 CrossrefISIGoogle Scholar[32] Petr Liebl and , Jiř Sedlacek, Umformung von Quadratmatrizen auf quasitrianguläre Form mit Mitteln der Graphentheorie, Apl. Mat., 11 (1966), 1–9 MR0195873 0171.13403 Google Scholar[33] H. B. Lee, R. A. Willoughby, An implementation of Gaussian elimination for sparse system of linear equations, Proc. Symposium on Sparse Matrices and Their Applications, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969, 75–84 Google Scholar[34] R. K. Livesley, The analysis of large structural systems, Comput. J., 3 (1960/1961), 34–39 10.1093/comjnl/3.1.34 MR0112344 0106.32501 CrossrefGoogle Scholar[35] Rosalind B. Marimont, A new method of checking the consistency of procedence matrices, J. Assoc. Comput. Mach., 6 (1959), 164–171 MR0102908 0086.33202 CrossrefISIGoogle Scholar[36] Rosalind B. Marimont, Applications of graphs and boolean matrices to computer programming., SIAM Rev., 2 (1960), 259–268 10.1137/1002058 MR0115295 0095.32101 LinkISIGoogle Scholar[37] Harry M. Markowitz, The elimination form of the inverse and its application to linear programming, Management Sci., 3 (1957), 255–269 MR0112244 0995.90592 CrossrefISIGoogle Scholar[38] B. H. Mayoh, A graph technique for inverting certain matrices, Math. Comp., 19 (1965), 644–646 MR0196924 0208.18104 CrossrefISIGoogle Scholar[39] C. W. McCormick, R. A. Willoughby, Application of partially banded matrix methods to structural analysis, Sparse Matrix Symposium, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969, 155–156 Google Scholar[40] A. Nathan and , R. K. Even, The inversion of sparse matrices by a strategy derived from their graphs, Comput. J., 10 (1967), 190–194 MR0214277 0155.46901 CrossrefISIGoogle Scholar[41] W. Orchard-Hays, Advanced Linear Programming Computing Techniques, McGraw-Hill, New York, 1968 Google Scholar[42] S. Parter, The use of linear graphs in Gauss elimination, SIAM Rev., 3 (1961), 119–130 10.1137/1003021 MR0143349 0102.11302 LinkISIGoogle Scholar[43] John R. Rice, Experiments on Gram-Schmidt orthogonalization, Math. Comp., 20 (1966), 325–328 MR0192673 0228.65034 CrossrefISIGoogle Scholar[44] Richard Rosen, Matrix band width minimization, Proc. 23rd National Conference of ACM, Publication P-68, Brandon Systems Press, Princeton, N.J., 1968, 585–595 Google Scholar[45] Ian C. Ross and , Frank Harary, A description of strengthening and weakening members of a group, Sociometry, 22 (1959), 139–147 MR0109790 CrossrefGoogle Scholar[46] J. Paul Roth, An application of algebraic topology: Kron's method of tearing, Quart. Appl. Math., 17 (1959), 1–24 MR0104337 CrossrefGoogle Scholar[47] N. Sato and , W. F. Tinney, Techniques for exploiting the sparsity of the network admittance matrix, IEEE Trans. Power Apparatus and Systems, PAS-82 (1963), 944–950 CrossrefGoogle Scholar[48] H. R. Schwarz, Tridiagonalization of a symmetric band matrix, Numer. Math., 12 (1968), 231–241 10.1007/BF02162505 0165.50201 CrossrefISIGoogle Scholar[49] D. M. Smith and , W. Orchard-Hays, R. L. Graves and , P. Wolfe, Computational efficiency in product form LP codesRecent Advances in Mathematical Programming, McGraw-Hill, New York, 1963, 211–218 Google Scholar[50] W. R. Spillers and , Norris Hickerson, Optimal elimination for sparse symmetric systems as a graph problem., Quart. Appl. Math., 26 (1968), 425–432 MR0233497 0164.20102 CrossrefISIGoogle Scholar[51] Donald V. Steward, On an approach to techniques for the analysis of the structure of large systems of equations, SIAM Rev., 4 (1962), 321–342 10.1137/1004088 MR0145652 0112.34602 LinkISIGoogle Scholar[52] Donald V. Steward, Partitioning and tearing systems of equations, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 345–365 MR0219224 0141.13502 LinkGoogle Scholar[53] R. P. Tewarson, On the product form of inverses of sparse matrices, SIAM Rev., 8 (1966), 336–342 10.1137/1008066 MR0208822 0222.65050 LinkISIGoogle Scholar[54] R. P. Tewarson, The product form of inverses of sparse matrices and graph theory, SIAM Rev., 9 (1967), 91–99 10.1137/1009004 MR0218003 0168.13302 LinkISIGoogle Scholar[55] R. P. Tewarson, Solution of a system of simultaneous linear equations with a sparse coefficient matrix by elimination methods, Nordisk Tidskr. Informations-Behandling (BIT), 7 (1967), 226–239 MR0219225 0222.65051 CrossrefGoogle Scholar[56] R. P. Tewarson, Row-column permutation of sparse matrices, Comput. J., 10 (1967), 300–305 10.1093/comjnl/10.3.300 MR0218002 0155.46902 CrossrefISIGoogle Scholar[57] R. P. Tewarson, On the orthonormalization of sparse vectors, Computing (Arch. Elektron. Rechnen), 3 (1968), 268–279 MR0239746 0174.46802 Google Scholar[58] R. P. Tewarson, Solution of linear equations with coefficient matrix in band form, Nordisk Tidskr. Informations-Behandling (BIT), 8 (1968), 53–58 MR0226839 0157.22503 CrossrefGoogle Scholar[59] R. P. Tewarson, The Crout reduction for sparse matrices, Comput. J., 12 (1969/1970), 158–159 10.1093/comjnl/12.2.158 MR0242356 0182.21301 CrossrefISIGoogle Scholar[60] R. P. Tewarson, On the transformation of symmetric sparse matrices to the triple diagonal form, Internat. J. Comput. Math., 2 (1970), 247–258 (1970) MR0282520 0233.65027 ISIGoogle Scholar[61] W. F. Tinney and , J. W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, Proc. IEEE, 55 (1967), 1801–1809 CrossrefISIGoogle Scholar[62] W. F. Tinney, R. A. Willoughby, Comments on using sparsity techniques for power systems problems, Proc. Symposium on Sparse Matrices and Their Applications, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969, 25–34 Google Scholar[63] Richard S. Varga, Matrix iterative analysis, Prentice-Hall Inc., Englewood Cliffs, N.J., 1962xiii+322 MR0158502 0133.08602 Google Scholar[64] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965xviii+662 MR0184422 Google Scholar[65] R. A. Willoughby, Symposium on Sparse Matrices and Their Applications, Rep. RAI(11707), IBM, Yorktown Heights, N.Y., 1969 Google Scholar Previous article Next article FiguresRelatedReferencesCited byDetails Combining Uneliminated Algebraic Formulations With Sparse Linear Solvers to Increase the Speed and Accuracy of Homotopy Path Tracking for Kinematic Synthesis17 August 2022 | Journal of Computing and Information Science in Engineering Cross Ref A survey of direct methods for sparse linear systems23 May 2016 | Acta Numerica, Vol. 25 Cross Ref Gaussian elimination for the solution of linear systems of equations Cross Ref References Cross Ref Matrices and Linear Algebra Cross Ref Analysis of global approaches to the simulation of counter-current separatorsComputers & Chemical Engineering, Vol. 8, No. 5 Cross Ref Computational methods of linear algebraJournal of Soviet Mathematics, Vol. 15, No. 5 Cross Ref A survey of sparse matrix researchProceedings of the IEEE, Vol. 65, No. 4 Cross Ref On solving problems with sparse matricesJournal of Soviet Mathematics, Vol. 7, No. 1 Cross Ref The theory and applications of the innersProceedings of the IEEE, Vol. 63, No. 7 Cross Ref The bordered triangular matrix and minimum essential sets of a digraphIEEE Transactions on Circuits and Systems, Vol. 21, No. 5 Cross Ref Some Experiments on Sparse Sets of Linear EquationsLjubomir B. Tosovic12 July 2006 | SIAM Journal on Applied Mathematics, Vol. 25, No. 2AbstractPDF (673 KB)A Survey of Indexing Techniques for Sparse MatricesACM Computing Surveys, Vol. 5, No. 2 Cross Ref A critique of the term value approach to determining molecular constants from the spectra of diatomic moleculesJournal of Molecular Spectroscopy, Vol. 46, No. 1 Cross Ref Sparsity-Oriented Ordering of Pivotal Operations on Network EquationsIsao Shirakawa, Akio Sakamoto, and Hiroshi Ozaki17 February 2012 | SIAM Journal on Applied Mathematics, Vol. 24, No. 1AbstractPDF (812 KB)Computing with sparse matricesInternational Journal for Numerical Methods in Engineering, Vol. 7, No. 2 Cross Ref The iterative calculation of several of the lowest or highest eigenvalues and corresponding eigenvectors of very large symmetric matricesJournal of Computational Physics, Vol. 11, No. 1 Cross Ref References Cross Ref On the optimal choice of pivots for the Gaussian eliminationComputing, Vol. 9, No. 3 Cross Ref On the gaussian elimination method for inverting sparse matricesComputing, Vol. 9, No. 1 Cross Ref On the fill-in when sparse vectors are orthonormalizedComputing, Vol. 9, No. 1 Cross Ref Volume 12, Issue 4| 1970SIAM Review History Submitted:27 October 1969Published online:18 July 2006 InformationCopyright © 1970 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/1012103Article page range:pp. 527-543ISSN (print):0036-1445ISSN (online):1095-7200Publisher:Society for Industrial and Applied Mathematics