Validated Root Enclosures for Interval Polynomials with Multiplicities

• Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
• Main Authors: Bréhard, Florent, Poteaux, Adrien, Soudant, Léo
• Other Authors: Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: multiple roots of univariate polynomials; fixed-point validation; [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]; Norway; Tromso
• Online Access: https://hal.science/hal-04138791; https://hal.science/hal-04138791/document; https://hal.science/hal-04138791/file/multrootval.pdf; https://doi.org/10.1145/3597066.3597122

International audience Twenty years ago, Zeng [28, 30] proposed floating-point algorithms to compute multiple roots of univariate polynomials with real or complex coefficients beyond the so-called "attainable accuracy barrier". Based on these foundations, we propose a validated numeric point of view on this problem. Our first contribution is an improvement of Zeng's multiplicity detection algorithm using a simple trick that allows us to recover much higher multiplicities. As our main contribution, we propose two floating-point validated algorithms to compute rigorous enclosures for multiple roots. They consist in carefully combining the ideas underlying Zeng's numerical algorithms with Newton-like fixed-point validation techniques. We also provide a prototype Julia implementation of these algorithms.