×

Accurate evaluation of polynomials in Legendre basis. (English) Zbl 1442.65023

Summary: This paper presents a compensated algorithm for accurate evaluation of a polynomial in Legendre basis. Since the coefficients of the evaluated polynomial are fractions, we propose to store these coefficients in two floating point numbers, such as double-double format, to reduce the effect of the coefficients’ perturbation. The proposed algorithm is obtained by applying error-free transformation to improve the Clenshaw algorithm. It can yield a full working precision accuracy for the ill-conditioned polynomial evaluation. Forward error analysis and numerical experiments illustrate the accuracy and efficiency of the algorithm.

MSC:

65D20 Computation of special functions and constants, construction of tables
65G50 Roundoff error

Software:

mctoolbox; LBNL; XBLAS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mason, J. C.; Handscomb, D. C., Chebyshev Polynomials (2003), Boca Raton, Fla, USA: Chapman & Hall/CRC, Boca Raton, Fla, USA
[2] Gottlieb, D.; Orszag, S. A., Numerical Analysis of Spectral Methods: Theory and Applications. Numerical Analysis of Spectral Methods: Theory and Applications, CBMS-NSF Regional Conference Series in Applied Mathematics, 26 (1977), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · Zbl 0412.65058
[3] Trefethen, L. N., Approximation Theory and Approximation Practice (2013), Philadelphia, Pennsylvania: SIAM, Philadelphia, Pennsylvania · Zbl 1264.41001
[4] Clenshaw, C. W., A note on the summation of Chebyshev series, Mathematical Tables and Other Aids to Computation, 9, 118-120 (1955) · Zbl 0065.05403
[5] Barrio, R., A unified rounding error bound for polynomial evaluation, Advances in Computational Mathematics, 19, 4, 385-399 (2003) · Zbl 1036.65025
[6] Oliver, J., Rounding error propagation in polynomial evaluation schemes, Journal of Computational and Applied Mathematics, 5, 2, 85-97 (1979) · Zbl 0399.65024
[7] Barrio, R., A matrix analysis of the stability of the Clenshaw algorithm, Extracta Mathematicae, 13, 1, 21-26 (1998) · Zbl 0963.65003
[8] Barrio, R., Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series, Journal of Computational and Applied Mathematics, 138, 2, 185-204 (2002) · Zbl 0998.65033
[9] Skrzipek, M., Polynomial evaluation and associated polynomials, Numerische Mathematik, 79, 4, 601-613 (1998) · Zbl 0909.65007
[10] Smoktunowicz, A., Backward stability of Clenshaw’s algorithm, BIT: Numerical Mathematics, 42, 3, 600-610 (2002) · Zbl 1019.65004
[11] Ogita, T.; Rump, S. M.; Oishi, S., Accurate sum and dot product, SIAM Journal on Scientific Computing, 26, 6, 1955-1988 (2005) · Zbl 1084.65041
[12] Graillat, S.; Langlois, P.; Louvet, N., Compensated Horner scheme, Research Report, RR2005-04, LP2A (2005), Perpignan, France: University of Perpignan, Perpignan, France
[13] Jiang, H.; Graillat, S.; Hu, C.; Li, S.; Liao, X.; Cheng, L.; Su, F., Accurate evaluation of the \(k\)-th derivative of a polynomial and its application, Journal of Computational and Applied Mathematics, 243, 28-47 (2013) · Zbl 1271.65040
[14] Jiang, H.; Li, S.; Cheng, L.; Su, F., Accurate evaluation of a polynomial and its derivative in Bernstein form, Computers & Mathematics with Applications, 60, 3, 744-755 (2010) · Zbl 1201.65028
[15] Jiang, H.; Barrio, R.; Li, H.; Liao, X.; Cheng, L.; Su, F., Accurate evaluation of a polynomial in Chebyshev form, Applied Mathematics and Computation, 217, 23, 9702-9716 (2011) · Zbl 1228.65028
[16] Bailey, D. H.; Barrio, R.; Borwein, J. M., High-precision computation: mathematical physics and dynamics, Applied Mathematics and Computation, 218, 20, 10106-10121 (2012) · Zbl 1248.65147
[17] Higham, N. J., Accuracy and Stability of Numerical Algorithm (2002), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · Zbl 1011.65010
[18] Knuth, D. E., The Art of Computer Programming: Seminumerical Algorithms (1998), Reading, Mass, USA: Addison-Wesley, Reading, Mass, USA · Zbl 0895.65001
[19] Dekker, T. J., A floating-point technique for extending the available precision, Numerische Mathematik, 18, 224-242 (1971) · Zbl 0226.65034
[20] Graillat, S., Accurate floating-point product and exponentiation, IEEE Transactions on Computers, 58, 7, 994-1000 (2009) · Zbl 1367.65218
[21] Barrio, R.; Jiang, H.; Serrano, S., A general condition number for polynomials, SIAM Journal on Numerical Analysis, 51, 2, 1280-1294 (2013) · Zbl 1273.65036
[22] Li, X.; Demmel, J. W.; Bailey, D. H.; Henry, G.; Hida, Y.; Iskandar, J.; Kahan, W.; Kang, S. Y.; Kapur, A.; Martin, M. C.; Thompson, B. J.; Tung, T.; Yoo, D. J., Design, implementation and testing of extended and mixed precision BLAS, ACM Transactions on Mathematical Software, 28, 2, 152-205 (2002) · Zbl 1070.65523
[23] Graillat, S.; Langlois, P.; Louvet, N., Algorithms for accurate, validated and fast polynomial evaluation, Japan Journal of Industrial and Applied Mathematics, 26, 2-3, 191-214 (2009) · Zbl 1184.65029
[24] Louvet, N., Compensated algorithms in floating point arithmetic: accuracy, validation, performances [Ph.D. thesis] (2007), Universite’ de Perpignan Via Domitia
[25] Langlois, P.; Louvet, N., More instruction level parallelism explains the actual efficiency of compensated algorithms, hal-00165020 (2007), Perpignan, France: DALI Research Team, University of Perpignan, Perpignan, France
[26] Table of Contents for MATH77/mathc90
[27] Hida, Y.; Li, X. S.; Bailey, D. H., Algorithms for quad-double precision floating point arithmetic, Proceedings of the 15th IEEE Symposium on Computer Arithmetic
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.