×

Accurate quotient-difference algorithm: error analysis, improvements and applications. (English) Zbl 1411.65057

Summary: The compensated quotient-difference (Compqd) algorithm is proposed along with some applications. The main motivation is based on the fact that the standard quotient-difference (qd) algorithm can be numerically unstable. The Compqd algorithm is obtained by applying error-free transformations to improve the traditional qd algorithm. We study in detail the error analysis of the qd and Compqd algorithms and we introduce new condition numbers so that the relative forward rounding error bounds can be derived directly. Our numerical experiments illustrate that the Compqd algorithm is much more accurate than the qd algorithm, relegating the influence of the condition numbers up to second order in the rounding unit of the computer. Three applications of the new algorithm in the obtention of continued fractions and in pole and zero detection are shown.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Software:

Compqd; QD; XBLAS; mctoolbox; LBNL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Hadamard, J., Essai sur l’étude des fonctions donnée par leurs dénveloppement de Taylor, J. Math. Pures Appl., 8, 101-186 (1992)
[2] Aitken, A. C., On Bernoulli’s numerical solution of algebraic equations, Proc. R. Soc. Edinb., 46, 289-305 (1926) · JFM 52.0098.05
[3] Aitken, A. C., Further numerical studies in algebraic equations and matrices, Proc. R. Soc. Edinb., 51, 80-90 (1931) · Zbl 0002.00703
[4] Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl. Bur. Stand., 45, 255-281 (1950)
[5] Gutknecht, M. H., From qd to LR, or, how were the qd and LR algorithms discovered, IMA J. Numer. Anal., 31, 741-754 (2011) · Zbl 1222.65032
[6] Lorentzen, L., Padé approximation and continued fractions, Appl. Numer. Math., 60, 1364-1370 (2010) · Zbl 1202.41009
[7] Cuyt, A.; Petersen, V. B.; Verdonk, B.; Waadeland, H.; Jones, W. B., Handbook of Continued Fractions for Special Functions (2008), Springer · Zbl 1150.30003
[8] Jones, W. B.; Thron, W. J., Continued Fractions: Analytic Theory and Applications (1980), Addison-Wesley: Addison-Wesley London · Zbl 0445.30003
[9] Henrici, P., Applied and Computational Complex Analysis, vol. 1 (1974), John Wiley: John Wiley New York · Zbl 0313.30001
[10] Allouche, H.; Cuyt, A., Reliable root detection with the qd-algorithm: when Bernoulli, Hadamard and Rutishauser cooperate, Appl. Numer. Math., 60, 1188-1208 (2010) · Zbl 1203.65081
[11] Rutishauser, H., Anwendungen des quotienten-differenzen-algorithmus, Z. Angel. Math. Phys., 5, 496-508 (1954) · Zbl 0056.35001
[12] Rutishauser, H., Solution of eigenvalue problems with the LR-transformation, Nat. Bur. Stand. Appl. Math. Ser., 49, 47-81 (1958)
[13] Parlett, B. N., What Hadamard Missed (1996), Center for Pure and Applied Mathematics, University of California at Berkeley, Technical Report
[14] Fernando, K. V.; Parlett, B. N., Accurate singular values and differential qd algorithms, Numer. Math., 67, 191-229 (1994) · Zbl 0814.65036
[15] Cuyt, A., Floating-point versus symbolic computations in the qd-algorithm, J. Symb. Comput., 24, 6, 695-703 (1997) · Zbl 0910.65002
[16] Ogita, T.; Rump, S. M.; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 1955-1988 (2005) · Zbl 1084.65041
[17] Rump, S. M.; Ogita, T.; Oishi, S., Accurate floating-point summation part I: faithful rounding, SIAM J. Sci. Comput., 31, 189-224 (2008) · Zbl 1185.65082
[18] Rump, S. M.; Ogita, T.; Oishi, S., Accurate floating-point summation part II: sign, K-fold faithful and rounding to nearest, SIAM J. Sci. Comput., 31, 1269-1302 (2008) · Zbl 1190.65074
[19] Graillat, S.; Langlois, P.; Louvet, N., Algorithms for accurate validated and fast polynomial evaluation, Jpn. J. Indust. Appl. Math., 26, 2-3, 191-214 (2009) · Zbl 1184.65029
[20] Graillat, S.; Langlois, P.; Louvet, N., Compensated Horner Scheme (2005), University of Perpignan: University of Perpignan France, Technical Report rr2005-04, lp2a
[21] Langlois, P.; Louvet, N., How to ensure a faithful polynomial evaluation with the compensated Horner algorithm, (Kornerup, P.; Muller, J. M., Proceedings of the Eighteenth IEEE International Symposium on Computer Arithmetic (2007), IEEE Computer Society), 141-149
[22] Jiang, H.; Li, S. G.; Cheng, L. Z.; Su, F., Accurate evaluation of a polynomial and its derivative in Bernstein form, Comput. Math. Appl., 60, 744-755 (2010) · Zbl 1201.65028
[23] Jiang, H.; Barrio, R.; Li, H. S.; Liao, X. K.; Cheng, L. Z.; Su, F., Accurate evaluation of a polynomial in Chebyshev form, Appl. Math. Comput., 217, 9702-9716 (2011) · Zbl 1228.65028
[24] Du, P. B.; Jiang, H.; Cheng, L. Z., Accurateevaluation of polynomials in Legendre basis, J. Appl. Math., 13 (2014)
[25] Rutishauser, H., Der quotienten-differenzen-algorithmus, Z. Angew. Math. Phys., 5, 233-251 (1954) · Zbl 0055.34702
[26] Higham, N. J., Accuracy and Stability of Numerical Algorithm (2002), SIAM: SIAM Philadelphia
[27] Rump, S. M., Verification methods: rigorous results using floating-point arithmetic, Acta Numer., 19, 287-449 (2010) · Zbl 1323.65046
[28] Knuth, D. E., The Art of Computer Programming: Seminumerical Algorithms (1998), Addison-Wesley · Zbl 0895.65001
[29] Dekker, T. J., A floating-point technique for extending the available precision, Numer. Math., 18, 224-242 (1971) · Zbl 0226.65034
[30] Louvet, N., Compensated algorithms in floating-point arithmetic: accuracy, validation, performances (2007), University of Perpignan: University of Perpignan France, Ph.d. thesis
[31] Pichat, M.; Vignes, J., Ingénierie du contrôle de la préision des calculs sur ordinateur (1993), Editions Technip, Technical Report
[32] Li, X. S.; 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 Trans. Math. Softw., 28, 2, 152-205 (2002) · Zbl 1070.65523
[34] Hida, Y.; Li, X. Y.; Bailey, D. H., Algorithms for quad-double precision floating point arithmetic, Proceedings of the Fifteenth IEEE Symposium on Computer Arithmetic, 155-162 (2001), IEEE Computer Society
[35] Langlois, P.; Louvet, N., More instruction level parallelism explains the actual efficiency of compensated algorithm (2007), DALI Research Team, University of Perpignan: DALI Research Team, University of Perpignan France, Technical Report hal-00165020
[36] Markstein, P., IA-64 and Elementary Functions: Speed and Precision (2000), Prentice-Hall: Prentice-Hall Englewood Cliffs, USA
[37] Nievergelt, Y., Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit, ACM Trans. Math. Softw., 29, 1, 27-48 (2003) · Zbl 1069.68505
[38] Henrici, P.; Watkins, B. O., Finding zeros of a polynomial by the qd algorithm, Comm. ACM, 8, 9, 570-574 (1965) · Zbl 0133.37903
[39] Szegö, G., Orthogonal Polynomials, American Mathematical Society Colloquium Publications, 23 (1939), Am. Math. Soc.: Am. Math. Soc. New York
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.