희소 행렬 (r1)

COO는 희소 행렬을 표현하는 가장 기본적인 방식 중 하나이다. COO는 Coordinate List 또는 Coordinate Format이라고도 불리며, 0이 아닌 요소의 값과 그 요소의 행 인덱스, 열 인덱스를 각각의 리스트에 순서대로 저장하는 방식이다. 예를 들어, (2, 3) 위치에 값 5가 있다면, 행 인덱스 리스트에 2, 열 인덱스 리스트에 3, 값 리스트에 5를 추가하는 식으로 데이터를 구성한다.

이 방식은 구현이 직관적이고 간단하다는 장점이 있다. 또한 새로운 0이 아닌 요소를 삽입하거나 삭제하는 작업이 비교적 용이하다. 데이터가 (행, 열, 값)의 튜플 형태로 저장되기 때문에, 행렬의 특정 위치에 대한 접근이나 순회가 자유롭다. 이는 그래프 알고리즘에서 인접 행렬을 구성할 때나, 초기 데이터 수집 단계에서 유용하게 활용된다.

그러나 COO 형식은 저장 공간과 계산 효율성 측면에서 한계를 가진다. 세 개의 리스트를 모두 유지해야 하므로, 다른 압축 형식에 비해 상대적으로 메모리 오버헤드가 크다. 또한 행렬과 벡터의 곱셈과 같은 연산을 수행할 때, 요소들이 행 또는 열 순서로 정렬되어 있지 않으면 캐시 효율이 떨어져 성능이 저하될 수 있다. 따라서 COO는 주로 데이터 입출력이나 간단한 변환 과정에서의 중간 저장 형식으로 사용되며, 실제 대규모 계산에는 CSR이나 CSC와 같은 더욱 압축된 형식으로 변환되어 활용되는 경우가 많다.

CSR은 희소 행렬을 표현하는 가장 일반적이고 효율적인 방식 중 하나이다. 이 방식은 0이 아닌 요소의 값과 열 인덱스를 저장하는 동시에, 각 행의 시작 위치를 별도의 배열로 압축하여 관리한다. 이는 COO 방식과 달리 중복된 행 인덱스 정보를 제거함으로써 메모리 사용을 더욱 최적화한다.

CSR 표현은 주로 세 개의 배열로 구성된다. values 배열은 0이 아닌 모든 요소의 값을 행 우선 순서로 저장한다. col_indices 배열은 각 값에 대응하는 열 인덱스를 저장한다. 가장 핵심적인 row_ptr 배열은 각 행의 첫 번째 요소가 values 배열에서 어디부터 시작하는지를 가리키는 포인터를 저장하며, 마지막 요소는 전체 0이 아닌 요소의 개수를 나타낸다. 이 구조 덕분에 특정 행의 모든 요소에 빠르게 접근할 수 있다.

이 방식의 주요 장점은 메모리 효율성과 행 단위 연산의 성능에 있다. row_ptr 배열의 길이는 행의 개수에 1을 더한 값이므로, 대규모 행렬에서 행 인덱스를 반복 저장하는 COO 방식에 비해 상당한 메모리 절약을 이룰 수 있다. 또한, 행렬 벡터 곱셈이나 특정 행의 요소를 순회하는 연산에서 매우 효율적이다. 이는 선형 시스템을 푸는 반복법이나 그래프 알고리즘에서 널리 활용되는 이유이다.

CSR의 단점은 행렬 구조 변경에 취약하다는 점이다. 새로운 0이 아닌 요소를 삽입하거나 삭제할 경우, row_ptr 배열 이후의 모든 데이터를 재조정해야 할 수 있어 비용이 크다. 또한, 열 단위 접근은 비효율적이어서, 열 단위 연산이 빈번한 경우에는 CSC 방식을 사용하는 것이 더 적합하다.

CSC (Compressed Sparse Column)는 희소 행렬을 표현하는 주요 방식 중 하나로, CSR (Compressed Sparse Row)과 유사한 원리이지만 열(Column) 중심으로 데이터를 압축한다는 점이 특징이다. 이 방식은 행렬의 각 열에 대해 0이 아닌 요소의 값과 그 요소의 행 인덱스를 저장하며, 열의 시작 위치를 가리키는 포인터 배열을 추가로 사용한다. 이로 인해 열 단위로 데이터에 접근하거나 연산을 수행할 때 매우 효율적이다.

CSC 형식은 주로 FORTRAN이나 MATLAB과 같이 열 우선(Column-major) 순서를 사용하는 수치 해석 및 과학 계산 환경에서 선호된다. 또한 선형 대수 라이브러리인 LAPACK이나 SuiteSparse와 같은 고성능 수치 라이브러리에서 내부 데이터 구조로 널리 채택되어 있다. CSR 형식이 행 단위 연산에 강점이 있다면, CSC는 열 단위 연산이나 전치 행렬 연산과 관련된 작업에서 유리한 구조를 가진다.

CSC 형식의 구체적인 저장 방식은 다음과 같은 세 가지 배열로 구성된다.

이 구조 덕분에 특정 열의 모든 0이 아닌 요소를 빠르게 순회할 수 있으며, 전체 메모리 사용량은 0이 아닌 요소의 개수에 비례하여 증가한다. 따라서 빅데이터나 고성능 컴퓨팅 분야에서 대규모 희소 행렬을 처리할 때 핵심적인 표현 방식으로 활용된다.

희소 행렬의 곱셈은 밀집 행렬과 동일한 수학적 정의를 따르지만, 연산 과정에서 0이 아닌 요소만을 효율적으로 처리하기 위한 특별한 알고리즘이 사용된다. 두 희소 행렬을 곱할 때, 결과 행렬은 일반적으로 피연산자 행렬보다 더 밀도가 높아질 수 있으며, 이는 예상치 못한 메모리 사용 증가를 초래할 수 있다. 따라서 알고리즘은 불필요한 0과의 연산을 최소화하면서, 결과 행렬의 새로운 0이 아닌 요소의 위치와 값을 효율적으로 계산하고 저장하는 데 중점을 둔다.

가장 일반적인 접근법은 CSR (Compressed Sparse Row) 형식이나 CSC (Compressed Sparse Column) 형식을 기반으로 한다. 예를 들어, CSR 형식으로 저장된 행렬 A와 CSC 형식으로 저장된 행렬 B를 곱하는 경우, A의 각 행과 B의 각 열 간의 내적을 계산하게 된다. 이때 내적 계산은 A 행의 0이 아닌 요소의 열 인덱스와 B 열의 0이 아닌 요소의 행 인덱스가 일치하는 경우에만 실제 곱셈이 발생하도록 최적화된다. 이 과정은 희소 행렬 곱셈의 핵심인 '스파스-스파스 곱셈'으로, 중간 결과를 임시로 누적하는 방식으로 구현된다.

효율적인 구현을 위해서는 결과 행렬의 구조를 사전에 예측하거나, 동적으로 생성하는 전략이 필요하다. 외적 곱셈(outer product) 방식이나 행별로 결과를 점진적으로 구성하는 방식 등 다양한 알고리즘이 존재하며, 수치 해석 라이브러리나 과학 계산 소프트웨어에서 이러한 고도로 최적화된 루틴을 제공한다. 이러한 연산은 머신러닝의 추천 시스템, 자연어 처리 모델, 또는 그래프 알고리즘에서 인접 행렬의 거듭제곱을 계산할 때 광범위하게 활용된다.

희소 행렬의 전치 행렬을 구하는 연산은 희소성의 특성을 활용하여 효율적으로 수행할 수 있다. 전치 연산은 행렬의 행과 열을 서로 바꾸는 작업으로, COO 형식에서는 저장된 각 요소의 행 인덱스와 열 인덱스 값을 단순히 교환함으로써 쉽게 구현된다. 이는 데이터 자체를 재배열할 필요 없이 인덱스 정보만 변경하면 되므로 매우 빠르게 처리된다.

반면, CSR이나 CSC 같은 압축된 형식에서는 전치 연산이 더 복잡해질 수 있다. CSR 형식은 행 기준으로 압축되어 있으므로, 이를 전치하면 열 기준으로 재구성된 CSC 형식과 동일한 구조가 된다. 따라서 CSR 행렬의 전치는 내부적으로 CSC 형식으로의 변환과 동일한 효과를 가지며, 이 과정에는 추가적인 정렬과 인덱스 배열의 재계산이 필요할 수 있다.

이러한 전치 연산의 효율성은 수치 해석이나 선형대수학에서 큰 희소 행렬을 다룰 때 중요하다. 예를 들어, 선형 시스템을 풀기 위한 반복법이나 그래프 알고리즘에서 인접 행렬을 전치하는 경우가 빈번히 발생한다. 적절한 저장 형식을 선택하고 전치 알고리즘을 최적화함으로써 전체적인 계산 성능을 크게 향상시킬 수 있다.

희소 행렬은 대규모 선형 시스템을 해결하는 데 필수적인 도구이다. 많은 공학 및 과학 문제, 예를 들어 유한 요소법이나 회로 해석은 방대한 연립방정식으로 이어지며, 이때 생성되는 계수 행렬은 대부분의 원소가 0인 희소 행렬의 형태를 띤다. 이러한 시스템을 해결하기 위해 가우스 소거법이나 LU 분해와 같은 직접법 또는 반복법 알고리즘을 적용할 때, 희소성을 고려하지 않은 일반 밀집 행렬 방식으로 처리하면 엄청난 메모리 낭비와 불필요한 계산(0과의 연산)이 발생한다.

따라서 희소 행렬을 위한 전용 선형대수학 라이브러리와 알고리즘이 개발되어 왔다. CSR이나 CSC와 같은 효율적인 저장 형식을 사용하면 0이 아닌 원소와 그 위치 정보만 저장하여 메모리 사용량을 극적으로 줄일 수 있다. 더 나아가, 채우기 감소를 위한 행렬 재배열 기법을 적용하면 인수분해 과정에서 발생하는 새로운 0이 아닌 원소의 수를 최소화하여 계산 효율을 더욱 높일 수 있다. 이는 수치 해석 분야의 핵심 과제 중 하나이다.

이러한 희소 선형 시스템 솔버는 컴퓨터 시뮬레이션, 컴퓨터 그래픽스, 최적화 문제 등 다양한 과학기술 계산의 기반을 이룬다. 대표적인 수치 해석 라이브러리인 LAPACK의 희소 행렬 버전이라 할 수 있는 SuiteSparse나 PETSc 같은 패키지들이 이 분야의 표준으로 널리 사용되고 있다.

희소 행렬은 그래프 이론에서 그래프를 표현하고 분석하는 데 핵심적인 자료구조로 활용된다. 인접 행렬은 그래프의 정점 간 연결 관계를 나타내는 가장 기본적인 행렬 표현 방식이다. 그러나 대부분의 실제 그래프, 특히 소셜 네트워크나 웹 그래프와 같이 정점 수에 비해 간선 수가 상대적으로 적은 희소 그래프의 경우, 인접 행렬의 대부분의 요소는 0이 된다. 이러한 희소성을 가진 인접 행렬을 그대로 저장하면 메모리 공간이 낭비되고, 너비 우선 탐색이나 페이지랭크 알고리즘과 같은 그래프 순회 및 분석 연산의 효율성이 떨어진다.

따라서 희소 행렬의 효율적인 저장 방식인 CSR이나 CSC 형식을 사용하여 인접 행렬을 표현한다. CSR 형식은 각 정점(행)에 연결된 이웃 정점들(열)의 목록을 압축하여 저장하므로, 특정 정점의 모든 이웃을 빠르게 순회하는 데 적합하다. 이는 그래프 알고이즘에서 가장 빈번하게 수행되는 연산 중 하나이다. 예를 들어, 최단 경로 문제를 푸는 다익스트라 알고리즘이나 벨만-포드 알고리즘은 반복적으로 정점의 이웃을 탐색하며 거리를 갱신하는데, CSR 형식의 희소 행렬 표현은 이러한 연산을 효율적으로 지원한다.

또한, 페이지랭크 알고리즘은 웹 페이지 간의 링크 구조를 매우 큰 희소 행렬(확률 행렬)로 모델링하고, 이 행렬의 주요 고유벡터를 반복적인 행렬-벡터 곱셈을 통해 계산한다. 이 과정에서 전체 조밀 행렬을 사용하는 대신 CSR 형식의 희소 행렬을 사용하면 메모리 사용량을 극적으로 줄이고 계산 속도를 높일 수 있다. 이처럼 희소 행렬 표현은 대규모 그래프 데이터를 처리하는 네트워크 분석과 추천 시스템의 기반이 된다.

머신러닝 분야에서 희소 행렬은 고차원 데이터를 효율적으로 표현하고 처리하는 데 핵심적인 역할을 한다. 특히 자연어 처리, 추천 시스템, 컴퓨터 비전 등에서 발생하는 데이터는 대부분의 특성값이 0인 경우가 많아 희소성을 띤다. 예를 들어, 문서를 단어의 출현 빈도로 표현하는 Bag-of-words 모델이나 TF-IDF 벡터는 단어 사전의 크기에 비해 실제 문서에 등장하는 단어는 극히 일부이기 때문에 희소 행렬로 표현된다.

이러한 희소 데이터를 밀집 행렬 형식으로 저장하면 메모리 공간을 낭비할 뿐만 아니라 불필요한 0 값에 대한 연산으로 인해 학습 속도가 크게 저하된다. 따라서 희소 행렬 표현 방식인 CSR이나 CSC를 사용하여 저장하고, 선형대수 라이브러리들은 희소 행렬에 최적화된 연산을 제공한다. Scikit-learn과 같은 머신러닝 라이브러리도 내부적으로 희소 행렬을 지원하여 메모리 사용량을 줄이고 행렬 곱셈 같은 연산의 효율을 높인다.

또한, 차원 축소 기법이나 특성 선택 알고리즘을 적용할 때도 희소 행렬 구조를 유지하며 계산하는 것이 중요하다. 최근의 많은 딥러닝 프레임워크도 희소 텐서에 대한 연산을 점차 지원하며, 대규모 그래프 신경망에서의 인접 행렬 표현 등 그 응용 범위는 계속 확장되고 있다.