CSR (압축)

CSR (Compressed Sparse Row, 압축 행 기준)은 희소 행렬을 저장하고 연산할 때 행 중심 접근을 빠르게 지원하는 압축 저장 방식이다.

개념

CSR은 행렬의 각 행(row)에 대해, 0이 아닌 원소(nonzero)들만 순차적으로 저장하고, 각 행이 시작하는 지점을 인덱스로 관리하는 방식이다. 이 방식은 행 접근(row slicing)이나 행 단위 연산(예: 행‑벡터 곱셈)에 효율적이다.

구성 요소

CSR 방식은 보통 다음 세 개의 1차원 배열을 사용하여 희소 행렬을 표현한다:

• values — 행렬의 0이 아닌 원소들의 값을 저장한 배열
• colIndex — 각 비제로 원소가 속한 열(column) 번호를 저장한 배열
• rowPtr — 각 행이 시작되는 위치를 나타내는 포인터 배열 (행 시작 인덱스)

rowPtr의 길이는 (행의 개수 + 1)이며, rowPtr[i]는 values 및 colIndex 배열 내에서 i번째 행의 첫 번째 비제로 원소가 저장된 인덱스를 가리킨다. 마지막 rowPtr[n]은 전체 비제로 원소 수, 즉 values 배열의 길이와 같다.

동작 원리 및 접근

행 i의 원소들을 순회하거나 접근할 때는 다음과 같은 방식으로 처리된다:

1. 시작 인덱스 = rowPtr[i]
2. 끝 인덱스 = rowPtr[i+1]
3. values[k] 및 colIndex[k] (k = 시작 인덱스부터 끝 인덱스 − 1 까지)들을 통해:
   1. (i, colIndex[k]) 위치에 값 values[k] 존재
   2. 나머지 위치는 0

장점

• 행 중심 접근이 빠르다 — 행 벡터 곱(row-vector multiplication)에 유리하다
• 메모리 절약 — 0 원소는 저장하지 않으므로 공간 효율성 증가
• 행 범위 인덱싱(row slicing) 및 행 연산에 유리하다

단점

• 열 방향 접근(column slicing)은 비효율적이다 — 열 인덱스를 직접 탐색해야 한다
• 희소 구조 변경(예: 새로운 비제로 원소 삽입/삭제) 시 비용이 크다
• 인덱스 배열 관리와 포인터 연산에 따른 오버헤드 존재

응용 및 구현 사례

• 수치 해석, 선형 대수 계산, 그래프 인접 행렬 표현 등에서 널리 쓰인다
• Python의 SciPy 패키지에서 csr_matrix로 구현되어 있다
• CSR5 형식 등 고성능 개선 버전들이 연구되고 있다

같이 보기

• CSC (압축)
• 희소 행렬 압축
• 신경망 가지치기
• 모델 압축

참고 문헌

• Wei, Y., Zhang, W., Li, Z., & Zhang, J. (2016). “Efficient Sparse Matrix-Vector Multiplication on GPUs using the CSR5 Format.”
• SciPy Documentation: scipy.sparse.csr_matrix