The P-MATRIX-MULTIPLY-RECURSIVE procedure has the disadvantage that it must allocate a temporary matrix T of size n × n, which can adversely affect the constants hidden by the ‚-notation. The P-MATRIX-MULTIPLY-RECURSIVE procedure does have high parallelism, however. For example, ignoring the constants in the ‚-notation, the parallelism for multiplying 1000 × 1000 matrices comes to approximately 1000³/10² = 107, since lg 1000 ≈ 10. Most parallel computers have far fewer than 10 million processors.

a. Describe a recursive multithreaded algorithm that eliminates the need for the temporary matrix T at the cost of increasing the span to Θ(n). Compute C = C + AB following the general strategy of P-MATRIX-MULTIPLYRECURSIVE, but initialize C in parallel and insert a sync in a judiciously chosen location.

b. Give and solve recurrences for the work and span of your implementation.

c. Analyze the parallelism of your implementation. Ignoring the constants in the ‚-notation, estimate the parallelism on 1000 × 1000 matrices. Compare with the parallelism of P-MATRIX-MULTIPLY-RECURSIVE.