I need question three thank you, all Information needed is in the picture 2 Parallel Matrix MultiplicationIn our lecture 3, we learned a divide-and-conquer algorithm for matrix multiplication. Our task here is toparallelize this algorithm.Questions:1.2.3.4.5.What is the 8-way divide-and-conquer algorithm for matrix multiplication we've learned in class?Describe the algorithm briefly. What is the time complexity of this algorithm?Parallelize the this 8-way divide-and-conquer matrix multiplication algorithm. Describe youralgorithm.Write down the recurrences for work and span of your algorithm.Solve the recurrences. What is the work and span of your algorithm?Does this idea also apply to Strassen's algorithm? If so, please describe the parallel version ofStrassen's algorithm. What is the work and span of this parallel Strassen's algorithm?

Divide and conquer is a beautiful method to solve a complex problem into smaller subproblems. and then, combine the results into a full solution. The technique is used recursively to divide whole problems in such a way that it becomes easy to solve them. Parallelism is a mechanism for dividing large computations into smaller ones that can be performed simultaneously.Given below is an algorithm for Matrix multiplication using the Divide and conquer approach for 8-way. MM(C, A, B, n)1 if n = 12 then c11 ← a11b11 return3 partition A, B, and C, into 4 submatrices4 create T, a temporary n × n matrix5 spawn MM(C11, A11, B11, n/2)6 spawn MM(C12, A11, B12, n/2)7 spawn MM(C21, A21, B11, n/2)8 spawn MM(C22, A21, B12, n/2)9 spawn MM(T11, A12, B21, n/2)10 spawn MM(T12, A12, B22, n/2)11 spawn MM(T21, A22, B21, n/2)12 spawn MM(T22, A22, B22, n/2)13 sync14 parallel for i ← 1 to n15 do parallel for j ← 1 to n16 do cij ← cij + tij Since you ask for 3rd part:- 3. One can add pairwise matrices in parallel, either using 2 for loops or by dividing them into four parts and performing it recursively. In any case, the work of adding two n×n matrices is Θn2 and the span is Θlog n. Therefore, the overall work of the algorithm is:- T1n=8T1n2+Θn2=Θn3 And the span is: T∞n=T∞n2+Θlog n=Θlg2n

Answered: 3. Write down the recurrences for work…

Engineering

Computer Science

3. Write down the recurrences for work and span of your algorithm.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

What are the names of Mark Dean's parents?
Useful information, but this is not answering the fill-in-the-blank question. Can you help me answer?
Please explain all steps in the answer provided above!
May I ask for the answer and explanation for question 7?
To get things rolling, what do you do initially? Please provide a few instances of this.
Who are Mark Dean's biological parents?
What is the “checkerboard” issue and why does it matter? Thank you.
What many types of information are taken into consideration in order to reach a conclusion?
Explain the purpose and functionalities of database query languages such as SQL (Structured Query Language). Discuss the different types of SQL queries (SELECT, INSERT, UPDATE, DELETE) and their applications.
Explain the meaning of the word inappropriately in the phrase “one users work does not inappropriately influence another user's work."
Definition of redundancy and problems that can occur due to redundancy.
Explanation it correctly and details Q)what is a schedule of values? why is it important