Metode berulang untuk sistem tidak terbatas tanpa struktur blok

9

Sistem matriks yang tidak terbatas muncul misalnya dalam diskritisasi masalah sadel oleh elemen hingga campuran. Matriks sistem kemudian dapat dimasukkan ke dalam formulir

(\begin{matrix} A & B^{t} \\ B & C \end{matrix})

$\begin{pmatrix} A & B^t \\ B & C\end{pmatrix}$

di mana negatif (semi) -definite, positif (semi-) pasti dan adalah arbitrer. Tentu saja, tergantung pada konvensi Anda dapat menggunakan kondisi ketetapan, tetapi ini cukup banyak struktur matriks tersebut. $A$ $C$ $B$

Untuk metode ini, metode Uzawa dapat digunakan, yang sebenarnya hanya "trik" untuk mengubah sistem menjadi sistem semi-pasti yang setara yang dapat dipecahkan oleh Conjugate Gradient, Gradient Descent dan sejenisnya.

Saya menghadapi sistem tak terbatas yang tidak memiliki struktur blok seperti itu. Metode tipe Uzawa tidak berlaku dalam kasus itu. Saya mengetahui metode Minimal Residual (MINRES) yang telah diperkenalkan oleh Paige & Saunders, yang hanya merupakan rekursi tiga periode dan tampaknya mudah diimplementasikan.

Pertanyaan: Apakah MINRES umumnya merupakan pilihan yang baik, misalnya, untuk membuat prototipe? Apakah ada relevansi praktisnya? Prakondisi bukanlah masalah utama saat ini.

linear-algebra iterative-method shuhalo
sumber

Bisakah Anda mengatakan lebih banyak tentang apa yang membuat matriks Anda istimewa? Misal masalah seperti apa asalnya? Apakah ada struktur lain untuk itu? Dll.

Bill Barth

Saya sengaja membiarkannya kosong, untuk mendapatkan jawaban yang paling umum (terus terang, ini secara implisit mengasumsikan ada jawaban umum yang memuaskan). Tetapi contoh dengan persamaan Helmholtz di bawah ini adalah apa yang ada dalam pikiran saya.

shuhalo

7

Jika Anda tidak khawatir tentang prasyarat, maka MINRES adalah pilihan standar. Namun, perlu diketahui bahwa MINRES membutuhkan preconditioner definitif positif simetris.

Jika Anda khawatir dengan kondisi awal, maka penting untuk mempertimbangkan perbedaan struktural antara sebagian besar masalah sadel dan masalah umum yang tidak terbatas. Sebagian besar masalah sadel muncul ketika memecahkan masalah elips dengan kendala yang ditegakkan oleh pengganda Lagrange. Ketidakterkompresan dan batasan kontak adalah contoh umum. Untuk masalah seperti itu, operator paksaan pada ruang bagian di mana kendala puas, dengan fungsi Green yang membusuk dengan cepat. Masalah seperti itu dapat diselesaikan secara efisien dengan menggunakan preconditioner blok (Uzawa yang dikondisikan sebelumnya adalah anggota keluarga ini), multigrid dengan smoothers yang kompatibel (misalnya Vanka atau berdasarkan dekomposisi blok), atau dekomposisi domain bertingkat dengan masalah lokal dan kasar yang sesuai.

Contoh prototipikal dari masalah tidak terbatas yang bukan merupakan masalah titik sadel adalah persamaan Helmholtz

- \nabla \cdot (a \nabla u) - k^{2} u = f

$-\nabla\cdot \big( a \nabla u \big) - k^2 u = f$

$a(x)$ $k$

Jed Brown
sumber

1

Agar adil, sementara prekondisi besar tentu saja teknis untuk diterapkan secara efisien secara paralel, idenya tidak spesifik untuk Helmholtz; persyaratan utama adalah kondisi batas yang menyerap (mis., Lapisan yang Cocok Sempurna).

Jack Poulson

3

Pertanyaan terkait yang mungkin menarik adalah Pedoman apa yang harus saya ikuti ketika memilih pemecah sistem linier yang jarang? , meskipun dalam hal ini, Anda hanya akan tertarik pada metode iteratif. Pemahaman saya tentang metode berulang adalah bahwa konvergensi untuk setiap metode yang diberikan sangat tergantung pada spektrum matriks Anda. Meskipun Anda tidak dapat menggunakan metode Uzawa, Anda masih bisa mencoba GMRES, Biconjugate stable gradient, MINRES, metode residu kuasi minimal, dan metode berulang lainnya di luar sana yang berlaku untuk matriks yang tidak terbatas.

Jika pengkodean berbagai metode menjadi perhatian, Anda bisa memanggil solver dalam algoritme Anda menggunakan perpustakaan seperti PETSc , yang mengimplementasikan berbagai solver linier berulang.

Geoff Oxberry
sumber

1

MINRES adalah pilihan terbaik untuk masalah jenis ini.

Kees Vuik
sumber

1

Tolong jangan menautkan situs pribadi Anda dengan cara ini. Jangan ragu untuk menautkan sumber daya spesifik yang relevan dengan jawaban Anda, tetapi jangan menautkan situs pribadi Anda dengan cara ini. Saya telah menghapusnya dari jawaban ini. Tautan semacam itu milik profil pengguna Anda.

Jed Brown

Bisakah Anda jelaskan mengapa MINRES adalah pilihan terbaik untuk masalah seperti ini? Menambahkan lebih banyak detail akan membantu membuat jawaban Anda lebih bermanfaat bagi komunitas, dan akan membantu Anda mendapatkan lebih banyak suara.

Geoff Oxberry

Metode berulang untuk sistem tidak terbatas tanpa struktur blok

Jawaban: