Jiang, Hao; Graillat, Stef; Barrio, Roberto; Yang, Canqun Accurate, validated and fast evaluation of elementary symmetric functions and its application. (English) Zbl 1410.65006 Appl. Math. Comput. 273, 1160-1178 (2016). Summary: This paper is concerned with the fast, accurate and validated evaluation of elementary symmetric functions in floating-point arithmetic. We present two new compensated algorithms, with real and complex floating-point inputs respectively, by applying error-free transformations to improve the accuracy of the so-called summation algorithm that is used, by example, in the MATLAB’s function. We derive forward roundoff error bounds and running error bounds for our new algorithms. The roundoff error bounds imply that the computed results are as accurate as if computed with twice the working precision and then rounded to the current working precision. The running error analysis provides a shaper bound along with the result, without increasing significantly the computational cost. Numerical experiments illustrate that our algorithms run much faster than the algorithms using the classic double-double library while sharing similar error estimates. Such algorithms can be widely applicable for example to compute characteristic polynomials from eigenvalues or polynomial’s coefficients from zeros. Some simple applications are presented to show that the proposed algorithms compute the coefficients of the characteristic polynomials of some real and complex matrices to high relative accuracy. Cited in 1 Document MSC: 65B10 Numerical summation of series 05E05 Symmetric functions and generalizations Keywords:elementary symmetric functions; floating-point arithmetic; roundoff error; error-free transformation; compensated algorithm; accurate algorithm Software:mctoolbox; ARPREC; MPFR; Algorithm 524; LBNL; Matlab; XBLAS PDFBibTeX XMLCite \textit{H. Jiang} et al., Appl. Math. Comput. 273, 1160--1178 (2016; Zbl 1410.65006) Full Text: DOI References: [1] Fischer, G., Einführung in die Theorie psychologischer tests: Grundlagen und Anwendungen (1974), Huber, Bern: Huber, Bern Switzerland · Zbl 0315.92016 [2] Rehman, R.; Ipsen, I., Computing characteristic polynomials from eigenvalues, SIAM J. Matrix. Anal. Applicat., 32, 1, 90-114 (2011) · Zbl 1220.65047 [3] Graillat, S., Accurate floating-point product and exponentiation, IEEE Trans. Comput., 58, 7, 994-1000 (2009) · Zbl 1367.65218 [4] Graillat, S.; Langlois, P.; Louvet, N., Algorithms for accurate, validated and fast polynomial evaluation, Jpn. J. Ind. Appl. Math., 26, 2, 215-231 (2009) [5] Graillat, S.; Morain, V., Accurate summation, dot product and polynomial evaluation in complex floating-point arithmetic, Inf. Comput., 216, 57-71 (2012) · Zbl 1259.65073 [6] Kornerup, P.; Lauter, C.; Lefèvre, V.; Louvet, N.; Muller, J., Computing correctly rounded integer powers in floating-point arithmetic, ACM Trans. Math. Software, 37, 1, 4:1-4:23 (2010) · Zbl 1364.65309 [7] Ogita, T.; Rump, S. M.; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 6, 1955-1988 (2005) · Zbl 1084.65041 [8] Rump, S. M., Ultimately fast accurate summation, SIAM J. Sci. Comput., 31, 5, 3466-3502 (2009) · Zbl 1202.65033 [9] Rump, S. M.; Ogita, T.; Oishi, S., Accurate floating-point summation part I: Faithful rounding, SIAM J. Sci. Comput., 31, 1, 189-224 (2006) · Zbl 1185.65082 [10] 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, 2, 1269-1302 (2008) · Zbl 1190.65074 [11] Calvetti, D.; Reichel, L., On the evaluation of polynomial coefficients, Numer. Algorithms, 33, 153-161 (2003) · Zbl 1035.65156 [12] Eisinberg, A.; Fedele, G., A property of the elementary symmetric functions, Calcolo, 42, 1, 31-36 (2005) · Zbl 1108.15005 [13] Baker, F.; Harwell, M., Computing elementary symmetric functions and their derivatives: A didactic, Appl. Psychol. Meas., 20, 2, 169-192 (1996) [14] Jiang, H.; Graillat, S.; Barrio, R., Accurate and Fast Evaluation of Elementary Symmetric Functions, Proceedings of 21st IEEE Symposium on Computer Arithmetic, 183-190 (2013), IEEE Computer Society [15] Higham, N., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010 [16] Knuth, D., The art of computer programming: Seminumerical algorithms, 2 (1998), Addison-Wesley · Zbl 0895.65001 [17] Dekker, T. J., A floating-point technique for extending the available precision, Numer. Math, 18, 3, 224-242 (1971) · Zbl 0226.65034 [18] Langlois, P.; Louvet, N., How to ensure a faithful polynomial evaluation with the compensated Horner algorithm, Proceedings of 18th IEEE Symposium on Computer Arithmetic, 141-149 (2007), IEEE Computer Society [19] Graillat, S.; Morain, V., Error-free transformations in real and complex floating-point arithmetic, Proceedings of the International Symposium on Nonlinear Theory and its Applications, 341-344 (2007) [20] Caprani, O., Roundoff errors in floating-point summation, BIT, 15, 5-9 (1975) · Zbl 0301.65020 [21] Jiang, H.; Graillat, S.; Hu, C. B.; Li, S. G.; Liao, X. K.; Cheng, L. Z.; Su, F., Accurate evaluation of the kth derivative of a polynomial and its application, J. Comput. Appl. Math., 243, 28-47 (2013) [22] Miller, W., Graph transformations for roundoff analysis, SIAM J. Comput., 5, 204-216 (1976) · Zbl 0327.65038 [23] Rehman, R., Numerical computation of the characteristic polynomial of a complex matrix (2010), North Carolina State University: North Carolina State University Raleigh, NC, Phd thesis [24] Bailey, D. H.; Hida, Y.; Li, X. S.; Thompson, B., ARPREC: an arbitrary precision computation package, Technical report (2002), Lawrence Berkeley National Laboratory [25] Brent, R. P., A FORTRAN multiple-precision arithmetic package, ACM Trans. Math. Softw., 4, 1, 57-70 (1978) [26] Fousse, L.; Hanrot, G.; lefèvre, V.; Pélissier, P.; Zimmermann, P., MPFR: A Multiple-precision binary floating-point library with correct rounding, ACM Trans. Math. Softw., 33, 2, 13:1-13:15 (2007) · Zbl 1365.65302 [27] D.H. Bailey, Library for Double-Double and Quad-Double Arithmetic (QD library), Retrieved from http://crd-legacy.lbl.gov/ dhbailey/mpdist/; D.H. Bailey, Library for Double-Double and Quad-Double Arithmetic (QD library), Retrieved from http://crd-legacy.lbl.gov/ dhbailey/mpdist/ [28] Li, X.; Demmel, J.; Bailey, D.; Henry, G.; Hida, Y.; Iskandar, J.; Kahan, W.; Kang, S.; Kapur, A.; Martin, M., Design, implementation and testing of extended and mixed precision blas, ACM Trans. Math. Softw., 28, 2, 152-205 (2002) · Zbl 1070.65523 [29] Louvet, N., Compensated algorithms in floating-point arithmetic: accuracy, validation, performances (2007), Université de Perpignan Via Domitia, Phd thesis [30] Lauter, C., Basic building blocks for a triple-double intermediate format, Technical report RR2005-38 (2005), LIP: LIP France [31] Hida, Y.; Li, X.; Bailey, D. H., Algorithms for quad-double precision floating-point arithmetic, Proceedings 15th IEEE Symposium on Computer Arithmetic, 155-162 (2001), IEEE Computer Society [32] Langlois, P.; Louvet, N., More instruction level parallelism explains the actual efficiency of compensated algorithms, Technical report, hal-00165020 (2007), DALI Research Team, University of Perpignan: DALI Research Team, University of Perpignan France 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.