Apa keuntungan dari prekondisi penguraian multigrid atas domain, dan sebaliknya?

Ini sebagian besar ditujukan untuk PDE elips lebih dari domain cembung, sehingga saya bisa mendapatkan gambaran yang baik dari dua metode.

Metode dekomposisi domain multigrid dan multilevel memiliki banyak kesamaan sehingga masing-masing biasanya dapat ditulis sebagai kasus khusus dari yang lain. Kerangka analisis agak berbeda, sebagai konsekuensi dari filosofi yang berbeda dari masing-masing bidang. Secara umum, metode multigrid menggunakan tarif pengkasaran moderat dan smoothers sederhana sementara metode domain dekomposisi menggunakan sangat pengkasaran cepat dan smoothers kuat .

Multigrid (MG)

Multigrid menggunakan tingkat pengerasan yang moderat dan mencapai ketahanan melalui modifikasi interpolasi dan smoothers. Untuk masalah elips, operator interpolasi harus "energi rendah", sehingga mereka mempertahankan ruang hampir nol dari operator (misalnya mode tubuh kaku). Contoh pendekatan geometris untuk interpolant berenergi rendah ini adalah Wan, Chan, Smith (2000) , dibandingkan dengan konstruksi aljabar agregasi halus Vaněk, Mandel, Brezina (1996) (implementasi paralel dalam ML dan PETSc via PCGAMG, pengganti untuk Prometheus ) . Buku Trottenberg, Oosterlee, dan Schüller adalah referensi umum yang baik tentang metode Multigrid.

Kebanyakan perokok multigrid melibatkan relaksasi searah, baik secara aditif (Jacobi) atau multiplikasi (Gauss Seidel). Ini sesuai dengan masalah Dirichlet (node ​​tunggal atau elemen tunggal) kecil. Beberapa adaptifitas spektral, ketahanan, dan kemampuan vektor dapat dicapai menggunakan Chebyshev smoothers, lihat Adams, Brezina, Hu, Tuminaro (2003) . Untuk masalah non-simetris (misalnya transportasi), smoothers multiplikatif seperti Gauss-Seidel pada umumnya diperlukan, dan interpolinan melawan angin dapat digunakan. Sebagai alternatif, smoothers untuk titik sadel dan masalah gelombang kaku dapat dibangun dengan mentransformasikan melalui "block preconditioners" yang diilhami Schur atau dengan "relaksasi terdistribusi" yang terkait, ke dalam sistem di mana smoothers sederhana efektif.

Efisiensi multigrid buku teks mengacu pada penyelesaian kesalahan diskritisasi dalam kelipatan kecil dari biaya beberapa evaluasi residu, sesedikit empat, pada fine grid. Ini menyiratkan bahwa jumlah iterasi ke toleransi aljabar tetap turun ketika jumlah level meningkat. Secara paralel, estimasi waktu melibatkan istilah logaritmik yang timbul karena sinkronisasi yang tersirat oleh hierarki multigrid.

Dekomposisi Domain (DD)

Metode dekomposisi domain pertama hanya memiliki satu tingkat. Tanpa tingkat kasar, jumlah kondisi dari operator yang dikondisikan tidak boleh kurang dari di manaLadalah diameter domain danHadalah ukuran subdomain nominal. Dalam praktiknya, angka-angka kondisi untuk DD satu tingkat berada di antara batas ini danO(L$\mathcal O\big( \frac{L^2}{H^2}\big)$$L$$H$di manahadalah ukuran elemen. Perhatikan bahwa jumlah iterasi yang diperlukan oleh metode Krylov berskala sebagai akar kuadrat dari nomor kondisi. Metode Schwarz Dioptimalkan(Gander 2006)meningkatkan konstanta dan ketergantungan padaH/hrelatif terhadap metode Dirichlet dan Neumann, tetapi umumnya tidak termasuk tingkat kasar dan dengan demikian menurunkan dalam kasus banyak subdomain. Lihat buku olehSmith, Bjørstad, dan Gropp (1996)atauToselli dan Widlund (2005)untuk referensi umum tentang metode dekomposisi domain.$\mathcal O\big( \frac{L^2}{hH} \big)$$h$$H/h$

Untuk tingkat konvergensi yang optimal atau kuasi-optimal, beberapa level diperlukan. Sebagian besar metode DD dianggap sebagai metode dua tingkat dan beberapa sangat sulit diperluas ke tingkat yang lebih tinggi. Metode DD dapat diklasifikasikan sebagai tumpang tindih atau tidak tumpang tindih.

Tumpang tindih

Metode Schwarz ini menggunakan tumpang tindih dan umumnya didasarkan pada pemecahan masalah Dirichlet. Kekuatan metode dapat ditingkatkan dengan meningkatkan tumpang tindih. Kelas metode ini biasanya kuat, tidak memerlukan identifikasi ruang nol lokal atau modifikasi teknis untuk masalah dengan kendala lokal (umum dalam teknik mesin padat), tetapi melibatkan kerja ekstra (terutama dalam 3D) karena tumpang tindih. Selain itu, untuk masalah-masalah terbatas seperti tidak dapat dikompres, konstanta inf-sup dari strip yang tumpang tindih biasanya muncul, yang mengarah ke tingkat konvergensi suboptimal. Metode tumpang tindih modern menggunakan ruang kasar serupa dengan BDDC / FETI-DP (dibahas di bawah) dikembangkan oleh Dorhmann, Klawonn, dan Widlund (2008) dan Dohrmann dan Widlund (2010) .

Non-tumpang tindih

Metode-metode ini biasanya menyelesaikan beberapa jenis masalah Neumann, yang berarti bahwa tidak seperti metode Dirichlet, mereka tidak dapat bekerja dengan matriks yang dirakit secara global, dan sebaliknya memerlukan matriks yang tidak dirakit atau dirakit sebagian. Metode Neumann yang paling populer baik menegakkan kontinuitas antara subdomain dengan menyeimbangkan pada setiap iterasi atau dengan pengganda Lagrange yang akan menegakkan kontinuitas hanya setelah konvergensi tercapai. Metode awal dari jenis ini (Balancing Neumann-Neumann dan FETI) membutuhkan karakterisasi yang tepat dari ruang nol dari setiap subdomain, baik untuk membangun tingkat kasar dan untuk membuat masalah subdomain non-singular. Metode selanjutnya (BDDC dan FETI-DP) memilih sudut subdomain dan / atau momen tepi / muka sebagai derajat kebebasan tingkat kasar. Lihat Klawonn dan Rheinbach (2007)untuk diskusi mendalam tentang pemilihan ruang kasar untuk elastisitas 3D. Mandel, Dohrmann, dan Tazaur (2005) menunjukkan bahwa BDDC dan FETI-DP memiliki semua nilai eigen yang sama, kecuali kemungkinan 0 dan 1.

Lebih dari dua level

Sebagian besar metode DD hanya dianggap sebagai metode dua tingkat, dan beberapa memilih ruang kasar yang tidak nyaman untuk digunakan dengan lebih dari dua tingkat. Sayangnya, terutama dalam 3D, masalah tingkat kasar dengan cepat menjadi hambatan, membatasi ukuran masalah yang bisa diselesaikan. Selain itu, jumlah kondisi dari operator yang dikondisikan, terutama untuk metode DD berdasarkan masalah Neumann, cenderung untuk skala sebagai

dimana adalah jumlah level. Selama pengerasan agresif digunakan, ini mungkin tidak begitu penting karena L ≤ $L$$L \le 4$$10^{12}$

Ini adalah langganan yang bagus tetapi saya pikir mengatakan bahwa (multilevel) DD dan MG memiliki banyak kesamaan tidak akurat, atau setidaknya tidak berguna. Metodenya sangat berbeda dan saya tidak berpikir bahwa keahlian dalam satu sangat berguna dalam yang lain.

Pertama, kedua komunitas menggunakan definisi kompleksitas yang berbeda: DD mengoptimalkan jumlah kondisi sistem yang dikondisikan sebelumnya dan MG mengoptimalkan kompleksitas kerja / memori. Ini adalah perbedaan mendasar yang besar - "optimalitas" memiliki arti yang sangat berbeda dalam dua konteks ini. Hal-hal tidak berubah ketika Anda menambahkan kompleksitas paralel (meskipun Anda mendapatkan istilah log yang ditambahkan dalam MG). Kedua komunitas hampir berbicara bahasa yang berbeda.

Kedua, MG memiliki multilevel bawaan ke dalamnya dan metode DD bertingkat semuanya telah dikembangkan dengan dua teori level dan implementasi. Ini membatasi ruang ruang kotak kasar yang dapat Anda gunakan dalam MG - mereka harus bersifat rekursif. Misalnya, Anda tidak dapat menerapkan FETI dalam kerangka MG. Orang-orang melakukan beberapa metode DD bertingkat seperti yang disebutkan Jed, tetapi setidaknya beberapa metode DD populer saat ini tampaknya tidak dapat diterapkan secara rekursif.

Ketiga, saya melihat algoritma itu sendiri, seperti yang dipraktikkan, sangat berbeda. Secara kualitatif, saya akan mengatakan bahwa metode proyek DD ke batas-batas domain dan menyelesaikan masalah antarmuka ini. MG bekerja langsung dengan persamaan asli. Menghindari proyeksi ini memungkinkan MG diterapkan pada masalah nonlinier dan tidak simetri dengan mudah. Meskipun teorinya semuanya hilang untuk masalah nonlinier dan tidak simetris, mereka telah bekerja untuk banyak orang. MG juga secara eksplisit memisahkan masalah menjadi dua bagian: ruang grid kasar untuk penskalaan dan pemecah iteratif (yang lebih halus) untuk menyelesaikan fisika. Ini sangat penting dalam memahami dan bekerja dengan MG dan merupakan properti yang menarik bagi saya.

Meskipun secara teoritis ruang smoothers dan grid kasar digabungkan secara ketat, dalam praktiknya Anda sering dapat menukar masuk dan keluar yang berbeda sebagai parameter optimasi. Seperti yang disebutkan Jed, titik atau titik smoothers populer dan biasanya lebih cepat, tetapi untuk masalah yang menantang, smoothers yang lebih berat dapat berguna. Plot ini dari disertasi saya yang menunjukkan waktu penyelesaian sebagai fungsi rasio Poisson untuk Jacobi, blok Jacobi dan "additive Schwarz" (tumpang tindih). Agak sulit dibaca tetapi pada rasio Poisson tertinggi (0,499), tumpang tindih Schwarz adalah sekitar 2x lebih cepat dari (vertex) Jocobi sedangkan itu sekitar 3x lebih lambat pada rasio Poisson pejalan kaki.

Menurut jawaban Jed, MG menggunakan kasar sedang sedangkan DD menggunakan kasar cepat. Saya pikir ini membuat perbedaan ketika mereka diparalelkan. Akan ada banyak komunikasi dan sinkronisasi untuk MG untuk melalui banyak tingkat pengerasan yang setara dengan pengerasan DD tunggal. Poin lain dari jawaban Jed adalah MG menggunakan lebih murah dan DD menggunakan lebih kuat. Mempertimbangkan kedua poin tersebut, telah dilaporkan bahwa MG pada level kasar akan memiliki rasio komunikasi / komputasi yang buruk. Jadi menurut hukum Amdahl , percepatan paralelnya tidak baik. Solusi untuk ini adalah koreksi grid paralel paralel seperti BPX preconditioner. Selain itu, MG dapat menggunakan DD lebih lancar seperti yang ditunjukkan Adams, dan MG juga dapat digunakan dalam subdomain DD. Berdasarkan pertimbangan yang ditunjukkan Barker, saya kira menggunakan MG dalam DD lebih baik, yang mengeksploitasi baik parallelsim dari DD dan kompleksitas optimal dari MG.

Saya ingin membuat satu tambahan kecil untuk jawaban Jed yang luar biasa, yaitu bahwa motivasi di balik kedua pendekatan itu (atau paling tidak) berbeda.

Dekomposisi domain dimotivasi sebagai teknik untuk komputasi paralel. Khusus untuk metode satu tingkat, DD sangat alami untuk diterapkan pada mesin paralel - Anda membagi domain menjadi beberapa bagian dan memberikan masing-masing bagian ke prosesor yang berbeda. Dalam arti motivasi di balik DD adalah untuk membagi operasi aritmatika antara prosesor.

Implementasi multigrid paralel yang baik ada, tetapi seringkali kurang alami untuk melakukannya secara paralel. Sebaliknya, motivasi di balik multigrid adalah untuk melakukan operasi aritmatika kurang di tempat pertama.

$H$$h$$\mathcal{O}(\frac{1}{Hh})$

Poin lain adalah tentang jumlah kondisi metode Schwarz yang dioptimalkan. Sebenarnya, itu meningkatkan eksponen$h$untuk metode satu tingkat ( non-tumpang tindih dan tumpang tindih ) dan juga eksponen$H$untuk metode dua tingkat .