시간의존 PDE 해석에서 효율을 극대화하는 행렬분해 전략: Cholesky vs. LU

이번 포스팅에서는 편미분방정식(PDE)을 수치적으로 풀 때 직면하게 되는 행렬분해 전략, 특히 LU 분해와 Cholesky 분해의 특징과 장단점을 다루어 보겠습니다. 특히 PDE 해석 전반의 흐름과 함께, 두 분해법이 어떤 상황에서 더 효율적인지 살펴보겠습니다.

---

1. PDE 수치해석에서 행렬분해가 중요한 이유

편미분방정식(PDE)을 유한요소법(FEM), 유한차분법(FDM) 등으로 이산화(discretization)하면, 일반적으로 아래와 같은 선형시스템 형태로 귀결됩니다.

$$A\mathbf{x}=\mathbf{b}$$

• $A$: 질량행렬(mass matrix), 스티프니스행렬(stiffness matrix) 등으로 불리며, 일반적으로 희소(sparse) 구조를 갖는 대규모 정방행렬
• $\mathbf{x}$: 해석하고자 하는 미지수(변위, 온도, 속도 등)의 해 벡터
• $\mathbf{b}$: 외력(또는 외부자극) 등으로부터 생성되는 오른쪽 항 벡터

시간의존 문제에서의 비효율성

시간에 따라 변화하는(time-dependent) PDE를 풀 때는 각 타임스텝마다 행렬 $A$를 새롭게 구성(또는 업데이트)해야 할 수도 있습니다. 이 과정을 단순히

1. 매 타임스텝마다 $A$를 다시 계산
2. $A^{-1}$을 구해 $\mathbf{x}=A^{-1}\mathbf{b}$로 직접 해석

하는 방식으로 진행하면, 대규모 연산이 반복되어 비효율적일 수밖에 없습니다.

미리 행렬분해를 해두는 전략

만약 일정 구간 동안 $A$가 고정된다고 가정할 수 있다면, 해당 행렬에 대한 분해(factorization)를 미리 해두면 좋습니다.

• $\mathbf{x}=A^{-1}\mathbf{b}$를 직접 계산하기보다는, $A=LU$ 또는 $A=L{L}^T$ 등으로 분해해두고, 전/후진 대치(forward/back substitution)만을 이용해 $\mathbf{x}$를 구하는 방식이 훨씬 효율적입니다.
• 특히 역행렬 자체를 구하는 것보다, 행렬분해를 통해서 각 $\mathbf{b}$에 대해 빠르게 해를 구하는 편이 수치안정성과 계산량 측면에서 유리합니다.

---

2. 행렬분해의 대표주자: Cholesky 분해 vs LU 분해

행렬분해 기법 중에서 LU 분해(LU decomposition)와 Cholesky 분해(Cholesky decomposition)는 가장 널리 사용되는 방식입니다. 두 기법 모두 주어진 정방행렬을 삼각 행렬로 나누어 표현한다는 공통점이 있지만, 적용 가능한 행렬 조건과 계산 구조에서 차이가 있습니다.

2.1 Cholesky 분해

• 적용 가능한 행렬

  • 실수 행렬의 경우, 대칭(symmetric)이고 양의 정부호(Positive Definite; SPD)인 행렬에만 적용 가능
  • 복소수 행렬의 경우, Hermitian(=자기수반)이고 양의 정부호인 행렬

• 분해 형태

  • 일반적으로 $A=L{L}^T$ 형태로 표현됩니다.
    • $L$: 하삼각(lower triangular) 행렬(대각 원소는 양수)
    • $L^T$: $L$의 전치(transpose)로 상삼각 행렬

• 장점 및 특징

  1. 계산 비용이 LU 분해의 절반 수준 (같은 크기일 때 일반 행렬 대비)
  2. SPD 행렬에서만 쓸 수 있기 때문에, FEM 질량행렬이나 스티프니스행렬 등 많은 수치해석 문제에서 자주 활용
  3. 수치 안정성 측면에서 LU 분해에 비해 오차 전파가 상대적으로 작음

• 예시

  • 2차원/3차원 PDE의 FEM 해석에서 생성되는 질량 행렬(대체로 SPD 형태), 스티프니스 행렬 등에 널리 사용

2.2 LU 분해

• 적용 가능한 행렬

  • 모든 비특이성 정방행렬에 대해 일반적으로 사용 (양의 정부호가 아니어도 가능)

• 분해 형태

  • $A=LU$ 또는 피벗팅을 고려해 $PA=LU$ 형태로 분해
    • $L$: 하삼각 행렬, $U$: 상삼각 행렬, $P$: 순열(permutation) 행렬

• 장점 및 특징

  1. 가장 범용적인 분해 — 특별한 구조를 가정하지 않아도 됨
  2. 수치 안정성을 높이기 위해 피벗팅(pivoting)을 활용 (부분 피벗팅, 완전 피벗팅 등)
  3. Cholesky 분해 대비 계산 비용이 더 크고(특수 구조가 없는 일반 행렬 기준), 메모리 접근 측면에서도 SPD 행렬이라면 Cholesky가 유리
  4. Sparse 행렬에서의 최적화, 피벗팅 전략 등에 따라 대규모 시스템 해석 시 효율을 높일 수 있음

• 예시

  • 대칭 여부나 양의 정부호 여부가 보장되지 않는 일반 선형시스템에서 거의 기본적으로 사용
  • “역행렬”을 직접 구하기보다는, LU 분해 후 전/후진 대치를 반복함으로써 $\mathbf{x}=A^{-1}\mathbf{b}$를 빠르게 구함
  • 여러 해석 기법(FEM, FDM, CFD 등)에서 생성되는 다양한 형태의 행렬에 적용 가능

---

3. 어떤 분해를 선택해야 할까?

가장 중요한 기준은 해당 행렬이 SPD(대칭 + 양의정부호) 인지 여부입니다.

• SPD 행렬이라면?

  • Cholesky 분해를 적극적으로 활용해야 합니다.
  • 계산량이 비교적 적고(약 절반 수준), 수치적으로 안정적인 이점을 얻을 수 있음.

• 그렇지 않은 일반 정방행렬이라면?

  • LU 분해(필요시 pivot 포함)를 사용합니다.
  • 범용성이 뛰어나고, 거의 모든 비특이성 정방행렬에 적용 가능.

부가적인 팁

• 대규모 Sparse 시스템에서는, 분해 방식 자체도 중요하지만, 어떻게 피벗팅을 설정하고(또는 피벗팅을 최소화하기 위한 행렬 재배열 등을 활용), 메모리를 효율적으로 사용하는지도 성능에 큰 영향을 미칩니다.
• 행렬 역행렬을 매번 직접 구하는 것보다는, 분해 과정을 통해 전/후진 대치로 $\mathbf{x}$를 구하는 편이 훨씬 안전하고 빠릅니다.

---

4. 결론

수치해석에서 가장 빈번하게 접하게 되는 과제 중 하나는 “어떤 방식으로 대규모 선형시스템을 풀 것인가?” 입니다. 특히 시간에 따라 반복적으로 시스템을 푸는 경우, 매 타임스텝마다 행렬을 새로 만들고 역행렬을 구하는 일은 너무 비효율적입니다.

• 미리 행렬을 분해해두면, 전/후진 대치 방식으로 각 타임스텝을 빠르게 해석 가능
• Cholesky 분해와 LU 분해 중 선택은 행렬의 구조(SPD 여부)가 핵심 기준
• Sparse 최적화, 피벗팅 전략 등을 잘 활용하면 대규모 문제에서도 계산 시간을 크게 단축할 수 있음

이처럼 PDE 해석에서의 성공적인 시간·자원 절감은 대부분 “어떤 수치 기법을 어떤 타이밍에 적용할지”라는 설계와 관련 있습니다. 최적의 행렬분해 전략을 선택하여 해석 효율을 높여보시길 바랍니다.

---

참고

• Trefethen & Bau, Numerical Linear Algebra, SIAM
• Quarteroni & Valli, Numerical Approximation of Partial Differential Equations, Springer