From quotient-difference to generalized eigenvalues and sparse polynomial interpolation

ABSTRACT

The numerical quotient-difference algorithm,or the qd-algorithm, can be used for determining the poles of a meromorphic function directly from its Taylor coeffcients. We show that the poles computed in the qd-algorithm, regardless of their multiplicities,are converging to the solution of a generalized eigenvalue problem. In a special case when all the poles are simple,such generalized eigenvalue problem can be viewed as a reformulation of Prony 's method,a method that is closely related to the Ben-Or/Tiwari algorithm for interpolating a multivariate sparse polynomial in computer algebra.

REFERENCES

• 1: 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]
• 2: Brezinski, C. Pad é type approximation and general orthogonal polynomials. ISNM 50,Birkhauser Verlag, Basel, 1980.
• 3: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 4: Chaffy, C. Interpolation polynomiale et rationnelle d'une fonction de plusieurs variables complexes. Thése, Inst. Polytech. Grenoble, 1984.
• 5: Cuyt, A. On the convergence of the multivariate "homogeneous "qd-algorithm. BIT 34 (1994), 535--545.
• 6: Cuyt, A., and Verdonk, B. Extending the qd-algorithm to tackle multivariate problems. In Computational methods and function theory (CMFT'97) (1999), N. Papamichael, S. Ruscheweyh, and B. Sa, Eds., pp. 135--159.
• 7: Dornstetter, J. L. On the equivalence between Berlekamp's and Euclid's algorithms. IEEE Trans.
• 8: Fernando, K., and Parlett, B. Accurate singular values and differential qd algorithms. Numer. Math. 67 (1994), 191--229.
• 9: Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145792]
• 10: 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]
• 11: Peter Henrici, Applied and computational complex analysis. Vol. 3: discrete Fourier analysis—Cauchy integrals—construction of conformal maps---univalent functions, John Wiley & Sons, Inc., New York, NY, 1986
• 12: Begnaud Francis Hildebrand, Introduction to numerical analysis: 2nd edition, Dover Publications, Inc., New York, NY, 1987
• 13: Householder, A. The numerical treatment of a single nonlinear equation. McGraw-Hill, New York, 1970.
• 14: Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345629]
• 15: Kravanja, P. On computing zeros of analytic functions and related problems in structured numerical linear algebra. PhD thesis, Katholieke Universiteit Leuven, Heverlee, Belgium, March 1999.
• 16: Kravanja, P., and Van Barel, M. Computing the zeros of analytic functions. LNM 1727, Springer Verlag, Berlin, 2000.
• 17: Massey, J. L. Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory it 15 (1969), 122--127.
• 18: Parlett, B. The new qd algorithms. Acta Numerica (1995), 459--491.
• 19: Prony, R. Essai expérimental et analytique sur les lois de la Dilatabilité des uidesélastique et sur celles de la Force expansive de la vapeur de l'eau et de la vapeur de l'alkool, ádiérentes températures. J. de l' École Polytechnique 1 (Floréal et Prairial III (1795)), 24--76. R. Prony is Gaspard(-Clair-Françcois-Marie) Riche, Baron de Prony.
• 20: Rutishauser, H. Der Quotienten-Differenzen-Algorithmus. Z. Angew. Math. Phys.5 (1954), 233--251.
• 21: Rutishauser, H. Lectures on Numerical Mathematics. Birkhäuser, 1990.
• 22: Urs von Matt, The Orthogonal qd-Algorithm, SIAM Journal on Scientific Computing, v.18 n.4, p.1163-1186, July 1997 [doi>10.1137/S1064827594274887]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Rational approximation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
Ben-Or/Tiwari algorithm, Prony's method, generalized eigenvalue, qd-algorithm, sparse polynomial interpolation