Dapatkah sistem linier simetris diagonal plus tetap diselesaikan dalam waktu kuadrat setelah perhitungan?

21

Apakah ada metode untuk menyelesaikan sistem linear dari bentuk mana adalah matriks SPD tetap dan adalah matriks diagonal positif? $O(n^3+n^2 k)$ $k$ $(D_i + A) x_i = b_i$ $A$ $D_i$

Misalnya, jika setiap adalah skalar, itu sudah cukup untuk menghitung SVD dari . Namun, ini rusak untuk umum karena kurangnya komutatif. $D_i$ $A$ $D$

Pembaruan : Jawaban sejauh ini adalah "tidak". Adakah yang punya intuisi yang menarik mengapa? Jawaban tidak berarti bahwa tidak ada cara nontrivial untuk mengompres informasi antara dua operator nonkomuter. Ini tidak terlalu mengejutkan, tetapi akan lebih baik untuk memahaminya dengan lebih baik.

linear-algebra algorithms performance complexity Geoffrey Irving
sumber

SPD = semi-positif pasti?

rcollyer

Ya, meskipun masalahnya pada dasarnya sama tanpa SPD. Saya menambahkan kendala itu hanya untuk memastikan bahwa sistem tidak pernah tunggal.

Geoffrey Irving

19

Jawaban positif terdekat untuk pertanyaan Anda yang dapat saya temukan adalah untuk gangguan diagonal yang jarang (lihat di bawah).

Dengan itu, saya tidak tahu algoritma apa pun untuk kasus umum, meskipun ada generalisasi teknik yang Anda sebutkan untuk perubahan skalar dari matriks SPD ke semua matriks persegi:

Dengan adanya matriks kuadrat , terdapat dekomposisi Schur , di mana adalah kesatuan dan adalah segitiga atas, dan memberikan dekomposisi Schur dari . Jadi, ide perhitungan Anda meluas ke semua matriks kuadrat melalui algoritma: $A$ $A=U T U^H$ $U$ $T$ $A+\sigma I = U (T + \sigma I) U^H$ $A + \sigma I$

Hitung dalam paling banyak bekerja. $[U,T]=\mathrm{schur}(A)$ $\mathcal{O}(n^3)$
Selesaikan masing-masing melalui dalam pekerjaan (inversi tengah hanyalah substitusi kembali). $(A+\sigma I) x = b$ $x := U (T +\sigma I)^{-1} U^H b$ $\mathcal{O}(n^2)$

Garis penalaran ini mengurangi ke pendekatan yang Anda sebutkan ketika adalah SPD karena dekomposisi Schur dikurangi menjadi EVD untuk matriks normal, dan EVD bertepatan dengan SVD untuk matriks pasti-positif Hermitian. $A$

Tanggapan untuk memperbarui: Sampai saya punya bukti, yang tidak saya miliki, saya menolak untuk mengklaim bahwa jawabannya adalah "tidak". Namun, saya dapat memberikan beberapa wawasan mengapa itu sulit, serta subkotak lain di mana jawabannya adalah ya.

Kesulitan mendasar adalah bahwa, meskipun pembaruan diagonal, itu masih dalam peringkat penuh secara umum, jadi alat utama untuk memperbarui invers, rumus Sherman-Morrison-Woodbury , tampaknya tidak membantu. Meskipun case shift skalar juga peringkat penuh, ini adalah kasus yang sangat istimewa karena ia berpindah dengan setiap matriks, seperti yang Anda sebutkan.

Dengan mengatakan bahwa, jika masing-masing jarang, yaitu, masing-masing memiliki nonzeros, maka rumus Sherman-Morrison-Woodbury menghasilkan diselesaikan dengan masing-masing pasangan . Misalnya, dengan satu nol di entri diagonal , sehingga : $D$ $\mathcal{O}(1)$ $\mathcal{O}(n^2)$ $\{D,b\}$ $j$ $D=\delta e_j e_j^H$

[A^{- 1} + δ e_{j} e_{j}^{H}]^{- 1} = A^{- 1} - \frac{δ A^{- 1} e_{j} e_{j}^{H} A^{- 1}}{1 + δ (e_{j}^{H} A^{- 1} e_{j})},

$[A^{-1}+\delta e_j e_j^H]^{-1} = A^{-1} - \frac{\delta A^{-1} e_j e_j^H A^{-1}}{1+\delta (e_j^H A^{-1} e_j)},$

di mana adalah vektor basis standar ke- . $e_j$ $j$

Pembaruan lain: Saya harus menyebutkan bahwa saya mencoba preconditioner yang disarankan @GeoffOxberry pada beberapa matriks SPD acak menggunakan PCG dan, mungkin tidak mengherankan, tampaknya sangat mengurangi jumlah iterasi ketika kecil, tetapi tidak ketika atau lebih besar. $A^{-1}$ $1000 \times 1000$ $||D||_2/||A||_2$ $\mathcal{O}(1)$

Jack Poulson
sumber

12

Jika adalah diagonal dominan untuk setiap , maka karya terbaru oleh Koutis, Miller, dan Peng (lihat situs Koutis' untuk bekerja pada simetris matriks diagonal yang dominan) dapat digunakan untuk memecahkan setiap sistem di waktu (sebenarnya waktu, di mana adalah jumlah maksimum entri bukan nol dalam atas semua $(D_{i} + A)$ $i$ $\mathcal{O}(n^2 \log(n))$ $\mathcal{O}(m\log(n))$ $m$ $(D_{i} + A)$ , jadi Anda bisa memanfaatkan sparsity juga). Kemudian, total waktu berjalan adalah , yang lebih baik daripada pendekatan untuk menyelesaikan setiap sistem secara naif menggunakan aljabar linier padat, tetapi sedikit lebih buruk daripada waktu lari kuadratik yang Anda gunakan. sedang meminta. $i$ $\mathcal{O}(n^2 \log(n) k)$ $\mathcal{O}(n^3 k)$

Sparsity yang signifikan dalam untuk semua yang dapat dieksploitasi oleh pemecah jarang untuk menghasilkan algoritma , tapi saya menduga bahwa jika Anda memiliki sparsity yang signifikan, maka Anda akan menyebutkannya. $(D_{i} + A)$ $i$ $\mathcal{O}(n^2 k)$

Anda juga dapat menggunakan sebagai prasyarat untuk menyelesaikan setiap sistem menggunakan metode berulang, dan melihat bagaimana hasilnya. $A^{-1}$

Tanggapan untuk memperbarui : @JackPaulson membuat poin yang bagus dari sudut pandang aljabar linier numerik dan algoritma. Saya akan fokus pada argumen kompleksitas komputasi sebagai gantinya.

Kompleksitas komputasi dari solusi sistem linier dan kompleksitas komputasi dari perkalian matriks pada dasarnya sama. (Lihat Teori Kompleksitas Aljabar .) Jika Anda dapat menemukan algoritma yang dapat memampatkan informasi antara dua operator non-komuter (mengabaikan bagian semidefinit positif) dan langsung memecahkan kumpulan sistem yang Anda usulkan dalam waktu kuadratik dalam , maka itu kemungkinan Anda bisa menggunakan algoritma seperti itu untuk membuat kesimpulan tentang multiplikasi matriks yang lebih cepat. Sulit untuk melihat bagaimana struktur semidefinit positif dapat digunakan dalam metode langsung dan padat untuk sistem linear untuk mengurangi kompleksitas komputasinya. $n$

Seperti @JackPaulson, saya tidak mau mengatakan bahwa jawabannya adalah "tidak" tanpa bukti, tetapi mengingat koneksi di atas, masalahnya sangat sulit dan menarik minat penelitian saat ini. Yang terbaik yang dapat Anda lakukan dari sudut pandang asimptotik tanpa memanfaatkan struktur khusus adalah peningkatan pada algoritma Coppersmith dan Winograd, menghasilkan algoritma , di mana . Algoritma itu akan sulit dikodekan, dan kemungkinan akan lambat untuk matriks kecil, karena faktor konstan sebelum perkiraan asimptotik mungkin sangat besar dibandingkan dengan eliminasi Gaussian. $\mathcal{O}(n^{\alpha}k)$ $\alpha \approx 2.375$

Geoff Oxberry
sumber

3

Saya belum melihat pernyataan konkret tentang di mana crossover itu berada, tetapi beberapa sumber yang memiliki reputasi telah menyatakan bahwa (selain masalah implementasi), Coppersmith-Winograd tidak dapat mengalahkan metode standar untuk ukuran matriks yang akan dapat masuk ke memori dalam waktu dekat. (beberapa dekade). Mengingat bahwa tolok ukur Linpack membutuhkan waktu lebih dari satu hari untuk berjalan di mesin-mesin top saat ini, tampaknya tidak mungkin bahwa Coppersmith-Winograd akan pernah digunakan dalam praktik. Strassen sebenarnya praktis untuk masalah-masalah besar, meskipun agak stabil secara numerik.

Jed Brown

Itu tidak mengejutkan saya. +1 untuk detail implementasi.

Geoff Oxberry

6

Ekspansi Taylor orde pertama dapat digunakan untuk meningkatkan konvergensi dari lagging sederhana. Misalkan kita memiliki preconditioner (atau faktor untuk langsung memecahkan) tersedia untuk , dan kami ingin menggunakannya untuk preconditioning . Kita bisa menghitung $A+D$ $A$

\begin{aligned} A^{- 1} & = (A + D - D)^{- 1} (A + D) (A + D)^{- 1} \\ = [(A + D)^{- 1} (A + D - D)]^{- 1} (A + D)^{- 1} \\ = [I - (A + D)^{- 1} D]^{- 1} (A + D)^{- 1} \\ \approx [I + (A + D)^{- 1} D] (A + D)^{- 1} \end{aligned}

$\begin{align} A^{-1} &= (A+D-D)^{-1} (A+D) (A+D)^{-1} \\ &= [(A+D)^{-1} (A+D-D)]^{-1} (A+D)^{-1} \\ &= [I - (A+D)^{-1} D]^{-1} (A+D)^{-1} \\ &\approx [I + (A+D)^{-1} D] (A+D)^{-1} \end{align}$

di mana ekspansi Taylor digunakan untuk menulis baris terakhir. Penerapan preconditioner ini membutuhkan dua memecahkan dengan . $A+D$

Ini bekerja cukup baik ketika prekondisi digeser dari 0 dengan jumlah yang sama atau lebih besar dari operator yang kita coba pecahkan dengan (misalnya ). Jika pergeseran dalam prekondisi lebih kecil ( ), operator prekondisi menjadi tidak terbatas. $D\gtrsim 0$ $D \lesssim \min \sigma(A)$

Jika pergeseran dalam prekondisi jauh lebih besar daripada di operator, metode ini cenderung menghasilkan angka kondisi sekitar setengah dari prakondisi oleh operator yang tertinggal (dalam tes acak yang saya jalankan, bisa lebih baik atau lebih buruk untuk kelas tertentu dari matriks). Faktor 2 dalam angka kondisi tersebut memberikan faktor dalam hitungan iterasi. Jika biaya iterasi didominasi oleh solves dengan, maka ini bukan faktor yang cukup untuk membenarkan ekspansi Taylor urutan pertama. Jika aplikasi matriks secara proporsional mahal (misalnya Anda hanya memiliki preconditioner yang murah untuk menerapkan), maka metode urutan pertama ini mungkin masuk akal. $\sqrt 2$ $A+D$ $A+D$

Jed Brown
sumber

Dapatkah sistem linier simetris diagonal plus tetap diselesaikan dalam waktu kuadrat setelah perhitungan?

Jawaban: