Skip to Main content Skip to Navigation
Journal articles

Truncated Normal Forms for Solving Polynomial Systems: Generalized and Efficient Algorithms

Bernard Mourrain 1 Simon Telen 2 Marc van Barel 2
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA | UoA - National and Kapodistrian University of Athens = University of Athens
Abstract : We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R/I and the solutions of I. This framework allows for the use of much more general bases than the standard monomials for R/I. This is exploited in this paper to introduce the use of two special (nonmonomial) types of basis functions with nice properties. This allows, for instance, to adapt the basis functions to the expected location of the roots of I. We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01738695
Contributor : Bernard Mourrain <>
Submitted on : Friday, December 7, 2018 - 9:16:25 AM
Last modification on : Tuesday, January 14, 2020 - 1:36:09 PM
Document(s) archivé(s) le : Friday, March 8, 2019 - 12:53:43 PM

Files

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Bernard Mourrain, Simon Telen, Marc van Barel. Truncated Normal Forms for Solving Polynomial Systems: Generalized and Efficient Algorithms. Journal of Symbolic Computation, Elsevier, 2019, ⟨10.1016/j.jsc.2019.10.009⟩. ⟨hal-01738695v2⟩

Share

Metrics

Record views

157

Files downloads

553