CareerCup

The resulting matrix would be a n*n matrix. Each element of the matrix can be computed, independently of the other. So if there are n^2 computers, each has a column and a row to multiply. For e.g. computer1 has row1 and col1, computer2 has row1 and col2. Each computer takes O(n) to multiply the row and column. So the whole matrix can be multiplied in O(n) time.

strassen's algorithm?

matrix decomposition?

- You got a matrix of M x N
- Arrange the available machines in form of a logical grid of P x Q
- Give each machine a block of matrix M/P x N/Q
- Each machine will self-multiply each small block given above. O((MN/PQ)^3) complexity
- Each machine will send the result to the first machine in its row which will add up the sub-blocks element by element.
- All machines in the first column combined will have the result.