Predicting zero coefficients in formal power series computations.

DOI10.1006/JSCO.2000.0495MaRDI QIDQ1599549zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 11 June 2002

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/122b392bf643e6c2cb34a990bdc5d853636f3afa

zbMATH Keywords

long sequences of zero coefficients in a power seriesrandomized algorithms

Mathematics Subject Classification ID

Formal power series rings (13F25) Computational aspects and applications of commutative rings (13P99) Symbolic computation and algebraic computation (68W30)

Review text

The author considers the problem of predicting long sequences of zero coefficients in a power series obtained by multiplication, division or reversion, where all coefficients are integers. He describes efficient randomized algorithms whose probability of error can be controlled by the user. A runtime analysis is given and some experimental results are also presented that compare his algorithms with classical ones for formal power series computations. He envisages the algorithms given here as being of greatest use in situations where several processors are available so that the possibility of a long sequence of zeros can be tested in parallel to the normal computation of coefficients.

Recommendations

• scientific article; zbMATH DE number 2151225
• Relax, but don't be too lazy
• Series prediction based on algebraic approximants
• Inverting Polynomials and Formal Power Series
• A fast numerical algorithm for the composition of power series with complex coefficients

Cites work

• A Fast Monte-Carlo Test for Primality
• Fast Algorithms for Manipulating Formal Power Series
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 481965 (Why is no real title available?)
• scientific article; zbMATH DE number 621810 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Inverting Polynomials and Formal Power Series
• On the computational power of pushdown automata

This page was built for publication: Predicting zero coefficients in formal power series computations.

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