Giesbrecht, Mark ;
Labahn, George ;
Lee, Wen-Shin
Probabilistically Stable Numerical Sparse Polynomial Interpolation
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: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/opus/volltexte/2006/775},
URN = {urn:nbn:de:0030-drops-7759},
doi = {10.4230/DagSemProc.06271.14},
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 |
25.10.2006
