Fast solvers for the high-order FEM simplicial de Rham complex: Extended edition

논문 요약: 고차 유한 요소법 (High-Order FEM) 을 위한 심플렉스 (Simplicial) 데 라함 (de Rham) 복합체의 빠른 솔버

1. 연구 배경 및 문제 제기

• 고차 유한 요소법의 한계: 고차 (High-order, $p$-version) 유한 요소법은 빠른 수렴 속도와 높은 산술 강도 (arithmetic intensity) 를 가지지만, 구현 시 메모리 사용량과 부동 소수점 연산 횟수 (flops) 가 다항식 차수 $p$가 증가함에 따라 급격히 증가하는 문제가 있습니다.
• 기존 방법의 비효율성:
  • 텐서 곱 격자 (quadrilaterals/hexahedra) 에서는 텐서 곱 기저를 이용해 문제를 1 차원 문제로 분해하여 $O(p^{d+1})$ 연산으로 해결할 수 있습니다.
  • 그러나 심플렉스 (삼각형/사면체) 격자에서는 이러한 구조가 부재하여, 밀집 행렬을 다루는 경우 연산 비용이 $O(p^{3d})$ (3 차원의 경우 $O(p^9)$) 로 증가하고, 메모리 또한 $O(p^{2d})$를 요구합니다.
• 목표: 심플렉스 격자에서 데 라함 복합체 (de Rham complex, $H(\text{grad})$, $H(\text{curl})$, $H(\text{div})$) 에 해당하는 리즈 맵 (Riesz maps) 및 호드 라플라시안 (Hodge Laplacians) 문제를 고차에서 효율적으로 해결할 수 있는 새로운 기저 함수와 솔버를 개발하는 것입니다.

2. 주요 방법론 (Methodology)

가. 새로운 유한 요소 기저 함수 설계

• 데모코비치 (Demkowicz) 등의 아이디어 확장: 기존 데모코비치 등의 보간 자유도 (degrees of freedom) 개념을 차용하되, **정규 직교성 (Orthogonality)**을 극대화하는 새로운 기저를 구성합니다.
• 내부 - 인터페이스 분리 (Interior-Interface Decoupling):
  • 기준 셀 (Reference cell) 에서 내부 자유도 (interior DOFs) 와 인터페이스 자유도 (interface DOFs) 간의 결합이 약하도록 설계합니다.
  • 이를 위해 bubble space(셀 내부에서만 지지되는 함수 공간) 에 대해 두 가지 내적 ($L^2$ 및 $H(dk)$) 에서 정규 직교하는 고유벡터 (eigenbasis) 를 사전에 계산하여 기저로 사용합니다.
  • 결과적으로, 질량 행렬 (Mass matrix) 과 강성 행렬 (Stiffness matrix) 의 내부 - 내부 블록이 대각 행렬이 되며, 내부 - 인터페이스 결합 블록은 매우 약해집니다.

나. 전처리기 (Preconditioner) 전략

• 공간 분해 (Space Decomposition):
  • 내부 - 인터페이스 분해: 내부 자유도는 점 - 야코비 (point-Jacobi, 대각 스케일링) 솔버로 처리하고, 인터페이스 자유도는 영역 분해 (Domain Decomposition) 기법을 적용합니다.
  • PAFW 및 Hiptmair-Toselli 분해: Pavarino-Arnold-Falk-Winther (PAFW) 및 Hiptmair-Toselli (HT) 분해법을 변형하여 적용합니다. 특히, Type-I (Whitney forms 및 고차 인터페이스 버블) 과 Type-II (외부 미분으로 생성된 함수) 공간을 분리하여 더 작은 서브도메인 문제를 풉니다.
• 계산 복잡도 최적화:
  • 내부 자유도의 결합을 무시하거나 대각화하여 처리함으로써, 3 차원에서 $O(p^6)$의 연산 비용과 $O(p^4)$의 메모리 사용량을 달성합니다. (기존의 $O(p^9)$ 대비 획기적 개선).

다. 구현 및 적용

• Firedrake 구현: 제안된 기저와 전처리기 로직을 오픈소스 FEM 프레임워크인 Firedrake 에 구현했습니다.
• 적용 대상:
  • Riesz maps (1.1)-(1.3): $H(\text{grad})$, $H(\text{curl})$, $H(\text{div})$ 공간에서의 선형 시스템.
  • Hodge Laplacians: 데 라함 복합체의 혼합 형식 (mixed formulation) 문제.

3. 주요 기여 (Key Contributions)

1. 새로운 고차 유한 요소 기저 개발: 심플렉스 격자에서 내부 자유도와 인터페이스 자유도가 약하게 결합되도록 설계된 새로운 기저 함수를 제안했습니다. 이는 기준 셀에서 수치적으로 계산된 고유벡터를 기반으로 합니다.
2. p-robust한 솔버 복잡도 달성: 3 차원 심플렉스 격자에서 Riesz 맵을 해결하는 데 필요한 연산 비용을 $O(p^9)$에서 $O(p^6)$으로, 메모리 사용량을 $O(p^6)$에서 $O(p^4)$으로 줄였습니다. 이는 텐서 곱 격자에서의 최적 복잡도 ($O(p^4)$ 연산) 에 근접하는 수준입니다.
3. 효율적인 공간 분해 전처리기: 내부 - 인터페이스 결합을 무시하는 전처리기 전략과 PAFW/HT 공간 분해법을 결합하여, 고차 문제에서도 반복 횟수가 $p$와 무관하게 유지되거나 매우 완만하게 증가하는 것을 증명했습니다.
4. Hodge Laplacian에 대한 증강 라그랑지안 전처리기: 개발된 Riesz 맵 솔버를 블록 대각 전처리기 (Block diagonal preconditioner) 로 사용하여, 증강 라그랑지안 기법과 결합된 Hodge Laplacian 문제를 효율적으로 해결했습니다.

4. 실험 결과 (Numerical Results)

• 반복 횟수 (Iteration Counts):
  • $H(\text{grad})$, $H(\text{curl})$, $H(\text{div})$ 문제에 대해 다양한 $p$ (3~10) 와 계수 $\alpha, \beta$에서 테스트했습니다.
  • 내부 - 인터페이스 분해 기법을 적용한 솔버는 전체 시스템을 푸는 솔버와 거의 동일한 반복 횟수를 보였으며, 이는 $p$가 커져도 robust하게 유지되었습니다.
  • 특히 $\alpha \ge 1$인 경우, 모든 분해 기법에서 반복 횟수가 매우 낮고 안정적이었습니다.
• 계산 비용:
  • Figure 1 에 따르면, 제안된 방법 (facet splitting) 은 전체 행렬을 푸는 방법 (full) 에 비해 연산 횟수 (Flops) 와 메모리 사용량이 $p$가 증가함에 따라 훨씬 효율적으로 감소함을 확인했습니다.
  • $p=10$ 수준에서도 $O(p^6)$ 스케일의 연산이 가능하여 고차 해석이 실용적이 되었습니다.
• Hodge Laplacian 적용:
  • Fichera corner와 같은 특이점이 있는 영역에서도 전처리기 기반의 MINRES 솔버가 $p$에 대해 robust하게 동작함을 보였습니다.

5. 의의 및 결론 (Significance)

이 논문은 심플렉스 격자 (삼각형/사면체) 에서의 고차 유한 요소법의 가장 큰 병목 현상이었던 선형 시스템 해결의 계산 비용 문제를 해결했습니다.

• 이론적 의의: 데 라함 복합체 전체에 걸쳐 내부 - 인터페이스 분리가 가능한 새로운 기저를 구성하고, 이를 통해 $O(p^6)$ 연산 복잡도를 달성함을 수학적으로 증명했습니다.
• 실용적 의의: 복잡한 형상의 3 차원 문제를 고차 정확도로 풀 때, 텐서 곱 격자가 불가능한 경우에도 기존 $O(p^9)$ 방식의 비효율성을 극복하고 실용적인 계산 시간을 확보할 수 있게 되었습니다.
• 향후 전망: 이 방법은 복잡한 물리 현상 (유체, 전자기, 탄성 등) 을 고차 FEM 으로 모델링할 때 필수적인 전처리기 기술로 자리 잡을 것으로 기대됩니다.

핵심 키워드: 고차 유한 요소법 (High-order FEM), 심플렉스 격자 (Simplicial mesh), 데 라함 복합체 (de Rham complex), 내부 - 인터페이스 분해 (Interior-Interface decoupling), 전처리기 (Preconditioning), $O(p^6)$ 복잡도.