A fast numerical algorithm for the composition of power series with complex coefficients
Let P, Q be formal power series in a variable t over an infinite field K, \(P(0)=0\). The composition problem is the task of computing the coefficients of the polynomial \(Q\circ P\) mod \(t^{n+1}\) given the first \(n+1\) coefficients of P and Q. The best known upper bound for the Ostrowski complexity of this problem is reached by an \(O(n^{3/2}(\log n)^{1/2})\) algorithm due to Brent and Kung. On the other hand no nonlinear lower bound is known so far. The author shows that the composition problem is essentially equivalent to computing only the nth coefficient of \(Q\circ P\). A second result determines the complexity of an approximate version. It is shown that the complexity of computing \(Q\circ P\) mod\(\prod^{n}_{i=0}(t-\epsilon_ i)\) \((\epsilon_ 0,...,\epsilon_ n\in K^{\times}\) pairwise different) is of order n log n.
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- An algorithm for division of powerseries
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Fast Algorithms for Manipulating Formal Power Series
- Fast modular transforms
- Fast multiplication of large numbers
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- The complexity of partial derivatives
- Composing power series over a finite ring in essentially linear time
- Predicting zero coefficients in formal power series computations.
- Numerics of analytic functions and complexity
- Fast multivariate multi-point evaluation revisited
- On computing the coefficients of bivariate holonomic formal series
- Fast algorithms for elementary operations on complex power series
- Inverting Polynomials and Formal Power Series
- Root refinement for real polynomials using quadratic interval refinement
- Computing real roots of real polynomials
- Power series composition and change of basis
- A fast algorithm for reversion of power series
- Nearly optimal computations with structured matrices
- Fast summation of power series with coefficients analytic at infinity
- Fast evaluation and root finding for polynomials with floating-point coefficients
- Fast coefficient computation for algebraic power series in positive characteristic
- Fast evaluation and root finding for polynomials with floating-point coefficients
- Faster modular composition
- Modular composition via factorization
- Fast modular composition using spiroids
- A simple and fast algorithm for computing exponentials of power series
This page was built for publication: A fast numerical algorithm for the composition of power series with complex coefficients
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095657)
