From quotient-difference to generalized eigenvalues and sparse polynomial interpolation

Citation

Lee W (2007) From quotient-difference to generalized eigenvalues and sparse polynomial interpolation. In: SNC '07 Proceedings of the 2007 international workshop on Symbolic-numeric computation. Symbolic-Numeric Computation 2007 (SNC 2007), London, Ontario, Canada, 25.07.2007-27.07.2007. New York: ACM, pp. 110-116. https://dl.acm.org/citation.cfm?id=1277518

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 coefficients. 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.

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

Notes
DOI

People

Dr Wen-shin Lee

Lecturer, Computing Science and Mathematics - Division