Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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
Published electronically: July 9, 2004
MathSciNet review: 2085413
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [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 $Z\sb m$.
    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

Similar Articles

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: http://dx.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