The multivariate Horner scheme revisited (Q906952)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The multivariate Horner scheme revisited |
scientific article |
Statements
The multivariate Horner scheme revisited (English)
0 references
1 February 2016
0 references
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.
0 references
multivariate polynomial
0 references
Horner scheme
0 references
computational complexit
0 references
backwards stability
0 references
0 references