The multivariate Horner scheme revisited
type: Item
instance of: scholarly article
title: The multivariate Horner scheme revisited
zbMATH Open document ID: 1337.65019
author: Johannes Czekansky
author: Tomas Sauer
published in: BIT
publication date: 2016-02-01T00:00:00Z
review text: The Horner scheme is a classical and well understood method for effectively computing the value of a univariate polynomial at a given point. When it comes to generalizing the approach so that it can deal with multivariate polynomials, two different implementations have been proposed by \textit{C. de Boor} [Adv. Comput. Math. 12, No. 4, 289--301 (2000; Zbl 0944.41002)] and \textit{J. M. Peña} [SIAM J. Numer. Anal. 37, No. 4, 1186--1197 (2000; Zbl 0961.65007)] and \textit{J. M. Peña} and \textit{T. Sauer} [Computing 65, No. 4, 313--322 (2000; Zbl 0984.65006)], respectively. This paper provides a comparison of the two approaches with respect to their computational complexity and their backwards stability. The main outcome is that de Boor's approach [loc. cit.] is superior in either respect by a noticeable, but not extremely huge, margin.
reviewed by: Kai Diethelm
Mathematics Subject Classification ID: 65D20
Mathematics Subject Classification ID: 65G50
Mathematics Subject Classification ID: 65Y04
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 26A09
Mathematics Subject Classification ID: 12E05
Mathematics Subject Classification ID: 12Y05
zbMATH DE Number: 6537630
zbMATH Keywords: multivariate polynomial
zbMATH Keywords: Horner scheme
zbMATH Keywords: computational complexit
zbMATH Keywords: backwards stability
describes a project that uses: mctoolbox
MaRDI profile type: Publication
full work available at URL: s10543-014-0533-x
OpenAlex ID: W1990097712
cites work: Computational aspects of multivariate polynomial interpolation: Indexing the coefficients
cites work: Accuracy and Stability of Numerical Algorithms
cites work: On the Multivariate Horner Scheme
cites work: On the multivariate Horner scheme. II: Running error analysis
cites work: Computational aspects of multivariate polynomial interpolation
cites work: Efficient evaluation of multivariate polynomials
DOI: 10.1007/S10543-014-0533-X
description: scientific article; zbMATH DE number 6537630