License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7759
URL: http://drops.dagstuhl.de/opus/volltexte/2006/775/

Giesbrecht, Mark ; Labahn, George ; Lee, Wen-Shin

Probabilistically Stable Numerical Sparse Polynomial Interpolation

pdf-format:
Dokument 1.pdf (244 KB)


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.

BibTeX - Entry

@InProceedings{giesbrecht_et_al:DSP:2006:775,
  author =	{Mark Giesbrecht and George Labahn and Wen-Shin Lee},
  title =	{Probabilistically Stable Numerical Sparse Polynomial Interpolation},
  booktitle =	{Challenges in Symbolic Computation Software},
  year =	{2006},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt },
  number =	{06271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/775},
  annote =	{Keywords: Symbolic-numeric computing, multivariate interpolation, sparse polynomial}
}

Keywords: Symbolic-numeric computing, multivariate interpolation, sparse polynomial
Seminar: 06271 - Challenges in Symbolic Computation Software
Issue date: 2006
Date of publication: 25.10.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI