진화 알고리즘을 이용한 문법 기반 대수 멀티그리드 설계 자동화

Automated Grammar-based Algebraic Multigrid Design With Evolutionary Algorithms

멀티그리드는 많은 중요한 편미분 방정식을 해결하는 데 있어 점근적으로 최적이지만, 그 효율성은 개별 알고리즘 구성 요소의 신중한 선택에 크게 의존합니다. 최근에는 딥러닝 기술을 사용하여 특정 멀티그리드 구성 요소를 최적화하는 접근 방식이 있지만, 본 연구에서는 상호 보완적인 전략을 채택하여, 검증된 알고리즘 구성 요소를 활용하여 효율적인 멀티그리드 사이클을 구성하는 데 진화 알고리즘을 사용합니다. 본 논문에서는 '유연한 사이클링'이라고 불리는, 즉, 레벨별 스무딩 시퀀스와 비재귀적 사이클링 패턴을 갖는 효율적인 대수 멀티그리드 방법을 생성하는 데의 적용 사례를 제시합니다. 이러한 비표준 사이클을 가진 탐색 공간은 수동으로 탐색하기 어렵기 때문에, 컨텍스트 자유 문법에 의해 안내되는 유전 프로그래밍(GP)을 사용하여 생성됩니다. 선형 대수 라이브러리인 *hypre*를 사용한 수치 실험 결과는 이러한 비표준 GP 사이클이 멀티그리드 성능을 솔버 및 프리컨디셔너로서 모두 향상시킬 수 있는 잠재력을 보여줍니다.

Although multigrid is asymptotically optimal for solving many important partial differential equations, its efficiency relies heavily on the careful selection of the individual algorithmic components. In contrast to recent approaches that can optimize certain multigrid components using deep learning techniques, we adopt a complementary strategy, employing evolutionary algorithms to construct efficient multigrid cycles from proven algorithmic building blocks. Here, we will present its application to generate efficient algebraic multigrid methods with so-called \emph{flexible cycling}, that is, level-specific smoothing sequences and non-recursive cycling patterns. The search space with such non-standard cycles is intractable to navigate manually, and is generated using genetic programming (GP) guided by context-free grammars. Numerical experiments with the linear algebra library, \emph{hypre}, demonstrate the potential of these non-standard GP cycles to improve multigrid performance both as a solver and a preconditioner.