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

research-article

Separating linear forms for bivariate systems

Authors:

Yacine Bouzidi,

Sylvain Lazard,

Fabrice RouillierAuthors Info & Claims

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

Pages 117 - 124

https://doi.org/10.1145/2465506.2465518

Published: 26 June 2013 Publication History

Abstract

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation of a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity.

Given two bivariate polynomials of total degree at most d with integer coefficients of bitsize at most τ, our algorithm computes a separatin linear form in Õ_B(d⁸+d⁷τ+d⁵τ²) bit operations in the worst case, where the previously known best bit complexity for this problem was Õ_B(d¹⁰+d⁹τ) (whereÕ refers to the complexity where polylogarithmic factors are omitted and Õ_B refers to the bit complexity)

References

[1]

M.-E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Multiplicities and idempotents for zerodimensional systems. In Algorithms in Algebraic Geometry and Applications, volume 143 of Progress in Mathematics, pages 1--20. Birkhäuser, 1996.

Digital Library

[2]

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, 2nd edition, 2006.

Digital Library

[3]

A. Bostan, B. Salvy, and É. Schost. Fast algorithms for zero-dimensional polynomial systems using duality. Applicable Algebra in Engineering, Communication and Computing, 14(4):239--272, 2003.

[4]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Rational Univariate Representations of Bivariate Systems and Applications. In ISSAC, 2013.

Digital Library

[5]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Separating linear forms for bivariate systems. Research Report RR-8261, INRIA, Mar. 2013.

Digital Library

[6]

D. I. Diochnos, I. Z. Emiris, and E. P. Tsigaridas. On the asymptotic and practical complexity of solving bivariate systems over the reals. J. Symb. Comput., 44(7):818--835, 2009.

Digital Library

[7]

M. El Kahoui. An elementary approach to subresultants theory. J. Symb. Comput., 35(3):281--292, 2003.

Digital Library

[8]

M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for solving polynomial systems. J. of Complexity, 17(1):154--211, 2001.

Digital Library

[9]

L. González-Vega and M. El Kahoui. An improved upper complexity bound for the topology computation of a real algebraic plane curve. J. of Complexity, 12(4):527--544, 1996.

Digital Library

[10]

M. Kerber and M. Sagraloff. A worst-case bound for topology computation of algebraic curves. J. Symb. Comput., 47(3):239--258, 2012.

Digital Library

[11]

X. Li, M. Moreno Maza, R. Rasheed, and É. Schost. The modpn library: Bringing fast polynomial arithmetic into maple. J. Symb. Comput., 46(7):841--858, 2011.

Digital Library

[12]

D. Reischert. Asymptotically fast computation of subresultants. In ISSAC, pp. 233--240, 1997.

Digital Library

[13]

F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. J. of Applicable Algebra in Engineering, Communication and Computing, 9(5):433--461, 1999.

[14]

B.-L. Van der Waerden. Moderne Algebra I. Springer, Berlin, 1930.

[15]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge Univ. Press, Cambridge, U.K., 2nd edition, 2003.

Digital Library

[16]

C. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, Oxford-New York, 2000.

Digital Library

Cited By

Mantzaflaris ATsigaridas EYap CEl Din M(2017)Resultants and Discriminants for Bivariate Tensor-Product PolynomialsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087646(309-316)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087646
Moroz GSchost EAbramov SZima EGao X(2016)A Fast Algorithm for Computing the Truncated ResultantProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930931(341-348)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930931
Kobel ASagraloff M(2015)On the complexity of computing with planar algebraic curvesJournal of Complexity10.1016/j.jco.2014.08.00231:2(206-236)Online publication date: Apr-2015
https://doi.org/10.1016/j.jco.2014.08.002
Show More Cited By

Index Terms

Separating linear forms for bivariate systems
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Separating linear forms and Rational Univariate Representations of bivariate systems

We address the problem of solving systems of bivariate polynomials with integer coefficients. We first present an algorithm for computing a separating linear form of such systems, that is a linear combination of the variables that takes different values ...
Rational univariate representations of bivariate systems and applications
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

We address the problem of solving systems of two bivariate polynomials of total degree at most d with integer coefficients of maximum bitsize τ We suppose known a linear separating form (that is a linear combination of the variables that takes different ...
Improved algorithm for computing separating linear forms for bivariate systems
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

June 2013

400 pages

ISBN:9781450320597

DOI:10.1145/2465506

General Chairs:
Michael Monagan
Simon Fraser University, Burnaby, Canada
,
Gene Cooperman
Northeastern University, Boston, USA
,
Program Chair:
Mark Giesbrecht
University of Waterloo, Waterloo, Canada

Copyright © 2013 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC'13

Sponsor:

SIGSAM

ISSAC'13: International Symposium on Symbolic and Algebraic Computation

June 26 - 29, 2013

Maine, Boston, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
67
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mantzaflaris ATsigaridas EYap CEl Din M(2017)Resultants and Discriminants for Bivariate Tensor-Product PolynomialsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087646(309-316)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087646
Moroz GSchost EAbramov SZima EGao X(2016)A Fast Algorithm for Computing the Truncated ResultantProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930931(341-348)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930931
Kobel ASagraloff M(2015)On the complexity of computing with planar algebraic curvesJournal of Complexity10.1016/j.jco.2014.08.00231:2(206-236)Online publication date: Apr-2015
https://doi.org/10.1016/j.jco.2014.08.002
Diatta DRouillier FRoy MNagasaka KWinkler FSzanto A(2014)On the computation of the topology of plane curvesProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608670(130-137)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.1145/2608628.2608670
Bouzidi YLazard SPouget MRouillier FMonagan MCooperman GGiesbrecht M(2013)Rational univariate representations of bivariate systems and applicationsProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465519(109-116)Online publication date: 26-Jun-2013
https://dl.acm.org/doi/10.1145/2465506.2465519

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents