In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here “almost as quickly” means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many -th roots of unity.

Keywords: power series, multiplication, algorithm, FFT, computer algebra

A.M.S. subject classification: 68W25, 42-04, 68W30, 30B10, 33F05, 11Y55

View: Html, TeXmacs, Pdf, BibTeX