## Description

Question 1 Matrices Multiplication:

- (5 marks) Given two square matrices A
_{n n}and B_{n n}, design a multithreded algorithm (in pseducode) that computes A B with work (n^{3}) but span only (log n).

- (6 marks) Using your algorithm in (a) as a base, design a multithreaded algorithm that compute A B where A
_{p q}and B_{q r}are two given matrices.

- (6 marks) Analyze both of your algorithms in (a) and (b).

Note: in part (b), your algorithm should be highly parallel even if any of p, q, and r are 1.

Question 2 (a) (5 marks) Given a square matrix A_{n n}, design an e cient multithreaded algorithm that compute A^{T} (A-transpose) in place by using a divide-and-conquer approach (i.e. dividing the matrix recursively into four (n=2 n=2) submatrices C, D, E, and F .)

A = | C | D | ; |

E | ^{F} n n |

where the dimensions of all C; D; E; and F are (^{n}_{2} ^{n}_{2}__ __)

- (3 marks) Analyze your algorithm in (a).

1