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

Hao Jiang, Stef Graillat, Roberto Barrio and Canqun Yang

Applied Mathematics and Computation, 2016, vol. 273, issue C, 1160-1178

Abstract: 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.

Keywords: Elementary symmetric functions; Floating-point arithmetic; Roundoff error; Error-free transformation; Compensated algorithm; Accurate algorithm (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315012151
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:273:y:2016:i:c:p:1160-1178

DOI: 10.1016/j.amc.2015.08.134

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().