The SAC-1 system: An introduction and survey

ABSTRACT

SAC-1 is a program system for performing operations on multivariate polynomials and rational functions with infinite-precision coefficients. It is programmed, with the exception of a few simple primitives, in ASA Fortran. As a result the system is extremely accessible, portable, easy to learn, and indeed has been implemented at more than 20 institutions. The SAC-1 system's range of programmed capabilities is exceptionally broad, including, besides the usual operations, polynomial greatest common divisor and resultant calculation, polynomial factorization, exact polynomial real zero calculation, partial fraction decomposition, rational function integration, and solution of systems of linear equations with polynomial coefficients. SAC-1 is also outstanding in its computing time efficiency, which is achieved partially through the use of appropriate data structures, but primarily through the use of mathematically sophisticated and analyzed algorithms, which are briefly surveyed. The efficiency gains, frequently orders of magnitude, are such that many new applications are rendered feasible.

REFERENCES

• 1: S. Gorn, FORTRAN vs. Basic FORTRAN: a programming language for informational processing on automatic data processing systems, Communications of the ACM, v.7 n.10, p.591-624, Oct. 1964 [doi>10.1145/364888.876694]
• 2: Bareiss, E. H., Sylvester's Identity and Multi-step Integer-Preserving Gaussian Elimination, Math. of Comp., Vol. 22, No. 103 (July 1968), pp. 565-578.
• 3: Berlekamp, E. R., Factoring Polynomials over Finite Fields, Bell System Tech. J., Vol. 46 (1967), pp. 1853-1859.
• 4: Berlekamp, E. R., Algebraic Coding Theory, McGraw-Hill, 1968
• 5: Brown, W. S., The ALPAK System for Non-numerical Algebra on a Digital Computer - I: Polynomials in Several Variables and Truncated Power Series with Polynomial Coefficients, Bell System Tech. J., Vol. 42, No. 3 (Sept. 1963), pp. 2081-2120.
• 6: Brown, W. S., The Compleat Euclidean Algorithm, Bell Telephone Laboratories Report, June 1968, 68 pages.
• 7: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 8: G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
• 9: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 10: Collins, George E., The SAC-1 List Processing System, University of Wisconsin Computing Center Technical Report, July 1967, 34 pages.
• 11: Collins, George E., and James R. Pinkert, The Revised SAC-1 Integer Arithmetic System, University of Wisconsin Computing Center Technical Report No. 9, Nov. 1968, 50 pages.
• 12: Collins, George E., The SAC-1 Polynomial System, University of Wisconsin Computing Center Technical Report No. 2, March 1968, 68 pages.
• 13: Collins, George E., The SAC-1 Rational Function System, University of Wisconsin Computing Center Technical Report No. 8, July 1968, 31 pages.
• 14: Collins, George E., Computing Multiplicative Inverses in GF(p), Math. Comp., Vol. 23, No. 105 (Jan. 1969), pp. 197-200.
• 15: Collins, George E., Algorithmic Approaches to Symbolic Integration and Simplification (Summary of the 1968 FJCC Panel Session), SIGSAM Bulletin, No. 12 (July 1968), pp. 5-16.
• 16: Collins, George E., L. E. Heindel, E. Horowitz, M. T. McClellan, and D. R. Musser, the SAC-1 Modular Arithmetic System, University of Wisconsin Technical Report No. 10, June 1969, 50 pages.
• 17: Collins, George E., Computing Time Analyses for Some Arithmetic and Algebraic Algorithms, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation (Robert G. Tobey, ed.), IBM Federal Systems Center, June 1969, pp. 195-232.
• 18: Collins, George E., and Ellis Horowitz, The SAC-1 Partial Fraction Decomposition and Rational Function Integration System, University of Wisconsin Computing Center Technical Report No. 12, Feb. 1970, 47 pages.
• 19: Collins, George E., and Lee E. Heindel, The SAC-1 Polynomial Real Zero System, University of Wisconsin Computing Center Technical Report No. 18, Aug. 1970.
• 20: George E. Collins, The calculation of multivariate polynomial resultants, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.212-222, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806289]
• 21: Collins, George E., The SAC-1 Polynomial Greatest Common Divisor and Resultant System. In preparation.
• 22: Collins, George E., and David R. Musser, The SAC-1 Polynomial Factorization System. In preparation.
• 23: Collins, George E., and Michael T. McClellan, The SAC-1 Polynomial Linear Algebra System. In preparation.
• 24: Hardy, G. H., The Integration of Functions of a Single Variable, seconded., Cambridge Univ. Press, 1916.
• 25: Lee Edward Heindel, Algorithms for exact polynomial root calculation, 1971
• 26: Peter Henrici, A Subroutine for Computations with Rational Numbers, Journal of the ACM (JACM), v.3 n.1, p.6-9, Jan. 1956 [doi>10.1145/320815.320818]
• 27: Horowitz, Ellis, Algorithms for Symbolic Integration of Rational Functions, Ph.D. Thesis, University of Wisconsin Computer Sciences Department, Nov. 1969, 132 pages.
• 28: Horowitz, Ellis, Algorithms for Partial Fraction Decomposition and Rational Function Integration, University of Wisconsin Computer Sciences Department Technical Report No. 91, June 1970, 44 pages.
• 29: Johnson, S. C., Tricks for Improving Kronecker's Polynomial Factoring Algorithm, Bell Telephone Laboratories Report, 1966.
• 30: Dale E. Jordan , Lewis C. Clapp , Richard Y. Kain, Symbolic factoring of polynomials in several variables, Communications of the ACM, v.9 n.8, p.638-643, Aug. 1966 [doi>10.1145/365758.365809]
• 31: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 32: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 33: Lipson, John D., Symbolic Methods for the Computer Solution of Linear Equations with Applications to Flowgraphs, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation (Robert G. Tobey, ed.), June 1969, IBM Federal Systems Center, pp. 233-303.
• 34: Manove, M., S. Bloom, and C. Engelman, Rational Functions in MATHLAB. In Bobrow, D. G. (Ed.), Symbol Manipulation Languages and Techniques, North Holland, Amsterdam, 1968, pp. 86-102.
• 35: McClellan, Michael T., Algorithms for the Exact Solution of Systems of Linear Equations with Polynomial Coefficients, University of Wisconsin Computer Sciences Department Ph.D. Thesis. In preparation.
• 36: David Rea Musser, Algorithms for polynomial factorization., 1971
• 37: Risch, Robert H., Symbolic Integration of Elementary Functions, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation (Robert G. Tobey, ed.), June 1969, IBM Federal Systems Center, pp. 133-147.
• 38: Tarski, A., A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951 (Second ed., rev.).
• 39: Tobey, Robert G., Algorithms for Anti-Differentiation of Rational Functions, Ph.D. Thesis, Harvard University, 1967.
• 40: Van der Waerden, B. L., Modern Algebra, Vol. I, Frederick Ungar Publishing Co., 1948.

INDEX TERMS

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.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)
      I.1.3 Languages and Systems

General Terms:
Algorithms, Languages, Theory