Reference

• 방송통신대학 - 컴퓨터과학 개론(자료구조)
• Mathworks - MATLAB을 활용한 AI

---

희소 행렬(Sparse Matrix)이 뭔가요

• 배열을 이용하여 행렬을 표현하는 2가지 방법

• 2차원 배열을 이용하여 전체 요소를 저장하는 방법
  0이 아닌 요소들만 저장하는 방법(위치, 요소)

• 대부분의 항들이 0인 배열

---

희소 행렬 예시

1. 2차원 배열에 전체 요소를 저장 하는 경우
   장점 : 연산 구현이 간단함
   단점 : 대부분의 항이 0인 희소 행렬의  경우에는 메모리 공간낭비가 있음

2. 0이 아닌 요소들만 저장하는 경우
   장점 : 희소 행렬에 경우에는 메모리 공간 절약이 된다.
   단점 : 각종 행렬 연산들의 구현이 복잡해진다

• 형태 : "[(x,y),요소]" 식으로 저장

#include <stdio.h>
#define MAX_TERMS 101

typedef struct {
	int row;
	int col;
	int value;
} element;


typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows; // 행의 개수
	int cols; // 열의 개수
	int terms; // 항의 개수
} SparseMatrix;


SparseMatrix matrix_transpose2(SparseMatrix a) {
	SparseMatrix b;
	int bindex; // 행렬 b에서 현재 저장 위치
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;
	if (a.terms > 0) {
		bindex = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {
				b.data[bindex].row = a.data[i].col;
				b.data[bindex].col = a.data[i].row;
				b.data[bindex].value = a.data[i].value;
				bindex++;
				}
			}
		}
	}
	return b;
}

void matrix_print(SparseMatrix a) {
	printf("====================\n");
	for (int i = 0; i<a.terms; i++) {
		printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);
	}
	printf("====================\n");
}


int main(void) {
	SparseMatrix m = {
		{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},
        6,
		6,
		7
	};
	SparseMatrix result;
	result = matrix_transpose2(m);
	matrix_print(result);
	return 0;
}

행렬 전치
행을 열로 열을 행으로 바꾸어놓는 것

#include <stdio.h>

#define ROWS 3
#define COLS 3

void matrix_transp(int A[ROWS][COLS], intB[ROWS][COLS]){
	for (int r= 0; r<ROWS; r++){
    	for (int c=0; c<COLS; c++){
        	B[c][r] = A[r][c];
        }
    }
}

void matrix_print(int A[ROWS][COLS]){
	printf("===================\n");
    for (int r=0;r<ROWS;r++){
    	for (int c=0;c<COLS;c++){
        	printf("%d", A[r][c]);
        }
        printf("\n");
    }
    printf("===================\n");
}

int main(void){
	int array1[ROWS][COLS] = {{2,3,0}, {8,9,1}, {7,0,5}};
    int array2[ROWS][COLS];
    matrix_transp(array1,array2);
    matrix_print(array1);
    matrix_print(array2);
    
    return 0;
}
 
 

---

희소 행렬이 해결하는 문제는 무엇인가요?

그렇다면 이것을 왜 사용하는가?
조사해본 결과, 메모리 낭비를 절약하는 방식과 연산을 편하게 하는 방식이 있으며
그것의 장단점과 도대체 어떤식으로 구현이 되는지 코드를 참고하여 알아보는게 좋을 것 같다고 생각이 들었지만
강의에서는 요즘은 컴퓨터 성능 빵빵.. GPU 메모리 빵빵하다고 얘기하고 넘어갔다..

내가 알아본 희소행렬을 통해 우리가 얻을 수 있는 이점

• 메모리 관리
  • 행렬에서 0이 아닌 요소만 해당 인덱스와 함께 저장
  • 0 요소에 대한 연산을 제거하여 계산 시간을 줄일 수 있다.
• 연산 효율성
  • 불필요한 로우 레벨 산술 연산을 수행하지 않으며 그 결과 얻게 되는 효율성으로, 대량의 희소 형식 데이터를 사용하여 작업을 수행하는 프로그램의 실행 시간에 급격한 향상이 이뤄질 수 있다고 한다.
    • 치환과 재정렬, 희소성을 위한 재정렬, 대역폭 감소를 위한 재정렬, AMD(Approximate Minimum Degree) 정렬... 등등 mathworks에 예시와 자세한 내용이 정리되어 있음!