Then we consider the following polynomials of degree 1 in and with square matrices of order 2 for coefficients:

- How many additions and multiplications in
are needed
in order to compute the product
in a
*naive way*. - Check that Karatsuba's trick applies here (despite of the fact that matrix multiplication is not commutative).
- Explain briefly why we can compute using only 21 multiplications in . How many additions in are needed in this case?
- Explain briefly in which circumstances using the multiplication scheme of the previous question makes sense.

2008-01-31