Быстрые алгоритмы для элементарных операций с комплексными степенными рядами

Показано, что инвертирование комплексного степенного ряда может быть выполнено асимптотически со сложностью 5/4 умножений (если сравнивать верхние оценки). Кроме того показано, что извлечение квадратного корня выполняется асимптотически также со сложностью 5/4, вычисление экспоненты – со сложностью 13/6, а возведение в произвольную степень требует 41/12 умножений.
Работа выполнена при поддержке Российского Фонда фундаментальных исследований, проекты 08–01–00863 и 08–01–00632а, программы Президента Российской Федерации поддержки ведущих научных школ, проект НШ 4470.2008.1, и программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.