Fast algorithms for elementary operations on complex power series

摘要

It is shown that the inversion of a complex-valued power series can be realisedasymptotically with complexity of 5/4 multiplications (if we compare the upper bounds). Itis shown that the calculation of the square root requires asymptotically also no more than 5/4multiplications, the computation of an exponential has the complexity equal to 13/6 multiplic-ations, and raising to an arbitrary power requires 41/12 multiplications.This research was supported by the Russian Foundation for Basic Research, grants08-01-00863 and 08-01-00632а, by the program of the President of Russian Federation for thesupport of leading scientific schools, grant 4470.2008.1, and by the fundamental research pro-gram of the Department of Mathematical Sciences of Russian Academy of Sciences `Algebraicand Combinatorial Methods of Mathematical Cybernetics,' project `Synthesis and Complexityof Control Systems.'