Toward accurate polynomial evaluation in rounded arithmetic

Details Toward accurate polynomial evaluation in rounded arithmetic Toward accurate polynomial evaluation in rounded arithmetic

2005-08-18

arxiv.org/abs/math/0508350v2

in Foundations of Computational Mathematics: Santander 2005 (L. Pardo et al, eds.) Cambridge University Press, 2006, pp. 36-10

Mathematics

Numerical Analysis

54 pages, 6 figures; refereed version; to appear in Foundations of Computational Mathematics: Santander 2005, Cambridge Univer

Scientific paper

Given a multivariate real (or complex) polynomial $p$ and a domain $\cal D$, we would like to decide whether an algorithm exists to evaluate $p(x)$ accurately for all $x \in {\cal D}$ using rounded real (or complex) arithmetic. Here ``accurately'' means with relative error less than 1, i.e., with some correct leading digits. The answer depends on the model of rounded arithmetic: We assume that for any arithmetic operator $op(a,b)$, for example $a+b$ or $a \cdot b$, its computed value is $op(a,b) \cdot (1 + \delta)$, where $| \delta |$ is bounded by some constant $\epsilon$ where $0 < \epsilon \ll 1$, but $\delta$ is otherwise arbitrary. This model is the traditional one used to analyze the accuracy of floating point algorithms.Our ultimate goal is to establish a decision procedure that, for any $p$ and $\cal D$, either exhibits an accurate algorithm or proves that none exists. In contrast to the case where numbers are stored and manipulated as finite bit strings (e.g., as floating point numbers or rational numbers) we show that some polynomials $p$ are impossible to evaluate accurately. The existence of an accurate algorithm will depend not just on $p$ and $\cal D$, but on which arithmetic operators and which constants are are available and whether branching is permitted. Toward this goal, we present necessary conditions on $p$ for it to be accurately evaluable on open real or complex domains ${\cal D}$. We also give sufficient conditions, and describe progress toward a complete decision procedure. We do present a complete decision procedure for homogeneous polynomials $p$ with integer coefficients, ${\cal D} = \C^n$, and using only the arithmetic operations $+$, $-$ and $\cdot$.

Affiliated with

Also associated with

No associations

Rating

Toward accurate polynomial evaluation in rounded arithmetic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Toward accurate polynomial evaluation in rounded arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Toward accurate polynomial evaluation in rounded arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120271