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

article

Root isolation of zero-dimensional polynomial systems with linear univariate representation

Authors:

Leilei GuoAuthors Info & Claims

Journal of Symbolic Computation, Volume 47, Issue 7

Pages 843 - 858

https://doi.org/10.1016/j.jsc.2011.12.011

Published: 01 July 2012 Publication History

Abstract

In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Grobner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation.

References

[1]

Zeros, multiplicities, and idempotents for zerodimensional systems. In: Algorithms in Algebraic Geometry and Applicatiobns, Birkhauser. pp. 1-15.

[2]

Algorithms in Real Algebraic Geometry. 2nd edition. Springer.

[3]

An efficient algorithm for the stratification and triangulation of an algebraic surface. Computational Geometry. v43 i3. 257-278.

[4]

Canny, J.F., 1988. Some algebraic and geometric computation in pspace. In: ACM Symp. on Theory of Computing, SIGACT. pp. 460-469.

[5]

Root isolation for bivariate polynomial systems with local generic position method. In: Proc. ISSAC 2009, ACM Press. pp. 103-109.

[6]

Determining the topology of real algebraic surfaces. In: Martin, R., Bez, H., Sabin, M. (Eds.), LNCS, vol. 3604. pp. 121-146.

[7]

Complete numerical isolation of real roots in zero-dimensional triangular systems. Journal of Symbolic Computation. v44 i7. 768-785.

[8]

A tangent-secant method for polynomial complex root calculation. In: Proc. ISSAC 1996, ACM Press. pp. 137-141.

[9]

Solving equations via algebras. In: Dichenstein, Alicia, Emiris, Ioannis Z. (Eds.), Solving Polnomial Equations, Springer.

[10]

Using algebraic geometry. 2nd edition. Springer-Verlag.

[11]

The DMM bound: multivariate (aggregate) separation bounds. In: Proc. ISSAC 2010, ACM, New York, NY, USA. pp. 243-250.

[12]

Efficient computation of zero-dimensional Gröbner basis by changing of order. Journal of Symbolic Computation. v16 i4. 329-344.

[13]

On the theory of resolvents and its applications. Systems Science and Mathematical Science. v12. 17-30.

[14]

Algebraic solution of systems of polynomial equations using Groebner bases. In: LNCS, vol. 356. pp. 247-257.

[15]

Algorithmes¿disons rapides¿pour la dècomposition d'une varièté algébrique en composantes irréducibles et équidimensionnelles. In: Proc MEGA¿ 90, Birkhäuser. pp. 169-193.

[16]

A Gröbner free alternative for polynomial system solving. Journal of Complexity. v17. 154-211.

[17]

Keyser, J., Rojas, J.M., Ouchi, K., 2005. The exact rational univariate representation and its application. AMS/DIMACS Volume on Computer Aided Design and Manufacturing. American Mathematical Society/Center for Discrete Mathematics and Computer Science.

[18]

Solving systems of algebraic equations. In: Proc. ISSAC 1988, ACM Press. pp. 139-149.

[19]

Solving systems of algebraic equations by a general elimination method. Journal of Symbolic Computation. v5 i3. 303-320.

[20]

Grundzüge einer arithmetischen theorie der algebraischen grössen. Journal für die Reine und Angewandte Mathematik. v92. 1-22.

[21]

On the complexity of zero-dimensional algebraic systems. In: Progess in Mathematics, vol. 94. Birkhäuser, Basel. pp. 217-225.

[22]

Resolution des systemes d'equations algebriques. Theoretical Computer Science. v15. 77-110.

[23]

Interval Analysis. Prentice Hall, Englewood Cliffs, NJ.

[24]

Interval Methods for Systems of Equations. Cambridge University Press.

[25]

An exact method for finding the roots of a complex polynomial. ACM Transactions on Mathematical Software. v2 i4. 351-363.

[26]

On the computaional complexity and geometry of the first-order theoery of the reals. Part I. Journal of Symbolic Computation. v13. 255-299.

[27]

Solving zero-dimensional systems through the rational univariate representation. Applicable Algebra in Engineering, Communication and Computing. v9 i5. 433-461.

[28]

Sagraloff, M., Yap, C.K., 2009. An efficient exact subdivision algorithm for isolating complex roots of a polynomial and its complexity analysis. October (submitted for publication).

[29]

A global bisection algorithm for computing the zeros of polynomials in the complex plane. Journal of the ACM. v25 i3. 415-420.

[30]

Fundamental Problems of Algorithmic Algebra. Oxford Press.

[31]

Computing primitive elements of extension fields. Journal of Symbolic Computation. v8 i6. 553-580.

Cited By

Tan LLi BZhang BCheng J(2023)An Algorithm for the Intersection Problem of Planar Parametric CurvesComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_17(312-329)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-41724-5_17
Burr MGao STsigaridas EYap CEl Din M(2017)The Complexity of an Adaptive Subdivision Method for Approximating Real CurvesProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087654(61-68)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087654
Brand CSagraloff MAbramov SZima EGao X(2016)On the Complexity of Solving Zero-Dimensional Polynomial Systems via ProjectionProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930934(151-158)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930934
Show More Cited By

Root isolation of zero-dimensional polynomial systems with linear univariate representation
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

A generic position based method for real root isolation of zero-dimensional polynomial systems

We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant ...
Root isolation for bivariate polynomial systems with local generic position method
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

A local generic position method is proposed to isolate the real roots of a bivariate polynomial system ∑={f(x,y),g(x,y)}. In this method, the roots of the system are represented as linear combinations of the roots of two univariate polynomial equations ...
From approximate factorization to root isolation
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

We present an algorithm for isolating all roots of an arbitrary complex polynomial p which also works in the presence of multiple roots provided that arbitrary good approximations of the coefficients of p and the number of distinct roots are given. Its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 47, Issue 7

July, 2012

152 pages

ISSN:0747-7171

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2011.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 July 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan LLi BZhang BCheng J(2023)An Algorithm for the Intersection Problem of Planar Parametric CurvesComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_17(312-329)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-41724-5_17
Burr MGao STsigaridas EYap CEl Din M(2017)The Complexity of an Adaptive Subdivision Method for Approximating Real CurvesProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087654(61-68)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087654
Brand CSagraloff MAbramov SZima EGao X(2016)On the Complexity of Solving Zero-Dimensional Polynomial Systems via ProjectionProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930934(151-158)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930934
Cheng JJin K(2015)A generic position based method for real root isolation of zero-dimensional polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2014.09.01768:P1(204-224)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.jsc.2014.09.017
Li JCheng JTsigaridas E(2012)Local generic position for root isolation of zero-dimensional triangular polynomial systemsProceedings of the 14th international conference on Computer Algebra in Scientific Computing10.1007/978-3-642-32973-9_16(186-197)Online publication date: 3-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32973-9_16

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents