The multivariate Horner scheme revisited (Q906952)

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.