## A solution to certain polynomial equations with applications to nonlinear fitting

HTML articles powered by AMS MathViewer

- by Chris Connell PDF
- Math. Comp.
**74**(2005), 303-319 Request permission

## Abstract:

We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in $2N$ variables by reducing it to the problem of solving two special linear systems of size $N$ and rooting a single univariate polynomial of degree $N$. Over $\mathbb {C}$, all solutions can be found with fixed precision using, up to polylogarithmic factors, $O(N^2)$ bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to $O(N)$ bit operations, up to polylogarithmic factors. As an application, we show how this can be used to fit data to a complex exponential sum with $N$ terms in the same, nearly optimal, time.## References

- Ruben G. Airapetyan and Alexander G. Ramm,
*Numerical inversion of the Laplace transform from the real axis*, J. Math. Anal. Appl.**248**(2000), no. 2, 572–587. MR**1776030**, DOI 10.1006/jmaa.2000.6945 - Dario Bini, Gianna M. Del Corso, Giovanni Manzini, and Luciano Margara,
*Inversion of circulant matrices over $Z_m$*, Math. Comp.**70**(2001), no. 235, 1169–1182. MR**1710660**, DOI 10.1090/S0025-5718-00-01235-7 - G. Beylkin,
*On the fast Fourier transform of functions with singularities*, Appl. Comput. Harmon. Anal.**2**(1995), no. 4, 363–381. MR**1354915**, DOI 10.1006/acha.1995.1026 - A. B. Cain, J. H. Ferziger, and W. C. Reynolds,
*Discrete orthogonal function expansions for nonuniform grids using the fast Fourier transform*, J. Comput. Phys.**56**(1984), no. 2, 272–286. MR**768478**, DOI 10.1016/0021-9991(84)90096-2 - A. Dutt and V. Rokhlin,
*Fast Fourier transforms for nonequispaced data*, SIAM J. Sci. Comput.**14**(1993), no. 6, 1368–1393. MR**1241591**, DOI 10.1137/0914081 - D. G. Gardner, J. C. Gardner, G. Laush, and W. W. Meinke. Method for the analysis of multicomponent experimental decay curves.
*J. Chem. Phys.*, 31:978–986, 1959. - M. C. Gouveia,
*Regular Hankel matrices over integral domains*, Linear Algebra Appl.**255**(1997), 335–347. MR**1433247**, DOI 10.1016/S0024-3795(96)00003-1 - Shôkichi Iyanaga (ed.),
*Encyclopedic dictionary of mathematics. Vol. I*, Translated from the second Japanese edition, MIT Press, Cambridge, Mass.-London, 1977. Abel to multivariate analysis; Translation reviewed by Kenneth O. May; With a foreword by Saunders Mac Lane. MR**490100** - A. Iserles, E. B. Saff, and Xiaoyan Liu,
*On zeros of Hankel determinants with iterated polynomial entries*, IMA J. Numer. Anal.**12**(1992), no. 3, 387–403. IMA Conference on Dynamics of Numerics and Numerics of Dynamics (Bristol, 1990). MR**1181257**, DOI 10.1093/imanum/12.3.387 - Alain Lascoux,
*Inversion des matrices de Hankel*, Linear Algebra Appl.**129**(1990), 77–102 (French, with English summary). MR**1053054**, DOI 10.1016/0024-3795(90)90299-R - Nhu Nguyen and Qing Huo Liu,
*The regular Fourier matrices and nonuniform fast Fourier transforms*, SIAM J. Sci. Comput.**21**(1999), no. 1, 283–293. MR**1722138**, DOI 10.1137/S1064827597325712 - Victor Pan,
*Complexity of computations with matrices and polynomials*, SIAM Rev.**34**(1992), no. 2, 225–262. MR**1166176**, DOI 10.1137/1034049 - Victor Y. Pan,
*Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding*, J. Symbolic Comput.**33**(2002), no. 5, 701–733. Computer algebra (London, ON, 2001). MR**1919911**, DOI 10.1006/jsco.2002.0531 - Sebastian Pauli,
*Factoring polynomials over local fields*, J. Symbolic Comput.**32**(2001), no. 5, 533–547. MR**1858009**, DOI 10.1006/jsco.2001.0493 - M. R. Smith, S. Cohn-Sfetcu, and H. A. Buckmaster,
*Decomposition of multicomponent exponential decays by spectral analytic techniques*, Technometrics**18**(1976), no. 4, 467–482. MR**441534**, DOI 10.2307/1268663 - Victor Shoup,
*A new polynomial factorization algorithm and its implementation*, J. Symbolic Comput.**20**(1995), no. 4, 363–397. MR**1384454**, DOI 10.1006/jsco.1995.1055 - John Strain,
*A fast Laplace transform based on Laguerre functions*, Math. Comp.**58**(1992), no. 197, 275–283. MR**1106983**, DOI 10.1090/S0025-5718-1992-1106983-2 - Joachim von zur Gathen and Daniel Panario,
*Factoring polynomials over finite fields: a survey*, J. Symbolic Comput.**31**(2001), no. 1-2, 3–17. Computational algebra and number theory (Milwaukee, WI, 1996). MR**1806203**, DOI 10.1006/jsco.1999.1002

## Additional Information

**Chris Connell**- Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637
- Address at time of publication: Department of Mathematics, Rawles Hall, Indiana University, Bloomington, Indiana 47401
- MR Author ID: 666258
- Email: cconnell@math.uchicago.edu
- Received by editor(s): January 18, 2002
- Received by editor(s) in revised form: January 6, 2003
- Published electronically: July 9, 2004
- Additional Notes: The author was supported in part by an NSF postdoctoral fellowship
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 303-319 - MSC (2000): Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-04-01663-1
- MathSciNet review: 2085413