DROPS

Document

Probabilistically Stable Numerical Sparse Polynomial Interpolation

Authors: Mark Giesbrecht, George Labahn, and Wen-Shin Lee

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract

We consider the problem of sparse interpolation of a multivariate black-box polynomial in floating-point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all values are represented in standard, fixed-precision, floating-point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give an efficient and numerically robust solution with high probability. We outline the numerical stability of our algorithm, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques through numerical experiments.

Cite as

Mark Giesbrecht, George Labahn, and Wen-Shin Lee. Probabilistically Stable Numerical Sparse Polynomial Interpolation. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{giesbrecht_et_al:DagSemProc.06271.14,
  author =	{Giesbrecht, Mark and Labahn, George and Lee, Wen-Shin},
  title =	{{Probabilistically Stable Numerical Sparse Polynomial Interpolation}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.14},
  URN =		{urn:nbn:de:0030-drops-7759},
  doi =		{10.4230/DagSemProc.06271.14},
  annote =	{Keywords: Symbolic-numeric computing, multivariate interpolation, sparse polynomial}
}

Search Results

Documents authored by Giesbrecht, Mark

Probabilistically Stable Numerical Sparse Polynomial Interpolation

Abstract

Cite as

Thanks for your feedback!

Could not send message