On fast multiplication of polynomials over arbitrary algebras (Q1186518)

We generalize the well-known Schönhage-Strassen algorithm [\textit{A. Schönhage} and \textit{V. Strassen}, Computing 7, 281--292 (1972; Zbl 0223.68007)] for multiplying large integers to an algorithm for multiplying polynomials with coefficients from an arbitrary, not necessarily commutative, not necessarily associative, algebra \({\mathcal A}\). Our main result is an algorithm to multiply polynomials of degree \(<n\) in \(O(n\log n)\) algebra multiplications and \(O(n\log n\log\log n)\) algebra additions/subtractions (we count a subtraction as an addition). The constant implied by the ``\(O\)'' does not depend upon the algebra \({\mathcal A}\). The parallel complexity of our algorithm, i.e., the depth of the corresponding arithmetic circuit, is \(O(\log n)\).