Some results on sparse matrices
Authors:
Robert K. Brayton, Fred G. Gustavson and Ralph A. Willoughby
Journal:
Math. Comp. 24 (1970), 937954
MSC:
Primary 65.35
MathSciNet review:
0275643
Fulltext 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 GaussJordan 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 fillin 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 fillin.
 [1]
Richard
S. Varga, Matrix iterative analysis, PrenticeHall, Inc.,
Englewood Cliffs, N.J., 1962. MR 0158502
(28 #1725)
 [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,
McGrawHill Book Co., Inc., New YorkTorontoLondon, 1958. MR 0096554
(20 #3037)
 [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
(19,1197e)
 [7]
G. B. Dantzig & P. Wolfe, "Decomposition principle for linear programs," Operations Res., v. 8, 1960, pp. 101111.
 [8]
George
B. Dantzig and Philip
Wolfe, The decomposition algorithm for linear programs,
Econometrica 29 (1961), 767–778. MR 0138506
(25 #1953)
 [9]
George
B. Dantzig, Linear programming and extensions, Princeton
University Press, Princeton, N.J., 1963. MR 0201189
(34 #1073)
 [10]
Recent advances in mathematical programming, Edited by Robert L.
Graves and Philip Wolfe, McGrawHill Book Co., Inc., New YorkSan
FranciscoTorontoLondon, 1963. MR 0157776
(28 #1005)
 [11]
Philip
Wolfe and Leola
Cutler, Experiments in linear programming, Recent advances in
mathematical programming, McGrawHill, New York, 1963,
pp. 177–200. MR 0155682
(27 #5616)
 [12]
D. M. Smith & W. OrchardHays, Computational Efficiency in Product Form LP Codes, Recent Advances in Mathematical Programming, McGrawHill, New York, 1963, pp. 211218.
 [13]
Michel
Simonnard, Linear programming, Translated from the French by
William S. Jewell, PrenticeHall, Inc., Englewood Cliffs, N.J., 1966. MR 0201195
(34 #1079)
 [14]
W. OrchardHays, Advanced Linear Programming Computing Techniques, McGrawHill, New York, 1968.
 [15]
R. L. Weil, Jr., "The decomposition of economic production systems," Econometrica, v. 36, 1968, pp. 260278.
 [16]
George
B. Dantzig and Wm.
OrchardHays, The product form for the inverse in
the simplex method, Math. Tables and Other Aids
to Computation 8
(1954), 64–67. MR 0061469
(15,831c), http://dx.doi.org/10.1090/S00255718195400614698
 [17]
L. J. Larson, "A modified inversion procedure for product form of inverse in linear programming codes," Comm. ACM, v. 5, 1962, pp. 382383.
 [18]
R.
P. Tewarson, On the product form of inverses of sparse
matrices, SIAM Rev. 8 (1966), 336–342. MR 0208822
(34 #8631)
 [19]
R.
P. Tewarson, The product form of inverses of sparse matrices and
graph theory, SIAM Rev. 9 (1967), 91–99. MR 0218003
(36 #1092)
 [20]
Harry
M. Markowitz, The elimination form of the inverse and its
application to linear programming, Management Sci. 3
(1957), 255–269. MR 0112244
(22 #3098)
 [21]
George
B. Dantzig, Compact basis triangularization for the simplex
method, Recent Advances in Mathematical Programming, McGrawHill, New
York, 1963, pp. 125–132. MR 0183530
(32 #1010)
 [22]
A.
M. Turing, Roundingoff errors in matrix processes, Quart. J.
Mech. Appl. Math. 1 (1948), 287–308. MR 0028100
(10,405c)
 [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
(16,1054j), http://dx.doi.org/10.1090/S00029939195500695854
 [25]
E.
Bodewig, Matrix calculus, NorthHolland Publishing Company,
Amsterdam, 1956. MR 0080363
(18,235e)
 [26]
Eryk
Kosko, Matrix inversion by partitioning, Aero. Quart.
8 (1957), 157–184. MR 0090113
(19,769c)
 [27]
Alston
S. Householder, A survey of some closed methods for inverting
matrices, J. Soc. Indust. Appl. Math. 5 (1957),
155–169. MR 0091521
(19,982h)
 [28]
L.
B. Wilson, Solution of certain large sets of equations on Pegasus
using matrix methods, Comput. J. 2 (1959),
130–133. MR 0107359
(21 #6084)
 [29]
E.
E. Osborne, On preconditioning of matrices, J. Assoc. Comput.
Mach. 7 (1960), 338–345. MR 0143333
(26 #892)
 [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
(22 #8682)
 [32]
David
L. Elliott, A note on systems of linear equations, SIAM Rev.
3 (1961), 66–69. MR 0121975
(22 #12702)
 [33]
S.
Parter, The use of linear graphs in Gauss elimination, SIAM
Rev. 3 (1961), 119–130. MR 0143349
(26 #908)
 [34]
J.
H. Wilkinson, Error analysis of direct methods of matrix
inversion, J. Assoc. Comput. Mach. 8 (1961),
281–330. MR 0176602
(31 #874)
 [35]
Frank
Harary, A graph theoretic approach to matrix inversion by
partitioning, Numer. Math. 4 (1962), 128–135.
MR
0139545 (25 #2977)
 [36]
D.
R. Fulkerson and P.
Wolfe, An algorithm for scaling matrices, SIAM Rev.
4 (1962), 142–146. MR 0137587
(25 #1039)
 [37]
A.
L. Dulmage and N.
S. Mendelsohn, On the inversion of sparse
matrices, Math. Comp. 16 (1962), 494–496. MR 0156452
(27 #6375), http://dx.doi.org/10.1090/S00255718196201564522
 [38]
W. M. McKeeman, "Crout with equilibration and iteration," Comm. ACM, v. 5, 1962, pp. 553555.
 [39]
F.
L. Bauer, Optimally scaled matrices, Numer. Math.
5 (1963), 73–87. MR 0159412
(28 #2629)
 [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
(27 #4224)
 [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
(32 #1896)
 [43]
L.
Fox, An introduction to numerical linear algebra, Monographs
on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436
(29 #1733)
 [44]
Alston
S. Householder, The theory of matrices in numerical analysis,
Blaisdell Publishing Co. Ginn and Co. New YorkTorontoLondon, 1964. MR 0175290
(30 #5475)
 [45]
Waikai
Chen, The inversion of matrices by flow graphs, J. Soc.
Indust. Appl. Math. 12 (1964), 676–685. MR 0171796
(30 #2023)
 [46]
F. H. Branin, Jr., et al., "An interpretive program for matrix arithmetic," IBM Systems J., v. 4. 1965, pp. 224.
 [47]
J. C. Dickson, Finding Permutation Operations to Produce a Large Triangular SubMatrix, Twentyeighth 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
(33 #5108), http://dx.doi.org/10.1090/S00255718196501969240
 [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
(32 #1888)
 [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. 264272.
 [53]
W. Kahan, "Numerical linear algebra," Canad. Math. Bull., v. 9, 1966, pp. 757801.
 [54]
A. Jennings, "A compact storage scheme for the solution of symmetric linear simultaneous equations," Comput. J., v. 9, 1966/67, pp. 281285.
 [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, http://dx.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 (35 #6390)
 [58]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
(36 #2306)
 [59 J]
H. Wilkinson, The Solution of IllConditioned Linear Equations, Mathematical Methods for Digital Computers, vol. 2, Wiley, New York, 1967, pp. 6593.
 [60]
R.
P. Tewarson, Solution of a system of simultaneous linear equations
with a sparse coefficient matrix by elimination methods, Nordisk
Tidskr. InformationsBehandling (BIT) 7 (1967),
226–239. MR 0219225
(36 #2308)
 [61]
Frank
Harary, Graphs and matrices, SIAM Rev. 9
(1967), 83–90. MR 0210615
(35 #1501)
 [62]
George
E. Forsythe, Today’s computational methods of linear
algebra, SIAM Rev. 9 (1967), 489–515. MR 0218000
(36 #1089)
 [63]
W. F. Tinney & J. W. Walker, "Direct solutions of sparse network equations by optimally ordered triangular factorization," Proc. IEEE, v. 55, 1967, pp. 18011809.
 [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
(35 #5128)
 [65]
R.
P. Tewarson, Rowcolumn permutation of sparse matrices,
Comput. J. 10 (1967), 300–305. MR 0218002
(36 #1091)
 [66]
Joan
R. Westlake, A handbook of numerical matrix inversion and solution
of linear equations, John Wiley & Sons, Inc., New
YorkLondonSydney, 1968. MR 0221742
(36 #4794)
 [67]
R.
P. Tewarson, Solution of linear equations with coefficient matrix
in band form, Nordisk Tidskr. InformationsBehandling (BIT)
8 (1968), 53–58. MR 0226839
(37 #2425)
 [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
(38 #1818)
 [69]
G.
Loizou, An empirical estimate of the relative error of the computed
solution 𝑥 of 𝐴𝑥=𝑏, Comput. J.
11 (1968/1969), 91–94. MR 0225474
(37 #1067)
 [70]
Richard Rosen, Matrix Band Width Minimization, ACM National Conference, Las Vegas, Nevada, 1968.
 [71]
System/360 Matrix Language (MATLAN), Application Description, IBM H200479; Program Description Manual, IBM H200564; Operations Manual, IBM H200559; System Manual, IBM Y200261.
 [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
(17,902l)
 [75]
J. B. Ward & H. W. Hale, "Digital computer solution of power flow problems," Trans. AIEE, v. PAS75, 1956, part III, pp. 398404.
 [76]
R. J. Brown & W. F. Tinney, "Digital solutions for large power networks," Trans. AIEE, v. PAS76, 1957, part III, p. 347.
 [77]
J. E. Van Ness, "Iteration methods for digital load flow studies," Trans. AIEE, v. PAS78A, 1959, part III, pp. 583588.
 [78]
R.
K. Livesley, The analysis of large structural systems, Comput.
J. 3 (1960/1961), 34–39. MR 0112344
(22 #3195)
 [79]
C. H. Norris & J. B. Wilbur, Elementary Structural Analysis, 2nd ed., McGrawHill, New York, 1960.
 [80]
J. E. Van Ness, "Convergence of iterative loadflow studies," Trans. AIEE, v. PAS79, 1960, part III, pp. 15901597.
 [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. PAS80, 1961, part III, pp. 299304.
 [83]
F. H. Branin, Jr., DC and Transient Analysis of Networks Using a Digital Computer, IRE Internat. Conference Rec., part 2, 1962, pp. 236256.
 [84]
H. E. Brown, G. K. Carter, H. H. Happ & C. E. Person, "Power flow solution by matrix iterative method," Trans. AIEE, v. PAS82, 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. PAS82, 1963, pp. 561564.
 [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 networktopological formulation of structural analysis," ASCE J. Structural Division, v. 89, 1963, pp. 483514.
 [88]
S. J. Fenves, STRESS (Structural Engineering System Solver) A Computer Programming System for Structural Engineering Problems, M.I.T. Technical Report T632, 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. EM4, pp. 2129.
 [91]
W. R. Spillers, "Applications of topology in structural analysis," Proc. ASCE J. Structural Division, v. 89, 1963, no. ST4, pp. 301313.
 [92]
M. A. Laughton & M. W. H. Davies, "Numerical techniques in solution of powersystem loadflow problems," Proc. IEEE, v. 1ll, 1964, p. 1575.
 [93]
W. R. Spillers, "Network techniques applied to structures," Matrix Tensor Quart., v. 15, 1964, pp. 3141.
 [94]
R. Baumann, "Some new aspects on loadflow calculation: Iimpedance matrix generation controlled by network topologv," AIEE Trans., v. PAS85, 1966, pp. 11641176.
 [95]
F. H. Branin, Jr., The AlgebraicTopological 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. 453491.
 [96]
F. F. Kuo, "Network analysis by digital computer," Proc. IEEE, v. 54, 1966, pp. 820829.
 [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. 17871801.
 [99]
G. H. Jensen, "Efficient matrix techniques applied to transmission tower design," Proc. IEEE, v. 55, 1967, pp. 19972000.
 [100]
G. H. Jensen, Designing Selfsupporting Transmission Towers with the Digital Computer, PICA Conference, 1967, pp. 303319.
 [101]
W. F. Tinney & C. E. Hart, "Power flow solution by Newton's method," Trans. AIEE, v. PAS86, 1967, pp. 14491460.
 [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. 343349.
 [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, McGrawHill, New York, 1967.
 [105]
J. S. Przemieniecki, Theory of Matrix Structural Analysis, McGrawHill, 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. ElAbiad, Computer Methods in Power System Analysis, McGrawHill, New York, 1968.
 [108]
N. Sato & W. F. Tinney, "Techniques for exploiting the sparsity of the network admittance matrix," Trans. AIEE, v. PAS82, 1963, pp. 944950.
 [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. 87109.
 [110]
Ȧke
Björck, Solving linear least squares problems by GramSchmidt
orthogonalization, Nordisk Tidskr. InformationsBehandling
7 (1967), 1–21. MR 0214275
(35 #5126)
 [111]
T.
S. Motzkin, The assignment problem, Proceedings of Symposia in
Applied Mathematics. Vol. VI. Numerical analysis, Published by McGrawHill
Book Company, Inc., New York, 1956 for the American Mathematical Society,
Providence, R. I., 1956, pp. 109–125. MR 0090480
(19,822a)
 [112]
James
Munkres, Algorithms for the assignment and transportation
problems, J. Soc. Indust. Appl. Math. 5 (1957),
32–38. MR
0093429 (19,1244f)
 [113]
L.
R. Ford Jr. and D.
R. Fulkerson, Flows in networks, Princeton University Press,
Princeton, N.J., 1962. MR 0159700
(28 #2917)
 [114]
A. Yaspan, "On finding a maximal assignment," Operations Res., v. 14, 1966, pp. 646651.
 [115]
V. V. Klyuyev & N. I. KokovkinShcherbak, On the Minimization of the Number of Arithmetic Operations for the Solution of Linear Algebraic Systems, Stanford Comput. Sci. Report CS24, 1965.
 [116]
S. Winograd, On the Number of Multiplications Necessary to Compute Certain Functions, IBM Watson Research Center, RC 2285, 1968.
 [1]
 R. S. Varga, Matrix Iterative Analysis, PrenticeHall, Englewood Cliffs, N. J., 1962. MR 28 #1725. MR 0158502 (28:1725)
 [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]
 S. I. Gass, Linear Programming: Methods and Applications, McGrawHill, New York, 1958. MR 20 #3037. MR 0096554 (20:3037)
 [6]
 V. Riley <& S. I. Gass, Linear Programming and Associated Techniques, Bibliographic Reference Series, no. 5, Johns Hopkins Press, Baltimore, Md., 1958. MR 19, 1197. MR 0093014 (19:1197e)
 [7]
 G. B. Dantzig & P. Wolfe, "Decomposition principle for linear programs," Operations Res., v. 8, 1960, pp. 101111.
 [8]
 G. B. Dantzig & P. Wolfe, "The decomposition algorithm for linear programs," Econometrica, v. 29, 1961, pp. 767778. MR 25 #1953. MR 0138506 (25:1953)
 [9]
 G. B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, Princeton, N. J., 1963. MR 0201189 (34:1073)
 [10]
 R. L. Graves & P. Wolfe (Editors), Recent Advances in Mathematical Programming, McGrawHill, New York, 1963. MR 0157776 (28:1005)
 [11]
 P. Wolfe & L. Cutler, Experiments in Linear Programming, Recent Advances in Mathematical Programming, McGrawHill, New York, 1963, pp. 177200. MR 0155682 (27:5616)
 [12]
 D. M. Smith & W. OrchardHays, Computational Efficiency in Product Form LP Codes, Recent Advances in Mathematical Programming, McGrawHill, New York, 1963, pp. 211218.
 [13]
 M. Simonnard, Linear Programming, PrenticeHall, Englewood Cliffs, N. J., 1966. MR 0201195 (34:1079)
 [14]
 W. OrchardHays, Advanced Linear Programming Computing Techniques, McGrawHill, New York, 1968.
 [15]
 R. L. Weil, Jr., "The decomposition of economic production systems," Econometrica, v. 36, 1968, pp. 260278.
 [16]
 G. B. Dantzig & W. OrchardHays, "The product form of the inverse in the simplex method," MTAC, v. 8, 1954, pp. 6467. MR 15, 831. MR 0061469 (15:831c)
 [17]
 L. J. Larson, "A modified inversion procedure for product form of inverse in linear programming codes," Comm. ACM, v. 5, 1962, pp. 382383.
 [18]
 R. P. Tewarson, "On the product form of inverses of sparse matrices," SIAM Rev., v. 8, 1966, pp. 336342. MR 34 #8631. MR 0208822 (34:8631)
 [19]
 R. P. Tewarson, "On the product form of inverses of sparse matrices and graph theory," SIAM Rev., v. 9, 1967, pp. 9199. MR 36 #1092. MR 0218003 (36:1092)
 [20]
 H. M. Markowitz, "The elimination form of the inverse and its application to linear programming," Management Sci., v. 3, 1957, pp. 255269. MR 22 #3098. MR 0112244 (22:3098)
 [21]
 G. B. Dantzig, Compact Basis Triangulartzation for the Simplex Method, Recent Advances in Mathematical Programming, McGrawHill, New York, 1963, pp. 125132. MR 32 #1010. MR 0183530 (32:1010)
 [22]
 A. M. Turing, "Roundingoff errors in matrix processes," Quart. J. Mech. Appl. Math., v. 1, 1948, pp. 287308. MR 10, 405. MR 0028100 (10:405c)
 [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 & E. G. Straus, "On best conditioned matrices," Proc. Amer. Math. Soc., v. 6, 1955, pp. 340345. MR 16, 1054. MR 0069585 (16:1054j)
 [25]
 E. Bodewig, Matrix Calculus, NorthHolland, Amsterdam, 1956. MR 18, 235. MR 0080363 (18:235e)
 [26]
 E. Kosko, "Matrix inversion by partitioning," Aero. Quart., v. 8, 1957, pp. 157184. MR 19, 769. MR 0090113 (19:769c)
 [27]
 A. S. Householder, "A survey of some closed methods for inverting matrices," J. Soc. Indust. Appl. Math., v. 5, 1957, pp. 155169. MR 19, 982. MR 0091521 (19:982h)
 [28]
 L. B. Wilson, "Solution of certain large sets of equations on Pegasus using matrix methods," Comput. J., v. 2, 1959, pp. 130133. MR 21 #6084. MR 0107359 (21:6084)
 [29]
 E. E. Osborne, "On preconditioning of matrices," J. Assoc Comput. Mach., v. 7, 1960, pp. 338345. MR 26 #892. MR 0143333 (26:892)
 [30]
 G. E. Forsythe, "Crout with pivoting," Comm. ACM, v. 3, 1960, p. 507.
 [31]
 A. Orden, Matrix Inversion and Related Topics by Direct Methods, Mathematical Methods for Digital Computers, vol. 1, Wiley, New York, 1960, pp. 3955. MR 22 #8682. MR 0117908 (22:8682)
 [32]
 D. L. Elliott, "A note on systems of linear equations," SIAM Rev., v. 3, 1961, pp. 6669. MR 22 #12702. MR 0121975 (22:12702)
 [33]
 S. Parter, "The use of linear graphs in Gauss elimination," SIAM Rev., v. 3, 1961, pp. 119130. MR 26 #908. MR 0143349 (26:908)
 [34]
 J. H. Wilkinson, "Error analysis of direct methods of matrix inversion," J. Assoc. Comput. Mach., v. 8, 1961, pp. 281330. MR 31 #874. MR 0176602 (31:874)
 [35]
 F. Harary, "A graph theoretic approach to matrix inversion by partitioning," Numer. Math., v. 4, 1962, pp. 128135. MR 25 #2977. MR 0139545 (25:2977)
 [36]
 D. R. Fulkerson & P. Wolfe, "An algorithm for scaling matrices," SIAM Rev., v. 4, 1962, pp. 142146. MR 25 #1039. MR 0137587 (25:1039)
 [37]
 A. L. Dulmage & N. S. Mendelsohn, "On the inversion of sparse matrices," Math. Comp., v. 16, 1962, pp. 494496. MR 27 #6375. MR 0156452 (27:6375)
 [38]
 W. M. McKeeman, "Crout with equilibration and iteration," Comm. ACM, v. 5, 1962, pp. 553555.
 [39]
 F. L. Bauer, "Optimally scaled matrices," Numer. Math., v. 5, 1963, pp. 73087. MR 28 #2629. MR 0159412 (28:2629)
 [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 & N. S. Mendelsohn, "Two algorithms for bipartite graphs," J. Soc Indust. Appl. Math., v. 11, 1963, pp. 183194. MR 27 #4224. MR 0154275 (27:4224)
 [42]
 J. Carpentier, "Éliminations ordonnées," un processus diminuant le volume des calculs dans la résolutions des systèmes linéaires à matrice creuse, Troisième Congr. de Calcul et de Traitement de l'Information AFCALTI, Dunod, Paris, 1965, pp. 6371. MR 32 #1896. MR 0184424 (32:1896)
 [43]
 L. Fox, An Introduction to Numerical Linear Algebra, Clarendon Press, Oxford, 1964. MR 29 #1733. MR 0164436 (29:1733)
 [44]
 A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, Waltbam, Mass., 1964. MR 30 #5475. MR 0175290 (30:5475)
 [45]
 W.K. Chen, "The inversion of matrices by flow graphs," J. Soc. Indust. Appl. Math., v. 12, 1964, pp. 676685. MR 30 #2023. MR 0171796 (30:2023)
 [46]
 F. H. Branin, Jr., et al., "An interpretive program for matrix arithmetic," IBM Systems J., v. 4. 1965, pp. 224.
 [47]
 J. C. Dickson, Finding Permutation Operations to Produce a Large Triangular SubMatrix, Twentyeighth National Meeting Operations Research Society of America, Houston, Texas, 1965.
 [48]
 B. H. Mayoh, "A graph technique for inverting certain matrices," Math. Comp., v. 19, 1965, pp. 644646. MR 33 #5108. MR 0196924 (33:5108)
 [49]
 W. Oettlie, W. Prager & J. H. Wilkinson, "Admissible solutions of linear systems with not sharply defined coefficients," J. Soc. Indust. Appl. Math. Ser. B. Numer. Anal., v. 2, 1965, pp. 291299. MR 32 #1888. MR 0184416 (32:1888)
 [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. 264272.
 [53]
 W. Kahan, "Numerical linear algebra," Canad. Math. Bull., v. 9, 1966, pp. 757801.
 [54]
 A. Jennings, "A compact storage scheme for the solution of symmetric linear simultaneous equations," Comput. J., v. 9, 1966/67, pp. 281285.
 [55]
 H. J. Bowdler, R. S. Martin, G. Peters & J. H. Wilkinson, "Solution of real and complex systems of linear equations," Numer. Math., v. 8, 1966, pp. 217234. MR 1553947
 [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]
 B. A. Chartres & J. C. Geuder, "Computable error bounds for direct solution of linear equations," J. Assoc. Comput. Mach., v. 14, 1967, pp. 6371. MR 35 #6390. MR 0215550 (35:6390)
 [58]
 G. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Equations, PrenticeHall, Englewood Cliffs, N. J., 1967. MR 36 #2306. MR 0219223 (36:2306)
 [59 J]
 H. Wilkinson, The Solution of IllConditioned Linear Equations, Mathematical Methods for Digital Computers, vol. 2, Wiley, New York, 1967, pp. 6593.
 [60]
 R. P. Tewarson, "Solution of a system of simultaneous linear equations with a sparse coefficient matrix by elimination methods," Nordisk Tidskr. InformationsBehandling, v. 7, 1967, pp. 226239. MR 36 #2308. MR 0219225 (36:2308)
 [61]
 F. Harary, "Graphs and matrices," SIAM Rev., v. 9, 1967, pp. 8390. MR 35 #1501. MR 0210615 (35:1501)
 [62]
 G. E. Forsythe, "Today's computational methods of linear algebra," SIAM Rev., v. 9, 1967, pp. 489515. MR 36 #1089. MR 0218000 (36:1089)
 [63]
 W. F. Tinney & J. W. Walker, "Direct solutions of sparse network equations by optimally ordered triangular factorization," Proc. IEEE, v. 55, 1967, pp. 18011809.
 [64]
 A. Nathan & R. K. Even, "The inversion of sparse matrices by a strategy derived from their graphs," Comput. J., v. 10, 1967, pp. 190194. MR 35 #5128. MR 0214277 (35:5128)
 [65]
 R. P. Tewarson, "Rowcolumn permutation of sparse matrices," Comput. J., v. 10, 1967, pp. 300305. MR 36 #1091. MR 0218002 (36:1091)
 [66]
 J. R. Westlake, A Handbook of Numerical Matrix Inversion and Solution of Linear Systems, Wiley, New York, 1968. MR 36 #4794. MR 0221742 (36:4794)
 [67]
 R. P. Tewarson, "Solution of linear equations with coefficient matrix in band from" Nordisk Tidskr. InformationsBehandling, v. 8, 1968, pp. 5358. MR 37 #2425. MR 0226839 (37:2425)
 [68]
 W. R. Spillers & N. Hickerson, "Optimal elimination for sparse symmetric systems as a graph problem," Quart. Appl. Math., v. 26, 1968, pp. 425432. MR 38 #1818. MR 0233497 (38:1818)
 [69]
 G. Loizou, "An empirical estimate of the relative error of the computed solution of " Comput. J., v. 11, 1968/69, pp. 9194. MR 37 #1067. MR 0225474 (37:1067)
 [70]
 Richard Rosen, Matrix Band Width Minimization, ACM National Conference, Las Vegas, Nevada, 1968.
 [71]
 System/360 Matrix Language (MATLAN), Application Description, IBM H200479; Program Description Manual, IBM H200564; Operations Manual, IBM H200559; System Manual, IBM Y200261.
 [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., v. 28, 1956, pp. 7076. MR 17, 902. MR 0076468 (17:902l)
 [75]
 J. B. Ward & H. W. Hale, "Digital computer solution of power flow problems," Trans. AIEE, v. PAS75, 1956, part III, pp. 398404.
 [76]
 R. J. Brown & W. F. Tinney, "Digital solutions for large power networks," Trans. AIEE, v. PAS76, 1957, part III, p. 347.
 [77]
 J. E. Van Ness, "Iteration methods for digital load flow studies," Trans. AIEE, v. PAS78A, 1959, part III, pp. 583588.
 [78]
 R. Livesley, "The analysis of large structural systems," Comput. J., v. 3, 1960/61, pp. 3439. MR 22 #3195. MR 0112344 (22:3195)
 [79]
 C. H. Norris & J. B. Wilbur, Elementary Structural Analysis, 2nd ed., McGrawHill, New York, 1960.
 [80]
 J. E. Van Ness, "Convergence of iterative loadflow studies," Trans. AIEE, v. PAS79, 1960, part III, pp. 15901597.
 [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. PAS80, 1961, part III, pp. 299304.
 [83]
 F. H. Branin, Jr., DC and Transient Analysis of Networks Using a Digital Computer, IRE Internat. Conference Rec., part 2, 1962, pp. 236256.
 [84]
 H. E. Brown, G. K. Carter, H. H. Happ & C. E. Person, "Power flow solution by matrix iterative method," Trans. AIEE, v. PAS82, 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. PAS82, 1963, pp. 561564.
 [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 networktopological formulation of structural analysis," ASCE J. Structural Division, v. 89, 1963, pp. 483514.
 [88]
 S. J. Fenves, STRESS (Structural Engineering System Solver) A Computer Programming System for Structural Engineering Problems, M.I.T. Technical Report T632, 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. EM4, pp. 2129.
 [91]
 W. R. Spillers, "Applications of topology in structural analysis," Proc. ASCE J. Structural Division, v. 89, 1963, no. ST4, pp. 301313.
 [92]
 M. A. Laughton & M. W. H. Davies, "Numerical techniques in solution of powersystem loadflow problems," Proc. IEEE, v. 1ll, 1964, p. 1575.
 [93]
 W. R. Spillers, "Network techniques applied to structures," Matrix Tensor Quart., v. 15, 1964, pp. 3141.
 [94]
 R. Baumann, "Some new aspects on loadflow calculation: Iimpedance matrix generation controlled by network topologv," AIEE Trans., v. PAS85, 1966, pp. 11641176.
 [95]
 F. H. Branin, Jr., The AlgebraicTopological 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. 453491.
 [96]
 F. F. Kuo, "Network analysis by digital computer," Proc. IEEE, v. 54, 1966, pp. 820829.
 [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. 17871801.
 [99]
 G. H. Jensen, "Efficient matrix techniques applied to transmission tower design," Proc. IEEE, v. 55, 1967, pp. 19972000.
 [100]
 G. H. Jensen, Designing Selfsupporting Transmission Towers with the Digital Computer, PICA Conference, 1967, pp. 303319.
 [101]
 W. F. Tinney & C. E. Hart, "Power flow solution by Newton's method," Trans. AIEE, v. PAS86, 1967, pp. 14491460.
 [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. 343349.
 [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, McGrawHill, New York, 1967.
 [105]
 J. S. Przemieniecki, Theory of Matrix Structural Analysis, McGrawHill, 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. ElAbiad, Computer Methods in Power System Analysis, McGrawHill, New York, 1968.
 [108]
 N. Sato & W. F. Tinney, "Techniques for exploiting the sparsity of the network admittance matrix," Trans. AIEE, v. PAS82, 1963, pp. 944950.
 [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. 87109.
 [110]
 Å. Björck, "Solving linear least squares problems by GramSchmidt orthogonalization," Nordisk Tidskr. InformationsBehandling, v. 7, 1967, pp. 121. MR 35 #5126. MR 0214275 (35:5126)
 [111]
 T. S. Motzkin, The Assignment Problem, Proc. Sympos. Appl. Math., vol. 6, Amer. Math Soc., Providence, R. I., 1956, pp. 109125. MR 19, 822. MR 0090480 (19:822a)
 [112]
 J. Munkres, "Algorithms for the assignment and transportation problems," J. Soc. Indust. Appl. Math., v. 5, 1957, pp.3238. MR 19, 1244. MR 0093429 (19:1244f)
 [113]
 L. R. Ford, Jr. & D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, N. J., 1962. MR 28 #2917. MR 0159700 (28:2917)
 [114]
 A. Yaspan, "On finding a maximal assignment," Operations Res., v. 14, 1966, pp. 646651.
 [115]
 V. V. Klyuyev & N. I. KokovkinShcherbak, On the Minimization of the Number of Arithmetic Operations for the Solution of Linear Algebraic Systems, Stanford Comput. Sci. Report CS24, 1965.
 [116]
 S. Winograd, On the Number of Multiplications Necessary to Compute Certain Functions, IBM Watson Research Center, RC 2285, 1968.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65.35
Retrieve articles in all journals
with MSC:
65.35
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197002756438
PII:
S 00255718(1970)02756438
Keywords:
Sparse matrices,
elimination form of inverse,
product form of inverse,
fillin,
symbolic and numerical zeros,
minimal algorithms
Article copyright:
© Copyright 1970
American Mathematical Society
