Predicting zero coefficients in formal power series computations. (Q1599549)

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.