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

Article

Free access

The calculation of multivariate polynomial resultants

Author:

George E. CollinsAuthors Info & Claims

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

Pages 212 - 222

https://doi.org/10.1145/800204.806289

Published: 23 March 1971 Publication History

Abstract

An efficient algorithm is presented for the exact calculation of resultants of multivariate polynomials with integer coefficients. The algorithm applies modular homomorphisms and the Chinese remainder theorem, evaluation homomorphisms and interpolation, in reducing the problem to resultant calculation for univariate polynomials over GF(p), whereupon a polynomial remainder sequence algorithm is used.

The computing time of the algorithm is analyzed theoretically as a function of the degrees and coefficient sizes of its inputs . As a very special case, it is shown that when all degrees are equal and the coefficient size is fixed, its computing time is approximately proportional to λ^2r+l, where λ is the common degree and r is the number of variables .

Empirically observed computing times of the algorithm are tabulated for a large number of examples, and other algorithms are compared. Potential application of the algorithm to the solution of systems of polynomial equations is briefly discussed.

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]

Bodewig, E., Matrix Calculus, North Holla Holland Publ. Co., 1959.

[3]

Brown, W. S ., The Compleat Euclidean Algorithm, Bell Telephone Laboratories Report, June 1968, 68 pages.

[4]

Butcher, J. C ., On Runge-Kutta Processes of High Order, J. Australian Math. Soc., Vol. 4 (1964), pp. 179-194.

[5]

Ceschino, F ., and J. Kuntzmann, Numerical Solution of Initial Value Problems, pp. 72-74, Prentice-Hall, 1966.

[6]

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

Digital Library

[7]

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

Digital Library

[8]

Collins, George E ., The SAC-1 Polynomial System, Univ. of Wisconsin Computing Center Technical Report No. 2, March 1968, 68 pages.

[9]

Collins, George E., L. E. Heindel, E. Horowitz, M. T. McClellan, and D. R. Musser, The SAC-1 Modular Arithmetic System, Univ. of Wisconsin Technical Report No. 10, June 1969, 50 pages.

[10]

Collins, George E ., Comment on a Paper by Ku and Adler (Letter to the Editor), Comm. A.C.M., Vol. 12, No. 6 (June 1969), p. 302.

Digital Library

[11]

Collins, George E., The SAC-1 Polynomial G.C.D. and Resultant System. In preparation.

[12]

Collins, George E., The SAC-I System: An Introduction and Survey, Proc. Second Symposium on Symbolic and Algebraic Manipulation, Los Angeles, March 1971.

Digital Library

[13]

Heindel, Lee E ., Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Proc. Second Symposium on Symbolic and Algebraic Manipulation, Los Angeles, March 1971.

Digital Library

[14]

Jacobson, Nathan, Lectures in Abstract Algebra, Vol. III (Theory of Fields and Galois Theory), Van Nostrand, 1964.

[15]

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

Digital Library

[16]

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

Digital Library

[17]

Ku, S. Y., and R. J. Adler, Algebra-Based Methods for Solving Multivariate Polynomial Equations, Chemical Engineering Science Division Report No. 10-22-68, Case Western Reserve Univ ., 162 pages.

[18]

Ku, S. Y., and R. J. Adler, Computing Polynomial Resultants: Bezout's Determinant vs . Collins ' Reduced P. R.S. Algorithm, Comm. A. C. M., Vol. 12, No. 1 (Jan. 1969), pp. 23-30.

Digital Library

[19]

McClellan, Michael T ., Algorithms for Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Ph.D. Thesis, Computer Sciences Dept., Univ. of Wis. In preparation.

[20]

Moses, Joel, Solution of Systems of Polynomial Equations by Elimination, Comm. A.C.M., Vol. 9, No. 8 (Aug. 1966), pp. 634-637.

Digital Library

[21]

Musser, David R., Algorithms for Polynomial Factorization, Ph.D. Thesis, Computer Sciences Dept., Univ. of Wis. In preparation .

Digital Library

[22]

Takahasi, H ., and Y. Ishibashi, A New Method for Exact Calculation by Computer, Information Processing in Japan, Vol. 1 (1961), pp. 28-42.

[23]

Van der Waerden, B. L ., Modern Algebra, Vol. 1, Ungar Publ. Co ., 1948.

Cited By

Jin CGu KNiculescu SBoussaada I(2018)Stability Analysis of Systems With Delay-Dependent Coefficients: An OverviewIEEE Access10.1109/ACCESS.2018.28288716(27392-27407)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2828871
Simpson MYi QKalita J(2016)Automatic Algorithm Selection in Computational Software Using Machine Learning2016 15th IEEE International Conference on Machine Learning and Applications (ICMLA)10.1109/ICMLA.2016.0064(355-360)Online publication date: Dec-2016
https://doi.org/10.1109/ICMLA.2016.0064
(2013)Exact symbolic-numeric computation of planar algebraic curvesTheoretical Computer Science10.1016/j.tcs.2013.04.014491:C(1-32)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1016/j.tcs.2013.04.014
Show More Cited By

Index Terms

The calculation of multivariate polynomial resultants
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm

Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation ...
Multivariate resultants in Bernstein basis
ADG'08: Proceedings of the 7th international conference on Automated deduction in geometry

Macaulay and Dixon resultant formulations are proposed for parametrized multivariate polynomial systems represented in Bernstein basis. It is proved that the Macaulay resultant for a polynomial system in Bernstein basis vanishes for the total degree ...
Exact resultants for corner-cut unmixed multivariate polynomial systems using the Dixon formulation
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)

Structural conditions on the support of a multivariate polynomial system are developed for which the Dixon-based resultant methods compute exact resultants. The concepts of a corner-cut support and almost corner-cut support of an unmixed polynomial ...

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

14
Total Citations
View Citations
145
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jin CGu KNiculescu SBoussaada I(2018)Stability Analysis of Systems With Delay-Dependent Coefficients: An OverviewIEEE Access10.1109/ACCESS.2018.28288716(27392-27407)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2828871
Simpson MYi QKalita J(2016)Automatic Algorithm Selection in Computational Software Using Machine Learning2016 15th IEEE International Conference on Machine Learning and Applications (ICMLA)10.1109/ICMLA.2016.0064(355-360)Online publication date: Dec-2016
https://doi.org/10.1109/ICMLA.2016.0064
(2013)Exact symbolic-numeric computation of planar algebraic curvesTheoretical Computer Science10.1016/j.tcs.2013.04.014491:C(1-32)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1016/j.tcs.2013.04.014
Berberich EEmeliyanenko PKobel ASagraloff MKotsireas I(2012)Arrangement computation for planar algebraic curvesProceedings of the 2011 International Workshop on Symbolic-Numeric Computation10.1145/2331684.2331698(88-98)Online publication date: 7-Jun-2012
https://dl.acm.org/doi/10.1145/2331684.2331698
Emeliyanenko P(2010)A complete modular resultant algorithm targeted for realization on graphics hardwareProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837219(35-43)Online publication date: 21-Jul-2010
https://dl.acm.org/doi/10.1145/1837210.1837219
Stussak CSchenzel P(2010)Parallel computation of bivariate polynomial resultants on graphics processing unitsProceedings of the 10th international conference on Applied Parallel and Scientific Computing - Volume 210.1007/978-3-642-28145-7_8(78-87)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-28145-7_8
Emeliyanenko P(2010)Modular resultant algorithm for graphics processorsProceedings of the 10th international conference on Algorithms and Architectures for Parallel Processing - Volume Part I10.1007/978-3-642-13119-6_37(427-440)Online publication date: 21-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13119-6_37
Yeh RGood DMusser D(1973)New directions in teaching the fundamentals of computer science — discrete structures and computational analysisACM SIGCSE Bulletin10.1145/953053.8080805:1(60-67)Online publication date: 1-Jan-1973
https://dl.acm.org/doi/10.1145/953053.808080
Yeh RGood DMusser D(1973)New directions in teaching the fundamentals of computer science — discrete structures and computational analysisProceedings of the third SIGCSE technical symposium on Computer science education10.1145/800010.808080(60-67)Online publication date: 1-Jan-1973
https://dl.acm.org/doi/10.1145/800010.808080
Horowitz ESammet JTobey RMoses J(1971)Modular arithmetic and finite field theoryProceedings of the second ACM symposium on Symbolic and algebraic manipulation10.1145/800204.806287(188-194)Online publication date: 23-Mar-1971
https://dl.acm.org/doi/10.1145/800204.806287
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