Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6861240 | Journal of Symbolic Computation | 2016 | 21 Pages |
Abstract
This paper focuses on online (or relaxed) algorithms for the multiplication of power series over a field and their complexity analysis. We propose a new online algorithm for the multiplication using middle and short products of polynomials as building blocks, and we give the first precise analysis of the arithmetic complexity of various online multiplications. Our algorithm is faster than Fischer and Stockmeyer's by a constant factor; this is confirmed by experimental results.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Romain Lebreton, Ãric Schost,