-
Notifications
You must be signed in to change notification settings - Fork 0
/
Strassen_Graph.py
123 lines (98 loc) · 4.04 KB
/
Strassen_Graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import timeit
import perf
import random
import matplotlib.pyplot as plt
###Split a matrix into four equal-sized submatrices.
def split_matrix(matrix):
rows, cols = len(matrix), len(matrix[0])
split_row, split_col = rows // 2, cols // 2
# Split the matrix into four submatrices
A11 = [row[:split_col] for row in matrix[:split_row]]
A12 = [row[split_col:] for row in matrix[:split_row]]
A21 = [row[:split_col] for row in matrix[split_row:]]
A22 = [row[split_col:] for row in matrix[split_row:]]
return A11, A12, A21, A22
### Add two matrices element-wise.
def add_matrices(matrix1, matrix2):
return [
[matrix1[i][j] + matrix2[i][j] for j in range(len(matrix1[0]))]
for i in range(len(matrix1))
]
###Subtract one matrix from another element-wise.
def subtract_matrices(matrix1, matrix2):
return [
[matrix1[i][j] - matrix2[i][j] for j in range(len(matrix1[0]))]
for i in range(len(matrix1))
]
###Strassen's Matrix Multiplication algorithm.
def strassen(matrix1, matrix2):
# Base case: if matrices are 1x1, perform standard multiplication
if len(matrix1) == 1:
return [[matrix1[0][0] * matrix2[0][0]]]
# Split matrices into submatrices
A11, A12, A21, A22 = split_matrix(matrix1)
B11, B12, B21, B22 = split_matrix(matrix2)
# Calculate intermediate matrices
P1 = strassen(A11, subtract_matrices(B12, B22))
P2 = strassen(add_matrices(A11, A12), B22)
P3 = strassen(add_matrices(A21, A22), B11)
P4 = strassen(A22, subtract_matrices(B21, B11))
P5 = strassen(add_matrices(A11, A22), add_matrices(B11, B22))
P6 = strassen(subtract_matrices(A12, A22), add_matrices(B21, B22))
P7 = strassen(subtract_matrices(A11, A21), add_matrices(B11, B12))
# Calculate result submatrices
C11 = subtract_matrices(add_matrices(P5, P4), subtract_matrices(P2, P6))
C12 = add_matrices(P1, P2)
C21 = add_matrices(P3, P4)
C22 = subtract_matrices(subtract_matrices(P5, P3), subtract_matrices(P1, P7))
# Combine result submatrices into the final result matrix
result = [
C11[i] + C12[i]
for i in range(len(C11))
] + [
C21[i] + C22[i]
for i in range(len(C21))
]
return result
def generate_random_matrix(rows, cols , seed = None):
if seed is not None :
random.seed(Seed)
else:
return [[random.randint(1, 100) for _ in range(cols)] for _ in range(rows)]
def benchmark(matrix_size, repetitions=5, warm_up_runs=3, seed=None):
runtimes = []
# Warm-up runs to stabilize the system and trigger optimizations
for _ in range(warm_up_runs):
matrix1 = generate_random_matrix(matrix_size, matrix_size, seed=seed)
matrix2 = generate_random_matrix(matrix_size, matrix_size, seed=seed)
strassen(matrix1, matrix2) # Warm-up run
# Actual benchmarking repetitions
for _ in range(repetitions):
matrix1 = generate_random_matrix(matrix_size, matrix_size, seed=seed)
matrix2 = generate_random_matrix(matrix_size, matrix_size, seed=seed)
# Repeat the measurement and calculate average runtime
start_time = timeit.default_timer()
strassen(matrix1, matrix2)
end_time = timeit.default_timer()
runtime = end_time - start_time
runtimes.append(runtime)
print(f"Matrix size: {matrix_size}x{matrix_size}")
print(f"Run {len(runtimes)} - Runtime: {runtime} seconds")
print("The result is", strassen(matrix1, matrix2)[0][:min(matrix_size, 5)], "...")
print()
return runtimes # Return the list of runtimes for further analysis
# Collect benchmark data
matrix_sizes = [2,4,8,16,32,64,128]
repetitions = 10
runtimes = []
for matrix_size in matrix_sizes:
runtime = benchmark(matrix_size, repetitions=repetitions)
runtimes.append(runtime)
# Plotting
plt.plot(matrix_sizes, runtimes, marker='o')
plt.title('Strassen Algorithm Benchmark')
plt.xlabel('Matrix Size')
plt.ylabel('Average Runtime (seconds)')
plt.yscale('log') # Use logarithmic scale for better visualization
plt.grid(True)
plt.show()