희소 행렬(Sparse Matrix)은 대다수의 요소가 0인 행렬을 의미하며, 이러한 행렬의 특성을 활용하면 계산 효율성을 크게 향상시킬 수 있다. 본 장에서는 희소 행렬에 LU 분해를 적용할 때의 특수한 고려 사항과 효율적인 알고리즘을 다룬다.

희소 행렬의 특성과 LU 분해의 어려움

희소 행렬은 저장 공간을 절약하고 연산 속도를 향상시키는 데 유리하지만, LU 분해를 수행할 때 몇 가지 문제점이 발생할 수 있다. 일반적인 LU 분해 알고리즘은 중간 단계에서 0이 아닌 값들이 새롭게 생겨나는 현상(이를 fill-in이라 함)을 초래할 수 있다. 이러한 fill-in은 행렬이 희소한 성질을 잃게 만들고, 결과적으로 메모리 사용량이 크게 증가할 수 있다.

예를 들어, 행렬 $\mathbf{A}$가 다음과 같은 희소 행렬이라고 가정하자.

이 행렬에 LU 분해를 적용하면, 일반적으로 $\mathbf{L}$과 $\mathbf{U}$ 행렬에서 추가적인 0이 아닌 요소들이 발생할 수 있다. 이는 계산 비용을 증가시키며, 특히 매우 큰 규모의 행렬을 다룰 때 문제가 된다.

Fill-in 현상을 최소화하는 전략

희소 행렬의 LU 분해에서 중요한 과제는 fill-in 현상을 최소화하는 것이다. 이를 위해 주로 사용하는 전략은 순서 재배열(ordering)이다. 행렬의 행과 열을 특정 순서에 따라 재배열하면 fill-in을 최소화할 수 있다. 가장 널리 사용되는 순서 재배열 알고리즘 중 하나는 반대 대각선(Bandwidth reduction) 또는 최소 정도(minimum degree) 알고리즘이다.

예를 들어, Cuthill-McKee 알고리즘은 행렬의 대각선 근처로 비제로(non-zero) 요소들을 모으는 방식으로 fill-in을 줄이다. 이 알고리즘은 희소 행렬의 그래프 표현에서 노드의 차수(degree)를 기준으로 노드를 재배열한다.

Pivoting과 희소 LU 분해

LU 분해에서 pivoting은 수치적 안정성을 확보하기 위해 필수적이지만, pivoting으로 인해 희소 행렬의 구조가 깨질 수 있다. 일반적인 pivoting 전략, 예를 들어 partial pivoting이나 complete pivoting은 행렬의 비제로 구조를 유지하는 데 최적화되어 있지 않는다. 따라서, 희소 LU 분해에서는 fill-in을 줄이기 위해 pivoting을 제한하거나, pivoting을 수행하면서도 희소성을 최대한 유지할 수 있는 방법을 찾아야 한다.

Sparse Pivoting 전략은 희소 행렬에 적합한 pivoting 방법으로, pivoting 시 발생할 수 있는 fill-in을 고려한다. 이는 대개 정교한 대각선 스케일링(diagonal scaling) 기법이나 기하학적 영역 분할(geometric domain decomposition) 기법을 활용하여 이루어진다. 이러한 방법들은 행렬의 특정 부분을 개별적으로 처리하여 전체적인 fill-in을 줄이는 데 기여할 수 있다.

희소 행렬에 대한 특화된 LU 분해 알고리즘

희소 행렬에서의 LU 분해를 효과적으로 수행하기 위해 몇 가지 특화된 알고리즘이 개발되었다. 이러한 알고리즘은 일반적인 LU 분해보다 희소성 유지에 중점을 두며, 연산량을 줄이고 메모리 사용을 최소화한다.

1. UMFPACK: Unsymmetric MultiFrontal sparse LU factorization package는 비대칭 희소 행렬의 LU 분해를 위한 알고리즘이다. 이 알고리즘은 행렬을 여러 개의 작은 부분 행렬로 분해하고, 각 부분 행렬에 대해 LU 분해를 수행한 후 결과를 합쳐 최종 LU 분해를 얻는다. 이 방식은 fill-in을 효과적으로 줄이며, 병렬화에도 유리한다.

2. SuperLU: SuperLU는 대형 희소 행렬의 LU 분해를 효율적으로 수행하는 라이브러리이다. 이 라이브러리는 행렬의 열 기반 접근법을 사용하여 fill-in을 최소화하며, 정교한 pivoting 기법을 적용하여 수치적 안정성과 희소성을 동시에 유지한다.

3. PARDISO: 이 알고리즘은 대형 희소 행렬의 병렬 LU 분해를 지원하며, 특히 대칭성과 비대칭성 모두를 고려한 효율적인 분해를 제공한다. PARDISO는 fill-in을 줄이기 위해 고급 순서 재배열 알고리즘과 함께 사용된다.

희소 LU 분해의 저장과 계산 효율성

희소 LU 분해에서는 결과 행렬 $\mathbf{L}$과 $\mathbf{U}$도 희소한 형태를 유지하도록 효율적인 데이터 구조를 사용하는 것이 중요하다. 일반적으로 사용되는 데이터 구조는 압축 행렬 형식(Compressed Sparse Row, CSR) 또는 압축 열 형식(Compressed Sparse Column, CSC)이다. 이들 형식은 비제로 요소만을 저장하여 메모리 사용량을 줄이고, 연산 속도를 향상시킨다.

CSR 형식

CSR 형식에서는 행렬의 비제로 요소들만을 일차원 배열에 저장하고, 각 행의 시작 위치와 열 인덱스를 별도의 배열에 저장한다. 예를 들어, 행렬 $\mathbf{A}$가 다음과 같다면:

CSR 형식으로 표현하면:

• 값 배열 (values): [10, 2, 3, 9, 7, 8, 7, 3, 8, 7, 5, 8, 9, 9]
• 열 인덱스 배열 (column indices): [0, 4, 0, 1, 1, 2, 3, 0, 2, 3, 4, 1, 3, 4]
• 행 포인터 배열 (row pointers): [0, 2, 4, 7, 11, 14]

이와 같은 저장 방식은 희소 LU 분해의 효율성을 높이는 데 크게 기여한다.