A fast numerical algorithm for the composition of power series with complex coefficients

DOI10.1016/0304-3975(86)90107-6MaRDI QIDQ1095657zbMATH OpenOpenAlexFDO

Authors Peter Ritzmann

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90107-6

zbMATH Keywords

formal power seriescomposition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Fast algorithms for elementary operations on complex power series
• Composing power series over a finite ring in essentially linear time
• Power series composition and change of basis
• A fast algorithm for reversion of power series
• Composition modulo powers of polynomials

Cites work

• scientific article; zbMATH DE number 3856407 (Why is no real title available?)
• 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
• The complexity of partial derivatives
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication

Cited in

(17)

• Predicting zero coefficients in formal power series computations.
• Inverting Polynomials and Formal Power Series
• Fast coefficient computation for algebraic power series in positive characteristic
• A fast algorithm for reversion of power series
• A simple and fast algorithm for computing exponentials of power series
• Modular composition via factorization
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Composing power series over a finite ring in essentially linear time
• Root refinement for real polynomials using quadratic interval refinement
• Computing real roots of real polynomials
• Power series composition and change of basis
• Fast multivariate multi-point evaluation revisited
• On computing the coefficients of bivariate holonomic formal series
• Nearly optimal computations with structured matrices
• Fast algorithms for elementary operations on complex power series
• Fast summation of power series with coefficients analytic at infinity

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)