Strassen および通常の行列乗算メソッドを実行する Python プログラムを作成しようとしています。ただし、createRandom Matrix 関数で作成されたランダムに生成されたマトリックスで Strassen 関数を実行しようとすると、次のエラーが発生します。
Traceback (most recent call last):
File "matrixMult.py", line 106, in <module>
print strassen(c, d, 10)
File "matrixMult.py", line 77, in strassen
p1 = strassen(addMatrix(a11,a22), addMatrix(b11,b22), n/2)
File "matrixMult.py", line 78, in strassen
p2 = strassen(addMatrix(a21,a22), b11, n/2)
File "matrixMult.py", line 82, in strassen
p6 = strassen(subMatrix(a21,a11), addMatrix(b11,b12), n/2)
File "matrixMult.py", line 62, in subMatrix
c.append(a[i][j] - b[i][j])
IndexError: list index out of range
これがコードです。ランダムに 10x10 マトリックスを作成し、それを使用して Strassen を実行しようとすると、前述のエラーが発生します。ただし、最後に定義した単純な 4x4 マトリックスを使用すると、strassen は正常に動作し、ランダムなマトリックスが問題なく生成されているように見えるので、問題がどこにあるのかわかりません。誰にもアイデアはありますか？
import random
import time
random.seed()
def createEmptyMatrix(x, y): # create empty matrix
matrix = [[0 for row in range(x)] for col in range(y)]
return matrix
def createRandomMatrix(size): # create matrix filled with random ints
matrix = []
matrix = [[random.randint(1,20) for row in range(size)] for col in range(10)]
return matrix
def regular(a, b): # standard O(n^3) matrix multiplication
c = createEmptyMatrix(len(a), len(b[0]))
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(b)):
c[i][j] += a[i][k]*b[k][j]
return c
def split(matrix): # split matrix into quarters for strassen
a = matrix
b = matrix
c = matrix
d = matrix
while(len(a) > len(matrix)/2):
a = a[:len(a)/2]
b = b[:len(b)/2]
c = c[len(c)/2:]
d = d[len(d)/2:]
while(len(a[0]) > len(matrix[0])/2):
for i in range(len(a[0])/2):
a[i] = a[i][:len(a[i])/2]
b[i] = b[i][len(b[i])/2:]
c[i] = c[i][:len(c[i])/2]
d[i] = d[i][len(d[i])/2:]
return a,b,c,d
def addMatrix(a, b): # add 2 matrices
d = []
for i in range(len(a)):
c = []
for j in range(len(a[0])):
c.append(a[i][j] + b[i][j])
d.append(c)
return d
def subMatrix(a, b): # subtract 2 matrices
d = []
for i in range(len(a)):
c = []
for j in range(len(a[0])):
c.append(a[i][j] - b[i][j])
d.append(c)
return d
def strassen(a, b, n): # strassen matrix multiplication method
#base case
if n == 1:
d = [[0]]
d[0][0] = a[0][0] * b[0][0]
return d
else:
a11, a12, a21, a22 = split(a)
b11, b12, b21, b22 = split(b)
p1 = strassen(addMatrix(a11,a22), addMatrix(b11,b22), n/2)
p2 = strassen(addMatrix(a21,a22), b11, n/2)
p3 = strassen(a11, subMatrix(b12,b22), n/2)
p4 = strassen(a22, subMatrix(b21,b11), n/2)
p5 = strassen(addMatrix(a11,a12), b22, n/2)
p6 = strassen(subMatrix(a21,a11), addMatrix(b11,b12), n/2)
p7 = strassen(subMatrix(a12,a22), addMatrix(b21,b22), n/2)
c11 = addMatrix(subMatrix(addMatrix(p1, p4), p5), p7)
c12 = addMatrix(p3, p5)
c21 = addMatrix(p2, p4)
c22 = addMatrix(subMatrix(addMatrix(p1, p3), p2), p6)
c = createEmptyMatrix(len(c11)*2,len(c11)*2)
for i in range(len(c11)):
for j in range(len(c11)):
c[i][j] = c11[i][j]
c[i][j+len(c11)] = c12[i][j]
c[i+len(c11)][j] = c21[i][j]
c[i+len(c11)][j+len(c11)] = c22[i][j]
return c
a = [[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]
b = [[5,5,5,5],[6,6,6,6],[7,7,7,7],[8,8,8,8]]
c = createRandomMatrix(10)
d = createRandomMatrix(10)
print "Strassen Outputs:"
#print strassen(c, d, 10)
print "Should be:"
print regular(c, d)
print c
print d
print a
print b
print strassen(a, b, 4)