Kompleksitas inversi matriks pada numpy

Saya memecahkan persamaan diferensial yang perlu membalik matriks kuadrat padat. Pembalikan matriks ini menghabiskan sebagian besar waktu perhitungan saya, jadi saya bertanya-tanya apakah saya menggunakan algoritma tercepat yang tersedia.

Pilihan saya saat ini adalah numpy.linalg.inv . Dari angka saya, saya melihat bahwa itu skala sebagai mana n adalah jumlah baris, sehingga metode ini tampaknya menjadi eliminasi Gaussian. $O(n^3)$

Menurut Wikipedia , ada algoritma yang lebih cepat tersedia. Adakah yang tahu kalau ada perpustakaan yang mengimplementasikan ini?

Saya bertanya-tanya, mengapa tidak numpy menggunakan algoritma yang lebih cepat ini?

numpy dense-matrix inverse fisikaBeli
sumber

Anda perlu melakukan matriks Anda sebelumnya. Lihatlah Scipy. Jarang untuk bantuan Anda. Ini berisi banyak alat yang Anda butuhkan.

Tobal

@ Global tidak yakin saya mengikuti ... bagaimana Anda "melakukan" sebuah matriks? dan bagaimana tepatnya akan scipy.sparsemembantu?

GoHokies

@ GoHokies scipy adalah pelengkap untuk numpy. Matriks padat / jarang harus diimplementasikan dengan baik sebelum Anda melakukan beberapa perhitungan, itu meningkatkan perhitungan Anda. Silakan baca docs.scipy.org/doc/scipy/reference/sparse.html ini menjelaskan lebih baik daripada saya dengan bahasa Inggris saya yang buruk.

Tobal

@ Global Pertanyaan khusus mengacu pada matriks padat , jadi saya tidak melihat bagaimana scipy.sparserelevan di sini?

Christian Clason

@ Global - saya pikir saya masih tidak mengerti. Apa sebenarnya yang Anda maksud dengan "membentuk matriks Anda", dan "matriks harus diimplementasikan dengan baik sebelum Anda melakukan beberapa perhitungan"? Mengenai komentar terakhir Anda, pasti Anda akan setuju bahwa teknik yang dapat digunakan untuk matriks jarang dan padat sangat berbeda.

Wolfgang Bangerth

Jawaban:

(Ini terlalu panjang untuk dikomentari ...)

Saya akan menganggap Anda benar-benar perlu menghitung invers dalam algoritma Anda. ¹ Pertama, penting untuk dicatat bahwa algoritma alternatif ini sebenarnya tidak diklaim lebih cepat , hanya saja mereka memiliki kompleksitas asimptotik yang lebih baik (artinya jumlah operasi elementer yang diperlukan tumbuh lebih lambat). Bahkan, dalam praktiknya ini sebenarnya (jauh) lebih lambat daripada pendekatan standar (untuk diberikan ), karena alasan berikut: $n$

The -notation kulit konstan di depan kekuatan , yang dapat astronomis besar - begitu besar sehingga bisa jauh lebih kecil dari untuk setiap yang dapat ditangani oleh komputer manapun di masa mendatang. (Contohnya untuk algoritma Coppersmith – Winograd.) $\mathcal{O}$ $n$ $C_1 n^3$ $C_2 n^{2.x}$ $n$
Kompleksitas mengasumsikan bahwa setiap operasi (aritmatika) membutuhkan waktu yang sama - tetapi ini jauh dari benar dalam praktik yang sebenarnya: Mengalikan banyak angka dengan angka yang sama jauh lebih cepat daripada mengalikan jumlah yang sama dari angka yang berbeda . Hal ini disebabkan oleh fakta bahwa leher botol utama dalam komputasi saat ini adalah memasukkan data ke dalam cache, bukan operasi aritmetika aktual pada data tersebut. Jadi suatu algoritma yang dapat diatur ulang untuk memiliki situasi pertama (disebut cache-aware ) akan jauh lebih cepat daripada yang tidak memungkinkan. (Ini kasus untuk algoritma Strassen, misalnya.)

Juga, stabilitas numerik setidaknya sama pentingnya dengan kinerja; dan di sini, sekali lagi, pendekatan standar biasanya menang.

$\mathcal{O}(n^3)$ $\mathcal{O}(n^{2.x})$

¹ Tapi saya akan salah jika saya tidak menunjukkan bahwa ini sangat jarang benar-benar diperlukan: kapan saja Anda perlu menghitung produk

, Anda harus menyelesaikan sistem linier

(misalnya, menggunakan ) dan gunakan

sebagai gantinya - ini jauh lebih stabil, dan dapat dilakukan (tergantung pada struktur matriks

) jauh lebih cepat. Jika Anda perlu menggunakan

beberapa kali, Anda dapat melakukan precompute faktorisasi

(yang biasanya merupakan bagian paling mahal dari penyelesaian) dan menggunakannya kembali nanti.

A^{- 1} b

$A^{-1}b$

A x = b

$Ax=b$ numpy.linalg.solve

x

$x$

A

$A$

A^{- 1}

$A^{-1}$

A

$A$

Christian Clason
sumber

Jawaban yang bagus, terima kasih pak, khususnya untuk menunjukkan setan dalam detail (konstanta dalam notasi O besar) yang membuat perbedaan besar antara kecepatan teoretis dan kecepatan praktis.

Gaborous

Saya pikir bagian "terbalik jarang diperlukan" harus lebih ditekankan. Jika tujuannya adalah untuk menyelesaikan sistem persamaan diferensial, tampaknya tidak mungkin diperlukan inversi penuh.

Jared Goguen

@ o_o Yah, itu komentar pertama saya yang asli (yang saya hapus setelah menggabungkan semuanya menjadi satu jawaban). Tapi saya pikir, untuk kepentingan situs (dan pembaca kemudian), jawaban harus menjawab pertanyaan aktual dalam pertanyaan (yang masuk akal dan sesuai topik), bahkan jika ada masalah XY di belakangnya. Juga, saya tidak ingin terdengar terlalu menegur ...

Christian Clason

n

$n$

A

$A$

Anda mungkin harus mencatat bahwa, terkubur jauh di dalam kode sumber numpy (lihat https://github.com/numpy/numpy/blob/master/numpy/linalg/umath_linalg.c.src ) rutin inv mencoba untuk memanggil fungsi dgetrf dari paket sistem LAPACK Anda, yang kemudian melakukan dekomposisi LU dari matriks asli Anda. Ini secara moral setara dengan eliminasi Gaussian, tetapi dapat disesuaikan dengan kompleksitas yang sedikit lebih rendah dengan menggunakan algoritma multiplikasi matriks yang lebih cepat dalam BLAS kinerja tinggi.

Jika Anda mengikuti rute ini, Anda harus diingatkan bahwa memaksa seluruh rantai perpustakaan untuk menggunakan perpustakaan baru daripada sistem yang menyertai distribusi Anda cukup rumit. Salah satu alternatif pada sistem komputer modern adalah dengan melihat metode paralel menggunakan paket-paket seperti scaLAPACK atau (di dunia python) petsc4py. Namun ini biasanya lebih bahagia digunakan sebagai pemecah iteratif untuk sistem aljabar linier daripada diterapkan pada metode langsung dan PETSc dalam target tertentu sistem jarang lebih dari yang padat.

origimbo
sumber