HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

How to Count Efficiently all Affine Roots of a Polynomial System

Ioannis Z. Emiris 1 Jan Verschelde
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so far mostly dealt with roots having nonzero coordinates. We shift attention to arbitrary affine roots, and improve upon the existing algorithms for counting them and computing them numerically. The one existing approach is too expensive in practice because of the usage of recursive liftings of the given point configuration. Instead, we define a single lifting which yields the desired count and defines a homotopy continuation for computing all solutions. We enhance the numerical stability of the homotopy by establishing lower bounds on the lifting values and prove that they can be derived dynamically to obtain the lowest possible values. Our construction may be regarded as a generalization of the dynamic lifting algorithm for the computation of mixed cells.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073477
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:57:20 PM
Last modification on : Friday, February 4, 2022 - 3:16:06 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:47:41 PM

Identifiers

  • HAL Id : inria-00073477, version 1

Collections

Citation

Ioannis Z. Emiris, Jan Verschelde. How to Count Efficiently all Affine Roots of a Polynomial System. RR-3212, INRIA. 1997. ⟨inria-00073477⟩

Share

Metrics

Record views

64

Files downloads

119