Michael Kaminski
Abstract
Let Mq(n) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q-element field by means of bilinear algorithms. It is shown that Mq(n) ≱ 3n - o(n). In particular, if q/2 < n ⪇ q + 1, we establish the tight bound Mq(n) = 3n + 1 [q/2].The technique we use can be applied to analysis of algorithms for multiplication of polynomials modulo a polynomial as well.
- 1 AHO, A. A., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., i974. Google Scholar
- 2 BROCKETT, R. W., AND DOBKIN, O. On the optimal evaluation of a set of bilinear forms. Linear Alg. Applic. 19 (1978), 207-235.Google Scholar
- 3 BROWN, M. R., AND DOBKiN, D.P. An improved lower bound on polynomial multiplication. IEEE Trans. Comput. 29 (1980), 337-340.Google Scholar
- 4 FEDUCCIA, C. M., AND ZALCSTEIN, Y, Algebras having linear multiplicative complexity. J. ACM Google Scholar
- 5 HOPCROFT, J., AND MUNSlNSKI, J. Duality applied to the complexity of matrix multiplication. SIAM J. Comput. 2 (1973), 159-173.Google Scholar
- 6 JACOBSON, N. Basic Algebra I. Freeman and Co. New York, 1985.Google Scholar
- 7 JA' J A', J. Optimal evaluation of pairs of bilinear forms. SlAM J. Comput. 8 (1979), 443-462.Google Scholar
- 8 JA' JA', J. Computation ofbilinear forms over finite fields. J. ACM 27 (1980), 822-830. Google Scholar
- 9 K~A.M!NSK!, M. .A lnw~r hntlrtct fnr nnlvnnrrtlnlr..~ mltltipliontlnrt ..... Th,c,,'~rat Co.m.put. ..qrq ... dD (IQRcl),... 319-322. Google Scholar
- 10 KAMtNSKI, M., AND BSHOUTY, N.H. Multiplicative complexity of polynomial multiplication over finite fields. In Proceedings of 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 138-140.Google Scholar
- 11 LEMPEL, A., SEROUSSI, G., AND WINOGRAD, S. On the complexity of multiplication in finite fields. Theoret. Comput. Sci. 22 (1983), 285-296.Google Scholar
- 12 LEMPEL, A., AND WINOGRAD, S. A new approach to error-correcting codes. IEEE Trans. Inf. Theory 23 (1977), 503-508.Google Scholar
- 13 LIDL, R., AND NIEDERREITER, H. Finite fields. In Encyclopedia of Mathematics and Its Applications, Vol. 20, G.-C. Rota, Ed. Addison-Wesley, Reading, Mass., 1983.Google Scholar
- 14 PETERSON, W. W., AND WELl)ON, E.J. Error-Correcting Codes. MIT Press, Cambridge, Mass., 1972.Google Scholar
- 15 SCHONHAGE, A. Schnelle Multiplikation von Polynomen iiber K6rpern der Charakteristik 2. Acta Inf. 7 (1977), 395-398.Google Scholar
- 16 STRASSEN, V. Vermeidung von Divisionen. J. Reine Angew. Math. 264 (1973), 184-202.Google Scholar
- 17 WINOGRAD, S. On the number of multiplications necessary to compute certain functions. Commun. Pure and Appl. Math. 23 (1970), 165-179.Google Scholar
- 18 WINOGRAD, S. Some bilinear forms whose multiplicative complexity depends on the field constants. Math. Syst. Theory 10 (1976/77), 169-180.Google Scholar
Index Terms
- Multiplicative complexity of polynomial multiplication over finite fields
Recommendations
Certain classes of polynomial expansions and multiplication formulas
The authors first present a class of expansions in a series of Bernoulli polyomials and then show how this general result can be applied to yield various (known or new) polynomial expansions. The corresponding expansion problem involving the Euler ...
Multiplicative complexity of polynomial multiplication over finite fields
SFCS '87: Proceedings of the 28th Annual Symposium on Foundations of Computer ScienceLet Mq(n) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q-element field by means of bilinear algorithms. It is shown that Mq(n) ≥ 3n - o(n). In particular, if q/2 < n ≤ q + ...
On the complexity of multivariate blockwise polynomial multiplication
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic ComputationIn this article, we study the problem of multiplying two multivariate polynomials which are somewhat but not too sparse, typically like polynomials with convex supports. We design and analyze an algorithm which is based on blockwise decomposition of the ...
Reviews
Victor Y. Pan
To evaluate the coefficients of the product of two polynomials of degree n, one may evaluate these polynomials at 2 n + 1 points (such as the (2 n + 1)th roots of 1), then pairwise multiply the results and finally obtain the desired coefficients by interpolation. This scheme uses 2 n + 1 bilinear (nonscalar) multiplications, but it does not work over finite fields F q that have q < n elements. The known upper bound on the number M( q,n) of bilinear multiplications is superlinear; this paper establishes a new sharp bound, M( q,n) = 3 n + 1 ? &fll0; q/2 &flr0; , whenever q/2 < n < q + 1, and a new record lower bound, M( q,n) > 3 n ? n/(log q n ? 3) for any q greater than 2. As is customary, the authors assume bilinear algorithms and estimate the number of bilinear multiplications. Their proof techniques are novel; they rely on the analysis of linear recurrence sequences and Hankel matrices, while the previous lower bounds on M( q,n) were obtained by studying the associated linear codes over F q, which gave inferior estimates for M( q,n). This paper is a theoretical and technical advance. It will primarily interest researchers in the area of the design and analysis of algorithms for computations with polynomials over finite fields.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments