Acta Numerica

Research Article

Accurate and efficient expression evaluation and linear algebra

James Demmela1*, Ioana Dumitriua2, Olga Holtza3 and Plamen Koeva4§

a1 Department of Mathematics and Computer Science Division, University of California, Berkeley, CA 94720, USA

a2 Department of Mathematics, University of Washington, Seattle, WA 98195, USA

a3 Department of Mathematics, University of California, Berkeley, CA 94720, USA and Department of Mathematics, Technische Universität Berlin, D-10623, Berlin, Germany

a4 Department of Mathematics, North Carolina State University, Raleigh, NC 27695, USA

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.

Footnotes

* Supported by NSF grants CCF-0444486, CNS 0325873, by DOE grant DE-FC02-06ER25786, and by the University of California, Berkeley, Richard Carl Dehmel Distinguished Professorship.

† Supported by the Miller Institute for Basic Research in Science.

‡ Supported by the Sofja Kovalevskaja programme of the Alexander von Humboldt Foundation.

§ Supported by NSF grants DMS-0314286, DMS-0411962 and DMS-0608306.