Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u]/\langle{} u^ n \rangle\). (English) Zbl 0744.68071
This paper deals with the classification of all minimal bilinear algorithms for the computation of a product of polynomials modulo another polynomial \(R\). As a consequence of the Chinese remainder theorem it is only interesting to consider the case that \(R=Q^ \ell\) is a power of an irreducible polynomial \(Q\). The case that \(\ell=1\) was already treated by S. Winograd [Theor. Comput. Sci. 8, 337-359 (1979; Zbl 0404.12016)]. The case that \(\ell>1\) and \(\deg(Q)>1\) was treated in the first part of the paper [A. Averbuch, Z. Galil and S. Winograd, Theor. Comput. Sci. 58, 17-56 (1988; Zbl 0656.68040)]. In this part the final case \(\ell>1\) and \(\deg(Q)=1\) is treated.
A minimal algorithm for computing the product of two polynomials modulo \(u^ n\) needs \(2n-1\) multiplications. Together with the results of the above mentioned papers it is shown that each minimal algorithm needs first to compute the coefficients of the product after which reduction is being done, hence large coefficients will appear during the computation.
A minimal algorithm for computing the product of two polynomials modulo \(u^ n\) needs \(2n-1\) multiplications. Together with the results of the above mentioned papers it is shown that each minimal algorithm needs first to compute the coefficients of the product after which reduction is being done, hence large coefficients will appear during the computation.
Reviewer: F.J.van der Linden (Eindhoven)
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 12E05 | Polynomials in general fields (irreducibility, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 12-04 | Software, source code, etc. for problems pertaining to field theory |
References:
| [1] | Averbuch, A.; Galil, Z.; Winograd, S., Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial, Part I: The algebra \(G[u]\)/〈\(Q(u)^l\)〉, \(l > 1\), Theoret. Comput. Sci., 58, 1-3, 17-56 (1988) · Zbl 0656.68040 |
| [2] | Averbuch, A.; Galil, Z.; Winograd, S., Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial, Part II: The algebra \(G[u]\)/〈\(u^n\)〉, Technical Report 82/87 (1987), Dept. of Computer Science, Tel-Aviv University |
| [3] | de Groote, H. F., On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of bilinear mapping, Theoret. Comput. Sci., 7, 1-24 (1978) · Zbl 0418.68036 |
| [4] | de Groote, H. F., On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for 2 × 2 matrix multiplication, Theoret. Comput. Sci., 7, 124-148 (1978) · Zbl 0418.68037 |
| [5] | de Groote, H. F., On varieties of optimal algorithms for the computation of bilinear mappings. III. Optimal algorithms for the computation of xy and yx where \(x, y\) ϵ \(M_2(K)\), Theoret. Comput. Sci., 7, 239-249 (1978) · Zbl 0447.68024 |
| [6] | Feig, E., On systems of bilinear forms whose minimal division-free algorithms are all bilinear, J. Algorithms, 2, 261-281 (1981) · Zbl 0476.68029 |
| [7] | Feig, E., Certain systems of bilinear forms whose minimal algorithms are all quadratic, J. Algorithms, 4, 137-149 (1983) · Zbl 0518.68028 |
| [8] | Winograd, S., On multiplication in algebraic extension fields, Theoret. Comput. Sci., 8, 359-377 (1979) · Zbl 0404.12016 |
| [9] | Winograd, S., Some linear forms whose multiplicative complexity depends on the field of constants, Math. Systems Theory, 10, 169-180 (1977) · Zbl 0363.65014 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
