Variations on computing reciprocals of power series
Over infinite fields, inverting b(0) + b(1)x + ... + b(n)x(n) + ... mod x(n+1) has nonscalar complexity < 3.75 . n, versus 2n + 1 for multiplication mod x(n+1). For fields like C supporting FFTs, and counting all arithmetic operations, we can bound the total cost for inversion mod x(n+1) by (13.5 + o(1)) . n . logn, versus approximate to 9n . logn (presently the best known) for multiplication. Furthermore we describe a new method how to compute reciprocals by Graeffe root squaring steps and demonstrate this novel approach with the inversion of (monic) power series over Z. (C) 2000 Elsevier Science B.V. All rights reserved.
reciprocals of power series algorithms computational complexity