On the Fast Evaluation of Polynomials
P. Abascal Fuentes *
Department of Mathematics, University of Oviedo, Edificio Polivalente Campus de Viesques, 33203-Gijon, Asturias, Espana.
F. Fueyo Tirado
Department of Mathematics, University of Oviedo, Edificio Polivalente Campus de Viesques, 33203-Gijon, Asturias, Espana.
D. Garcia Quintas
Department of Mathematics, University of Oviedo, Edificio Polivalente Campus de Viesques, 33203-Gijon, Asturias, Espana.
J. Jimenez Meana
Department of Mathematics, University of Oviedo, Edificio Polivalente Campus de Viesques, 33203-Gijon, Asturias, Espana.
A. Palacio Muniz
Department of Mathematics, University of Oviedo, Edificio Polivalente Campus de Viesques, 33203-Gijon, Asturias, Espana.
*Author to whom correspondence should be addressed.
Abstract
Minimizing the computational cost of polynomial evaluation is a main problem in Computational Science.
Horner's algorithm efficiently solves the problem of evaluating a polynomial of degree n in time O(n). It is also used to evaluate multivariate polynomials and, as an extension, matrix polynomials.
If, in addition, a parallel execution of this method can be carried out, the computational cost of this problem would be further minimized.
This makes it especially important to develop a strategy for parallel execution of Horner's method for fast and ecient polynomial evaluation.
In this paper we present a parallelization of Horner's method based on polynomial partitioning, as well as a modification of this method to exploit its advantages in the evaluation of sparse polynomials.
We also provide an analysis of the numerical error between the proposed parallel method and the classic algorithm.
Keywords: Parallel polynomial evaluation, parallel algorithms, sparse polynomials