DOIAbstract
AbstractLet C[[z]] be the ring of power series over an effective ring C. In Brent and Kung (1978), it was first shown that differential equations over C[[z]] may be solved in an asymptotically efficient way using Newton’s method. More precisely, if M(n) denotes the complexity for multiplying two polynomials of degree <n over C, then the first n coefficients of the solution can be computed in time O(M(n)). However, this complexity does not take into account the dependency on the order r of the equation, which is exponential for the original method (van der Hoeven, 2002) and quadratic for a recent improvement (Bostan et al., 2007). In this paper, we present a technique for further improving the dependency on r, by applying Newton’s method up ...
Add to ORKG