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

DOI10.1016/0304-3975(86)90107-6zbMATH Open0632.68039OpenAlexW2030141403MaRDI QIDQ1095657FDOQ1095657

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

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

zbMATH Keywords

formal power seriescomposition problem

Mathematics Subject Classification ID

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

Cites Work

• The complexity of partial derivatives
• Fast modular transforms
• Fast multiplication of large numbers
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Fast Algorithms for Manipulating Formal Power Series
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• An algorithm for division of powerseries
• Title not available (Why is that?)

Cited In (17)

• Inverting Polynomials and Formal Power Series
• Predicting zero coefficients in formal power series computations.
• 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)