Some results on sparse matrices

Authors:
Robert K. Brayton, Fred G. Gustavson and Ralph A. Willoughby

Journal:
Math. Comp. **24** (1970), 937-954

MSC:
Primary 65.35

DOI:
https://doi.org/10.1090/S0025-5718-1970-0275643-8

MathSciNet review:
0275643

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A comparison in the context of sparse matrices is made between the Product Form of the Inverse PFI (a form of Gauss-Jordan elimination) and the Elimination Form of the Inverse EFI (a form of Gaussian elimination). The precise relation of the elements of these two forms of the inverse is given in terms of the nontrivial elements of the three matrices , , associated with the triangular factorization of the coefficient matrix ; i.e., , where is lower triangular and is unit upper triangular. It is shown that the zerononzero structure of the PFI always has more nonzeros than the EFI. It is proved that Gaussian elimination is a minimal algorithm with respect to preserving sparseness if the diagonal elements of the matrix are nonzero. However, Gaussian elimination is not necessarily minimal if has some zero diagonal elements. The same statements hold for the PFI as well. A probabilistic study of fill-in and computing times for the PFI and EFI sparse matrix algorithms is presented. This study suggests quantitatively how rapidly sparse matrices fill up for increasing densities, and emphasizes the necessity for reordering to minimize fill-in.

**[1]**Richard S. Varga,*Matrix iterative analysis*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR**0158502****[2]**T. Koopmans (Editor),*Activity Analysis of Production and Allocation*, Cowles Commission Monograph, no. 13, Wiley, New York and Chapman & Hall, London, 1951. MR**13**, 670.**[3]**V. Riley & R. L. Allen,*Interindustry Economic Studies*, Johns Hopkins Press, Baltimore, Md., 1955.**[4]***Linear Inequalities and Related Systems*, Ann. of Math. Studies, no. 38, Princeton Univ. Press, Princeton, N. J., 1956.**[5]**Saul I. Gass,*Linear programming: methods and applications*, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR**0096554****[6]**Vera Riley and Saul I. Gass,*Linear programming and associated techniques*, Bibliographic Reference Series No. 5, Published for Operations Research Office, The Johns Hopkins University, by the The Johns Hopkins Press, Baltimore, Md., 1958. MR**0093014****[7]**G. B. Dantzig & P. Wolfe, "Decomposition principle for linear programs,"*Operations Res.*, v. 8, 1960, pp. 101-111.**[8]**George B. Dantzig and Philip Wolfe,*The decomposition algorithm for linear programs*, Econometrica**29**(1961), 767–778. MR**0138506**, https://doi.org/10.2307/1911818**[9]**George B. Dantzig,*Linear programming and extensions*, Princeton University Press, Princeton, N.J., 1963. MR**0201189****[10]***Recent advances in mathematical programming*, Edited by Robert L. Graves and Philip Wolfe, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963. MR**0157776****[11]**Philip Wolfe and Leola Cutler,*Experiments in linear programming*, Recent advances in mathematical programming, McGraw-Hill, New York, 1963, pp. 177–200. MR**0155682****[12]**D. M. Smith & W. Orchard-Hays,*Computational Efficiency in Product Form LP Codes*, Recent Advances in Mathematical Programming, McGraw-Hill, New York, 1963, pp. 211-218.**[13]**Michel Simonnard,*Linear programming*, Translated from the French by William S. Jewell, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR**0201195****[14]**W. Orchard-Hays,*Advanced Linear Programming Computing Techniques*, McGraw-Hill, New York, 1968.**[15]**R. L. Weil, Jr., "The decomposition of economic production systems,"*Econometrica*, v. 36, 1968, pp. 260-278.**[16]**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. MR**0061469**, https://doi.org/10.1090/S0025-5718-1954-0061469-8**[17]**L. J. Larson, "A modified inversion procedure for product form of inverse in linear programming codes,"*Comm. ACM*, v. 5, 1962, pp. 382-383.**[18]**R. P. Tewarson,*On the product form of inverses of sparse matrices*, SIAM Rev.**8**(1966), 336–342. MR**0208822**, https://doi.org/10.1137/1008066**[19]**R. P. Tewarson,*The product form of inverses of sparse matrices and graph theory*, SIAM Rev.**9**(1967), 91–99. MR**0218003**, https://doi.org/10.1137/1009004**[20]**Harry M. Markowitz,*The elimination form of the inverse and its application to linear programming*, Management Sci.**3**(1957), 255–269. MR**0112244**, https://doi.org/10.1287/mnsc.3.3.255**[21]**George B. Dantzig,*Compact basis triangularization for the simplex method*, Recent Advances in Mathematical Programming, McGraw-Hill, New York, 1963, pp. 125–132. MR**0183530****[22]**A. M. Turing,*Rounding-off errors in matrix processes*, Quart. J. Mech. Appl. Math.**1**(1948), 287–308. MR**0028100**, https://doi.org/10.1093/qjmam/1.1.287**[23]**L. J. Paige & O. Taussky (Editors), "Simultaneous linear equations and the determination of eigenvalues,"*Nat. Bur. Standards Appl. Math. Ser.*, v. 29, 1953.**[24]**G. E. Forsythe and E. G. Straus,*On best conditioned matrices*, Proc. Amer. Math. Soc.**6**(1955), 340–345. MR**0069585**, https://doi.org/10.1090/S0002-9939-1955-0069585-4**[25]**E. Bodewig,*Matrix calculus*, North-Holland Publishing Company, Amsterdam, 1956. MR**0080363****[26]**Eryk Kosko,*Matrix inversion by partitioning*, Aero. Quart.**8**(1957), 157–184. MR**0090113****[27]**Alston S. Householder,*A survey of some closed methods for inverting matrices*, J. Soc. Indust. Appl. Math.**5**(1957), 155–169. MR**0091521****[28]**L. B. Wilson,*Solution of certain large sets of equations on Pegasus using matrix methods*, Comput. J.**2**(1959), 130–133. MR**0107359**, https://doi.org/10.1093/comjnl/2.3.130**[29]**E. E. Osborne,*On pre-conditioning of matrices*, J. Assoc. Comput. Mach.**7**(1960), 338–345. MR**0143333**, https://doi.org/10.1145/321043.321048**[30]**G. E. Forsythe, "Crout with pivoting,"*Comm. ACM*, v. 3, 1960, p. 507.**[31]**Alex Orden,*Matrix inversion and related topics by direct methods*, Mathematical methods for digital computers, Wiley, New York, 1960, pp. 39–55. MR**0117908****[32]**David L. Elliott,*A note on systems of linear equations*, SIAM Rev.**3**(1961), 66–69. MR**0121975**, https://doi.org/10.1137/1003006**[33]**S. Parter,*The use of linear graphs in Gauss elimination*, SIAM Rev.**3**(1961), 119–130. MR**0143349**, https://doi.org/10.1137/1003021**[34]**J. H. Wilkinson,*Error analysis of direct methods of matrix inversion*, J. Assoc. Comput. Mach.**8**(1961), 281–330. MR**0176602**, https://doi.org/10.1145/321075.321076**[35]**Frank Harary,*A graph theoretic approach to matrix inversion by partitioning*, Numer. Math.**4**(1962), 128–135. MR**0139545**, https://doi.org/10.1007/BF01386304**[36]**D. R. Fulkerson and P. Wolfe,*An algorithm for scaling matrices*, SIAM Rev.**4**(1962), 142–146. MR**0137587**, https://doi.org/10.1137/1004032**[37]**A. L. Dulmage and N. S. Mendelsohn,*On the inversion of sparse matrices*, Math. Comp.**16**(1962), 494–496. MR**0156452**, https://doi.org/10.1090/S0025-5718-1962-0156452-2**[38]**W. M. McKeeman, "Crout with equilibration and iteration,"*Comm. ACM*, v. 5, 1962, pp. 553-555.**[39]**F. L. Bauer,*Optimally scaled matrices*, Numer. Math.**5**(1963), 73–87. MR**0159412**, https://doi.org/10.1007/BF01385880**[40]**D. K. Faddeev & V. N. Faddeeva,*Computational Methods in Linear Algebra*, Fizmatgiz, Moscow, 1960; English transi, of 1st ed., Freeman, San Francisco, Calif., 1963. MR**28**#1742; MR**28**#4659.**[41]**A. L. Dulmage and N. S. Mendelsohn,*Two algorithms for bipartite graphs*, J. Soc. Indust. Appl. Math.**11**(1963), 183–194. MR**0154275****[42]**J. Carpentier,*“Éliminations ordonnées”, un processus diminuant le volume des calculs dans la résolution des systèmes linéaires à matrice creuse*, Troisième Congr. de Calcul et de Traitement de l’Information AF CALTI, Dunod, Paris, 1965, pp. 63–71 (French). MR**0184424****[43]**L. Fox,*An introduction to numerical linear algebra*, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR**0164436****[44]**Alston S. Householder,*The theory of matrices in numerical analysis*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1964. MR**0175290****[45]**Wai-kai Chen,*The inversion of matrices by flow graphs*, J. Soc. Indust. Appl. Math.**12**(1964), 676–685. MR**0171796****[46]**F. H. Branin, Jr., et al., "An interpretive program for matrix arithmetic,"*IBM Systems J.*, v. 4. 1965, pp. 2-24.**[47]**J. C. Dickson,*Finding Permutation Operations to Produce a Large Triangular Sub-Matrix*, Twenty-eighth National Meeting Operations Research Society of America, Houston, Texas, 1965.**[48]**B. H. Mayoh,*A graph technique for inverting certain matrices*, Math. Comp.**19**(1965), 644–646. MR**0196924**, https://doi.org/10.1090/S0025-5718-1965-0196924-0**[49]**W. Oettli, W. Prager, and J. H. Wilkinson,*Admissible solutions of linear systems with not sharply defined coefficients*, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal.**2**(1965), 291–299. MR**0184416****[50]**D. Bree, Jr.,*Some Remarks on the Application of Graph Theory to the Solution of Sparse Systems of Linear Equations*, Thesis, Dept. of Mathematics, Princeton University, Princeton, N. J., 1965.**[51]**H. Edelmann,*Ordered Triangular Factorization of Matrices*, Proc. Power System Computation Conference, Stockholm, 1966.**[52]**G. G. Alway & D. W. Martin, "An algorithm for reducing the bandwidth of a matrix of symmetrical configuration,"*Comput. J.*, v. 8, 1965/66, pp. 264-272.**[53]**W. Kahan, "Numerical linear algebra,"*Canad. Math. Bull.*, v. 9, 1966, pp. 757-801.**[54]**A. Jennings, "A compact storage scheme for the solution of symmetric linear simultaneous equations,"*Comput. J.*, v. 9, 1966/67, pp. 281-285.**[55]**H. J. Bowdler, R. S. Martin, G. Peters, and J. H. Wilkinson,*Handbook Series Linear Algebra: Solution of real and complex systems of linear equations*, Numer. Math.**8**(1966), no. 3, 217–234. MR**1553947**, https://doi.org/10.1007/BF02162559**[56]**A. M. Hershdorfer, et al.,*On the Efficient Inversion of Large Structured Matrices*, Proc. ASCE Engineering Mechanics Division Specialty Conference, Washington, D. C., 1966.**[57]**Bruce A. Chartres and James C. Geuder,*Computable error bounds for direct solution of linear equations*, J. Assoc. Comput. Mach.**14**(1967), 63–71. MR**0215550**, https://doi.org/10.1145/321371.321376**[58]**George E. Forsythe and Cleve B. Moler,*Computer solution of linear algebraic systems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR**0219223****[59 J]**H. Wilkinson,*The Solution of Ill-Conditioned Linear Equations*, Mathematical Methods for Digital Computers, vol. 2, Wiley, New York, 1967, pp. 65-93.**[60]**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. MR**0219225****[61]**Frank Harary,*Graphs and matrices*, SIAM Rev.**9**(1967), 83–90. MR**0210615**, https://doi.org/10.1137/1009003**[62]**George E. Forsythe,*Today’s computational methods of linear algebra*, SIAM Rev.**9**(1967), 489–515. MR**0218000**, https://doi.org/10.1137/1009071**[63]**W. F. Tinney & J. W. Walker, "Direct solutions of sparse network equations by optimally ordered triangular factorization,"*Proc. IEEE*, v. 55, 1967, pp. 1801-1809.**[64]**A. Nathan and R. K. Even,*The inversion of sparse matrices by a strategy derived from their graphs*, Comput. J.**10**(1967), 190–194. MR**0214277**, https://doi.org/10.1093/comjnl/10.2.190**[65]**R. P. Tewarson,*Row-column permutation of sparse matrices*, Comput. J.**10**(1967), 300–305. MR**0218002**, https://doi.org/10.1093/comjnl/10.3.300**[66]**Joan R. Westlake,*A handbook of numerical matrix inversion and solution of linear equations*, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0221742****[67]**R. P. Tewarson,*Solution of linear equations with coefficient matrix in band form*, Nordisk Tidskr. Informations-Behandling (BIT)**8**(1968), 53–58. MR**0226839****[68]**W. R. Spillers and Norris Hickerson,*Optimal elimination for sparse symmetric systems as a graph problem.*, Quart. Appl. Math.**26**(1968), 425–432. MR**0233497**, https://doi.org/10.1090/S0033-569X-1968-0233497-9**[69]**G. Loizou,*An empirical estimate of the relative error of the computed solution 𝑥 of 𝐴𝑥=𝑏*, Comput. J.**11**(1968/1969), 91–94. MR**0225474**, https://doi.org/10.1093/comjnl/11.1.91**[70]**Richard Rosen,*Matrix Band Width Minimization*, ACM National Conference, Las Vegas, Nevada, 1968.**[71]**System/360*Matrix Language*(MATLAN), Application Description, IBM H20-0479; Program Description Manual, IBM H20-0564; Operations Manual, IBM H20-0559; System Manual, IBM Y20-0261.**[72]**G. B. Dantzig, R. P. Harvey, R. D. McKnight & S. S. Smith,*Sparse Matrix Techniques in Two Mathematical Programming Codes*, Proc. Sparse Matrix Sympos., IBM Watson Research Center, Yorktown Heights, New York, 1968.**[73]**G. Kron,*Tensor Analysis of Networks*, Wiley, New York, 1939.**[74]**P. M. Hunt,*The electronic digital computer in aircraft structural analysis. The programming of the Argyris matrix formulation of structural theory for an electronic digital computer. I. A description of a matrix interpretive scheme and its application to a particular example*, Aircraft Engrg.**28**(1956), 70–76. MR**0076468****[75]**J. B. Ward & H. W. Hale, "Digital computer solution of power flow problems,"*Trans. AIEE*, v. PAS-75, 1956, part III, pp. 398-404.**[76]**R. J. Brown & W. F. Tinney, "Digital solutions for large power networks,"*Trans. AIEE*, v. PAS-76, 1957, part III, p. 347.**[77]**J. E. Van Ness, "Iteration methods for digital load flow studies,"*Trans. AIEE*, v. PAS-78A, 1959, part III, pp. 583-588.**[78]**R. K. Livesley,*The analysis of large structural systems*, Comput. J.**3**(1960/1961), 34–39. MR**0112344**, https://doi.org/10.1093/comjnl/3.1.34**[79]**C. H. Norris & J. B. Wilbur,*Elementary Structural Analysis*, 2nd ed., McGraw-Hill, New York, 1960.**[80]**J. E. Van Ness, "Convergence of iterative load-flow studies,"*Trans. AIEE*, v. PAS-79, 1960, part III, pp. 1590-1597.**[81]**A. S. Hall & R. W. Woodhead,*Frame Analysis*, Wiley, New York, 1961.**[82]**J. E. Van Ness & J. H. Griffin, "Elimination methods for loadflow studies,"*Trans. AIEE*, v. PAS-80, 1961, part III, pp. 299-304.**[83]**F. H. Branin, Jr., D-C*and Transient Analysis of Networks Using a Digital Computer*, IRE Internat. Conference Rec., part 2, 1962, pp. 236-256.**[84]**H. E. Brown, G. K. Carter, H. H. Happ & C. E. Person, "Power flow solution by matrix iterative method,"*Trans. AIEE*, v. PAS-82, 1963, part III, p. 1.**[85]**H. E. Brown, H. H. Happ, G. K. Carter & C. E. Person, "Power flow solution by impedance matrix iterative method,"*Trans. AIEE*, v. PAS-82, 1963, pp. 561-564.**[86]**R. W. Clough, E. L. Wilson & I. P. King, "Large capacity multistory frame analysis programs,"*ASCE J. Structural Division*, v. 89, 1963, p. 179.**[87]**S. J. Fenves & F. Branin, "A network-topological formulation of structural analysis,"*ASCE J. Structural Division*, v. 89, 1963, pp. 483-514.**[88]**S. J. Fenves,*STRESS (Structural Engineering System Solver) A Computer Programming System for Structural Engineering Problems*, M.I.T. Technical Report T63-2, 1963.**[89]**G. Kron,*Diakoptics*, Macdonald, London, 1963.**[90]**W. R. Spillers, "Network analogy for linear structures,"*Proc. ASCE J. Engrg. Mech. Division*, v. 89, 1963, no. EM-4, pp. 21-29.**[91]**W. R. Spillers, "Applications of topology in structural analysis,"*Proc. ASCE J. Structural Division*, v. 89, 1963, no. ST-4, pp. 301-313.**[92]**M. A. Laughton & M. W. H. Davies, "Numerical techniques in solution of power-system load-flow problems,"*Proc. IEEE*, v. 1ll, 1964, p. 1575.**[93]**W. R. Spillers, "Network techniques applied to structures,"*Matrix Tensor Quart.*, v. 15, 1964, pp. 31-41.**[94]**R. Baumann, "Some new aspects on load-flow calculation: I-impedance matrix generation controlled by network topologv,"*AIEE Trans.*, v. PAS-85, 1966, pp. 1164-1176.**[95]**F. H. Branin, Jr.,*The Algebraic-Topological Basis for Network Analogies and the Vector Calculus*, Proc. Sympos. on Generalized Networks, vol. 16, Microwave Res. Inst. Sympos. Ser. Poly. Inst. of Brooklyn, 1963, pp. 453-491.**[96]**F. F. Kuo, "Network analysis by digital computer,"*Proc. IEEE*, v. 54, 1966, pp. 820-829.**[97]**F. F. Kuo & J. F. Kaiser (Editors),*System Analysis by Digital Computer*, Wiley, New York, 1966.**[98]**F. H. Branin, Jr., "Computer methods of network analysis,"*Proc. IEEE*, v. 55, 1967, pp. 1787-1801.**[99]**G. H. Jensen, "Efficient matrix techniques applied to transmission tower design,"*Proc. IEEE*, v. 55, 1967, pp. 1997-2000.**[100]**G. H. Jensen,*Designing Self-supporting Transmission Towers with the Digital Computer*, PICA Conference, 1967, pp. 303-319.**[101]**W. F. Tinney & C. E. Hart, "Power flow solution by Newton's method,"*Trans. AIEE*, v. PAS-86, 1967, pp. 1449-1460.**[102]**A. T. Trihaus & R. Zimering,*A Digital Computer Program for an Exhaustive Fault Study of a Large Power System Network*, IEEE Power Industry Computer Applications Conference Rec., Pittsburgh, 1967, pp. 343-349.**[103]**W. Weaver, Jr.,*Computer Programs for Structural Analysis*, Van Nostrand, Princeton, N.J., 1967.**[104]**O. C. Zienkiewicz.*The Finite Element Method In Structural and Continuum Mechanics*, McGraw-Hill, New York, 1967.**[105]**J. S. Przemieniecki,*Theory of Matrix Structural Analysis*, McGraw-Hill, New York, 1968.**[106]**W. R. Spillers, "Analysis of large structures: Kron's methods and more recent work,"*Proc. ASCE*(To appear.)**[107]**G. W. Stagg & A. H. El-Abiad,*Computer Methods in Power System Analysis*, McGraw-Hill, New York, 1968.**[108]**N. Sato & W. F. Tinney, "Techniques for exploiting the sparsity of the network admittance matrix,"*Trans. AIEE*, v. PAS-82, 1963, pp. 944-950.**[109]**F. Gustavson, W. Liniger & R. Willoughby, "Symbolic generation of an optimal Crout algorithm for sparse systems of linear equations,"*J. Assoc. Comput. Mach.*, v. 17, 1970, pp. 87-109.**[110]**È¦ke Björck,*Solving linear least squares problems by Gram-Schmidt orthogonalization*, Nordisk Tidskr. Informations-Behandling**7**(1967), 1–21. MR**0214275****[111]**T. S. Motzkin,*The assignment problem*, Proceedings of Symposia in Applied Mathematics. Vol. VI. Numerical analysis, Published by McGraw-Hill Book Company, Inc., New York, 1956 for the American Mathematical Society, Providence, R. I., 1956, pp. 109–125. MR**0090480****[112]**James Munkres,*Algorithms for the assignment and transportation problems*, J. Soc. Indust. Appl. Math.**5**(1957), 32–38. MR**0093429****[113]**L. R. Ford Jr. and D. R. Fulkerson,*Flows in networks*, Princeton University Press, Princeton, N.J., 1962. MR**0159700****[114]**A. Yaspan, "On finding a maximal assignment,"*Operations Res.*, v. 14, 1966, pp. 646-651.**[115]**V. V. Klyuyev & N. I. Kokovkin-Shcherbak,*On the Minimization of the Number of Arithmetic Operations for the Solution of Linear Algebraic Systems*, Stanford Comput. Sci. Report CS-24, 1965.**[116]**S. Winograd,*On the Number of Multiplications Necessary to Compute Certain Functions*, IBM Watson Research Center, RC 2285, 1968.

Retrieve articles in *Mathematics of Computation*
with MSC:
65.35

Retrieve articles in all journals with MSC: 65.35

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1970-0275643-8

Keywords:
Sparse matrices,
elimination form of inverse,
product form of inverse,
fill-in,
symbolic and numerical zeros,
minimal algorithms

Article copyright:
© Copyright 1970
American Mathematical Society