Article

Free access

Solving systems of nonlinear polynomial equations faster

Authors:

J. F. Canny,

E. Kaltofen,

L. YagatiAuthors Info & Claims

ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation

Pages 121 - 128

https://doi.org/10.1145/74540.74556

Published: 17 July 1989 Publication History

PDF eReader

References

[1]

AGNARSSON, S., KANDRI-RODY, A., KAPVR, D., NARENDRAN, P., and SAUNt)rFtS, B. D., "Complexity of testing whether a polynomial ideal is nontrivial,' Proc. 1984 MACSYMA Users' ConE, pp. 452- 458 (1984).

Google Scholar

[2]

AHo, A., HOPCi~OFT, J., and ULLMAN, J., The Design and Analysis of Algorithms; Addison and Wesley, Reading, MA, 1974.

Digital Library

Google Scholar

[3]

BAjAJ, C., GnRRITY, T., and WARREN, J., "On the applications of multi-equational resultants," Tech. Report CSD-TR-826, Comput. Sci. Dept., Purdue University, November 1988.

Google Scholar

[4]

BAUR, W. and STRASSEN, V., "The complexity of partial derivatives," Theoretical Comp. Sci. 22, pp. 317- 330 (~983).

Crossref

Google Scholar

[5]

BEN-OR, M and TIWARI, P., "A deterministic algorithm for sparse multivariate polynomial interpoltion,' Proc. 20th Annual ACM Syrup. Theory Comp., pp. 301-309 (1988).

Digital Library

Google Scholar

[6]

BR~.~T, R. P., GUSTAVSOS, F. G., and YVN, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).

Crossref

Google Scholar

[7]

BROWN, W. S. and TaAUB, J. F., "On Euclid's algorithm and the theory of subresultants," J. ACM 18, pp. 505-514 (1971).

Digital Library

Google Scholar

[8]

BUCtqBERCER, B., "GrSbner bases: An algorithmic method in polynomial ideal theory," in Recent Trends in Multidimensional Systems Theory, edited by N. K. Bose; D. Reidel Publ. Comp., Dordrecht (Holland), pp. 184-2321985.

Google Scholar

[9]

CA~;mLtA, L., GALLIaO, A., and HEINTZ, J., "Some new effectivity bounds in Computational Geometry," Proc. AAECC-6, Springer Leer. Notes in Comp. Sci., to appear (1988).

Google Scholar

[10]

CAN~Y, J., "Some algebraic and geometric computa. tions in P-space,' Proc. 20th Annual A CM Syrup. Theory Comp., pp. 460-467 (1988a).

Digital Library

Google Scholar

[11]

CANNY, J., "Generalized characteristic polynomials," Proc. ISSAC '88, Springer Lect. Notes Comput. Sci., to appear (1988b).

Digital Library

Google Scholar

[12]

CANNY, J., The Complexity of Robot Motion Planning;, ACM Ph.D. Thesis Award 1987; MIT Press, Cambridge, MA, 1988c.

Digital Library

Google Scholar

[13]

DREXLEa, F. J., "Eine Methode zur Berechnung s~imtlicher L'6sungen yon Polynomgleichungssystemen," Numer. Math. 29, pp. 45-58 (1977). (In Germall.)

Digital Library

Google Scholar

[14]

GARCIA, C. B. and ZANGWILL, W. I., "Finding all solutions to polynomial systems and other systems of equations," Math. Program. 16, pp. 159-176 (1979).

Crossref

Google Scholar

[15]

GPdaORYEV, D. Yu. and CHISTOV, A. L., "Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations," Soviet Math. Dokl. (AMS Translation)29, pp. 380-383 (1984).

Google Scholar

[16]

KALTOFEN, E. and LAKSHMAN, YAGATI, "Improved sparse multivariate polynomial interpolation algorithms," Proc. ISSAC '88, Springer Lect. Notes Comput. Sci., to appear (1988).

Digital Library

Google Scholar

[17]

KALTOFEN, E. and TRAGE~, B., "Computing with polynomials given by black boxes for their evalua. tions: Greatest common divisors, factorization, separation of numerators and denominators," Proc. 29th Annum Syrup. Foundations of Comp. Sci., pp. 296- 305 (1988).

Google Scholar

[18]

KNVTH, D. E., The Art of Programrrdng, wol. 2, Semi- Numerical Algorithms, ed. 2; Addison Wesley, Reading, MA, 1981.

Digital Library

Google Scholar

[19]

LAZArtD, D., "Resolution des systemes d'equation algebriques," Theoretical Comput. Sci. 15, pp. 77-110 (1981). (In French).

Crossref

Google Scholar

[20]

LI, T.-Y., SAOEP, T., and YORKE, J. A., "Numerically determining solutions of systems of polynomial equations," AMS Bulletin 18/2, pp. 173-177 (1988).

Crossref

Google Scholar

[21]

MACAULAY, F. S., "Algebraic theory of modular systerns," Cambridge Tracts 19, Cambridge, 1916.

Google Scholar

[22]

RENAGAI~, J., "On the efficiency of Newton's method for approximating all zeros of a system of polynomials,' Math. Op. Res. 1/12, pp. 121-148 (1987a).

Digital Library

Google Scholar

[23]

RENAGAR, J., "On the worst case arithmetic complexity of approximating zeros of systems of polynomials," Tech. Rep. 748, School of OR, Cornell Univ., 1987b.

Google Scholar

[24]

SCHWARTZ, J. T., "Fast probabilistic algorithms for verification of polynomial identities," J. ACM 27, pp. zo 17 980).

Digital Library

Google Scholar

[25]

SCHSNHAaE, A., "Schnelle Multiplikation yon Polynomen ilber K5rpern der Charakteristik 2," Acta Inf. 7, pp. 395-398 (1977). (In German).

Digital Library

Google Scholar

[26]

VAN DER WAERDEN, $. L., Modern Algebra; F. Ungar Publ. Co., New York, 1953.

Google Scholar

[27]

WIEDEMANN, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54- 62 (1986).

Digital Library

Google Scholar

[28]

ZWPEL, R. E., "Interpolating polynomials from their values," J. Symbolic Comput., to appear (1990).

Digital Library

Google Scholar

[29]

ZULEHNER, W., "A simple homotopy method for determining all isolated solutions to polynomial systems," Math. Comp. 50/181, pp. 167-177 (1988).

Crossref

Google Scholar

Cited By

View all

Gaillard LSafey El Din M(2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669718
Colotti AFontán JGoldsztejn ABriot SChaumette FKermorgant ODin M(2024)Determination of All Stable and Unstable Equilibria for Image-Point-Based Visual ServoingIEEE Transactions on Robotics10.1109/TRO.2024.342205040(3406-3424)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3422050
van der Hoeven JLecerf G(2024)Fast interpolation of multivariate polynomials with sparse exponentsJournal of Complexity10.1016/j.jco.2024.101922(101922)Online publication date: Dec-2024
https://doi.org/10.1016/j.jco.2024.101922
Show More Cited By

Index Terms

Solving systems of nonlinear polynomial equations faster
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on polynomials
      2. Interpolation

Recommendations

Convergence analysis of modified Newton-HSS method for solving systems of nonlinear equations

Hermitian and skew-Hermitian splitting(HSS) method has been proved quite successfully in solving large sparse non-Hermitian positive definite systems of linear equations. Recently, by making use of HSS method as inner iteration, Newton-HSS method for ...
Solving rank-deficient separable nonlinear equations

Separable nonlinear equations have the form A(y)z+b(y)=0 where the matrix A(y) and the vector b(y) are continuously differentiable functions of y@?R^n. Such equations can be reduced to solving a smaller system of nonlinear equations in y alone. We ...
Chebyshev polynomial solutions of systems of linear integral equations

A Chebyshev collocation method has been presented to solve systems of linear integral equations in terms of Chebyshev polynomials. This method transforms the integral system into the matrix equation with the help of Chebyshev collocation points and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation

July 1989

399 pages

ISBN:0897913256

DOI:10.1145/74540

Editor:
G. H. Gonnet
Univ. of Waterloo, Waterloo, Ont., Canada

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 July 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC89

Sponsor:

SIGSAM

ISSAC89: Intl Symposium on Symbolic & Algebraic Computation

July 17 - 19, 1989

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,730
Total Downloads

Downloads (Last 12 months)235
Downloads (Last 6 weeks)26

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gaillard LSafey El Din M(2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669718
Colotti AFontán JGoldsztejn ABriot SChaumette FKermorgant ODin M(2024)Determination of All Stable and Unstable Equilibria for Image-Point-Based Visual ServoingIEEE Transactions on Robotics10.1109/TRO.2024.342205040(3406-3424)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3422050
van der Hoeven JLecerf G(2024)Fast interpolation of multivariate polynomials with sparse exponentsJournal of Complexity10.1016/j.jco.2024.101922(101922)Online publication date: Dec-2024
https://doi.org/10.1016/j.jco.2024.101922
Schost ÉSt-Pierre C(2024)Newton iteration for lexicographic Gröbner bases in two variablesJournal of Algebra10.1016/j.jalgebra.2024.04.018Online publication date: Apr-2024
https://doi.org/10.1016/j.jalgebra.2024.04.018
van der Hoeven JLecerf G(2024)Sparse polynomial interpolation: faster strategies over finite fieldsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-024-00655-5Online publication date: 27-Apr-2024
https://doi.org/10.1007/s00200-024-00655-5
Faugère JLabahn GSafey El Din MSchost ÉVu T(2023)Computing critical points for invariant algebraic systemsJournal of Symbolic Computation10.1016/j.jsc.2022.10.002116(365-399)Online publication date: May-2023
https://doi.org/10.1016/j.jsc.2022.10.002
van der Hoeven JMaza MZhi L(2022)On the Complexity of Symbolic ComputationProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535493(3-12)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535493
van der Hoeven JMonagan M(2021)Computing one billion roots using the tangent Graeffe methodACM Communications in Computer Algebra10.1145/3457341.345734254:3(65-85)Online publication date: 15-Mar-2021
https://dl.acm.org/doi/10.1145/3457341.3457342
Le HEl Din M(2021)Solving parametric systems of polynomial equations over the reals through Hermite matricesJournal of Symbolic Computation10.1016/j.jsc.2021.12.002Online publication date: Dec-2021
https://doi.org/10.1016/j.jsc.2021.12.002
Huang Q(2021)Sparse polynomial interpolation based on diversificationScience China Mathematics10.1007/s11425-020-1791-565:6(1147-1162)Online publication date: 10-Apr-2021
https://doi.org/10.1007/s11425-020-1791-5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Convergence analysis of modified Newton-HSS method for solving systems of nonlinear equations

Solving rank-deficient separable nonlinear equations

Chebyshev polynomial solutions of systems of linear integral equations