A Subdivision Solver for Systems of Large Dense Polynomials

Rémi Imbach 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We describe here the package {\tt subdivision\_solver} for the mathematical software {\tt SageMath}. It provides a solver on real numbers for square systems of large dense polynomials. By large polynomials we mean multivariate polynomials with large degrees, which coefficients have large bit-size. While staying robust, symbolic approaches to solve systems of polynomials see their performances dramatically affected by high degree and bit-size of input polynomials. Available numeric approaches suffer from the cost of the evaluation of large polynomials and their derivatives. Our solver is based on interval analysis and bisections of an initial compact domain of $\R^n$ where solutions are sought. Evaluations on intervals with Horner scheme is performed by the package {\tt fast\_polynomial} for {\tt SageMath}. The non-existence of a solution within a box is certified by an evaluation scheme that uses a Taylor expansion at order 2, and existence and uniqueness of a solution within a box is certified with krawczyk operator. The precision of the working arithmetic is adapted on the fly during the subdivision process and we present a new heuristic criterion to decide if the arithmetic precision has to be increased.
Type de document :
Rapport
[Technical Report] RT-0476, INRIA Nancy. 2016, pp.13
Liste complète des métadonnées


https://hal.inria.fr/hal-01293526
Contributeur : Rémi Imbach <>
Soumis le : jeudi 6 octobre 2016 - 15:01:26
Dernière modification le : vendredi 7 octobre 2016 - 01:05:22
Document(s) archivé(s) le : vendredi 3 février 2017 - 15:51:34

Fichiers

RT-476.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01293526, version 2
  • ARXIV : 1603.07916

Collections

Citation

Rémi Imbach. A Subdivision Solver for Systems of Large Dense Polynomials. [Technical Report] RT-0476, INRIA Nancy. 2016, pp.13. <hal-01293526v2>

Partager

Métriques

Consultations de
la notice

98

Téléchargements du document

34