Skip to content
Research Article Open access CC BY 4.0

On the Fast Evaluation of Polynomials

P. Abascal Fuentes, F. Fueyo Tirado, D. Garcia Quintas, J. Jimenez Meana, A. Palacio Muniz

Journal of Advances in Mathematics and Computer Science · pp. 20–35 · Published 9 Jul 2022

10.9734/jamcs/2022/v37i630457

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.

Parallel polynomial evaluation parallel algorithms sparse polynomials

References (13)

  1. 1 The theory of error-correcting codes [DOI]
  2. 2 Organization of computer systems [DOI]
  3. 3 Mathematical Software – ICMS 2014 [DOI]
  4. 4 Mathematical Software – ICMS 2010 [DOI]
  5. 5 Fast operations on linearized polynomials and their applications in coding theory [DOI]
  6. 6 On the Multivariate Horner Scheme [DOI]
  7. 7 The multivariate Horner scheme revisited [DOI]
  8. 8 On the Multivariate Horner Scheme II: Running Error Analysis [DOI]
  9. 9 On the evaluation of some sparse polynomials [DOI]
  10. 10 On the parallel evaluation of a sparse polynomial at a point [DOI]
  11. 11 Fast Parallel Algorithm for Polynomial Evaluation [DOI]
  12. 12 Improvements on binary coding using parallel computing [DOI]
  13. 13 The Art of Computer Programming [DOI]

Cited by 2

Swarm Intelligence Algorithms for Solving Optimization Problems in Telecommunication Systems

L. S. Adonin, A. G. Vladyko · Proceedings of Telecommunication Universities · 2025

Showing 1 of 2 known citations — external sources report more than can currently be individually listed.

Article metrics

Real usage data collected on this platform.

37

Page views

0

PDF downloads

5

Outbound clicks

2

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.