×

Accurate and efficient expression evaluation and linear algebra. (English) Zbl 1169.65022

The authors discuss the accuracy and efficiency of algorithms for the numerical evaluation of multivariate polynomials and for numerical linear algebra with certain structured matrices. Specifically, the goal is to find algorithms that are efficient (in the sense that their computational complexity is polynomial in terms of the size of the input) and accurate (in the sense that the result has at least one correct leading digit).
In the traditional model of arithmetic, where the relative error of a binary operation is less than machine epsilon, the authors show that efficient and accurate algorithms exist for a large number of concrete tasks like finding eigenvalues of arbitrary products of totally non-negative matrices, the inversion of such matrices, the computation of their Schur complements, etc. On the other hand it turns out that for the formally very simple task of computing the trivariate polynomial \(x+y+z\) no such algorithm exists in the traditional model.
This survey paper presents a very thorough investigation of the background of these observations and the resulting consequences for a large class of algorithms and elaborates on extended models of arithmetic that do not have the disadvantages of the traditional model.

MSC:

65D20 Computation of special functions and constants, construction of tables
65G50 Roundoff error
65F30 Other matrix algorithms (MSC2010)
65D15 Algorithms for approximation of functions
65Y20 Complexity and performance of numerical algorithms
65F05 Direct numerical methods for linear systems and matrix inversion
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis

Software:

Hull; LAPACK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Eisenstat, SIAM J. Numer. Anal. (1995)
[2] Stanley, Enumerative Combinatorics 2 62 (1999) · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[3] MATLAB Reference Guide (1992)
[4] Martínez, Recent Research on Pure and Applied Algebra pp 85– (2003)
[5] Gantmacher, Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems (2002) · Zbl 1002.74002 · doi:10.1090/chel/345
[6] Demmel, Foundations of Computational Mathematics 331 pp 36– (2006)
[7] Macdonald, Symmetric Functions and Orthogonal Polynomials 12 (1998) · Zbl 0887.05053
[8] Reznick, Some Concrete Aspects of Hilbert’s 17th Problem 253 (2000) · Zbl 0972.11021
[9] Anderson, LAPACK Users’ Guide (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604
[10] Peña, Electron. Trans. Numer. Anal. 18 pp 198– (2004)
[11] Aho, The Design and Analysis of Computer Algorithms (1975)
[12] Gasca, Total Positivity and its Applications pp 109– (1996) · doi:10.1007/978-94-015-8674-0_7
[13] Parlett, Acta Numerica 4 pp 459– (1995)
[14] Ziegler, Lectures on Polytopes 152 (1995) · Zbl 0823.52002 · doi:10.1007/978-1-4613-8431-1
[15] Ye, SIAM J. Matrix Anal. Appl. (2008)
[16] Demmel, Applied Mathematics Entering the 21st Century pp 73– (2004)
[17] Ye, Math. Comp. (2008)
[18] Demmel, Structured Matrices in Mathematics, Computer Science, and Engineering II 281 pp 117– (2001) · doi:10.1090/conm/281/04652
[19] Karlin, Total Positivity I (1968)
[20] Taylor, Several Complex Variables with Connections to Algebraic Geometry and Lie Groups (2004)
[21] Tarski, A Decision Method for Elementary Algebra and Geometry (1951) · Zbl 0044.25102
[22] Miller, Combinatorial Commutative Algebra 227 (2005) · Zbl 1090.13001
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.