More Web Proxy on the site http://driver.im/

Article

Free access

The SAC-1 system: An introduction and survey

Author:

George E. CollinsAuthors Info & Claims

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

Pages 144 - 152

https://doi.org/10.1145/800204.806279

Published: 23 March 1971 Publication History

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]

American Standards Association, A Programming Language for Information Processing on Automatic Data Processing Systems, Comm. A.C.M., Vol. 7, No. 10 (Oct. 1964), pp. 591-625.]]

Digital Library

[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]

Collins, George E., A Method for the Overlapping and Erasure of Lists, Comm. A.C.M., Vol. 3, No. 12 (Dec. 1960), pp. 655-657.]]

Digital Library

[8]

Collins, George E., PM, A System for Polynomial Manipulation, Comm. A.C.M., Vol. 9, No. 8 (Aug. 1966), pp. 578-589.]]

Digital Library

[9]

Collins, George E., Subresultants and Reduced Polynomial Remainder Sequences, Jour. A.C.M., Vol. 14, No. 1 (Jan. 1967), pp. 128-142.]]

Digital Library

[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.]]

Digital Library

[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]

Collins, George E., The Calculation of Multivariate Polynomial Resultants, Proc. of the Second Symposium on Symbolic and Algebraic Manipulation, Los Angeles, March 1971.]]

Digital Library

[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]

Heindel, Lee E., Algorithms for Exact Polynomial Root Calculation, Ph.D. Thesis, University of Wisconsin Computer Sciences Department, July 1970, 153 pages.]]

Digital Library

[26]

Henrici, P., A Subroutine for Computations with Rational Numbers, Jour. A.C.M., Vol. 3, No. 1 (Jan. 1956), pp. 6-9.]]

Digital Library

[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]

Jordan, D. E., R. Y. Cain, and L. C. Clapp, Symbolic Factoring of Polynomials in Several Variables, Comm. A.C.M., Vol. 9, No. 8 (Aug. 1966), pp. 638-643.]]

Digital Library

[31]

Knuth, D. E., The Art of Computer Programming, Vol. 1 (Fundamental Algorithms), Addison-Wesley, 1968.]]

Digital Library

[32]

Knuth, D. E., The Art of Computer Programming, Vol. 2 (Seminumerical Algorithms), Addison-Wesley, 1969.]]

Digital Library

[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]

Musser, David R., Algorithms for Polynomial Factorization, University of Wisconsin Computer Sciences Department Ph.D. Thesis. In preparation.]]

Digital Library

[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.]]

Cited By

Ábrahám EAbbott JBecker BBigatti ABrain MBuchberger BCimatti ADavenport JEngland MFontaine PForrest SGriggio AKroening DSeiler WSturm T(2016)$$\mathsf {SC}^\mathsf{2} $$ : Satisfiability Checking Meets Symbolic ComputationIntelligent Computer Mathematics10.1007/978-3-319-42547-4_3(28-43)Online publication date: 12-Jul-2016
https://doi.org/10.1007/978-3-319-42547-4_3
Roda G(2010)Connecting the dotsACM SIGIR Forum10.1145/1842890.184290344:1(82-86)Online publication date: 18-Aug-2010
https://dl.acm.org/doi/10.1145/1842890.1842903
Ramesh RRamakrishnan I(2005)Optimal speedups for parallel pattern matching in treesRewriting Techniques and Applications10.1007/3-540-17220-3_23(274-285)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-17220-3_23
Show More Cited By

Index Terms

The SAC-1 system: An introduction and survey
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Computer algebra systems
    2. Representation of mathematical objects
      1. Representation of polynomials
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations

Recommendations

Computing real zeros of polynomials with SAC-1

SAC-1 contains a subsystem for computing real zeros of univariate polynomials over the integers. Here we present an engineering approach to the improvement of this subsystem. We will show that a considerable amount of computing time can be saved by ...
On the system xn+ 1=ynx n-k/(yn-k +1(an+ bnynxn-k)), yn+1=xnyn-k/(xn-k+1(cn+dnxnyn-k))

It is shown that the system of difference equationsx"n"+"1=y"nx"n"-"ky"n"-"k"+"1(a"n+b"ny"nx"n"-"k),y"n"+"1=x"ny"n"-"kx"n"-"k"+"1(c"n+d"nx"ny"n"-"k),n@?N"0,where k@?N, the sequences a"n,b"n,c"n,d"n, n@?N"0, and the initial values x"-"i,y"-"i, i=0,k@? ...
On xq+1+ax+ b

We study the polynomial f(x)=x^q^+^1+ax+b over an arbitrary field F of characteristic p, where q is a power of p and ab<>0. The polynomial has arisen recently in several different contexts, including the inverse Galois problem, difference sets, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

March 1971

464 pages

ISBN:9781450377867

DOI:10.1145/800204

Copyright © 1971 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGNUM: ACM Special Interest Group on Numerical Mathematics
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIAM: Society for Industrial and Applied Mathematics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 1971

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
112
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)15

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ábrahám EAbbott JBecker BBigatti ABrain MBuchberger BCimatti ADavenport JEngland MFontaine PForrest SGriggio AKroening DSeiler WSturm T(2016)$$\mathsf {SC}^\mathsf{2} $$ : Satisfiability Checking Meets Symbolic ComputationIntelligent Computer Mathematics10.1007/978-3-319-42547-4_3(28-43)Online publication date: 12-Jul-2016
https://doi.org/10.1007/978-3-319-42547-4_3
Roda G(2010)Connecting the dotsACM SIGIR Forum10.1145/1842890.184290344:1(82-86)Online publication date: 18-Aug-2010
https://dl.acm.org/doi/10.1145/1842890.1842903
Ramesh RRamakrishnan I(2005)Optimal speedups for parallel pattern matching in treesRewriting Techniques and Applications10.1007/3-540-17220-3_23(274-285)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-17220-3_23
Watt SBroadbery PDooley SIglio PMorrison SSteinbach JSutor RMacCallum M(1994)A first report on the A# compilerProceedings of the international symposium on Symbolic and algebraic computation10.1145/190347.190356(25-31)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.1145/190347.190356
Abdali SCherry GSoiffer N(1986)A Smalltalk system for algebraic manipulationACM SIGPLAN Notices10.1145/960112.2872421:11(277-283)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.1145/960112.28724
Abdali SCherry GSoiffer N(1986)A Smalltalk system for algebraic manipulationConference proceedings on Object-oriented programming systems, languages and applications10.1145/28697.28724(277-283)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.1145/28697.28724
Raidy T(1985)Past, Present, and Future Applications of Computer Algebra in ChemistryApplications of Computer Algebra10.1007/978-1-4684-6888-5_5(112-118)Online publication date: 1985
https://doi.org/10.1007/978-1-4684-6888-5_5
Münzel GRenner G(1983)Zur Charakterisierung und Berechnung von symmetrischen KubaturformelnOn the characterization and computation of symmetric cubature formulaeComputing10.1007/BF0226343231:3(211-230)Online publication date: Sep-1983
https://doi.org/10.1007/BF02263432
Billard B(1981)Polynomial manipulation with APLCommunications of the ACM10.1145/358699.35871624:7(457-465)Online publication date: 1-Jul-1981
https://dl.acm.org/doi/10.1145/358699.358716
Andrews P(1981)Theorem Proving via General MatingsJournal of the ACM10.1145/322248.32224928:2(193-214)Online publication date: 1-Apr-1981
https://dl.acm.org/doi/10.1145/322248.322249
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents