다중 격자 방법

다중 격자 방법은 미세 격자에서의 저렴한 평활화와 더 거친 격자에서 계산된 보정을 결합하여 이산화된 편미분 방정식(PDE)의 해법을 가속화합니다. 이는 모든 길이 스케일에서 오차를 처리하고 메시 크기에 독립적인 수렴 속도를 달성합니다.

Definition

다중 격자 방법은 다양한 해상도의 격자 계층에서 오차를 표현하는 반복 솔버입니다. 이는 미세 격자에서 진동하는 오차 성분을 제거하기 위해 저렴한 이완을 사용하고, 모든 스케일에 걸쳐 재귀적으로 부드러운 성분을 제거하기 위해 거친 격자 해법을 사용합니다.

Scope

이 주제는 단순 반복의 평활화 속성, 제한(restriction) 및 확장(prolongation)을 통한 격자 간 잔차 및 보정 전달, 2-격자 및 V-, W-, 전체 다중 격자 주기, 기하학적 대수 다중 격자, 그리고 다중 격자를 타원형 문제에 대한 벤치마크 솔버로 만드는 최적의 (선형) 계산 복잡성을 다룹니다.

Core questions

• 단순 반복이 진동 오차를 빠르게 줄이지만 부드러운 오차는 느리게 줄이는 이유는 무엇이며, 이는 거친 격자를 사용하는 동기가 됩니까?
• 잔차는 어떻게 거친 격자로 제한되고 보정은 어떻게 미세 격자로 다시 확장됩니까?
• 다중 격자 주기는 이러한 연산을 어떻게 결합하여 메시 독립적인 수렴을 달성합니까?
• 대수 다중 격자는 기본 기하학적 격자가 없는 문제에 이 아이디어를 어떻게 확장합니까?

Key theories

평활화 및 거친 격자 보정

Gauss-Seidel과 같은 고전적인 이완은 고주파(진동) 오차를 빠르게 감쇠시키지만 저주파 오차에는 거의 영향을 미치지 않습니다. 다중 격자는 이 점을 이용하여 부드럽고 느리게 수렴하는 오차를 더 거친 격자로 전송하여 그곳에서 진동하는 것처럼 보이게 하고 저렴하게 줄입니다.

메시 독립적인 최적 복잡성

V- 또는 W-주기에서 평활화 및 거친 격자 보정을 재귀적으로 적용하면 격자 크기에 독립적으로 제한되는 수렴 계수가 생성되므로, 고정된 허용 오차까지 해결하는 작업은 미지수 수에 선형적으로만 증가합니다.

Mechanisms

다중 격자 주기는 미세 격자에서 시스템을 이완하여 오차를 평활화하고, 잔차를 계산하며, 이를 더 거친 격자로 제한하여 잔차 방정식을 해결합니다(동일한 주기에 의해 재귀적으로). 그런 다음 거친 격자 보정은 다시 확장되어 미세 격자 근사치에 추가되고, 추가적인 이완이 뒤따릅니다. 각 격자 수준은 가장 효율적인 오차 성분을 처리하기 때문에, 결합된 주기는 고정된 스윕 수 내에서 모든 스케일의 오차를 줄입니다. 대수 다중 격자는 행렬 항목에서 직접 격자 계층 및 전송 연산자를 구축하므로 기하학적 메시가 필요하지 않습니다.

Clinical relevance

다중 격자는 타원형 및 포물선형 PDE에서 발생하는 대규모 희소 시스템에 대한 가장 효율적인 솔버 중 하나이며, 전산 유체 역학, 구조 역학, 전자기학 및 이미지 처리에서 솔버 또는 전처리기로 사용됩니다. 거의 최적에 가까운 스케일링은 병렬 슈퍼컴퓨터에서의 극대 규모 시뮬레이션에 필수적입니다.

History

다중 격자 아이디어는 1961년경 Fedorenko에 의해 소개되었고, 1970년대 Achi Brandt에 의해 실용적이고 광범위하게 적용 가능한 방법으로 개발되었습니다. Hackbusch의 분석은 이를 엄격한 기반 위에 올려놓았고, 대수 다중 격자는 나중에 비구조적이고 비기하학적인 문제로 그 범위를 확장하여 최적 복잡성 솔버로서의 지위를 확고히 했습니다.

Key figures

• Radii Fedorenko
• Achi Brandt
• Wolfgang Hackbusch
• Stephen McCormick

Seminal works

• trottenberg2001
• briggs2000

Frequently asked questions

거친 격자가 왜 도움이 됩니까?

미세 격자 이완이 느리게 제거하는 부드러운 오차는 더 거친 격자에서는 진동하는 것처럼 보이며, 그곳에서 이완은 이를 빠르고 저렴하게 제거합니다. 따라서 다른 해상도의 격자를 순환함으로써 모든 오차 성분을 효율적으로 제거합니다.

기하학적 다중 격자와 대수 다중 격자의 차이점은 무엇입니까?

기하학적 다중 격자는 문제의 기하학적 구조에서 더 거친 메시의 명시적 계층을 사용하는 반면, 대수 다중 격자는 행렬에서 자동으로 거친 수준과 전송 연산자를 구성하므로 자연스러운 격자 계층이 존재하지 않을 때 적용할 수 있습니다.