Symbolic-numeric sparse interpolation of multivariate polynomials

ABSTRACT

We consider the problem of sparse interpolation of an approximate 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 numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony's method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We analyze the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.

REFERENCES

• 1: B. Beckermann. The condition number of real Vandermonde, Krylov and positive definite Hankel matrices. Numeriche Mathematik, 85:553--577, 2000.
• 2: B. Beckermann, G. Golub, and G. Labahn. On the numerical condition of a generalized Hankel eigenvalue problem. submitted to Numerische Matematik, 2005.
• 3: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 4: A. Córdova, W. Gautschi, and S. Ruscheweyh. Vandermonde matrices on the circle: spectral properties and conditioning. Numerische Mathematik, 57:577--591, 1990.
• 5: Robert M. Corless , Mark Giesbrecht , Ilias S. Kotsireas , Stephen M. Watt, Numerical Implicitization of Parametric Hypersurfaces with Linear Algebra, Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation, p.174-183, July 17-19, 2000
• 6: Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
• 7: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 8: Mariano Gasca , Thomas Sauer, On the history of multivariate polynomial interpolation, Journal of Computational and Applied Mathematics, v.122 n.1-2, p.23-35, Oct. 1, 2000 [doi>10.1016/S0377-0427(00)00353-8]
• 9: W. Gautschi. Norm estimates for inverses of Vandermonde matrices. Numerische Mathematik, 23:337--347, 1975.
• 10: W. Gautschi and G. Inglese. Lower bounds for the condition numbers of Vandermonde matrices. Numerische Mathematik, 52:241--250, 1988.
• 11: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 12: Gene H. Golub , Peyman Milanfar , James Varah, A Stable Numerical Method for Inverting Shape from Moments, SIAM Journal on Scientific Computing, v.21 n.4, p.1222-1243, Dec. 1999—March 2000 [doi>10.1137/S1064827597328315]
• 13: G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, Maryland, third edition, 1996.
• 14: Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
• 15: Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
• 16: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 17: L. Kronecker. Über einige Interpolationsformeln für ganze Funktionen mehrerer Variabeln, Lecture at the academy of sciences, December 21, 1865, volume H. Hensel (Ed.), L. Kroneckers Werke, Vol. I. Teubner, Stuttgart, 1895. reprinted by Chelsea, New York, 1968.
• 18: R. A. Lorentz, Multivariate Hermite interpolation by algebraic polynomials: a survey, Journal of Computational and Applied Mathematics, v.122 n.1-2, p.167-201, Oct. 1, 2000 [doi>10.1016/S0377-0427(00)00367-8]
• 19: Yishay Mansour, Randomized Interpolation and Approximationof Sparse Polynomials, SIAM Journal on Computing, v.24 n.2, p.357-368, April 1995 [doi>10.1137/S0097539792239291]
• 20: P. Milanfar, G. C. Verghese, W. C. Karl, and A. S. Wilsky. Reconstructing polygons from moments with connections to array processing. IEEE Trans. Signal Processing, 43(2):432--443, 1995.
• 21: Baron de Prony, Gaspard-Clair-François-Marie Riche. Essai expérimental et analytique sur les lois de la Dilatabilité des fluides élastique et sur celles de la Force expansive de la vapeur de l'eau et de la vapeur de l'alkool, à différentes températures. J. de l'École Polytechnique, 1:24--76, 1795.
• 22: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical factorization of multivariate complex polynomials, Theoretical Computer Science, v.315 n.2-3, p.651-669, 6 May 2004 [doi>10.1016/j.tcs.2004.01.011]
• 23: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 24: Zeljko Zilic , Katarzyna Radecka, On feasible multivariate polynomial interpolations over arbitrary fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.67-74, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309863]
• 25: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 26: Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms

Keywords:
multivariate interpolation, symbolic-numeric computing