On the complexity of computing with planar algebraic curves

DOI10.1016/j.jco.2014.08.002zbMath1309.65025arXiv1401.5690OpenAlexW2963548828MaRDI QIDQ2254683

Michael Sagraloff, Alexander Kobel

Publication date: 6 February 2015

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.5690

zbMATH Keywords

complexity analysisbivariate systemstopology analysisapproximate multipoint evaluationarrangement computationseparating form

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Plane and space curves (14H50) Complexity and performance of numerical algorithms (65Y20)

Related Items (17)

A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ On the complexity of quadratic programming with two quadratic constraints ⋮ Solving bivariate systems using rational univariate representations ⋮ Certified numerical real root isolation for bivariate nonlinear systems ⋮ On the complexity of computing the topology of real algebraic space curves ⋮ Computing the topology of a plane or space hyperelliptic curve ⋮ Algorithm for Connectivity Queries on Real Algebraic Curves ⋮ Separation bounds for polynomial systems ⋮ On Isolating Roots in a Multiple Field Extension ⋮ p-adic algorithm for bivariate Gröbner bases ⋮ Counting solutions of a polynomial system locally and exactly ⋮ Avoiding the general position condition when computing the topology of a real algebraic plane curve defined implicitly ⋮ Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems ⋮ Computing real roots of real polynomials ⋮ Bounds for polynomials on algebraic numbers and application to curve topology ⋮ The electrostatic equilibrium problem for classical discrete orthogonal polynomials

Uses Software

• CGAL
• PHCpack
• Bertini
• na20
• Lgp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact symbolic-numeric computation of planar algebraic curves
• CGAL Arrangements and their applications. A step-by-step guide
• On the topology of real algebraic plane curves
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Topology and arrangement computation of semi-algebraic planar curves
• A worst-case bound for topology computation of algebraic curves
• Subdivision methods for solving polynomial equations
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• A polynomial-time algorithm for the topological type of real algebraic curve
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Robust certified numerical homotopy tracking
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Cylindrical algebraic decomposition using validated numerics
• Fast multiplication of large numbers
• Modern Computer Algebra
• Root isolation for bivariate polynomial systems with local generic position method
• Rational univariate representations of bivariate systems and applications
• Separating linear forms for bivariate systems
• From approximate factorization to root isolation
• Improved algorithm for computing separating linear forms for bivariate systems
• On the computation of the topology of plane curves
• Faster Integer Multiplication
• Polynomial homotopy continuation with PHCpack
• An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
• On the complexity of solving a bivariate polynomial system
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• A generic algebraic kernel for non-linear geometric applications
• On Solving Systems of Bivariate Polynomials
• Algorithms in real algebraic geometry
• Sylvester-Habicht sequences and fast Cauchy index computation

This page was built for publication: On the complexity of computing with planar algebraic curves