컴퓨터좀 만져본 사람중 행렬 곱셈 코드를 안짜본 사람은 없다.
나도 이제 깨우치는 중이지만 상당히 많은 데이터가 행렬의 형태를 띄고, 많은 문제들이 수학적으로 모델링 될 때 행렬곱셈 연산이 포함되기 때문에 행렬 곱셈은 컴퓨터공학도에게는 꽤 중요한 연산중 하나다.
희소행렬
최근 데이터가 커지고 네트워크가 희소해지면서 희소행렬에 대한 연산이 중요해지고 있는데 희소행렬은 일반적인 행렬과 달리 2D array의 형태로 저장되지 않는다.
이유는 메모리 효율성 때문이다. 행렬이 N x N 이라면 2D array의 형태로 저장하기 위해선 N2의 메모리공간이 필요하다.
Space complexity for 2D array : \(O(N^{2})\)
따라서 스케일이 크고 희소한 행렬은 크게 두가지 포맷을 이용한다.
COO format
각각의 원소는 (row, col, value)로 표현된다.
위 행렬을 coo 포맷으로 저장하면 다음과 같다.
typedef struct _coo {
int row;
int col;
double val;
}coo;
typedef struct _spmat{
coo* elem;
}spmat;
int main(){
spmat A;
A.elem = (double*)malloc(sizeof(double)*4);
A.elem[0].row = 1; A.elem[0].col = 0; A.elem[0].val = 5;
A.elem[1].row = 1; A.elem[1].col = 1; A.elem[1].val = 8;
A.elem[2].row = 2; A.elem[2].col = 2; A.elem[2].val = 3;
A.elem[3].row = 3; A.elem[3].col = 1; A.elem[3].val = 6;
return 0;
}
희소행렬을 COO format으로 저장한다면 행렬원소의 개수가 E일 경우 필요한 메모리 공간은 대략 3E이다.
Space complexity for COO : \(O(3E)\)
COO 포맷은 굉장히 직관적이고 어느정도의 메모리 효율성을 보장하지만 실제 연산에서는 자주 이용되지 않는다.
이유는 각 행이나 열에 direct access 할 수가 없기 때문이다.
실제 연산에서는 CSR(Compressed Sparse Row), CSC(Compressed Sparse Column) 포맷을 이용한다.
Compressed sparse format 는 3개의 array(ptr, idx , val)로 이루어져 있다.
CSR 포맷을 예로 들어보면
ptr array는 각 행의 첫 원소의 위치를 저장하고
idx array는 각 원소의 col을 저장하고
val array는 각 원소의 value를 저장한다.
COO 포맷과 다른 것은 ptr array 뿐이다.
#define ROW_MAJOR 0
#define COL_MAJOR 1
typedef struct _cs {
int number_of_rows;
int number_of_cols;
int number_of_elems;
int order;
int* ptr;
int* idx;
double* val;
}cs;
typedef struct _spmat{
coo* elem;
cs csr;
cs csc;
}spmat;
int main(){
spmat A;
// CSR representation
A.csr.order = ROW_MAJOR;
A.csr.number_of_rows = 4;
A.csr.number_of_cols = 4;
A.csr.number_of_elems = 4;
A.csr.ptr = (int*)malloc(sizeof(int)*(number_of_rows+1));
A.csr.idx = (int*)malloc(sizeof(int)*(number_of_elems));
A.csr.val = (double*)malloc(sizeof(double)*(number_of_elems));
A.csr.ptr[0] = 0; // ptr[0] is always zero
A.csr.ptr[1] = 0; // because there's no nonzero element in row 0
A.csr.ptr[2] = 2; // two nonzero elements in row 1
A.csr.ptr[3] = 3; // one nonzero elements in row 2
A.csr.ptr[4] = 4; // one nonzero elements in row 3
A.csr.idx[0] = 0;
A.csr.idx[1] = 1;
A.csr.idx[2] = 2;
A.csr.idx[3] = 1;
A.csr.val[0] = 5;
A.csr.val[1] = 8;
A.csr.val[2] = 3;
A.csr.val[3] = 6
return 0;
}
만약 위 행렬에서 row 1 에 대한 탐색을 하고싶다면 A.csr.ptr[1]을 참조하고 A.csr.ptr[2]-A.csr.ptr[1] 개의 원소를 탐색하면 된다
CSC 포맷은 CSR 포맷과 구조는 같지만 column-major order로 저장되고 ptr는 각 열의 첫번째 원소의 위치, idx array는 행 값을 저장한다.
희소행렬을 CSR/CSC format으로 저장한다면 행렬원소의 개수가 E, 행렬의 크기가 NxN일 경우 필요한 메모리 공간은 N+2E이다.
Space complexity for CSC,CSR : \(O(N+2E)\)
희소행렬 데이터 소스 :
https://sparse.tamu.edu/
