Masalah di mana gradien konjugasi bekerja jauh lebih baik daripada GMRES

17

Saya tertarik pada kasus di mana konjugasi gradien bekerja jauh lebih baik daripada metode GMRES.

Secara umum, CG adalah pilihan yang lebih disukai dalam banyak kasus SPD (symmetric-positive-definite) karena memerlukan lebih sedikit penyimpanan dan ikatan teoritis pada tingkat konvergensi untuk CG dua kali lipat dari GMRES itu. Apakah ada masalah di mana angka tersebut benar-benar diamati? Apakah ada karakterisasi kasus di mana GMRES berkinerja lebih baik atau sebanding dengan CG untuk jumlah spmv yang sama (multiplikasi matriks-vektor jarang).

linear-solver conjugate-gradient gmres piyush_sao
sumber

8

Satu hal yang CG memiliki yang mendukung adalah bahwa hal itu tidak meminimalkan diskrit norma untuk polinomial sisa nya (apa GMRES tidak). Ini meminimalkan norma yang diinduksi matriks, dan sangat sering norma yang diinduksi matriks ini berakhir sangat dekat dengan norma energi untuk diskritisasi masalah fisik, dan seringkali ini adalah norma yang jauh lebih masuk akal untuk mengukur kesalahan karena sifat konservasi yang datang dari fisika. $l^2$

Anda benar-benar dapat mencapai efek semacam ini dengan GMRES juga jika melakukan faktorisasi Cholesky dari matriks massa tidak terlalu mahal, Anda dapat memaksa produk dalam menjadi produk energi dalam yang Anda inginkan.

Maka kasus-kasus di mana seseorang harus mengharapkan CG untuk melakukan sangat berbeda dari GMRES kemudian adalah ketika konstanta yang tersirat dalam kesetaraan norma sangat berbeda. Ini bisa benar misalnya dalam metode spektral-Galerkin orde tinggi di mana diskrit $l^2$ norma yang digunakan dalam GMRES memperlakukan semua derajat kebebasan sebagai sama, walaupun pada kenyataannya gradien polinomial yang paling tajam di dekat batas (maka node clustering), sehingga konstanta kesetaraan norma antara norma itu dan mengatakannorma kontinu yang $L^2$ diberikan oleh matriks massa bisa sangat besar.

Reid.Atcheson
sumber

Ingin memberi contoh di sini dengan metode orde tinggi dan sejarah konvergensi CG, GMRES, dan GMRES + Trik Cholesky .. tapi sayangnya satu-satunya kode yang saya miliki untuk masalah urutan kedua adalah DG dari variasi nonsimetri .. jadi CG tidak tidak berlaku, akan senang melihat ini beraksi.

Reid.Atcheson

3

Saya pikir jawaban Anda mendapatkan sesuatu yang penting tetapi saya harap Anda akan menjelaskan. Secara khusus, pertanyaannya adalah pertanyaan aljabar linier murni, dan jawaban Anda berbicara tentang norma fisik dan matriks massa dan seterusnya dari PDE numerik. Bisakah kita mengatakan sesuatu yang tepat tentang bagaimana meminimalkan norma yang berbeda di dalam ruang Krylov yang sama mengarah pada iterasi yang berbeda?

Andrew T. Barker

Selain dari contoh-contoh numerik, saya kira belum ada studi teoritis yang menjelaskan bagaimana norma yang berbeda menghasilkan jawaban yang secara substansial berbeda. Masalahnya saya pikir adalah bahwa hasil berputar di sekitar asimptotik, dan untuk sistem linear tetap, hasil teoritis akan menjadi faktor konstan modulo identik. Jika ada beberapa studi teoritis di luar sana, saya akan senang melihatnya, tetapi setelah bertanya kepada beberapa ahli aljabar linear numerik di departemen saya, sepertinya belum ada analisis teoritis yang tepat yang menunjukkan apa yang terjadi dengan norma yang berbeda.

Reid.Atcheson

4

Saya menduga secara umum tidak ada banyak perbedaan antara GMRES dan CG untuk matriks SPD.

Katakanlah kita sedang memecahkan dengan pasti positif simetris dan tebakan awal dan menghasilkan iterasi dengan CG dan GMRES, sebut mereka dan . Kedua metode iterasi akan membangun dari yang sama Krylov ruang . Mereka akan melakukannya dengan cara yang sedikit berbeda. $Ax = b$ $A$ $x_0 = 0$ $x_k^c$ $x_k^g$ $x_k$ $K_k = \{ b, Ab, A^2b, \ldots \}$

CG ditandai dengan meminimalkan kesalahan di norma energi yang disebabkan oleh , sehingga $e_k^c = x - x_k^c$ $A$

(A e_{k}^{c}, e_{k}^{c}) = (A (x - x_{k}^{c}), x - x_{k}^{c}) = min_{y \in K} (A (x - y), x - y) .

$\begin{equation} (A e_k^c, e_k^c) = (A (x - x_k^c), x - x_k^c) = \min_{y \in K} (A (x-y), x-y). \end{equation}$

GMRES meminimalkan bukannya sisa , dan melakukannya dalam diskrit norma, sehingga $r_k = b - A x^g_k$ $\ell^2$

(r_{k}, r_{k}) = (b - A x_{k}^{g}, b - A x_{k}^{g}) = min_{y \in K} (b - A y, b - A y) .

$\begin{equation} (r_k, r_k) = (b - A x_k^g, b - A x_k^g) = \min_{y \in K} (b - Ay, b - Ay). \end{equation}$ Sekarang menggunakan kesalahan persamaan

kita bisa GMRES juga menulis meminimalkan

di mana saya ingin menekankan bahwa ini hanya berlaku untuk sebuah SPD matriks

. Kemudian kami memiliki CG meminimalkan kesalahan sehubungan dengan

A e_{k} = r_{k}

$A e_k = r_k$

(r_{k}, r_{k}) = (A e_{k}^{g}, A e_{k}^{g}) = (A^{2} e_{k}^{g}, e_{k}^{g})

$\begin{equation} (r_k, r_k) = (A e_k^g, A e_k^g) = (A^2 e_k^g, e_k^g) \end{equation}$

A

$A$

A

$A$ norma dan GMRES meminimalkan kesalahan sehubungan dengan

norma. Jika kita ingin mereka berperilaku sangat berbeda, secara intuitif kita akan membutuhkan nilai

sehingga kedua norma ini sangat berbeda. Tetapi untuk SPD

norma-norma ini akan berperilaku sangat mirip.

A^{2}

$A^2$

A

$A$

A

$A$

Untuk mendapatkan lebih spesifik, dalam iterasi pertama dengan ruang Krylov , baik CG dan GMRES akan membangun perkiraan bentuk . CG akan memilih $K_1 = \{ b \}$ $x_1 = \alpha b$

α = \frac{(b, b)}{(A b, b)}

$\begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation}$

α = \frac{(A b, b)}{(A^{2} b, b)} .

$\begin{equation} \alpha = \frac{ (Ab,b) }{ (A^2b,b) }. \end{equation}$

A

$A$

(ϵ, 1, 1, 1, \dots)

$(\epsilon,1,1,1,\ldots)$

b = (1, 1, 0, 0, 0, \dots)

$b = (1,1,0,0,0,\ldots)$

ϵ \to 0

$\epsilon \rightarrow 0$

A

$A$

b

$b$ sehingga faktor dua perbedaan ini terus berlanjut sepanjang iterasi, tapi saya ragu itu menjadi lebih buruk dari itu.

Andrew T. Barker
sumber

2

b = (1, \sqrt{ϵ}, 0, 0, \dots)

$b = (1,\sqrt{\epsilon},0,0,\dotsc)$

| b | = \sqrt{1 + ϵ}

$|b| = \sqrt{1 + \epsilon}$

b^{T} A b = \sqrt{2} ϵ

$b^T A b = \sqrt{2} \epsilon$

b^{T} A^{2} b = ϵ \sqrt{1 + ϵ^{2}}

$b^T A^2 b = \epsilon \sqrt{1 + \epsilon^2}$

α_{CG} = \frac{ϵ^{- 1} + 1}{\sqrt{2}} \sim ϵ^{- 1}

$\alpha_{\text{CG}} = \frac{\epsilon^{-1}+1}{\sqrt 2} \sim \epsilon^{-1}$

α_{GMRES} = \sqrt{\frac{2}{1 + ϵ^{2}}} \sim \sqrt{2}

$\alpha_{\text{GMRES}} = \sqrt{\frac{2}{1 + \epsilon^2}} \sim \sqrt{2}$

ϵ^{- 1}

$\epsilon^{-1}$

3

Satu hal adalah bahwa GMRES tidak pernah digunakan di mana pun CG dapat diterapkan. Saya rasa tidak masuk akal untuk membandingkan keduanya. Untuk matriks SPD, CG jelas merupakan pemenang karena persyaratan penyimpanan dan alasan yang Anda sebutkan di atas. Sebuah pertanyaan yang akan menarik adalah, untuk menemukan perpanjangan dari CG, yang berlaku untuk masalah di mana CG tidak dapat diterapkan. Ada metode seperti BiCG-stab yang tidak memerlukan peningkatan memori linear seperti GMRES, tetapi konvergensi tidak sebagus GMRES (beberapa kali bahkan dengan restart GMRES).

pengguna1964178
sumber

2

Ada skema IDR yang menjembatani kesenjangan antara GMRES dan BiCG dalam hal penghematan memori, stabilitas, dan konvergensi: ta.twi.tudelft.nl/nw/users/gijzen/IDR.html Saya tidak yakin saya setuju bahwa GMRES tidak boleh digunakan jika CG bisa. Jika Anda dapat melakukan faktorisasi cholesky dari matriks yang menginduksi norma energi Anda, maka Anda dapat memasukkannya ke dalam iterasi Lanczos simetris dan mendapatkan solusi perulangan tiga jangka yang akan berperilaku sangat mirip dengan CG. Tentu saja, CG adalah pilihan yang lebih mudah, tetapi pilihan itu tersedia :)

Reid.Atcheson

2

Jika Anda menggunakan Krylov yang lebih halus, misalnya, maka GMRES kemungkinan lebih disukai karena menggunakan norma yang lebih lemah yang menargetkan nilai eigen yang lebih besar yang cenderung frekuensinya lebih tinggi.

Jed Brown

Masalah di mana gradien konjugasi bekerja jauh lebih baik daripada GMRES

Jawaban: