PROCEEDINGS OF THE IEEE, VOL. 55, NO. 11, NOVEMBER 1967 1801 algebraic systems” (translated by G. J. Tee), Computer Science Dept., Stanford University, Stanford, Calif., Tech. Rept. CS24, 1965. [291 N. Sato and W. F. Tinney, “Techniques for exploiting the sparsity of the network admittance matrix,’’ IEEE Trans. Power and Apparatus, vol. 82, pp. 944-950, December 1963. I3O1 W. F. Tinney and J. W. Walker, “Direct solutions of sparse net- work equations by optimally ordered triangular factorization,” this issue, p. 1801. S. Parter, “The use of linear graphs in gauss elimination,” SIAM Rev., vol. 3, pp. 119-130, April 1961. [321 D. Bree, Jr., “Some remarks on the application of graph theory to the solution of sparse systems of linear equations,” thesis, Dept. of Math., Princeton University, Princeton, N. J., May 1965. ‘’’I A. Orden, “Matrix inversion and related topics by direct methods,” in Mathematical Methods for Digital Computers, A. Ralston and H. S. Wilf, Eds. New York: Wiley, 1960, ch. 2. [341 F. B. Hildebrand, Introduction to Numerical Analysis. New York: McGraw-Hill, 1956. 1351 C. G. Broyden, “A class of methods for solving nonlinear simul- taneous equations,” Math. Comp., vol. 19, pp. 577-593, October 1965. [361 F. H. Branin, Jr., and H. H. Wan& “A fast reliable iteration method for dc analysis of nonlinear networks,” this issue, p. 1819. t371 J. Katzenelson, “An algorithm for solving nonlinear resistive net- works,” Bell Sys. Tech. J., vol. 44, pp. 1605-1620, November 1965. l3*1 J. G. F. Francis, “The Q-R transformation, pt. 1,” Cornpurer J., vol. 4, pp. 265-271, October, 1961; “The Q-R transformation, pt. 11,” Computer J., vol. 4, pp. 332-345, January 1962. [391 M. L. Liou, “A numerical solution oflinear time-invariant systems,” Proc. 3rd Allerton Conf: on Circuit and System Theory, pp. 669-676, 1965. I4O1 R. W. Stineman, “Digital timedomain analysis of systems with widely’separated poles,” J. Assoc. Comp. Mach., vol. 12, pp. 286-293, April 1965. I4l1 P. I. Richards, W. D. Lanning, and M. D. Torrey, “Numerical integration of large, highlydamped, nonlinear systems,” SIAM Rev.. vol. 7, pp. 376380, July 1965. [421 C. E. Treanor, “A method for the numerical integration of coupled first-order differential equations with greatly different time con- stants,” Math. Comp., vol. 20, pp. 3945, January 1966. ‘431 E. R. Cohen, “Some topics in reactor kinetics,” Proc. 2nd UN Internat’l Con$ on Peaceful Uses of Atomic Energy (Geneva, Switzerland), [441 E. R. Cohen and H. P. Flatt. “Numerical solution of quasi-linear equations,” Proc. Seminar on Codes for Reactor Computations (Vienna, Austria), pp. 461484, 1960. 14’] J. Certaine, “The solution of ordinary differential equations with large time constants,” in Mathematical Methods for Digital Computers, A. Ralston and H. S. Wilf, Eds. New York: Wiley, 1960, ch. 11. [461 J. Katzenelson, “AEDNET: a simulator tor nonlinear networks,” Proc. IEEE, vol. 54, pp. 15361552, November 1966. [471 G. N. Polozhii, The Method of Summary Representation for Numerical Solution of Problems of Mathematical Physics. New York: Pergamon, 1965. 1481 System Analysis by Digital Computer, F. F. Kuo and J. F. Kaiser, Eds. New York: Wiley, 1966. 1491 G. C. Temes and D. A. Calahan,” Computer-aided network optimization-The state-of-the-art,” this issue, p. 1832. G. D. Hachtel and R. A. Rehrer, “Techniques for the optimal design and synthesis of switching circuits,” this issue, p. 1864. VOI. 11, pp. 302-309, 1958. Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization WILLIAM F. TINNEY, SENIOR MEMBER, IEEE, AND JOHN W. WALKER, MEMBER, IEEE I. INTRODUCTION SUALLY, the objective in the matrix analysis of networks is to obtain the inverse of the matrix of coefficients of a system of simultaneous linear net- work equations. However, for large sparse systems such as occur in many network problems, the use of the inverse is Manuscript received February 10, 1967; revised August 9, 1967. The unrevised version of this paper was published in the Power Industry Computer Applicatwnr Con$ Rec., pp. 367-376,1967. This conference was sponsored by the IEEE Power Group. The authors are with the Bonneville Power Administration, Portland, Ore. very inefficient. In general, the matrix of the equations formed from the given conditions of a network problem is sparse, whereas its inverse is full. By means of an appro- priately ordered triangular decomposition, the inverse of a sparse matrix can be expressed as a product of sparse matrix factors, thereby gaining an advantage in computational speed, storage, and reduction of round-off error. The method consists of two parts : 1) a scheme of record- ing the operations of triangular decomposition of a matrix such that repeated direct solutions based on the matrix can be obtained without repeating the triangularization, and 2) a scheme of ordering the operations that tends to con- serve the sparsity of the original system. The first part of the method is not altogether new, but its computational possibilities are not widely recognized. The second part appears to be of recent origin, but it is probably only a rediscovery. Either part of the method can be applied in- dependently, but the greatest benefit is obtained from the combined application of both parts. The first part of the method is applicable to any matrix. Application of the second part, ordering to conserve sparsity, is limited to sparse matrices in which the pattern of nonzero elements is symmetric and for which an arbitrary Authorized licensed use limited to: Iowa State University. Downloaded on September 4, 2009 at 14:41 from IEEE Xplore. Restrictions apply.1802 order of decomposition does not adversely affect numerical accuracy. Such matrices are usually characterized by a strong diagonal, and ordering to conserve sparsity in- creases the accuracy of the decomposition. A large class of network problems fulfills this condition. Generally it is not worth considering optimal ordering unless at least 80 percent of the matrix elements are zero. At least three have been written on various aspects of optimally ordered triangular