최적의 행렬곱 연산 순서정하기

두개의 행렬이 있습니다.

행렬곱을 구하는 연산순서

A(3,4)행렬과 B(4,2) 행렬을 곱할경우, 위처럼 A Matrix의 Row와 B Matrix의 Col의 Vector 곱을 하게됩니다.

이때 한번의 Vector곱을 하기 위해서 4번의 곱,합 연산이 필요합니다.

때문에 행렬의 곱을 컴퓨터가 계산하기 위해선 4*3*2 = 24번의 곱,합 연산이 발생하죠

 

두개의 행렬을 곱할때는 한가지 경우만 있지만

 

행렬이 3개 이상일 경우 행렬곱을 할 수 있는 다양한 경우의수가 발생하게됩니다.

(Ex. A,B,C,D 행렬이 있다면 A(B(CD)), (AB)(CD), ((AB)C)D).....)

 

이 경우 Case에 따라 행렬곱을 계산하기위한 총 연산횟수가 다르게 됩니다.

 

이번 포스트의 알고리즘은 이 경우 중 최소한의 연산으로 행렬곱을 구하는 알고리즘이 되겠습니다.

 

 

해당 알고리즘은

1. N개의 행렬 중 2개의 행렬곱이 최소의 연산인 경우를 구한다

2. 2개의 행렬곱 결과를 하나의 행렬로 치환한다.

3. 행렬이 1개 남을때까지 1~2를 반복한다.

 

알고리즘은 간단합니다. 하지만 이번 알고리즘에서는 최소의 연산을 위한 행렬곱 순서또한 저장해야합니다.

 

해당 알고리즘은 전체에서 최적의 2개 Case를 찾는데 n2, 그리고 최 외곽에서 행렬이 1개남을때 까지 반복되기 때문에

O(n3)의 시간복잡도를 가집니다

 

파이썬으로 구현한 코드는 아래와 같습니다.

 

data = [[30,5],[5,20],[20,15],[15,10]]


def min_mat_mul_twmat(Data):    
    #최소 행렬곱을 산출하기 위해서, Infinit 값을 가진 변수를 준비합니다.
    min_count = 9999999
    #주어진 행렬들을 2개씩 조합하여 행렬곱을위한 연산 횟수를 계산하고
    #이 연산횟수가 가장 적은 값은 기록합니다
    for i in range(len(data)):
        for j in range(len(data)-(i+1)):            
            if data[i][1]==data[j+(i+1)][0]:
                if min_count > data[i][0]*data[i][1]*data[j+(i+1)][1]:
                    min_count = data[i][0]*data[i][1]*data[j+(i+1)][1]
                    first = i
                    second = j+(i+1)   
    #주어진 행렬 중 최소의 연산으로 행렬곱을 구할 수 있는 Case를 반환합니다
    return list([min_count, [first, second]])
                    

def min_mat_mul(Data, setting = list([0,[]])):    
    if len(Data)>1:
        #주어진 행렬 List에서 최소연산이 필요한 행렬곱 Case 반환
        temp = min_mat_mul_twmat(Data)        
        #Original List에서 최소연산의 행렬곱의 Case를 하나로 합쳐줍니다.
        Data[temp[1][0]] = [Data[temp[1][0]][0],Data[temp[1][1]][1]]
        del Data[temp[1][1]]
        #최소연산 행렬곱을 위한 연산 횟수와 연산Route를 저장합니다.
        setting[0] = temp[0] + setting[0]                
        setting[1] = temp[1] + setting[1]                
        min_mat_mul(Data, setting)        
        return setting        
    
min_mat_mul(data)

 

numpy나 pandas와 같은 패키지에서도, 이러한 사전 순서를 정하고 행렬곱은 연산하게 됩니다

(꼭 이 알고리즘이 아니더라두..)