희소 행렬 압축 편집하기

희소 행렬 압축(sparse matrix compression)은 요소의 대부분이 0인 희소 행렬을 저장 및 계산할 때, 0이 아닌 원소만을 효율적으로 표현하여 메모리와 연산 효율을 높이는 기술이다.
==개념 및 필요성==
*희소 행렬(sparse matrix)이란 행렬 원소 중 0이 아닌 값(nonzero)이 전체 원소 대비 매우 적은 비율을 차지하는 행렬이다.
*밀집 행렬(dense matrix) 방식으로 저장하면 많은 0 값도 공간을 차지하므로 비효율적이다.
*따라서 희소 행렬 압축은 0 값을 건너뛰고, 비(非)제로 값을 중심으로 저장하고 연산하는 방식이 필요하다.
*이는 대형 그래프 인접 행렬, 기계 학습 특성 행렬, 과학/공학 응용의 선형 시스템 등에서 매우 중요하다.
==대표 저장 방식==
여러 방법이 존재하며, 각각 장단점이 있다:
*'''Coordinate (COO) 형식'''
**행렬의 비제로 원소 각각에 대해 (행 인덱스, 열 인덱스, 값) 튜플을 저장
**구현이 단순하고 직관적이며 추가/수정이 유연하다는 장점이 있다
**하지만 행 또는 열 기반 연산에서는 비효율적일 수 있다

*'''Compressed Sparse Row (CSR, 압축 행 기준)'''
**각 비제로 원소의 값을 담은 배열(Val)
**각 비제로 원소의 열 인덱스를 담은 배열(ColIdx)
**각 행의 시작 위치를 담은 배열(RowPtr)
**행 방향 연산(예: 행벡터 곱셈)에 유리하다

*'''Compressed Sparse Column (CSC, 압축 열 기준)'''
**CSR의 전치된 방식으로, 열 중심 연산에 유리하다
**각 비제로 원소의 값, 각 비제로 원소의 행 인덱스, 각 열의 시작 위치를 저장

*'''Block Sparse Row / Block Sparse Column (BSR / BSC)'''
**행 또는 열을 블록 단위로 묶어 저장
**블록 내에 0이 일부 포함될 수 있지만, 패턴이 구조화돼 있거나 블록 단위 연산이 유리한 경우 사용

*'''기타 압축 기법 및 응용형 포맷'''
**희소 텐서 압축 기법 (예: Compressed Sparse Fibers, CSF)
**행렬 재배치(reordering) + 압축 기법 결합
**손실 압축 기법 (예: 근사 압축 방식)
==재배치 및 최적화 기법==
저장 방식만큼이나 중요한 것은 '''재배치와 최적화''' 전략이다:
*'''대역폭 최소화 재배치''' (예: Cuthill–McKee 알고리즘)
**대각선을 중심으로 비제로 원소가 모이게 행/열 순서를 재배치
**LU 분해나 가우스 소거 시 “fill-in(제로가 아닌 원소가 새로 생기는 현상)”을 줄이는 데 유리
**Reverse Cuthill-McKee 등 변형 기법 존재

*'''최소 차수 알고리즘''' (Minimum Degree Algorithm)
**대각화, 분해 시 발생할 비제로 증가를 줄이기 위해 변수의 차수를 기준으로 순서를 선택하는 방식

*'''하드웨어 가속 및 비트맵 기반 인덱싱''' (예: SMASH)
**지시자(pointer chasing) 연산을 줄이고 인덱싱 비용을 낮추는 구조와 하드웨어 협조 방식 제안됨
==압축 효과 및 연산 비용==
*저장 공간 절감: 비제로 원소만 저장하므로 밀집 방식 대비 메모리 사용량을 크게 줄일 수 있다
*계산 효율성: 0 요소를 건너 뛰므로 연산량 감소
*단, 인덱스 배열 관리, 포인터 연산, 캐시 효율 저하 등의 오버헤드가 존재
*압축 방식과 포맷에 따라 특정 연산(예: 행벡터 곱, 열벡터 곱, 전치 등)에 강점 또는 약점이 있음
==최신 연구 동향 및 응용==
*'''NeuKron''': 희소 행렬을 재배치하고 순환 신경망을 사용해 상수 크기로 손실 압축하는 방법 제안됨
*'''LoSparse''': 행렬을 저순위 근사 + 희소 근사 합으로 표현해 모델 압축 성능 개선 시도
==같이 보기==
*[[신경망 가지치기]]
*[[모델 압축]]
*[[희소 데이터]]
*[[행렬 분해]]
*[[텐서 압축]]
==참고 문헌==
*Nazli Goharian 외, “Comparative Analysis of Sparse Matrix Algorithms”
*Konstantinos Kanellopoulos 등, “SMASH: Co‑designing Software Compression and Hardware‑Accelerated Indexing for Efficient Sparse Matrix Operations”
*Taehyung Kwon 등, “NeuKron: Constant‑Size Lossy Compression of Sparse Reorderable Matrices and Tensors”
*Yixiao Li 등, “LoSparse: Structured Compression of Large Language Models based on Low‑Rank and Sparse Approximation”
==각주==
[[분류:데이터]]
[[분류:압축]]
[[분류:자료구조]]