A solution to certain polynomial equations with applications to nonlinear fitting
HTML articles powered by AMS MathViewer
- by Chris Connell;
- Math. Comp. 74 (2005), 303-319
- DOI: https://doi.org/10.1090/S0025-5718-04-01663-1
- Published electronically: July 9, 2004
- PDF | 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
Bibliographic 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