Accurate, validated and fast evaluation of elementary symmetric functions and its application

摘要

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 poly 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.