Strassen’s Matrix Multiplication


Another example of divide and conquer method is Strassen’s Matrix that help us to multiply two matrices of size n×n. Let A and B are the two n×n matrices, then its product C= AB is also n×n matrix. These n×n matrix product can be formed by taking the element in the ith row of A and jth column of B and multiplying them to get
 
To compute C(i,j), we need to have n multiplication. Divide and conquer method suggest another way to compute C(i,j) i.e the product matrix of n×n. imagine that A and B are two n×n matrices divided into two square matrices of size n/2 n/2. then the product matrix AB can be computed by using the above formula as
 
then


To compute AB, we have to perform 8 multiplication and 4 addition by the above formula of n/2 × n/2 matrices. Hence from such kind of method no improvement has to be done. Since the matrix multiplication is more expensive than the matrix addition. We can reformulate the formula in such a way that we can use fewer multiplication and possibly more addition. Volker Strassen has discovered a way to compute a product matrix Ci,j by using only 7 multiplication and only 18 addition or subtraction. His method involves the 7 n/2 n/2 matrix multiplication P,Q,R,S,T,U and V as follows.


For example

Lets consider
A11=1 ; A12=2 ; A21=3 ; A22=4
B11=5 ; B12=6 ; B21=7 ; B22=8
Thus,

P = (A11 + A22) (B11 + B22)
= (1+4) (5+8) = 65

Q = (A21 + A22) B11
= (3+4) 5 = 35

R = A11 (B12 - B22)
= 1 (6-8) = -2

S= A22 (B11 - B21)
= 4 (5-7) = -8

T = (A11 + A12) B22
= (1+2) 8 = 24

U = (A21 - A11) B22
= (3-1) (5+6) = 22

V = (A12 - A22) (B21 + B22)
= (2-4) (7+8) = -30

Hence, as we know
C11 = P + S - T + V
   = 65 - 8 - 24 -30 = 3
C12 = R + T
   = -2 + 24 = 22
C21 = Q + S
= 35-8 = 27
C22 = P + R - Q + U
= 65 - 2 -35 + 22 = 65 - 37 + 22 = 50 


Therefore,

Comments

Post a Comment

Popular posts from this blog

Articulation point of graph / Biconnected components and DFS traversal

Image
In the connected graph G, a vertex V is said to be an articulation point if and only if the deletion of vertex V disconnects the graph into two or more non - empty components. For more precisely satisfy this concept, consider the following connected graph   In this graph, basically vertex 2 is an articulation point, as if we delete the vertex, it will disconnects the graph into two non - empty component.
Read more

Brief shortnote on Requirement elicitation and requirement analysis

Image
- Requirement elicitation means gathering of requirements. - Perhaps it is most difficult, critical, most error prone and most communication intensive aspect of software development. - The most important goal of software requirement engineering is to find out what the customer really wants. - The users need can be identify only by understanding expectation of the user from the developers. - Requirements are gathered by asking the question to user and writing down their answers and their exceptions of the software that how he want to use software. - Gathering the requirements of users is the most difficult part of the software development, because both developer and user have different mindset regarding the software. - Here, communication of both the parties are the most essential for software product. - There are number of requirement elicitation method. https://en.wikipedia.org/wiki/Requirements_elicitation   - Some people think that one methodology is alway
Read more

Requirement Engineering

Image
- Requirement engineering produces one large document, written in natural language, contain a description of what the system will do without describing how will it do. - Requirement engineering is the discipline application of proven principles, methods, tools and notations to describe the proposed system’s intended behavior and its associated constraints. - This process contains the four steps as shown in fig i] Requirement Elicitation This is also known as gathering of requirements. Here the requirements are identified with the help of customer and existing system process are available. ii] Requirement Analysis Requirement analysis     are start with requirement elicitation. Here the requirements are analysis in order to identify inconsistencies, defects, omission etc. iii] Requirement Documentation This is the end product of requirement elicitation and analysis. The documentation is very important as it is the foundation of the software. iv] Requi
Read more