Matrix Multiplication using a PRAM CREW machine

Question

Matrix Multiplication using a CREW PRAM. Let A,B ∈ Rn×n be two square matrices and

C = A · B their matrix product given in coordinates

Design a CREW PRAM algorithm that uses O(n3) processors and O(n3) memory to compute the

matrix C in logarithmic time.

(i) State the pseudo-code that is needed to compute the result for n being a power of two.

(ii) Give a simple solution if n is not a power of two. Is the asymptotic complexity affected?

(iii) Is your solution cost-optimal? If not, make it so.