Hierarchical proximal Galerkin: a fast $hp$-FEM solver for variational problems with pointwise inequality constraints

기술 요약: 계층적 근사 갈레르킨 (Hierarchical Proximal Galerkin, hpG)

문제 정의
본 논문은 점별 부등식 제약 조건(특히 장애물 문제 $u \leq \phi$ 및 일반화된 탄성-소성 비틀림 문제 $|\nabla u| \leq \phi$)을 포함하는 변분 문제의 수치 해법을 다룬다. 이러한 문제들은 최적 제어, 위상 최적화, 탄성 이론 등 다양한 분야에서 발생한다. 이 문제를 해결하는 데 있어 주요한 어려움은, 도메인과 데이터가 매끄러운 경우에도 해의 정칙성(regularity)이 제한적($u \in H^s, s < 5/2$)이라는 점이다. 이러한 정칙성의 한계로 인해 전통적으로 저차 유한 요소법(FEM)이 선호되어 왔는데, 이는 고차 방법이 계산 비용 증가, 희소성 상실, 격자 의존적 수렴율 등의 문제를 겪는다고 인식되었기 때문이다. 또한, 기존의 고차 접근 방식은 직접 솔버(direct solvers)에 의존하거나 격자 의존적인 반복 횟수를 보여 확장성에 한계를 보였다.

방법론
저자는 Keith와 Surowiec가 도입한 잠재 변수 근사 점(Latent Variable Proximal Point, LVPP) 방식을 활용하는 고차 솔버인 계층적 근사 갈레르킨(hpG) 알고리즘을 제안한다. 핵심 방법론은 다음과 같다:

1. 이산화 전략: LVPP 사델-포인트 시스템을 계층적 $p$-FEM 기저를 사용하여 이산화한다.

   • 프라이멀 변수 $u$는 계층적 형상 함수(가중 야코비 다항식 및 hat function)를 사용하는 연속 $H^1$-합치 공간으로 이산화된다.
   • 잠재 변수 $\psi$는 스케일링 및 이동된 르장드르 다항식을 사용하는 불연속 $L^2$-합치 공간으로 이산화된다.
   • 이 특정 쌍(연속 $p$를 갖는 $u$, 불연속 $p-2$ 또는 $p-1$을 갖는 $\psi$)은 희소성을 유지하면서 inf-sup 안정성을 만족시키도록 선택되었다.

2. 뉴턴 선형화 (Newton Linearization): 생성된 비선형 시스템은 뉴턴 방법을 통해 선형화되며, 이는 대칭 사델-포인트 선형 시스템을 생성한다. 결정적으로, $\psi$에 대한 불연속 기저의 선택은 비선형 항의 선형화 결과가 블록 대각 행렬 구조를 갖도록 보장하여, 다항식 차수 $p$가 증가함에 따라 강성 행렬(stiffness matrix)과 질량 행렬(mass matrix)이 조밀(dense)해지는 것을 방지한다.

3. 프리컨디셔닝 및 솔버:

   • 선형 시스템은 블록 프리컨디셔닝된 크릴로프 부공간 방법(외부 루프를 위한 FGMRES, 내부 슈어 보충(Schur complement) 풀이를 위한 GMRES)을 사용하여 해결된다.
   • 슈어 보충에 대해 블록 대각 프리컨디셔너가 구성된다. 장애물 문제의 경우, 희소성을 유지하기 위해 스펙트럼 갈레르킨 기저를 사용하여 슈어 보충을 근사한다. 그래디언트 유형 제약의 경우 더 단순한 근사가 사용된다.
   • 솔버는 행렬의 조립 및 적용, 특히 불연속 기저에 대해 고속 변환(이산 코사인 변환을 통한)을 활용하여 준최적(quasi-optimal) 복잡도를 달성한다.
   • 이 접근 방식은 격자 세분화 및 다항식 차수 증가를 유도하기 위한 사후 오차 추정기(a posteriori error estimator)를 활용하여 **$hp$-적응성($hp$-adaptivity)**을 지원한다.

주요 기여
본 논문의 구체적인 기여는 다음과 같다:

• 고차 제약 조건에 대한 첫 번째 프리컨디셔너: 저자는 근사 갈레르킨 방법에서 발생하는 장애물 및 그래디언트 유형 제약에 대한 뉴턴 시스템을 위한 첫 번째 프리컨디셔너를 개발하였다. 이 프리컨디셔너들은 매우 효과적인 것으로 나타났다.
• 희소성 보존: 특정 계층적 기저 쌍을 활용함으로써, 저자는 $p \to \infty$임에도 불구하고 뉴턴 시스템의 희소성을 유지하며, 이는 고차 방법의 주요 장벽을 극복한 것이다.
• $hp$-강건성 (Robustness): 알고리즘은 수렴에 필요한 비선형(뉴턴) 반복 횟수에 대해 격자($h$) 및 차수($p$) 독립성을 보인다. 내부 크릴로프 반복 횟수는 $h \to 0$ 및 $p \to \infty$에 대해 완만한 다항 로그(polylogarithmic) 성장을 보인다.
• 경쟁력 있는 성능: 본 논문은 고차 이산화가 특정 문제(특히 텐서 곱 구조를 가진 경우)에 대해 저차 방법보다 현저히 빠를 수 있음을 보여주는 최초의 경쟁력 있는 실제 실행 시간(wall-clock time) 비교 결과를 제공한다.
• 고차 구현 능력: 본 솔버는 이전에는 반복 솔버를 사용하여 도달하기 어려웠던 매우 높은 다항식 차수(각 요소당 최대 $p=82$, 2D에서 총 차수 최대 164)의 이산화를 성공적으로 처리한다.

결과
저자는 다섯 가지 수치 예제를 통해 hpG 알고리즘을 검증한다:

1. 1D 진동 장애물 문제: $hp$-적응 전략이$O((h/p)^{10})$의 수렴율을 달성함을 입증한다. 이는 균일 세분화보다 크게 우수한 성능이다. 솔버는 세분화와 관계없이 유계된 뉴턴 반복 횟수를 요구한다.
2. 2D 장애물 문제: 고차 이산화가 저차($p=1$) 방법보다 자유도(dof) 및 단위 실행 시간당 더 작은 오차를 달성함을 보여준다. hpG 솔버는 동일한 오차 허용 오차에 도달하기 위해 저차 프라이멀-듀얼 액티브 셋(PDAS) 전략보다 선형 풀이당 최대 24배 더 빨랐다.
3. 2D 그래디언트 유형 제약: $hp$-강건성(뉴턴 반복 74–78회)과 제약의 불연속점과 격자가 일치할 때의 초수렴(superconvergence, $O(h^p)$)을 확인한다. 특정 오차에 도달하는 데 있어 고차 방법($p > 1$)이 저차 방법보다 약 100배 빠름을 발견하였다.
4. 열형성 준변분 부등식 (QVI): 고정점 반복을 사용하는 복잡한 장애물 유형 QVI에 솔버를 적용한다. 이 방법은 현재까지 문헌에 보고된 타원형 장애물 유형 QVI 중 가장 높은 차수의 이산화($p=82$)를 성공적으로 처리한다.
5. 3D 장애물 문제: 이 방법을 3차원으로 확장하여, 촐레스키 분해(Cholesky factorization)가 대규모 시스템에 대해 실행 불가능해질 수 있음에도 불구하고, 제안된 AMG 프리컨디셔닝을 갖춘 반복 솔버가 여전히 효과적임을 보여준다.

의의 및 주장
본 논문은 hpG 알고리즘이 점별 제약 문제에서 저차 이산화가 유일한 실행 가능한 옵션이라는 지배적인 관념에 근본적으로 도전한다고 주장한다. 저자는 다음과 같이 단언한다:

• 고차 이산화는 특히 $H^1$-노름에서 자유도당 수 자릿수(orders of magnitude) 더 작은 오차를 유도할 수 있다.
• 예상과 달리, 제안된 희소성 보존 이산화 및 프리컨디셔닝 전략과 결가될 경우 고차 방법이 이러한 문제들에 대해 저차 방법보다 계산 비용(실행 시간 기준)이 더 저렴할 수 있다.
• 이 방법은 점별 제약이 존재하는 변분 부등식을 해결하기 위한 견고하고 격자 독립적인 프레임워크를 제공하며, 위상 최적화나 탄성 이론과 같이 이러한 제약이 빈번하게 발생하는 응용 분야에서 고차 정확도를 사용할 수 있게 한다.

저자는 현재 구현이 텐서 곱(직교) 격자에 의존하고 있음을 언급하며, 비직교 셀이나 $p$-멀티그리드 전략으로의 확장이 향후 연구 과제로 남아 있다는 점을 밝히며 신중한 태도를 유지한다.