Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

For univariate polynomials f(x₁), Horner's scheme provides the fastest way to compute a value. For multivariate polynomials, several different version of Horner's scheme are possible; it is not clear which of them is optimal. In this paper, we propose a greedy algorithm, which it is hoped will lead to good computation times.The univariate Horner scheme has another advantage: if the value x₁ is known with uncertainty, and we are interested in the resulting uncertainty in f(x₁), then Horner scheme leads to a better estimate for this uncertainty that many other ways of computing f(x₁). The second greedy algorithm that we propose tries to find the multivariate Horner scheme that leads to the best estimate for the uncertainty in f(x₁,...,x_n).

REFERENCES

• 1: Martine Ceberio , Laurent Granvilliers, Solving Nonlinear Systems by Constraint Inversion and Interval Arithmetic, Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation, p.127-141, July 17-19, 2000
• 2: M. Ceberio and L. Granvilliers, "Résolution de systèmes non linéaires par inversion des contraintes et analyse des intervalles", Proceedings of the 9th French Conference on Logic Programming and Constraint Programming JFPLC'2000, Hermès, 2000, pp. 205--220.
• 3: M. Ceberio , L. Granvilliers, Horner's rule for interval evaluation revisited, Computing, v.69 n.1, p.51-81, September 2002 [doi>10.1007/s00607-002-1448-y]
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: L. Jaulin, M. Kieffer, O. Didrit, and E. Walter, Applied Interval Analysis, Springer-Verlag, Berlin, 2001.
• 6: R. B. Kearfott, Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, 1996.
• 7: R. B. Kearfott and V. Kreinovich (eds.), Applications of Interval Computations, Kluwer, Dordrecht, 1996.
• 8: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht, 1997.
• 10: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 11: A. Neumaier, Introduction to Numerical Analysis, Cambridge Univ. Press, Cambridge, UK, 2001.
• 12: J. M. Peña, On the Multivariate Horner Scheme, SIAM Journal on Numerical Analysis, v.37 n.4, p.1186-1197, Aug. 2000 [doi>10.1137/S0036142997324150]
• 13: J. M. Peña , Thomas Sauer, On the multivariate Horner scheme II: running error analysis, Computing, v.65 n.4, p.313-322, Nov. 2000 [doi>10.1007/s006070070002]
• 14: S. M. Rump, "Fast and parallel interval arithmetic", BIT Numerical Mathematics, 1999, Vol. 39, No. 3, pp. 534--554.
• 15: V. Stahl, Interval methods for bounding the range of polynomials and solving systems of nonlinear equations, Ph.D. Dissertation, University of Linz, Austria, 1995.
• 16: B. Traylor and V. Kreinovich, "A bright side of NP-hardness of interval computations: interval heuristics applied to NP-problems", Reliable Computing, 1995, Vol. 1, No. 3, pp. 343--360.
• 17: Stephen A. Vavasis, Nonlinear optimization: complexity issues, Oxford University Press, Inc., New York, NY, 1991