Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T02:04:09.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Accurate and efficient expression evaluation and linear algebra

Published online by Cambridge University Press:  25 April 2008

James Demmel ,
Ioana Dumitriu ,
Olga Holtz  and
Plamen Koev
James Demmel
Affiliation:
Department of Mathematics and Computer Science Division, University of California, Berkeley, CA 94720, USA
Ioana Dumitriu
Affiliation:
Department of Mathematics, University of Washington, Seattle, WA 98195, USA
Olga Holtz
Affiliation:
Department of Mathematics, University of California, Berkeley, CA 94720, USA and Department of Mathematics, Technische Universität Berlin, D-10623, Berlin, Germany
Plamen Koev
Affiliation:
Department of Mathematics, North Carolina State University, Raleigh, NC 27695, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We survey and unify recent results on the existence of accurate algorithms for evaluating multivariate polynomials, and more generally for accurate numerical linear algebra with structured matrices. By ‘accurate’ we mean that the computed answer has relative error less than 1, i.e., has some correct leading digits. We also address efficiency, by which we mean algorithms that run in polynomial time in the size of the input. Our results will depend strongly on the model of arithmetic: most of our results will use the so-called traditional model (TM), where the computed result of op(a, b), a binary operation like a+b, is given by op(a, b) * (1+δ) where all we know is that |δ| ≤ ε ≪ 1. Here ε is a constant also known as machine epsilon.

We will see a common reason for the following disparate problems to permit accurate and efficient algorithms using only the four basic arithmetic operations: finding the eigenvalues of a suitably discretized scalar elliptic PDE, finding eigenvalues of arbitrary products, inverses, or Schur complements of totally non-negative matrices (such as Cauchy and Vandermonde), and evaluating the Motzkin polynomial. Furthermore, in all these cases the high accuracy is ‘deserved’, i.e., the answer is determined much more accurately by the data than the conventional condition number would suggest.

In contrast, we will see that evaluating even the simple polynomial x + y + z accurately is impossible in the TM, using only the basic arithmetic operations. We give a set of necessary and sufficient conditions to decide whether a high accuracy algorithm exists in the TM, and describe progress toward a decision procedure that will take any problem and provide either a high-accuracy algorithm or a proof that none exists.

When no accurate algorithm exists in the TM, it is natural to extend the set of available accurate operations by a library of additional operations, such as x + y + z, dot products, or indeed any enumerable set which could then be used to build further accurate algorithms. We show how our accurate algorithms and decision procedure for finding them extend to this case.

Finally, we address other models of arithmetic, and the relationship between (im)possibility in the TM and (in)efficient algorithms operating on numbers represented as bit strings.

Type
Research Article
Information
Acta Numerica , Volume 17 , May 2008 , pp. 87 - 145
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aho, A. V., Hopcroft, J. E. and Ullman, J. D. (1975), The Design and Analysis of Computer Algorithms, second printing, Addison-Wesley Series in Computer Science and Information Processing.Google Scholar
Alfa, A. S., Xue, J. and Ye, Q. (2002), ‘Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix’, Math. Comp. 71, 217–236 (electronic).CrossRefGoogle Scholar
Anderson, E., Bai, Z., Bischof, C., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Blackford, S. and Sorensen, D. (1999), LAPACK Users' Guide, third edn, SIAM, Philadelphia.CrossRefGoogle Scholar
Björck, Å. and Pereyra, V. (1970), ‘Solution of Vandermonde systems of equations’, Math. Comp. 24, 893–903.CrossRefGoogle Scholar
Boman, E., Hendrickson, B. and Vavasis, S. (2004), ‘Solving elliptic finite element systems in near-linear time with support preconditioners’, arXiv.org:cs/0407022.Google Scholar
Boros, T., Kailath, T. and Olshevsky, V. (1999), ‘A fast Björck–Pereyra-type algorithm for parallel solution of Cauchy linear equations’, Linear Algebra Appl. 302/303, 265–293.CrossRefGoogle Scholar
Chan, T. (1987), ‘Rank revealing QR factorizations’, Linear Algebra Appl. 88/89, 67–82.CrossRefGoogle Scholar
Chandrasekaran, S. and Ipsen, I. (1994), ‘On rank-revealing QR factorizations’, SIAM J. Matrix Anal. Appl.CrossRefGoogle Scholar
Clarkson, K. (1992), Safe and effective determinant evaluation, in 33rd Annual Symposium on Foundations of Computer Science, pp. 387–395.Google Scholar
Demmel, J. (1987), ‘On condition numbers and the distance to the nearest ill-posed problem’, Numer. Math. 51, 251–289.CrossRefGoogle Scholar
Demmel, J. (1999), ‘Accurate singular value decompositions of structured matrices’, SIAM J. Matrix Anal. Appl. 21, 562–580 (electronic).CrossRefGoogle Scholar
Demmel, J. and Gragg, W. (1993), ‘On computing accurate singular values and eigenvalues of acyclic matrices’, Linear Algebra Appl. 185, 203–218.CrossRefGoogle Scholar
Demmel, J. and Hida, Y. (2003), ‘Accurate and efficient floating point summation’, SIAM J. Sci. Comput. 25, 1214–1248.CrossRefGoogle Scholar
Demmel, J. and Kahan, W. (1990), ‘Accurate singular values of bidiagonal matrices’, SIAM J. Sci. Statist. Comput. 11, 873–912.CrossRefGoogle Scholar
Demmel, J. and Koev, P. (2001), Necessary and sufficient conditions for accurate and efficient rational function evaluation and factorizations of rational matrices. In Structured Matrices in Mathematics, Computer Science, and Engineering II (Boulder, CO, 1999), Vol. 281 of Contemporary Mathematics, AMS, Providence, RI, pp. 117–143.Google Scholar
Demmel, J. and Koev, P. (2004 a), Accurate and efficient algorithms for floating point computation. In Applied Mathematics Entering the 21st Century, SIAM, Philadelphia, PA, pp. 73–88.Google Scholar
Demmel, J. and Koev, P. (2004 b), ‘Accurate SVDs of weakly diagonally dominant M-matrices’, Numer. Math. 98, 99–104.CrossRefGoogle Scholar
Demmel, J. and Koev, P. (2005), ‘The accurate and efficient solution of a totally positive generalized Vandermonde linear system’, SIAM J. Matrix Anal. Appl. 27, 142–152 (electronic).CrossRefGoogle Scholar
Demmel, J. and Koev, P. (2006), ‘Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials’, Linear Algebra Appl. 417, 382–396.CrossRefGoogle Scholar
Demmel, J. and Veselić, K. (1992), ‘Jacobi's method is more accurate than QR’, SIAM J. Matrix Anal. Appl. 13, 1204–1246.CrossRefGoogle Scholar
Demmel, J., Diament, B. and Malajovich, G. (2001), ‘On the complexity of computing error bounds’, in Found. Comput. Math. 1, 101–125.CrossRefGoogle Scholar
Demmel, J., Dumitriu, I. and Holtz, O. (2006), Toward accurate polynomial evaluation in rounded arithmetic. In Foundations of Computational Mathematics (Santander 2005), Vol. 331 of London Mathematical Society Lecture Notes, Cambridge University Press, Cambridge, pp. 36–105.Google Scholar
Demmel, J., Gu, M., Eisenstat, S., Slapničar, I., Veselić, K. and Drmač, Z. (1999), ‘Computing the singular value decomposition with high relative accuracy’, Linear Algebra Appl. 299, 21–80.CrossRefGoogle Scholar
Dopico, F. M., Molera, J. M. and Moro, J. (2003), ‘An orthogonal high relative accuracy algorithm for the symmetric eigenproblem’, SIAM J. Matrix Anal. Appl. 25, 301–351 (electronic).CrossRefGoogle Scholar
Drmač, Z. (1998), ‘Accurate computation of the product induced singular value decomposition with applications’, SIAM J. Numer. Anal. 35, 1969–1994.CrossRefGoogle Scholar
Eisenstat, S. and Ipsen, I. (1995), ‘Relative perturbation techniques for singular value problems’, SIAM J. Numer. Anal.CrossRefGoogle Scholar
Fallat, S. M. (2001), ‘Bidiagonal factorizations of totally nonnegative matrices’, Amer. Math. Monthly 108, 697–712.CrossRefGoogle Scholar
Farahat, H. K. (1958), ‘On Schur functions’, Proc. London Math. Soc. (3) 8, 621–630.CrossRefGoogle Scholar
Gantmacher, F. P. and Krein, M. G. (2002), Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, revised edn, AMS Chelsea Publishing, Providence, RI. Translation based on the 1941 Russian original.CrossRefGoogle Scholar
Gasca, M. and Peña, J. M. (1992), ‘Total positivity and Neville elimination’, Linear Algebra Appl. 165, 25–44.CrossRefGoogle Scholar
Gasca, M. and Peña, J. M. (1996), On factorizations of totally positive matrices, in Total Positivity and its Applications, Kluwer, Dordrecht, pp. 109–130.CrossRefGoogle Scholar
Gu, M. and Eisenstat, S. (1996), ‘An efficient algorithm for computing a strong rank-revealing QR factorization’, SIAM J. Sci. Comput. 17, 848–869.CrossRefGoogle Scholar
Higham, N. J. (1987), ‘Error analysis of the Björck–Pereyra algorithms for solving Vandermonde systems’, Numer. Math. 50, 613–632.CrossRefGoogle Scholar
Higham, N. J. (1988), ‘Fast solution of Vandermonde-like systems involving orthogonal polynomials’, IMA J. Numer. Anal. 8, 473–486.CrossRefGoogle Scholar
Higham, N. J. (1990), ‘Stability analysis of algorithms for solving confluent Vandermonde-like systems’, SIAM J. Matrix Anal. Appl. 11, 23–41.CrossRefGoogle Scholar
Holtz, O. (2005), ‘The inverse eigenvalue problem for symmetric anti-bidiagonal matrices’, Linear Algebra Appl. 408, 268–274.CrossRefGoogle Scholar
Hong, P. and Pan, C. T. (1992), ‘Rank-revealing QR factorizations and the singular value decomposition’, Math. Comp. 58, 213–232.Google Scholar
Hwang, T.-M., Lin, W.-W. and Yang, E. K. (1992), ‘Rank revealing LU factorization’, Linear Algebra Appl. 175, 115–141.CrossRefGoogle Scholar
Ikebe, Y. (1979), ‘On inverses of Hessenberg matrices’, Linear Algebra Appl. 24, 93–97.CrossRefGoogle Scholar
Kahan, W. and Farkas, I. (1963 a), ‘Algorithm 167: Calculation of confluent divided differences’, Commun. ACM 6, 164–165.CrossRefGoogle Scholar
Kahan, W. and Farkas, I. (1963 b), ‘Algorithm 168: Newton interpolation with backward divided differences’, Commun. ACM 6, 165.Google Scholar
Kahan, W. and Farkas, I. (1963 c), ‘Algorithm 169: Newton interpolation with forward divided differences’, Commun. ACM 6, 165.Google Scholar
Kailath, T. and Olshevsky, V. (1995), ‘Displacement structure approach to Chebyshev–Vandermonde and related matrices’, Integral Equations Operator Theory 22, 65–92.CrossRefGoogle Scholar
Kailath, T. and Olshevsky, V. (1997), ‘Displacement-structure approach to polynomial Vandermonde and related matrices’, Linear Algebra Appl. 261, 49–90.CrossRefGoogle Scholar
Karlin, S. (1968), Total Positivity, Vol. I, Stanford University Press, Stanford, CA.Google Scholar
Koev, P. (2005), ‘Accurate eigenvalues and SVDs of totally nonnegative matrices’, SIAM J. Matrix Anal. Appl. 27, 1–23 (electronic).CrossRefGoogle Scholar
Koev, P. (2007), ‘Accurate computations with totally nonnegative matrices’, SIAM J. Matrix Anal. Appl. 29, 731–751.CrossRefGoogle Scholar
Koev, P. and Dopico, F. (2007), ‘Accurate eigenvalues of certain sign regular matrices’, Linear Algebra Appl. 424, 435–447.CrossRefGoogle Scholar
Li, R.-C. (1999), ‘Relative perturbation theory II: Eigenspace and singular subspace variations’, SIAM J. Matrix Anal. Appl. 20, 471–492 (electronic).CrossRefGoogle Scholar
Macdonald, I. G. (1998), Symmetric Functions and Orthogonal Polynomials, Vol. 12 of University Lecture Series, AMS, Providence, RI.Google Scholar
Marco, A. and Martínez, J.-J. (2007), ‘A fast and accurate algorithm for solving Bernstein–Vandermonde linear systems’, Linear Algebra Appl. 422, 616–628.CrossRefGoogle Scholar
Martínez, J. J. and Peña, J. M. (1998), ‘Fast algorithms of Björck–Pereyra type for solving Cauchy–Vandermonde linear systems’, Appl. Numer. Math. 26, 343–352.CrossRefGoogle Scholar
Martínez, J. J. and Peña, J. M. (1998), ‘Factorizations of Cauchy–Vandermonde matrices’, Linear Algebra Appl. 284, 229–237.CrossRefGoogle Scholar
Martínez, J. J. and Peña, J. M. (2003), Factorizations of Cauchy–Vandermonde matrices with one multiple pole. In Recent Research on Pure and Applied Algebra, Nova Scientific, Hauppauge, NY, pp. 85–95.Google Scholar
The Math Works (1992), MATLAB Reference Guide, The Math Works, Natick, MA.Google Scholar
Mathias, R. (1996), ‘Accurate eigensystem computations by Jacobi methods’, SIAM J. Matrix Anal. Appl. 16, 977–1003.CrossRefGoogle Scholar
Miller, E. and Sturmfels, B. (2005), Combinatorial Commutative Algebra, Vol. 227 of Graduate Texts in Mathematics, Springer, New York.Google Scholar
Miranian, L. and Gu, M. (2003), ‘Strong rank revealing LU factorizations’, Linear Algebra Appl. 367, 1–16.CrossRefGoogle Scholar
Nabben, R. (1999), ‘Decay rates of the inverse of nonsymmetric tridiagonal and band matrices’, SIAM J. Matrix Anal. Appl. 20, 820–837.CrossRefGoogle Scholar
O'Cinneide, C. (1996), ‘Relative-error for the LU decomposition via the GTH algorithm’, Numer. Math. 73, 507–519.CrossRefGoogle Scholar
Parlett, B. (1995), The new qd algorithms, in Acta Numerica, Vol. 4, Cambridge University Press, pp. 459–491.Google Scholar
Peláez, M. J. and Moro, J. (2006), ‘Accurate factorization and eigenvalue algorithms for symmetric DSTU and TSC matrices’, SIAM J. Matrix Anal. Appl. 28, 1173–1198 (electronic).CrossRefGoogle Scholar
Peña, J. M. (2004), ‘LDU decompositions with L and U well conditioned’, Electron. Trans. Numer. Anal. 18, 198–208 (electronic).Google Scholar
Renegar, J. (1992), ‘On the computational complexity and geometry of the first-order theory of the reals I: Introduction. Preliminaries. The geometry of semialgebraic sets. The decision problem for the existential theory of the reals’, J. Symbolic Comput. 13, 255–299.CrossRefGoogle Scholar
Reznick, B. (2000), Some Concrete Aspects of Hilbert's 17th Problem, Vol. 253 of Contemporary Mathematics, AMS.Google Scholar
Rump, S. (1998), ‘Structured perturbations and symmetric matrices’, Linear Algebra Appl. 278, 121–132.CrossRefGoogle Scholar
Rump, S. (1999 a), ‘Ill-conditioned matrices are componentwise near to singularity’, SIAM Review 41, 102–112.CrossRefGoogle Scholar
Rump, S. (1999 b), ‘Ill-conditionedness need not be componentwise near to illposedness for least squares problems’, BIT 39, 143–151.CrossRefGoogle Scholar
Rump, S. (2003 a), ‘Structured perturbations I: Normwise distances’, SIAM J. Matrix Anal. Appl. 25, 1–30.CrossRefGoogle Scholar
Rump, S. (2003 b), ‘Structured perturbations II: Componentwise distances’, SIAM J. Matrix Anal. Appl. 25, 31–56.CrossRefGoogle Scholar
Shewchuk, J. R. (1997), ‘Adaptive precision floating-point arithmetic and fast robust geometric predicates’, Discrete Comput. Geom. 18, 305–363.CrossRefGoogle Scholar
Stanley, R. P. (1999), Enumerative Combinatorics 2, Vol. 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.CrossRefGoogle Scholar
Stewart, G. W. (1993), ‘Updating a rank-revealing ULV decomposition’, SIAM J. Matrix Anal. Appl. 14, 494–499.CrossRefGoogle Scholar
Tarski, A. (1951), A Decision Method for Elementary Algebra and Geometry, University of California Press, Berkeley.CrossRefGoogle Scholar
Taylor, J. (2004), Several Complex Variables with Connections to Algebraic Geometry and Lie Groups, AMS Series on Graduate Studies in Mathematics, AMS.Google Scholar
Valiant, L. G. (1979), ‘The complexity of computing the permanent’, Theoret. Comput. Sci. 8, 189–201.CrossRefGoogle Scholar
Ye, Q. (2008 a), ‘Computing singular values of diagonally dominant matrices to high relative accuracy’, Math. Comp., to appear.CrossRefGoogle Scholar
Ye, Q. (2008 b), ‘Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matrices’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Ziegler, G. M. (1995), Lectures on Polytopes, Vol. 152 of Graduate Texts in Mathematics, Springer, New York.CrossRefGoogle Scholar