Breuer's grow factor algorithm in computer algebra

ABSTRACT

Computer algebra can be of importance in solving electrical network synthesis problems. It enables to generate automatically FORTRAN-programs needed to solve the underlying systems of nonlinear multivariate polynomial equations. Such systems are obtained by equating the numerical target function and a symbolically computed equivalent. Breuer's grow factor algorithm is extended not only to eventually improve the result of required determinant calculations, but also to optimize FORTRAN-code describing the system and the associated Jacobian. It is indicated how this common subexpression search approach can be extended.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: 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]
• 4: D.A. Calahan, Computer design of linear frequency selective networks, Proceedings of the IEEE, vol. 53 no. 11 (November 1965), pp. 1701-1706.
• 5: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 6: H. Eisenpress and A. Bomberault, Efficient symbolic differentiation using PL/I-FORMAC, IBM New York, SC Report no. 320-2956 (September 1968).
• 7: M.L. Griss, The output of large expressions in Reduce, Utah Computational Physics Group, Operational Note no. 14 (May 1974).
• 8: A.C. Hearn, The problem of substitution, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation (R.G. Tobey, editor), IBM Boston Programming Center, Cambridge Mass (June 1969), pp. 3-20.
• 9: Anthony C. Hearn, REDUCE 2: A system and language for algebraic manipulation, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.128-133, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806277]
• 10: B.J.A. Hulshof, Code optimization in NETFORM, BSC Thesis (in Dutch), Twente University of Technology, in preparation.
• 11: Gershon Kedem, Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.150-165, June 1980 [doi>10.1145/355887.355890]
• 12: D.E. Knuth, An empirical study of Fortran programs, Software Practice and Experience Vol. 1 (1971), pp. 105-133.
• 13: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 14: Edward W. Ng, Symbolic-Numeric Interface: a review (in absentia), Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.330-345, June 01, 1979
• 15: E. Ng and B. Char, Gradient and Jacobian computation for numerical applications, Proceeding 1979 MACSYMA Users' Conference (V.E. Lewis, editor), M.I.T., Cambridge Mass (June 1979), pp. 604-621.
• 16: J. Smit, NETFORM manual (second edition), Twente University of Technology (Jan. 1981).
• 17: J. Smit, A cancellation free algorithm, with factoring capabilities, for the efficient solution of large sparse sets of equations, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.146-154, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806386]
• 18: J. Smit, Sparse Kirchhoff equations, an effective support tool for the numeric and symbolic solution of large sparse tableau based systems, THT/EL Report 1231-AM 0581 (Jan. 1981).
• 19: David R. Stoutemyer, Automatic Error Analysis Using Computer Algebraic Manipulation, ACM Transactions on Mathematical Software (TOMS), v.3 n.1, p.26-43, March 1977 [doi>10.1145/355719.355721]
• 20: R. G. Tobey, Experience with FORMAC algorithm design, Communications of the ACM, v.9 n.8, p.589-597, Aug. 1966 [doi>10.1145/365758.365773]
• 21: J. A. van Hulzen, Solving systems of polynomial equations with floating-point coefficients, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.346-357, June 01, 1979
• 22: J.A. van Hulzen, Breuer's grow factor algorithm in computer algebra, Memorandum No. 332, Department of Applied Mathematics, Twente University of Technology (april 1981).
• 23: D.D. Warner, A partial derivative generator, Bell Labs, Computing Science Technical Report # 28 (April 1975).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN
      D.3.4 Processors
          Subjects: Parsing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Languages, Theory