Strassen Algorithm using Divide and Conquer

Algorithm Strassen(A,B,C,n)

{

If(n==2) then

{

C11 := A11 B11 + A12 B12; 

C12 := A11 B12 + A12 B22;

C21 := A21 B11+ A22 B21; 

C22 := A21 B21+ A22 B22;

}

else

{

Partition A into 4 matrices A11, A12, A21, A22 each of size n/2; Partition B into 4 matrices B11,B12,B21,B22 each of size n/2;

P1 := Strassen(A11,(B12-B22),C,n/2); 

P2 := Strassen((A11+A12),B22,C,n/2); P3 := Strassen((A21+A22),B11,C,n/2); P4 := Strassen(A22,(B21-B11),CC,n/2);

P5 := Strassen((A11+A22),(B11+B22),C,n/2); 

P6 := Strassen((A12-A22),(B21+B22),C,n/2); 

P7 := Strassen((A11-A21),(B11+B12)C,n/2);

 

C11 := P5=P4-P2+P6; C12 := P1+P2;

C21 := P3+P4;

C22 := P1+P5-P3-P7;

}

Return C;

}


Source Code:

import numpy as np def splitmat(matrix):

row, col = matrix.shape row2, col2 = row//2, col//2

return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:, col2:]

 

def strmm(x, y):

if len(x) == 1:

return x*y

a, b, c, d = splitmat(x) 

e, f, g, h = splitmat(y)

p1 = strmm(a, f - h)

p2 = strmm(a + b, h)

p3 = strmm(c + d, e)

p4 = strmm(d, g - e)

p5 = strmm(a + d, e + h)

p6 = strmm(b - d, g + h)

p7 = strmm(a - c, e + f)

c11 = p5 + p4 - p2 + p6

c12 = p1 + p2

c21 = p3 + p4

c22 = p1 + p5 - p3 - p7

c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22)))) return c

 

x=np.array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])

y=np.array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])

print(strmm(x,y))

 


Comments

Post a Comment

Popular posts from this blog

2. Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.

Image
 In Cisco Packet Tracer, you can simulate this scenario by configuring access control lists (ACLs) on routers to control the flow of traffic between the networks. Here's a basic example: Procedure  1. **Create the Networks:**    - Place three routers on the workspace and label them R1, R2, and R3.    - Connect the routers as follows:      - Connect R1 to R2 and R3.      - Connect R2 to R3.    - Assign IP addresses to the router interfaces for each network (N1, N2, N3). 2. **Configure Router ACLs:**    - Access the CLI of each router.    For R1 (assuming FastEthernet interfaces):    ```bash    enable    configure terminal    interface FastEthernet0/0    ip address <N1_IP> <Subnet_Mask>    exit    interface FastEthernet0/1    ip address <N2_IP> <Subnet_Mask>    exit    access-li...
Read more

Kruskal algorithm using greedy technique.

Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do       { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then        { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); }                 } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Read more