A simple and fast algorithm for computing exponentials of power series

DOI10.1016/J.IPL.2009.03.012MaRDI QIDQ989478zbMATH OpenOpenAlexFDO

Authors Alin Bostan, Éric Schost

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5804

zbMATH Keywords

algorithmsfast Fourier transformpower seriesexponentialNewton iteration

Mathematics Subject Classification ID

Computation of special functions and constants, construction of tables (65D20) Numerical computation of solutions to single equations (65H05) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: As was initially shown by Brent, exponentials of truncated power series can be computed using a constant number of polynomial multiplications. This note gives a relatively simple algorithm with a low constant factor.

Recommendations

• A fast algorithm for reversion of power series
• scientific article; zbMATH DE number 732087
• A fast numerical algorithm for the composition of power series with complex coefficients
• A simple algorithm for expanding a power series as a continued fraction
• Faster algorithms for the square root and reciprocal of power series
• Fast calculation and high precision of basic elementary functions based on power series expansions
• Fast algorithms for elementary operations on complex power series
• Computing power series in polynomial time
• scientific article; zbMATH DE number 1350000
• A simple and fast online power series multiplication and its analysis

Cites work

• scientific article; zbMATH DE number 3533996 (Why is no real title available?)
• Fast Algorithms for Manipulating Formal Power Series
• Modern computer algebra
• Newton's method and FFT trading
• Relax, but don't be too lazy
• The truncated fourier transform and applications
• Variations on computing reciprocals of power series

Cited in

(8)

• A New Root–Finding Algorithm Using Exponential Series
• Faster algorithms for the square root and reciprocal of power series
• Fast coefficient computation for algebraic power series in positive characteristic
• Homotopy techniques for multiplication modulo triangular sets
• The J.C.P. miller recurrence for exponentiating a polynomial, and its q- analog
• Solving composite sum of powers via Padé approximation and orthogonal polynomials with application to optimal PWM problem
• Fast evaluation of real and complex exponential sums
• Fast algorithms for elementary operations on complex power series

This page was built for publication: A simple and fast algorithm for computing exponentials of power series

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989478)