We present an algorithm for the solution of polynomial equations and secular equations of the form $S(x)=0$ for $S(x)=sum_{i=1}^nrac{a_i}{x-b_i}-1=0$, which provides guaranteed approximation of the roots with any desired number of digits. It relies on the combination of two different strategies for dealing with the precision of the floating point computation: the strategy used in the package MPSolve of D.~Bini and G.~Fiorentino [Numer.~Algo.~23, 2000] and the strategy used in the package Eigensolve of S.~Fortune [J. Symb. Comput.~33, 2002]. The algorithm is based on the Ehrlich-Aberth (EA) iteration, and on several results introduced in the paper. In particular, we extend the concept and the properties of root-neighborhoods from polynomials to secular functions, provide perturbation results of the roots, obtain an effective stop condition for the EA iteration and guaranteed a posteriori error ounds. We provide an implementation, released in the package MPSolve 3.0, based on the GMP library. From the many numerical experiments it turns out that our code is generally much faster than MPSolve 2.0 and of the package Eigensolve. For certain polynomials, like the Mandelbrot or the partition polynomials the acceleration is dramatic. The algorithm exploits the parallel architecture of the computing platform.

Solving secular and polynomial equations: A multiprecision algorithm

BINI, DARIO ANDREA;Leonardo Robol
2014

Abstract

We present an algorithm for the solution of polynomial equations and secular equations of the form $S(x)=0$ for $S(x)=sum_{i=1}^nrac{a_i}{x-b_i}-1=0$, which provides guaranteed approximation of the roots with any desired number of digits. It relies on the combination of two different strategies for dealing with the precision of the floating point computation: the strategy used in the package MPSolve of D.~Bini and G.~Fiorentino [Numer.~Algo.~23, 2000] and the strategy used in the package Eigensolve of S.~Fortune [J. Symb. Comput.~33, 2002]. The algorithm is based on the Ehrlich-Aberth (EA) iteration, and on several results introduced in the paper. In particular, we extend the concept and the properties of root-neighborhoods from polynomials to secular functions, provide perturbation results of the roots, obtain an effective stop condition for the EA iteration and guaranteed a posteriori error ounds. We provide an implementation, released in the package MPSolve 3.0, based on the GMP library. From the many numerical experiments it turns out that our code is generally much faster than MPSolve 2.0 and of the package Eigensolve. For certain polynomials, like the Mandelbrot or the partition polynomials the acceleration is dramatic. The algorithm exploits the parallel architecture of the computing platform.
Bini, DARIO ANDREA; Robol, Leonardo
File in questo prodotto:
File Dimensione Formato  
secular-finale.pdf

accesso aperto

Descrizione: Postprint del lavoro
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 396.52 kB
Formato Adobe PDF
396.52 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/217326
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? 44
social impact