A cancellation free algorithm, with factoring capabilities, for the efficient solution of large sparse sets of equations

ABSTRACT

Symbolic solutions of large sparse systems of linear equations, such as those encountered in several engineering disciplines (electrical engineering, biology, chemical engineering etc.) are often very lengthy, and received for this reason only occasional attention. This places the designer of a new and probably more successful symbolic solution method for the hard problem to find a representation which is suitable in the corresponding engineering areas, while still being neat and compact. It is believed that this problem has been solved to a great deal with the introduction of the new Factoring Recursive Minor Expansion algorithm with Memo, FDSLEM, presented in this paper. The FDSLEM algorithm has important properties which make the implementation of an algorithm which can generate the approximate solution of a perturbed system of equations relatively straight forward. The algorithms given can operate on arbitrary sparse matrices, but one obtains optimal profit of the properties of the algorithm if the matrices have a certain fundamental form, as is illustrated in the paper.

REFERENCES

• 1: Hearn, A. C., An improved factored polynomial representation. Proc. Hawaii International Conf. on System Sciences, Honolulu (1977) 155.
• 2: W. S. Brown, On computing with factored rational expressions, ACM SIGSAM Bulletin, v.8 n.3, p.26-34, August 1974 [doi>10.1145/1086837.1086842]
• 3: Leibnitz, correspondence with de l'Hospital dated 28th of April 1693, published in: Leibnitzens Mathematische Schriften, herausgegeben von C.I. Gerhardt. 1. Abth. ii pp. 229, 238-240, 245. Berlin 1850.
• 4: Cramer, Introduction a l'Analyse des Lignes Courbes Algebriques. (pp. 59,60, 656-659) Geneve, 1750.
• 5: Bezout, Recherches sur le degree des equations resultantes de l'evanoussement des inconnues, et sur les moyens qu'il convient d'employer pour trouver ces equations. Hist. de l'Acad. Roy. des Sciences. Ann. 1764 (pp. 288-338), pp. 291-295.
• 6: Vandermonde, Memoire sur l'elimination. Hist. de l'Acad. Roy. des Sciences (Paris), Ann. 1772, 2e partie (pp. 516-532).
• 7: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 8: Bareiss E. H., Sylvesters identity and multistep integerpreserving Gaussian elimination. Math. Comput. 22, 103 (july 1968), pp. 565-578.
• 9: Lipson J., Symbolic methods for the computer solution of linear equations with applications to flowgraphs, Proceedings of the 1968 summer institute on symbolic mathematical computation, R. G. Tobey, editor.
• 10: Downs T., On the reduction and inversion of the nodal admittance matrix in rational form., IEEE Trans. CAS vol. CAS-21 Sept 1974, pp. 592-598.
• 11: E. Horowitz , S. Sahni, On Computing the Exact Determinant of Matrices with Polynomial Entries, Journal of the ACM (JACM), v.22 n.1, p.38-50, Jan. 1975 [doi>10.1145/321864.321868]
• 12: Tobey, R.G., Bobrow R.J., Zilles S., Automatic Simplification in FORMAC, Proc. of fall Joint computer conference, Spartan books vol. 27, nov. 1965.
• 13: Lin P. M. and Alderson G. E., "Computer generation of symbolic network functions - A new theory and implementation", IEEE Trans. Circuit Theory, Vol. C.T.-20, pp. 48-56, Jan 1973.
• 14: Singal K. and Vlach J., Symbolic analysis of analog and digital circuits. IEEE Trans. CAS vol. CAS-24 Nov. 1977, pp. 598-610.
• 15: J. Smit, New recursive minor expansion algorithms, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.74-87, June 01, 1979
• 16: Griss M. L., Efficient recursive minor expansion., Utah symbolic computation group, Report UCP-51, 1977.
• 17: Hulsegge E., The application of frequency matching for the synthesis of certain electrical networks. (in Dutch) THT report 1231-KV-0281/EL. Jan. 1981.
• 18: Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
• 19: J. A. van Hulzen, Breuer's grow factor algorithm in computer algebra, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.100-104, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806377]
• 20: Schilstra Y. G., Algorithms to minimize the representation of current and voltage law equations based on the introduction of new equations. (in Dutch) THT report 1231-KV-0181/EL. Jan. 1981.
• 21: Chua L. O. and Chen L., On optimally sparse cycle and coboundary basis for a linear graph, IEEE trans. on circ. Th., Vol. CT-20, No. 5, Sept 1973, pp. 495-503.
• 22: Herrero J.L. and Willoner G., Synthesis of Filters, Prentice-Hall, Englewood Clifs, New Yersey.
• 23: Smit J., An efficient factoring symbolic determinant expansion algorithm. THT report 1231-AM-O478/EL. Dec. 1978.
• 24: Smit J., A recursive tearing technique for systems in which small as well as large elementvalues are significant. THT Report 1231-AM-O378/EL. Dec. 1978.
• 25: Endy G. E. and Lin P. M., A minimization problem in systems characterized by loopless signal flowgraphs. 1980 IEEE intern. Symp. on Circ. and Syst. Proceedings, pp. 365-367.
• 26: Gentleman W. M. and Johnson S. C., The evaluation of determinants by expansion by minors and the general problem of substitution, Math. of comp., vol. 28, no. 126, april 1974, pp. 543-548.
• 27: Mielke R. R., A new signal flowgraph formulation of symbolic network functions. IEEE trans. circ. and syst., vol. CAS-25, pp. 334-340, june 1978.
• 28: Renkema G. H., Algorithms to minimize the representation of current and voltage law equations. (in Dutch) THT report 1231-BV-0879/EL.
• 29: Smit J., NETFORM users manual, THT report 1231-AM-0381/EL.
• 30: Hachtel G., Brayton R. K. and Gustavson F. G., The sparse tableau approach to network analysis and design, IEEE trans on circ. theory, Vol. CT-18, pp. 101-113, Jan 1971.
• 31: Smit J., Sparse Kirchhoff equations, an effective support tool for the numeric and symbolic solution of large sparse systems of network equations. THT report 1231-AM-O681/EL Jan 1981.
• 32: Martin L. Griss, An efficient sparse minor expansion algorithm, Proceedings of the annual conference, p.429-434, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805633]
• 33: Sedra A. and Smith K. C., A second generation current conveyor and its applications. IEEE Trans. on Circ. Theory, Vol. CT-17, 1970, pp. 132-134.
• 34: Bel N., A high presision monolitic current follower. Electronic circuits and systems, Jan. 1977, Vol. 1, No. 2, pp. 79-84.
• 35: Jager W. de, and Smit J., Application, design and symbolic analysis of a current follower, Electronic circuits and systems, Jan. 1977, Vol. 1, no. 2, pp. 79-84.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory