@inproceedings{83e0534e9d2247d9a462969f5522c686,
title = "Faster relaxed multiplication",
abstract = "In previous work, we have introduced several fast algorithms for relaxed power series multiplication (also known under the name on-line multiplication) up to a given order n. The fastest currently known algorithm works over an effective base field K with sufficiently many 2p-th roots of unity and has algebraic time complexity O(n log ne2 √ log 2 √ log log n). In this paper, we will generalize this algorithm to the cases when K is replaced by an effective ring of positive characteristic or by an effective ring of characteristic zero, which is also torsion-free as a ℤ-module and comes with an additional algorithm for partial division by integers. In particular, we may take K to be any effective field. We will also present an asymptotically faster algorithm for relaxed multiplication of p-adic numbers. Copyright is held by the owner/author(s).",
keywords = "Computer algebra, FFT, Multiplication, On-line algorithm, Power series",
author = "\{Van Der Hoeven\}, Joris",
year = "2014",
month = jul,
day = "23",
doi = "10.1145/2608628.2608657",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "405--412",
editor = "Katsusuke Nabeshima",
booktitle = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
note = "2014 39th International Symposium on Symbolic and Algebraic Computation, ISSAC 2014 ; Conference date: 23-07-2014 Through 25-07-2014",
}