zbMATH — the first resource for mathematics

On fast multiplication of polynomials over arbitrary algebras. (English) Zbl 0766.68055
We generalize the well-known Schönhage-Strassen algorithm [A. Schönhage and 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)\).
Reviewer: D.G.Cantor

68W30 Symbolic computation and algebraic computation
68W10 Parallel algorithms in computer science
13P05 Polynomials, factorization in commutative rings
Full Text: DOI
[1] Aho, A., Hopcroft, J., Ullman, J.: The design and analysis of computer algorithms. Reading, MA: Addison-Wesley 1974 · Zbl 0326.68005
[2] Apostol, T.M.: Resultants of cyclotomic polynomials. Proc. Am. Math. Soc.24, 457-462 (1970) · Zbl 0188.34002
[3] Cantor, D.G.: On arithmetical algorithms over finite fields. J. Combinat. Theory A50, 285-300 (1989) · Zbl 0696.12013
[4] Chudnovsky, D.V., Chudnovsky, G.V.: Algebraic complexities and algebraic curves over finite fields. J. Complexity4, 285-316 (1988) · Zbl 0668.68040
[5] Grigoriev, D.Yu.: Multiplicative complexity of a pair of bilinear forms and of the polynomial multiplication. Proc. 7th MFCS. (Lect. Notes Comput. Sci., vol. 64, pp. 250-256) Berlin, Heidelberg, New York: Springer 1978
[6] Kaltofen, E.: Greatest common divisors of polynomials given by straight-line programs. J. ACM35, 231-264 (1988) · Zbl 0642.68058
[7] Kaminski, M.: An algorithm for polynomial multiplication that does not depend on the ring of constants. J. Algorithms9, 137-147 (1988) · Zbl 0648.13001
[8] Knuth, D.E.: The art of computer programming, vol. 2. 2nd edn. Reading, MA: Addison-Wesley 1981 · Zbl 0477.65002
[9] Lang, S.: Algebraic number theory. Reading, MA: Addison-Wesley 1970 · Zbl 0211.38404
[10] Lempel, A., Seroussi, G., Winograd, S.: On the complexity of multiplication in finite fields. Theoret. Comput. Sci.22, 285-296 (1983) · Zbl 0498.68027
[11] Nussbaumer, H.J.: Fast polynomial transform algorithms for digital convolutions. IEEE Trans. ASSP28, 205-215 (1980) · Zbl 0524.65093
[12] Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf.7, 395-398 (1977) · Zbl 0362.65011
[13] Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing7, 281-292 (1971) · Zbl 0223.68007
[14] Winograd, S.: Arithmetic complexity of computations. CBMS-NSF Regional Conference Series in Applied Math. 33. Philadelphia, PA: SIAM 1980 · Zbl 0441.68045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.