Skip to Main content Skip to Navigation
Reports

A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications

Ioannis Z. Emiris 1
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Sparse elimination and the sparse resultant exploit the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. % The sparse, or Newton, resultant generalizes % the classical homogeneous resultant and its degree is a function % of the mixed volumes of the Newton polytopes. We sketch the sparse resultant constructions of Canny and Emiris and show how they reduce the problem of root-finding to an eigenproblem. A little known method for achieving this reduction is presented which does not increase the dimension of the problem. Together with an implementation of the sparse resultant construction, this provides a general solver for polynomial systems. We discuss the overall implementation and emphasize the numerical issues encountered in the matrix computations, based on the condition number of a matrix. We illustrate the program's capabilities by applying it to concrete problems from vision, robotics and computational biology. The high efficiency and accuracy of the solutions suggest that sparse elimination may be the method of choice for systems of moderate size.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073580
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:13:55 PM
Last modification on : Wednesday, October 17, 2018 - 5:02:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:50:49 PM

Identifiers

  • HAL Id : inria-00073580, version 1

Collections

Citation

Ioannis Z. Emiris. A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications. RR-3110, INRIA. 1997. ⟨inria-00073580⟩

Share

Metrics

Record views

324

Files downloads

441