Pedoman apa yang harus saya gunakan ketika mencari metode prekondisi yang baik untuk masalah tertentu?

Untuk solusi sistem linear besar menggunakan metode iteratif, sering kali menarik untuk memperkenalkan prakondisi, misalnya menyelesaikan , di mana sini digunakan untuk prakondisi kiri sistem. . Biasanya, kita harus memiliki dan memberikan dasar untuk (lebih banyak) solusi efisien atau pengurangan sumber daya komputasi (misalnya penyimpanan memori) dibandingkan dengan solusi dari sistem asli ( yaitu ketika ). Namun, pedoman apa yang harus kita gunakan untuk memilih prekondisi? Bagaimana para praktisi melakukan ini untuk masalah khusus mereka? $Ax=b$ $M^{-1}(Ax=b)$ $M$ $M^{-1}\approx A^{-1}$ $M=A$

linear-algebra iterative-method preconditioning Allan P. Engsig-Karup
sumber

Bahkan untuk satu kelas persamaan tertentu, ini membutuhkan jawaban yang sangat panjang dan terperinci ...

Jack Poulson

Seharusnya mungkin untuk menyarankan strategi heuristik untuk bagaimana prekondisi dapat dipilih. Misalnya, ketika diberi masalah, apa yang dilakukan praktisi dalam praktiknya untuk mencoba dan menemukan prasyarat yang baik? Mulailah dengan preconditioner diagonal dasar berdasarkan ekstraksi diagonal dari

A

$A$ ? atau?

Allan P. Engsig-Karup

Saya akan menyalurkan @MattKnepley dan mengatakan bahwa tindakan yang tepat adalah melakukan pencarian literatur. Jika gagal, coba semua opsi yang tersedia dengan mudah pada masalah yang cukup besar. Jika itu gagal, pikirkan secara mendalam tentang fisika dan bagaimana Anda dapat menemukan solusi perkiraan untuk masalah dengan murah, dan gunakan itu sebagai prasyarat.

Jack Poulson

@JackPoulson: Karena pertanyaan ini ada dalam nada yang sama dengan Yang solver sistem linear yang digunakan? dan Bagaimana memilih pemecah linier yang dapat diskalakan , tampaknya sesuai dengan topik saya (meskipun luas). Karena komentar Anda pada dasarnya adalah sebuah jawaban, bisakah Anda mengubahnya menjadi jawaban?

Geoff Oxberry

Saya telah memulai hadiah untuk pertanyaan ini, tetapi saya juga tertarik untuk melihat lebih banyak pertanyaan dalam nada ini yang mungkin lebih baik diajukan atau dibatasi untuk kelas masalah tertentu.

Aron Ahmadia

Jawaban:

Saya awalnya tidak ingin memberikan jawaban karena ini memerlukan perawatan yang sangat lama, dan semoga orang lain masih memberikannya. Namun, saya pasti bisa memberikan gambaran singkat tentang pendekatan yang direkomendasikan:

Lakukan pencarian literatur yang menyeluruh .
Jika itu gagal, coba setiap prasyarat yang masuk akal bahwa Anda bisa mendapatkan tangan Anda. MATLAB, PETSc, dan Trilinos adalah lingkungan yang bagus untuk ini.
Jika gagal, Anda harus memikirkan dengan hati-hati tentang fisika masalah Anda dan melihat apakah mungkin untuk menghasilkan solusi perkiraan yang murah, bahkan mungkin untuk versi yang sedikit berubah dari masalah Anda.

Contoh dari 3 adalah Helmholtz versi Laplacian yang bergeser, dan karya Jinchao Xu baru - baru ini tentang memprakondisi operator biharmonik dengan Laplacians.

Jack Poulson
sumber

Terima kasih! Sisa komentar ini memenuhi batas karakter minimum.

Geoff Oxberry

Yang lain telah mengomentari masalah prasyarat apa yang akan saya sebut matriks "monolitik", yaitu misalnya bentuk diskal dari persamaan skalar seperti persamaan Laplace, persamaan Helmholtz atau, jika Anda ingin menggeneralisasikannya, vektor-dihargai persamaan elastisitas. Untuk hal-hal ini, jelas bahwa multigrid (baik aljabar atau geometris) adalah pemenang jika persamaannya berbentuk bulat panjang, dan untuk persamaan lainnya tidak begitu jelas - tetapi sesuatu seperti SSOR sering bekerja dengan cukup baik (untuk beberapa arti dari "masuk akal").

Bagi saya, wahyu besar adalah apa yang harus dilakukan tentang masalah yang tidak monolitik, misalnya untuk operator Stokes Ketika saya mulai dengan analisis numerik sekitar 15 tahun yang lalu, saya pikir orang memiliki harapan bahwa teknik yang sama dapat diterapkan pada matriks seperti di atas, dan arah penelitian adalah untuk mencoba multigrid secara langsung atau menggunakan generalisasi SSOR (menggunakan " titik smoothers "seperti Vanka) dan metode serupa. Tapi ini sudah pudar karena tidak bekerja dengan baik.

(\begin{matrix} A & B \\ B^{T} & 0 \end{matrix}) .

$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$

Apa yang datang untuk menggantikan ini adalah apa yang awalnya disebut "prekondisi berbasis fisika" dan kemudian secara sederhana (dan mungkin lebih akurat) "blok prekondisi" seperti yang oleh Silvester dan Wathen. Ini sering didasarkan pada penghilangan blok atau komplemen Schur dan idenya adalah untuk membangun sebuah prekondisi sedemikian rupa sehingga orang dapat menggunakan kembali prekondisier untuk masing-masing blok yang diketahui bekerja dengan baik. Dalam kasus persamaan Stokes, misalnya, prekondisi Silvester / Wathen menggunakan matriks

{(\begin{matrix} A & B \\ 0 & B^{T} A^{- 1} B \end{matrix})}^{- 1}

$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$ ketika digunakan sebagai prekondisi dengan GMRES akan menghasilkan konvergensi tepat pada dua iterasi. Karena segitiga, inversinya juga jauh lebih sederhana, tetapi kami masih memiliki masalah apa yang harus dilakukan dengan blok diagonal, dan ada yang menggunakan perkiraan: mana tilde berarti mengganti invers yang tepat dengan pendekatan. Ini seringkali jauh lebih sederhana: karena blok adalah operator elips, baik diperkirakan oleh siklus-V multigrid, misalnya, dan ternyata di sini, diperkirakan dengan baik oleh ILU dari matriks massa.

(\begin{matrix} \tilde{A^{- 1}} & B \\ 0 & \tilde{(B^{T} A^{- 1} B)^{- 1}} \end{matrix})

$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$

A

$A$

\tilde{A^{- 1}}

$\widetilde{A^{-1}}$

\tilde{(B^{T} A^{- 1} B)^{- 1}}

$\widetilde{(B^T A^{-1} B)^{-1}}$

Gagasan bekerja dengan blok-blok individual yang terdiri dari matriks dan menggunakan kembali prekondisi pada masing-masing blok telah terbukti sangat kuat dan benar-benar mengubah cara kita berpikir tentang sistem persamaan awal saat ini. Tentu saja, ini relevan karena sebagian besar masalah aktual sebenarnya adalah sistem persamaan.

Wolfgang Bangerth
sumber

Man, ya, aku sangat menginginkan karunia itu! ;-)

Wolfgang Bangerth

Di paragraf kedua Anda: "Tapi ini sudah pudar karena tidak berfungsi dengan baik." Bisakah Anda memberi intuisi tentang mengapa itu tidak bekerja dengan baik? Apakah ada keadaan di mana ia dapat bekerja?

Andrew T. Barker

Alasan mengapa multigrid langsung diterapkan ke seluruh sistem belum terbukti begitu sukses adalah bahwa kebutuhan yang lebih halus untuk melestarikan sifat struktural dari persamaan, dan itu tidak perlu untuk dicapai. Misalnya, jika Anda ingin menerapkan multigrid ke persamaan Stokes, Anda harus memiliki yang lebih halus yang diberi vektor bebas divergensi memberi Anda vektor gratis divergensi. Ada yang lebih halus untuk Stokes, tapi itu tidak biasa untuk dibangun dan biasanya menghilangkan kualitas sebagai yang lebih halus / pemecah. Menjadi jauh lebih sulit untuk melestarikan properti dalam kasus yang lebih egal.

Wolfgang Bangerth

Adapun generalisasi hal-hal seperti Jacobi / SSOR / etc ke sistem: sebagian besar metode ini mengharuskan entri diagonal dari matriks tidak nol. Jelas itu bukan kasus Stokes. Jadi metode paling sederhana berikutnya adalah untuk tidak melihat baris matriks individu tetapi blok baris, misalnya, semua baris untuk DoF yang terkait dengan satu titik. Ini disebut "point-smoothers" (titik seperti dalam vertex) dan mereka bekerja sampai derajat tertentu, tetapi mereka mengalami penurunan kinerja yang sama dengan Jacobi / SSOR begitu masalah menjadi besar. Untuk menghindarinya, seorang prasyarat perlu bertukar informasi secara global seperti multigrid.

Wolfgang Bangerth

Multigrid terkenal tidak efektif dalam memecahkan Helmholtz karena, sebagian besar karena mode osilasi energi rendah sulit untuk dihaluskan atau untuk diwakili dalam ruang kasar. Ada beberapa pekerjaan pada gelombang-rangkap multigrid, tetapi formulasi ini sangat teknis dan itu bukan metodologi dewasa pada saat ini. Perhatikan bahwa sistem non-simetris juga dapat dipecahkan dengan menggunakan dekomposisi blok semacam ini. Bergantung pada pilihan variabel, (misalnya primitif vs konservatif), perubahan basis mungkin diperlukan di dalam prekondisi untuk mengekspos struktur yang diblokir.

Jed Brown

Jack telah memberikan prosedur yang baik untuk menemukan prekondisi. Saya akan mencoba menjawab pertanyaan, "Apa yang membuat prekondisi bagus?". Definisi operasional adalah:

Seorang Prekondisier M mempercepat solusi berulang dari , dan dapat diterapkan dengan murah dibandingkan dengan . $A x = b$ $M^{-1}$ $A^{-1}$

namun ini tidak memberi kita wawasan apa pun untuk mendesain prekondisi. Sebagian besar prekondisi didasarkan pada manipulasi spektrum operator. Secara umum, metode Krylov konvergen lebih cepat ketika nilai eigen dikelompokkan, lihat Iterasi Matriks atau Fungsi Meromorfik dan Aljabar Linier . Kadang-kadang kita dapat membuktikan hasil prekondisi hanya beberapa nilai eigen yang unik, misalnya Catatan tentang Prasyondisi untuk Sistem Linier Tidak Terbatas .

Strategi umum dicontohkan oleh Multigrid. Prasyarat relaksasi (di sini lebih baik) seperti SOR menghapus komponen frekuensi tinggi dalam kesalahan. Ketika residual diproyeksikan ke grid kasar, komponen kesalahan frekuensi yang lebih rendah menjadi frekuensi yang lebih tinggi dan dapat kembali diserang oleh SOR. Strategi dasar ini mendasari versi MG yang lebih rumit, seperti AMG. Perhatikan bahwa di bagian bawah, pemecah harus menyelesaikan frekuensi terendah dalam kesalahan secara akurat.

Strategi lain melibatkan penyelesaian persamaan dalam ruang bagian kecil, yang persis apa yang dilakukan pemecah Krylov. Dalam bentuk yang paling sederhana, ini adalah metode Kaczmarz atau Metode Additive Schwarz . Ketertarikan teori di sini, Domain Decomposition , berkonsentrasi pada perkiraan spektral dari kesalahan pada antarmuka, karena domain diasumsikan diselesaikan dengan cukup akurat.

Lalu ada banyak hal menghasilkan operator dekat dengan adalah beberapa pengertian, yang mudah untuk dibalik, tetapi tidak memberikan jaminan untuk benar-benar meningkatkan konvergensi iterasi Krylov, sejauh yang saya tahu. Prekondisi ini termasuk faktorisasi tidak lengkap (ICC, ILU), invers perkiraan jarang (SPAI), dan beberapa perkiraan peringkat rendah. $A$

Matt Knepley
sumber

Terimakasih atas balasan anda. Setiap pengalaman mengenai seberapa jauh kita harus benar - benar membuat bukti bahwa prakondisi berfungsi untuk sistem besar - dan mungkin bagaimana hal ini dapat atau harus dilakukan dalam praktik. Ini adalah pengalaman saya bahwa untuk banyak sistem kita harus bergantung pada intuisi, heuristik, dll.

Allan P. Engsig-Karup

Saya pikir intuisi terlalu jauh. Apa yang saya lihat dalam praktik adalah bukti untuk sistem yang sederhana. Kemudian argumen bahwa beberapa modifikasi harus peka terhadap parameter, atau jenis variasi tertentu. Kemudian percobaan numerik yang menunjukkan itu berfungsi bahkan di luar model variasi ini.

Matt Knepley