A solution to certain polynomial equations with applications to nonlinear fitting

Author:
Chris Connell

Journal:
Math. Comp. **74** (2005), 303-319

MSC (2000):
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-04-01663-1

Published electronically:
July 9, 2004

MathSciNet review:
2085413

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a combinatorial method for solving a certain system of polynomial equations of Vandermonde type in variables by reducing it to the problem of solving two special linear systems of size and rooting a single univariate polynomial of degree . Over , all solutions can be found with fixed precision using, up to polylogarithmic factors, bitwise operations in the worst case. Furthermore, if the data is well conditioned, then this can be reduced to 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 terms in the same, nearly optimal, time.

**[AR00]**R. G. Airapetyan and A. G. Ramm.

Numerical inversion of the Laplace transform from the real axis.*J. Math. Anal. Appl.*, 248(2):572-587, 2000. MR**2001g:65171****[BDCMM01]**D. Bini, G. M. Del Corso, G. Manzini, and L. Margara.

Inversion of circulant matrices over .*Math. Comp.*, 70(235):1169-1182, 2001. MR**2001j:65047****[Bey95]**G. Beylkin.

On the fast Fourier transform of functions with singularities.*Appl. Comput. Harmon. Anal.*, 2(4):363-381, 1995. MR**96i:65122****[CFR84]**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(2):272-286, 1984. MR**86e:65170****[DR93]**A. Dutt and V. Rokhlin.

Fast Fourier transforms for nonequispaced data.*SIAM J. Sci. Comput.*, 14(6):1368-1393, 1993. MR**95d:65114****[GGLM59]**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.**[Gou97]**M. C. Gouveia.

Regular Hankel matrices over integral domains.*Linear Algebra Appl.*, 255:335-347, 1997. MR**98c:15070****[IK77]**S. Iyanaga and Y. Kawada, editors.*Encyclopedic dictionary of mathematics. Vol. II*.

MIT Press, Cambridge, Mass., Japanese edition, 1977.

Networks to zeta functions, Translation reviewed by Kenneth O. May. MR**81d:00003b****[ISL92]**A. Iserles, E. B. Saff, and Xiaoyan Liu.

On zeros of Hankel determinants with iterated polynomial entries.*IMA J. Numer. Anal.*, 12(3):387-403, 1992.

IMA Conference on Dynamics of Numerics and Numerics of Dynamics (Bristol, 1990).MR**93m:58093****[Las90]**Alain Lascoux.

Inversion des matrices de Hankel.*Linear Algebra Appl.*, 129:77-102, 1990. MR**91d:15064****[NL99]**Nhu Nguyen and Qing Huo Liu.

The regular Fourier matrices and nonuniform fast Fourier transforms.*SIAM J. Sci. Comput.*, 21(1):283-293 (electronic), 1999. MR**2000j:65130****[Pan92]**V. Y. Pan.

Complexity of computations with matrices and polynomials.*SIAM Rev.*, 34(2):225-262, 1992. MR**93g:65179****[Pan02]**Victor Y. Pan.

Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding.*J. Symbolic Comput.*, 33(5):701-733, 2002.

Computer algebra (London, ON, 2001). MR**2003f:13030****[Pau01]**Sebastian Pauli.

Factoring polynomials over local fields.*J. Symbolic Comput.*, 32(5):533-547, 2001. MR**2002h:13038****[SCSB76]**M. R. Smith, S. Cohn-Sfetcu, and H. A. Buckmaster.

Decomposition of multicomponent exponential decays by spectral analytic techniques.*Technometrics*, 18(4):467-482, 1976. MR**55:14397****[Sho95]**Victor Shoup.

A new polynomial factorization algorithm and its implementation.*J. Symbolic Comput.*, 20(4):363-397, 1995. MR**97d:12011****[Str92]**John Strain.

A fast Laplace transform based on Laguerre functions.*Math. Comp.*, 58(197):275-283, 1992. MR**92e:44001****[vzGP01]**Joachim von zur Gathen and Daniel Panario.

Factoring polynomials over finite fields: a survey.*J. Symbolic Comput.*, 31(1-2):3-17, 2001.

Computational algebra and number theory (Milwaukee, WI, 1996). MR**2001k:11253**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65H10

Retrieve articles in all journals with MSC (2000): 65H10

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

Email:
cconnell@math.uchicago.edu

DOI:
https://doi.org/10.1090/S0025-5718-04-01663-1

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

Article copyright:
© Copyright 2004
American Mathematical Society