Computing Multiple Roots of Polynomials in Stochastic Arithmetic with Newton Method and Approximate GCD

EasyChair Preprint 7184

Abstract

In this article, we propose new methods to compute multiple roots of polynomials in floating-point arithmetic. We rely on stochastic arithmetic that makes it possible to deal with rounding errors. We develop the concept of stochastic GCD that we use to deflate a polynomial in order to obtain a polynomial with single roots. We can then apply Newton method to get fast and accurate approximations of the roots. Numerical experiments show the effectiveness and efficiency of our methods.

Keyphrases: Approximate GCD, Discrete Stochastic Arithmetic, Newton method, floating-point arithmetic, numerical validation, rounding errors

@booklet{EasyChair:7184,
  author    = {Stef Graillat and Fabienne Jézéquel and Enzo Queiros Martins and Maxime Spyropoulos},
  title     = {Computing Multiple Roots of Polynomials in Stochastic Arithmetic with Newton Method and Approximate GCD},
  howpublished = {EasyChair Preprint 7184},
  year      = {EasyChair, 2021}}