Tuesday, January 31, 2006
4:30 pm
5130 Upson Hall

Computer Science
Spring 2006

Ioana Dumitriu
University of California, Berkeley


Toward accurate polynomial evaluation in rounded arithmetic


Given a multivariate (real or complex) polynomial $p$ and a (real or complex) domain $\mathcal{D}$, we would like to decide if there is an algorithm that can evaluate $p$ accurately (i.e., with relative error less than $1$), using rounded (real or complex) "traditional model" arithmetic. We consider this problem both in the classical setting (where the operations are $+$, $-$, $\times$) and in a black-box setting (where other polynomial operations are allowed). We obtain necessary and sufficient conditions for $p$ to be accurately evaluable on $\mathcal{D}$ when $\mathcal{D} = \mathbb{R}^n$ or $\mathbb{C}^n $, and also for some smaller domains. I will also indicate progress toward constructing a complete decision procedure.