Membalik matriks band

Saya memiliki matriks pita - matriks yang jarang, kuadrat, simetris yang strukturnya tampak seperti berikut:$N \times N$

Di sini, area di bawah garis-garis biru adalah elemen bukan nol; yang lainnya nol

Apakah ada algoritma untuk membalikkan jenis matriks yang sederhana namun lebih efisien daripada eliminasi Gaussian dan dekomposisi LU?

Karena tidak ada komentar yang memberikan jawaban konkret, saya akan menuliskannya secara eksplisit di sini jika ada yang membutuhkannya (seperti yang saya lakukan).

Pertama, sayangnya, invers dari matriks terbatas-band adalah matriks penuh (tidak terbatas-band) secara umum, jadi hanya mengisi entri dari matriks invers akan mengambil $\Omega\left(n^2\right)$. Jadi saya anggap Anda hanya ingin menyelesaikan sistem linear$A x = b$.

Menggunakan algoritma dalam makalah ini , matriks band-terbatas umum$A$ ukuran $n \times n$ dengan bandwidth $k$ dapat diuraikan menjadi segitiga $k$matriks-bandwidth $L$ dan $U$ di $O \left( k^2 n \right)$waktu. Dari sana,$L U x = b$ dapat diselesaikan dengan cepat di $O(k n)$waktu. Jadi secara keseluruhan, runtime akan menjadi$O\left(k^2 n\right)$. Sebagai tindak lanjut, jika$k$ adalah konstan, itu berarti bahwa sistem dapat diselesaikan dalam waktu linier (sangat bermanfaat).