Search Results

Documents authored by Demmel, James


Document
Toward accurate polynomial evaluation in rounded arithmetic (short report)

Authors: James Demmel, Ioana Dumitriu, and Olga Holtz

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)


Abstract
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 constants are available to the algorithm and whether branching is permitted in the algorithm. 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$, using only arithmetic operations $+$, $-$ and $cdot$.

Cite as

James Demmel, Ioana Dumitriu, and Olga Holtz. Toward accurate polynomial evaluation in rounded arithmetic (short report). In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{demmel_et_al:DagSemProc.05391.8,
  author =	{Demmel, James and Dumitriu, Ioana and Holtz, Olga},
  title =	{{Toward accurate polynomial evaluation in rounded arithmetic (short report)}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.8},
  URN =		{urn:nbn:de:0030-drops-4477},
  doi =		{10.4230/DagSemProc.05391.8},
  annote =	{Keywords: Accurate polynomial evaluation, models or rounded arithmetic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail