Dalam kasus aplikasi apa skema preconditioning aditif lebih unggul daripada yang multiplikasi?

12

Dalam kedua metode dekomposisi domain (DD) dan multigrid (MG), seseorang dapat menyusun aplikasi pembaruan blok atau koreksi kasar baik sebagai aditif atau multiplikatif . Untuk pemecah poin point, ini adalah perbedaan antara iterasi Jacobi dan Gauss-Seidel. Multiplicative smoother untuk bertindak sebagai diterapkan sebagai $Ax = b$ $S(x^{old}, b) = x^{new}$

$x_{i+1} = S_n(S_{n-1}( ..., S_1(x_i, b) ..., b), b)$

dan aditif lebih halus diterapkan sebagai

$x_{i+1} = x_{i} + \displaystyle\sum_{\ell = 0}^{n}\lambda_\ell(S_\ell(x_i, b) - x_i)$

untuk beberapa redaman . Konsensus umum tampaknya adalah bahwa pembuat multiplikasi memiliki sifat konvergensi yang jauh lebih cepat, tetapi saya bertanya-tanya: di bawah situasi apa kinerja varian aditif dari algoritma ini lebih baik? $\lambda_i$

Lebih khusus lagi, Apakah ada yang punya kasus penggunaan di mana varian aditif harus dan / atau berkinerja secara signifikan lebih baik daripada varian multiplikatif? Apakah ada alasan teoretis untuk ini? Sebagian besar literatur tentang multigrid cukup pesimis tentang metode Aditif, tetapi banyak digunakan dalam konteks DD sebagai aditif Schwarz. Ini juga meluas ke masalah yang jauh lebih umum dari penulisan pemecah linear dan nonlinier, dan jenis konstruksi mana yang akan bekerja dengan baik dan berkinerja baik secara paralel.

linear-algebra performance multigrid domain-decomposition Peter Brune
sumber

6

Metode aditif mengekspos konkurensi lebih banyak. Mereka umumnya hanya lebih cepat daripada metode multiplikasi jika Anda dapat menggunakan konkurensi itu. Misalnya, tingkat multigrid kasar biasanya terbatas latensi. Jika Anda memindahkan level kasar ke subkomunikator yang lebih kecil, maka mereka bisa diselesaikan secara independen dari level yang lebih halus. Dengan skema multiplikasi, semua procs harus menunggu sementara level kasar diselesaikan.

Juga, jika algoritma membutuhkan reduksi pada setiap level, varian aditif mungkin dapat menyatukannya ketika metode multiplikasi dipaksa untuk melakukannya secara berurutan.

Jed Brown
sumber

Ini adalah jawaban yang saya pikir akan saya dapatkan, jadi saya kira saya akan melangkah lebih jauh dengan pertanyaan itu. Apakah ada situasi di mana metode yang diterapkan secara aditif termasuk DD dan MG, tetapi juga peletakan bidang (yang dapat dianggap seperti DD tetapi mungkin memiliki karakteristik yang berbeda dalam praktiknya) atau pemisahan PDE sebenarnya lebih baik dalam hal kinerja, ketahanan atau stabilitas daripada varian multiplikatif?

Peter Brune

1

Versi multiplikatif dari banyak algoritme perlu menyimpan lebih banyak informasi, tetapi terkadang konvergen kira-kira sama cepatnya. Kadang-kadang varian aditif simetris, tetapi mungkin jauh lebih sulit untuk membuat simetris multiplikatif. Dengan fieldsplit, preconditioner dapat menjadi lebih mendekati saat Anda menambahkan solve tambahan tersebut. Kami dapat menunjukkan ini dengan contoh PETSc Stokes jika Anda mau. Aditif selalu lebih mudah untuk di-vektorisasi / lebih konkuren, tetapi kinerja apa pun yang menang adalah masalah khusus dan arsitektur.

Jed Brown

5

Untuk masalah SPD, metode aditif lebih baik untuk pemulusan MG karena beberapa alasan seperti yang telah disebutkan dan beberapa lainnya:

@Article{Adams-02, 
author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, 
title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, 
journal = {J. Comp. Phys.}, 
year = {2003}, 
volume = {188}, 
number = {2}, 
pages = {593-610} }

Namun, metode multiplikatif memiliki sifat spektral yang benar secara langsung untuk MG yang lebih halus, yaitu, mereka tidak perlu redaman. Ini bisa menjadi kemenangan besar untuk masalah hiperbolik di mana smoothing polinomial tidak terlalu baik.

Adams
sumber

0

Saya akan menyatakan kembali apa yang dikatakan @Jed: Metode Multiplicative selalu menyatu setidaknya serta metode Additive (asymptotically), jadi Anda hanya menang berdasarkan konkurensi, tetapi itu bergantung pada arsitektur.

Matt Knepley
sumber

Secara teknis tidak benar, spektrum dari matriks iterasi untuk mengatakan Gauss-Seidel tidak secara seragam lebih unggul dari Jacobi (misalnya, satu nilai eigen terbunuh dengan satu iterasi Jacobi). Mark (bagaimana saya logout sebagai Jed ...)

Jed Brown

Dalam kasus aplikasi apa skema preconditioning aditif lebih unggul daripada yang multiplikasi?

Jawaban: