[C로 쓴 자료구조] 희소행렬의 곱

희소 행렬을 < col, row , value > 3원소 쌍을 사용하는 1차원 배열로 구성하였을 때 두 희소 행렬의 곱을 구해보자.

 

두 희소행렬 a와 b를 < col, row , value > 3원소 쌍을 사용하는 1차원 배열로 구성

 

 

 

행렬 곱셈의 원리상 a행렬의 한 행과 b행렬의 한열을 곱하는데 희소 행렬 표시에서 같은 row(열)로 계산하면 편하므로 b행렬을 전치하여 col을 row로 변경 후 계산한다.

 

 

 

계산을 시작해보자

 

먼저 a행렬의 row가 0일 때, b행렬의 row가 0일 때 부터 시작하자

col = 0 -> a[0][0]: 15  *  b[0][0]: 1 = 15

col = 3 -> a[0][3]: 22 * b 존재하지 않음 

col = 5 -> a[0][5]: -15 * b 존재하지 않음

 

a행렬의 row가 0일 때, b행렬의 row가 1 일 때

col = 0 -> 

col = 3 -> a[0][3] : 22 * b[1][3] :1 = 22

col = 5 -> a[0][5] : -15 * b 존재하지 않음

 

a행렬의 row가 1일 때, b행렬의 row가 0일 때

col = 1 -> a[1][1] : 11 * b 존재하지 않음

col = 2 -> a[1][2] : 3 * b[0][2] : 3 = 9

 

a행렬의 row가 1일 때, b행렬의 row가 1일 때

col = 1 -> a[1][1] : 11 * b[1][1] : 1 = 11

col = 2 -> a[1][2] : 3 * b 존재하지 않음   

 

이처럼 계산하면

 

          row  col  value

d[0]       6    2     7

d[1]       0    0    15 

d[2]       0    1    22

d[3]       1    0      9

d[4]       1    1     11

d[5]       2    1     -6

d[6]       4    0     91

d[7]       5    0     84

 

결과 값이다.

 

 

 

여기서 아래와 같이 b[0][1]의 값이 1로 변경되었을 때,  a행렬의 row가 1일 때를  다시 계산해 보자.

 

 

a행렬의 row가 1일 때, b행렬의 row가 0일 때

col = 1 -> a[1][1] : 11 * b[0][1] : 1 = 11

col = 2 -> a[1][2] : 3 * b[0][2] : 3 = 9

d[1][0] : 11 + 9 = 20

 

a행렬의 row가 1일 때, b행렬의 row가 1일 때

col = 1 -> a[1][1] : 11 * b[1][1] : 1 = 11

col = 2 -> a[1][2] : 3 * b 존재하지 않음