COO (압축)

COO(Coordinate, 좌표 형식 또는 triplet 형식)은 희소 행렬을 저장할 때 가장 직관적이고 간단한 방식 중 하나이다.

개념

COO 방식은 비제로(nonzero) 원소 각각을 (행 인덱스, 열 인덱스, 값) 튜플로 표현하는 방식이다. 즉, 세 개의 배열(행 인덱스 배열, 열 인덱스 배열, 값 배열)을 병렬로 유지하며, 배열의 같은 위치에서 대응되는 원소들이 하나의 비제로 항목을 나타낸다.

구성 요소

COO 방식은 보통 다음 세 배열로 표현된다:*rowIndices — 비제로 원소들의 행 인덱스 배열

• colIndices — 비제로 원소들의 열 인덱스 배열
• values — 비제로 원소들의 값 배열

각 배열의 길이는 nnz (non-zero count)이며, rowIndices[i], colIndices[i], values[i]는 비제로 원소 하나를 나타낸다.

특징 및 동작

• 데이터 삽입과 구성이 용이하다 — 비제로 원소를 순서대로 추가하여 구성할 수 있다.
• 정렬되지 않은 상태로 유지하는 경우가 많으며, 연산 전에 행 또는 열 기준으로 정렬할 수 있다.
• 전치(transpose) 연산 시, 행 인덱스 배열과 열 인덱스 배열을 교환하면 된다.
• COO는 주로 행렬을 생성하거나 수정하는 단계에서 사용되고, 연산을 위해 CSR 또는 CSC 등으로 변환되는 경우가 많다.

장점

• 구현이 단순하고 직관적이다.
• 비제로 원소를 추가하거나 편집하는 데 유리하다.
• 동일 위치에 여러 원소가 중복되는 경우 쉽게 병합할 수 있다.

단점

• 연산 성능은 떨어질 수 있다 — COO 상태로는 행렬-벡터 곱 연산 등에 비효율적이다.
• 랜덤 액세스나 행/열 슬라이싱이 비효율적이다.
• 대규모 연산 목적에는 CSR, CSC 방식보다 부적합할 수 있다.

응용 및 변환

• 과학 컴퓨팅 라이브러리인 SciPy에서는 coo_matrix 클래스로 COO 형식을 제공한다.
• 연산 효율을 위해 보통 COO에서 CSR 또는 CSC 형식으로 변환하여 사용된다.
• 전치 행렬은 rowIndices와 colIndices를 교환함으로써 얻을 수 있다.

예시

다음은 4x4 희소 행렬을 COO 형식으로 표현한 예이다:

행렬:

0  0  3  0  
22  0  0  0
7  5  0  0  
0  0  0  1  

COO 형식으로 표현하면 다음과 같다:

• rowIndices = [0, 1, 2, 2, 3]
• colIndices = [2, 0, 0, 1, 3]
• values = [3, 22, 7, 5, 1]

각 원소는 (행, 열, 값) = (0,2,3), (1,0,22), (2,0,7), (2,1,5), (3,3,1)을 나타낸다.

코드 예시

다음은 Python의 SciPy 라이브러리를 사용하여 COO 형식의 행렬을 생성하고 활용하는 예제이다:

import numpy as np
from scipy.sparse import coo_matrix

# 비제로 원소의 좌표와 값
row = np.array([0, 1, 2, 2, 3])
col = np.array([2, 0, 0, 1, 3])
data = np.array([3, 22, 7, 5, 1])

# COO 형식으로 희소 행렬 생성
sparse_mat = coo_matrix((data, (row, col)), shape=(4, 4))

# 밀집 행렬(dense matrix)로 변환하여 출력
print(sparse_mat.toarray())

실행 결과:

[[ 0  0  3  0]
 [22  0  0  0]
 [ 7  5  0  0]
 [ 0  0  0  1]]

같이 보기

• CSR (압축)
• CSC (압축)
• 희소 행렬 압축
• 텐서 압축

참고 문헌

• Saad, Y. (2003). *Iterative Methods for Sparse Linear Systems*. SIAM.