8. Suppose n is even and define n/2 f(x) = x2i-1x2i, i=1 (a) Show that the...

 

Transcribed Image Text:

8. Suppose n is even and define n/2 f(x) = x2i-1x2i, i=1 (a) Show that the inner product can be re-expressed as n/2 V x Rn. xy = (x2i1 + y2i)(x2i + Y2i1) f(x) (y), i=1 3 V x, y Rn. (b) Now consider the matrix multiplication C = AB for A, B = Rnxn. Give an algorithm for com- puting C that uses only n + O(n) scalar multiplications. (Notice that a standard matrix mul- tiplication needs n scalar multiplications. Together with other techniques, we can obtain Copper- smith-Winograd algorithm whose complexity is only O(n 2.375).) 8. Suppose n is even and define n/2 f(x) = x2i-1x2i, i=1 (a) Show that the inner product can be re-expressed as n/2 V x Rn. xy = (x2i1 + y2i)(x2i + Y2i1) f(x) (y), i=1 3 V x, y Rn. (b) Now consider the matrix multiplication C = AB for A, B = Rnxn. Give an algorithm for com- puting C that uses only n + O(n) scalar multiplications. (Notice that a standard matrix mul- tiplication needs n scalar multiplications. Together with other techniques, we can obtain Copper- smith-Winograd algorithm whose complexity is only O(n 2.375).)