Ioana Dumitriu
Mathematics Department
University of Washington
The recent proliferation of structured matrix classes on which linear algebra operations can be performed accurately hints at the existence of an underlying algebraic property. Here accurately means "with relative accuracy" (i.e. the computed value is only a percentage away from the true one). Demmel and Koev (2004) showed that a necessary condition for accurate LA operations (LU, SVD, EIG, inv(), etc.) to be performed on a matrix is for the determinant of that matrix (as a polynomial in the entries) to be accurately evaluable.
With this as motivation, we consider the problem of evaluating multivariate (real or complex) polynomials accurately over real or complex domains. The answer turns out to depend on the variety (set of zeros) of the polynomial, as well as the basic (i.e. accurate) arithmetic operations allowed. Our ultimate goal is to establish a decision procedure that, for any polynomial $p$ and domain $\mathcal{D}$, either exhibits an accurate algorithm, or produces a ``minimal" set of operations (e.g. computing $2 \times 2$ determinants) that have to be added to the arithmetic (i.e. implemented with extra accuracy) in order to make the polynomial (or class of polynomials) evaluable.
We found necessary and sufficient conditions for this to happen, and made significant process toward such a decision procedure. Along the way, we also obtained ``negative" results: some classes of polynomials turn out to not be evaluable with any set (possibly infinite!) of bounded-degree operations (e.g., for certain classes of structured matrices, one has to go to arbitrary precision in order to perform linear algebra accurately).
This is joint work with Jim Demmel and Olga Holtz.