A summary of three methods for Python to achieve matrix multiplication

Problem description

Three algorithms of matrix multiplication are implemented respectively, and the size of the three algorithms is 22∗ respectively. 2222 the & # 8727; 22, 23 & # 8727; 2323 the & # 8727; 23, 24 & # 8727; 2424 the & # 8727; 24, 25 & # 8727; 2525 the & # 8727; 25, 26 & # 8727; 2626 the & # 8727; 26, 27 & # 8727; 2727 the & # 8727; 27, 28 & # 8727; 2828 the & # 8727; 28, 29 & # 8727; 2929 the & # 8727; The running time at 29 is multiplied by the matrix with MATLAB, and the time comparison diagram is drawn.

The problem solving method

This paper adopts the following methods to evaluate: matrix calculation method, definition method, divide-and-conquer method and Strassen method. Here we use Matlab and Python to deal with this problem and compare the speed difference between the two languages under the condition of 1.

A programming language

Python

Specific code

#-*- coding: utf-8 -*-
from matplotlib.font_manager import FontProperties
import numpy as np
import time
import random
import math
import copy
import matplotlib.pyplot as plt

#n = [2**2, 2**3, 2**4, 2**5, 2**6, 2**7, 2**8, 2**9, 2**10, 2**11, 2**12]
n = [2**2, 2**3, 2**4, 2**5, 2**6, 2**7, 2**8, 2**9, 2**10, 2**11]
Sum_time1 = []
Sum_time2 = []
Sum_time3 = []
Sum_time4 = []
for m in n:
 A = np.random.randint(0, 2, [m, m])
 B = np.random.randint(0, 2, [m, m])
 A1 = np.mat(A)
 B1 = np.mat(B)
 time_start = time.time()
 C1 = A1*B1
 time_end = time.time()
 Sum_time1.append(time_end - time_start)

 C2 = np.zeros([m, m], dtype = np.int)
 time_start = time.time()
 for i in range(m):
  for k in range(m):
   for j in range(m):
    C2[i, j] = C2[i, j] + A[i, k] * B[k, j]
 time_end = time.time()
 Sum_time2.append(time_end - time_start)
 A11 = np.mat(A[0:m//2, 0:m//2])
 A12 = np.mat(A[0:m//2, m//2:m])
 A21 = np.mat(A[m//2:m, 0:m//2])
 A22 = np.mat(A[m//2:m, m//2:m])
 B11 = np.mat(B[0:m//2, 0:m//2])
 B12 = np.mat(B[0:m//2, m//2:m])
 B21 = np.mat(B[m//2:m, 0:m//2])
 B22 = np.mat(B[m//2:m, m//2:m])
 time_start = time.time()
 C11 = A11 * B11 + A12 * B21
 C12 = A11 * B12 + A12 * B22
 C21 = A21 * B11 + A22 * B21
 C22 = A21 * B12 + A22 * B22
 C3 = np.vstack((np.hstack((C11, C12)), np.hstack((C21, C22))))
 time_end = time.time()
 Sum_time3.append(time_end - time_start)
 time_start = time.time()
 M1 = A11 * (B12 - B22)
 M2 = (A11 + A12) * B22
 M3 = (A21 + A22) * B11
 M4 = A22 * (B21 - B11)
 M5 = (A11 + A22) * (B11 + B22)
 M6 = (A12 - A22) * (B21 + B22)
 M7 = (A11 - A21) * (B11 + B12)
 C11 = M5 + M4 - M2 + M6
 C12 = M1 + M2
 C21 = M3 + M4
 C22 = M5 + M1 - M3 - M7
 C4 = np.vstack((np.hstack((C11, C12)), np.hstack((C21, C22))))
 time_end = time.time()
 Sum_time4.append(time_end - time_start)

f1 = open('python_time1.txt', 'w')
for ele in Sum_time1:
 f1.writelines(str(ele) + '\n')
f1.close()

f2 = open('python_time2.txt', 'w')
for ele in Sum_time2:
 f2.writelines(str(ele) + '\n')
f2.close()

f3 = open('python_time3.txt', 'w')
for ele in Sum_time3:
 f3.writelines(str(ele) + '\n')
f3.close()

f4 = open('python_time4.txt', 'w')
for ele in Sum_time4:
 f4.writelines(str(ele) + '\n')
f4.close()

font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=8)
plt.figure(1)
plt.subplot(221)
plt.semilogx(n, Sum_time1, 'r-*')
plt.ylabel(u" time (s)", fontproperties=font)
plt.xlabel(u" Dimension of a matrix n", fontproperties=font)
plt.title(u'python Built-in method ', fontproperties=font)
plt.subplot(222)
plt.semilogx(n, Sum_time2, 'b-*')
plt.ylabel(u" time (s)", fontproperties=font)
plt.xlabel(u" Dimension of a matrix n", fontproperties=font)
plt.title(u' Define the method ', fontproperties=font)
plt.subplot(223)
plt.semilogx(n, Sum_time3, 'y-*')
plt.ylabel(u" time (s)", fontproperties=font)
plt.xlabel(u" Dimension of a matrix n", fontproperties=font)
plt.title( u' Divide and conquer method ', fontproperties=font)
plt.subplot(224)
plt.semilogx(n, Sum_time4, 'g-*')
plt.ylabel(u" time (s)", fontproperties=font)
plt.xlabel(u" Dimension of a matrix n", fontproperties=font)
plt.title( u'Strasses method ', fontproperties=font)
plt.figure(2)
plt.semilogx(n, Sum_time1, 'r-*', n, Sum_time2, 'b-+', n, Sum_time3, 'y-o', n, Sum_time4, 'g-^')
#plt.legend(u'python Built-in method ', u' Define the method ', u' Divide and conquer method ', u'Strasses method ', fontproperties=font)
plt.show()