Memecahkan tanpa membalikkan

Saya memiliki matriks dan . jarang dan dengan sangat besar (bisa dalam urutan beberapa juta.) adalah matriks tinggi dengan agak kecil ( ) dan setiap kolom dapat hanya memiliki satu entri dengan sisanya menjadi 's, sehingga . sangat besar, jadi sangat sulit untuk membalikkan, dan saya bisa menyelesaikan sistem linear seperti secara iteratif menggunakan metode ruang bagian Krylov seperti , tapi saya tidak punya $A$ $G$ $A$ $n\times n$ $n$ $G$ $n\times m$ $m$ $1 \lt m \lt 1000$ $1$ $0$ $G^TG = I$ $A$ $Ax = b$ $\mathrm{BiCGStab}(l)$ $A^{-1}$ secara eksplisit.

Saya ingin menyelesaikan sistem formulir: , di mana dan adalah vektor panjang . Salah satu cara untuk melakukannya adalah dengan menggunakan algoritma iteratif dalam algoritma iteratif untuk menyelesaikan untuk untuk setiap iterasi dari algoritma iteratif luar. Ini akan menjadi sangat mahal secara komputasi. Saya bertanya-tanya apakah ada cara komputasi yang lebih mudah untuk menyelesaikan masalah ini. $(G^TA^{-1}G)x = b$ $x$ $b$ $m$ $A^{-1}$

linear-algebra linear-solver sparse-matrix krylov-method Costis
sumber

Saya baru saja menambahkan jawaban saya pada komentar tentang mengeksploitasi struktur 0-1.

Arnold Neumaier

Jawaban:

Perkenalkan vektor dan selesaikan sistem berpasangan besar , untuk secara bersamaan, menggunakan metode iteratif. Jika adalah simetris (seperti tampaknya meskipun Anda tidak menyatakannya secara eksplisit) maka sistemnya adalah simetris (tetapi tidak terbatas, meskipun quasidefinite jika adalah pasti positif), yang mungkin membantu Anda memilih metode yang tepat. (kata kunci yang relevan: matriks KKT, matriks quasidefinite). $y:=-A^{-1}Gx$ $Ay+Gx=0$ $G^Ty=-b$ $(y,x)$ $A$ $A$

Sunting: Karena adalah simetris yang kompleks, demikian pula matriks yang ditambah, tetapi tidak ada quasidefiniteness. Namun Anda dapat menggunakan rutin untuk menghitung ; karena itu Anda dapat mengadaptasi metode seperti QMR ftp://ftp.math.ucla.edu/pub/camreport/cam92-19.pdf (dirancang untuk sistem nyata, tetapi Anda dapat dengan mudah menulis ulang untuk sistem yang kompleks, menggunakan adjoin di tempat transpos) untuk menyelesaikan masalah Anda. $A$ $Ax$ $A^*x=\overline{A\overline x}$

Sunting2: Sebenarnya, (0,1) -struktur berarti Anda dapat menghilangkan dan komponen secara simbolis, sehingga berakhir dengan sistem yang lebih kecil untuk dipecahkan. Ini berarti mengacaukan struktur , dan membayar hanya ketika diberikan secara eksplisit dalam format jarang daripada sebagai operator linier. $G$ $x$ $G^Ty$ $A$ $A$

Arnold Neumaier
sumber

Terima kasih! A adalah simetris yang kompleks. Apakah ada alasan untuk mengharapkan kondisi matriks yang diperbesar menjadi lebih buruk daripada kondisi matriks asli ? Jika m kecil, matriks augmented hanya sedikit lebih besar dalam ukuran dari A, jadi saya menduga bahwa memecahkan sistem augmented ini secara iteratif seharusnya tidak lebih sulit daripada menyelesaikan sistem dengan A?

A

$A$

Costis

Jumlah kondisi kedua sistem tersebut pada umumnya cukup tidak terkait; itu sangat tergantung pada apa adalah. - Saya menambahkan ke informasi jawaban saya tentang cara mengeksploitasi simetri kompleks.

G

$G$

Arnold Neumaier

Halo kawan-kawan! Terima kasih atas semua balasannya; tempat ini hebat! Perpanjangan dari pertanyaan awal: Asumsikan sekarang saya punya , di mana G dan A memiliki makna yang sama seperti dalam pertanyaan asli tetapi B adalah peringkat kekurangan nxn matriks (ukuran yang sama dengan A) dan seluruh adalah peringkat penuh. Bagaimana Anda pergi tentang memecahkan sistem baru, karena sekarang kebalikan dari B tidak ada jadi Anda tidak dapat memiliki . Saya tidak berpikir itu akan berhasil hanya dengan pseudoinverse dari B juga.

(G^{T} A^{- H} B A^{- 1} G) x = b

$(G^TA^{-H}BA^{-1}G)x=b$

G^{T} A^{- H} B A^{- 1} G

$G^TA^{-H}BA^{-1}G$

A B^{- 1} A^{H}

$AB^{-1}A^H$

Costis

Perkenalkan dan , dan lanjutkan secara analogi dengan kasus yang berhasil. (Mungkin Anda juga perlu memasukkan faktor ke dalam matriks peringkat penuh dan memperkenalkan vektor perantara tambahan.)

y := A^{- 1} G x

$y:=A^{-1}Gx$

z := A^{- H} B y

$z:=A^{-H}By$

B

$B$

Arnold Neumaier

Hai Arnold. Terima kasih, ini memang berhasil! Saya mengujinya dengan beberapa contoh uji yang sangat kecil, dan itu bekerja dengan baik. Namun, pemecah iteratif saya mengalami masalah besar pembalik matriks augmented. Meskipun hanya membutuhkan sekitar 80 iterasi (beberapa detik) untuk menyelesaikan sistem bentuk dengan matriks A asli, sistem dengan matriks yang diperbesar (yaitu 2n + mx 2n + m atau 2n-mx 2n-m menggunakan pendekatan @ wolfgang-bangerth) membutuhkan lebih dari puluhan ribu iterasi (beberapa jam) untuk menyelesaikan satu RHS. Apakah ada strategi untuk mempercepat konvergensi? mungkin seorang prasyarat?

A x = b

$Ax=b$

Costis

Mengikuti jawaban Arnold, ada sesuatu yang dapat Anda lakukan untuk menyederhanakan masalah. Secara khusus, tulis ulang sistem sebagai . Kemudian perhatikan bahwa dari pernyataan bahwa adalah tinggi dan sempit dan setiap baris hanya memiliki satu 1 dan nol sebaliknya, maka pernyataan berarti bahwa himpunan bagian dari elemen memiliki nilai tetap, yaitu unsur-unsur dari . $Ay+Gx=0, G^Ty=-b$ $G$ $G^Ty=-b$ $y$ $-b$

Mari kita katakan bahwa untuk kesederhanaan bahwa memiliki kolom dan baris dan bahwa persis baris pertama memiliki yang di dalamnya dan yang menyusun kembali unsur-unsur saya dapat membuatnya sehingga memiliki matriks identitas di atas dan nol matriks di bagian bawah. Kemudian saya dapat mempartisi ke dalam "constrained" dan "free" sehingga . Saya juga dapat mempartisi sehingga . Dari persamaan $G$ $m$ $n$ $m$ $x$ $G$ $m \times m$ $n-m \times m$ $y=(y_c,y_f)$ $m$ $n-m$ $y_c=-b$ $A$ $A=\begin{pmatrix} A_{cc} & A_{cf} \\ A_{fc} & A_{ff} \end{pmatrix}$ $Ay+Gx=0$ Saya kemudian mendapatkan yang berikut: dan menggunakan apa yang kita ketahui tentang kita miliki dari persamaan kedua ini dan akibatnya Dengan kata lain, satu-satunya matriks yang harus Anda invert adalah subset dari yang baris dan kolomnya tidak disebutkan dalam (ruang nol dari ). Ini dapat Anda lakukan dengan mudah: (i) menghitung ; (ii) gunakan pemecah apa pun yang Anda miliki untuk menyelesaikan ; (iii) menghitung .

A_{c c} y_{c} + A_{c f} y_{f} + x = 0, A_{f c} y_{c} + A_{f f} y_{f} = 0

$A_{cc} y_c + A_{cf} y_f + x = 0, \\ A_{fc} y_c + A_{ff} y_f = 0$

y_{c}

$y_c$

A_{f f} y_{f} = A_{f c} b

$A_{ff} y_f = A_{fc} b$

x = A_{c c} b - A_{c f} A_{f f}^{- 1} A_{f c} b .

$x = A_{cc} b - A_{cf} A_{ff}^{-1} A_{fc} b.$

A

$A$

G

$G$

G

$G$

z = A_{f c} b

$z=A_{fc} b$

A_{f f} h = z

$A_{ff} h = z$

x = A_{c c} b - A_{c f} h

$x = A_{cc} b - A_{cf} h$

Dengan kata lain, mengingat struktur , memecahkan sistem linear yang Anda miliki adalah benar-benar tidak lebih sulit daripada memecahkan sistem linear tunggal dengan . $G$ $A$

Wolfgang Bangerth
sumber

Tapi kita tahu , dan , jadi $G$ $G^T$ $A$

$G^T A^{-1} G x = b$

$G G^T A^{-1} G x = G b$

Karena , maka , jadi : $G^T G = I$ $G^T = G^{-1}$ $G G^T=I$

$A^{-1} G x = G b$

$A A^{-1} G x = A G b$

$G x = A G b$

$G^T G x = G^T A G b$

$x = G^T A G b$

Kecuali jika saya melewatkan sesuatu, Anda tidak perlu iterasi, atau pemecah apa pun untuk menghitung x yang diberikan , dan . $G$ $A$ $b$

Phil H
sumber

G^{T}

$G^T$ menjadi kebalikan dari tidak berarti bahwa itu juga kebalikan dari kanan. Pertimbangkan , di mana adalah invers kiri, tapi .

G

$G$

G = e_{1}

$G=e_1$

G^{T} = e_{1}^{T}

$G^T=e_1^T$

G G^{T} = e_{1} e_{1}^{T} \neq I

$GG^T=e_1e_1^T\neq I$

Jack Poulson

G \in C^{n} \otimes C^{m}

$G\in \mathbb{C}^n\otimes \mathbb{C}^m$ , karenanya , tetapi . Melainkan itu adalah proyektor pada subruang.

G^{T} G = I_{m \times m}

$G^TG=I_{m\times m}$

G G^{T} \neq I_{n \times n}

$GG^T\ne I_{n\times n}$

Deathbreath