×

Algorithms for accurate, validated and fast polynomial evaluation. (English) Zbl 1184.65029

Summary: We survey a class of algorithms to evaluate polynomials with floating point coefficients and for computation performed with IEEE-754 floating point arithmetic. The principle is to apply, once or recursively, an error-free transformation of the polynomial evaluation with the Horner algorithm and to accurately sum the final decomposition. These compensated algorithms are as accurate as the Horner algorithm performed in \(K\) times the working precision, for \(K\) an arbitrary positive integer. We prove this accuracy property with an a priori error analysis. We also provide validated dynamic bounds and apply these results to compute a faithfully rounded evaluation. These compensated algorithms are fast. We illustrate their practical efficiency with numerical experiments on significant environments. Comparing to existing alternatives these \(K\)-times compensated algorithms are competitive for \(K\) up to 4, i.e., up to 212 mantissa bits.

MSC:

65D20 Computation of special functions and constants, construction of tables
26A09 Elementary functions
26C05 Real polynomials: analytic properties, etc.
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Software:

mctoolbox; LBNL; XBLAS
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] High-Precision Software Directory. http://crd.lbl.gov/\(\sim\)dhbailey/mpdist.
[2] T.J. Dekker, A floating-point technique for extending the available precision. Numer. Math.,18 (1971), 224–242. · Zbl 0226.65034 · doi:10.1007/BF01397083
[3] J.W. Demmel, Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0879.65017
[4] S. Graillat, P. Langlois and N. Louvet, Compensated Horner scheme. Algebraic and Numerical Algorithms and Computer-Assisted Proofs, B. Buchberger, S. Oishi, M. Plum and S.M. Rump (eds.), Dagstuhl Seminar Proceedings, No. 05391, Internationales Begenungs-und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2006.
[5] S. Graillat, P. Langlois and N. Louvet, Improving the compensated Horner scheme with a fused multiply and add. Proceedings of the 21st Annual ACM Symposium on Applied Computing, Vol. 2, Association for Computing Machinery, 2006, 1323–1327.
[6] Y. Hida, X.S. Li and D.H. Bailey, Quad-double arithmetic: Algorithms, implementation, and application. 15th IEEE Symposium on Computer Arithmetic, N. Burgess and L. Ciminiera (eds.), IEEE Computer Society, 2001, 155–162.
[7] N.J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002. · Zbl 1011.65010
[8] C.M. Hoffmann, G. Park, J.-R. Simard and N.F. Stewart, Residual iteration, and accurate polynomial evaluation for shape-interrogation applications. Proceedings of the 9th ACM Symposium on Solid Modeling and Applications, 2004, 9–14.
[9] IEEE Standards Committee 754, IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Standard 754–1985. Institute of Electrical and Electronics Engineers, Los Alamitos, CA, USA, 1985, Reprinted in SIGPLAN Notices,22 (1987), 9–25.
[10] D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, Vol. 2, 3rd edition. Addison-Wesley, Reading, MA, USA, 1998. · Zbl 0895.65001
[11] P. Langlois, More accuracy at fixed precision. J. Comp. Appl. Math.,162 (2004), 57–77. · Zbl 1037.65046 · doi:10.1016/j.cam.2003.08.017
[12] P. Langlois and N. Louvet, How to ensure a faithful polynomial evaluation with the compensated Horner algorithm. 18th IEEE International Symposium on Computer Arithmetic, P. Kornerup and J.-M. Muller (eds.), IEEE Computer Society, 2007, 141–149.
[13] P. Langlois and N. Louvet, More instruction level parallelism explains the actual efficiency of compensated algorithms. Technical Report hal-00165020, DALI Research Project, HALCCSD 2007.
[14] P. Langlois and N. Louvet, Compensated Horner algorithm inK times the working precision. RNC-8, Real Numbers and Computer Conference, J. Brugera and M. Daumas (eds.), Santiago de Compostela, Spain, 2008.
[15] X.S. Li, J.W. Demmel, D.H. Bailey, G. Henry, Y. Hida, J. Iskandar, W. Kahan, S.Y. Kang, A. Kapur, M.C. Martin, B.J. Thompson, T. Tung and D.J. Yoo, Design, implementation and testing of extended and mixed precision BLAS. ACM Trans. Math. Software,28 (2002), 152–205. · Zbl 1070.65523 · doi:10.1145/567806.567808
[16] The MPFR Library (version 2.2.1). Available at http://www.mpfr.org.
[17] Y. Nievergelt, Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit. ACM Trans. Math. Software,29 (2003), 27–48. · Zbl 1069.68505 · doi:10.1145/641876.641878
[18] T. Ogita, S.M. Rump and S. Oishi, Accurate sum and dot product. SIAM J. Sci. Comput.,26 (2005), 1955–1988. · Zbl 1084.65041 · doi:10.1137/030601818
[19] S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation, Part I: Faithful rounding. SIAM J. Sci. Comput.,31 (2008), 189–224. · Zbl 1185.65082 · doi:10.1137/050645671
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.