Dengan sistem linear tridiagonal SPD, dapatkah kita melakukan prekomputasi sehingga tiga indeks dapat dihubungkan dalam waktu O (1)?

11

Pertimbangkan sistem linear tridiagonal pasti positif simetris mana A R n × n dan b R n . Diberikan tiga indeks 0 i < j < k < n , jika kita mengasumsikan hanya baris persamaan antara i dan k tahan, kita dapat menghilangkan variabel perantara untuk mendapatkan persamaan bentuk u x i + v x j + w x k = c

Ax=b
ARn×nbRn0i<j<k<nik
uxi+vxj+wxk=c
dimana . Persamaan ini menghubungkan nilai x j ke x i , x k independen dari pengaruh "luar" (katakanlah, jika kendala yang mempengaruhi x 0 diperkenalkan).v>0xjxi,xkx0

Pertanyaan : Apakah mungkin untuk memproses ulang sistem linear dalam waktu O ( n ) sehingga persamaan penautan untuk setiap ( i , j , k ) dapat ditentukan dalam waktu O ( 1 ) ?Ax=bO(n)(i,j,k)O(1)

Jika diagonal adalah 2, offdiagonals adalah - 1 , dan b = 0 , hasil yang diinginkan adalah hasil analitik untuk persamaan Poisson yang diskrit. Sayangnya, tidak mungkin untuk mengubah sistem tridiagonal SPD umum menjadi persamaan Poisson koefisien konstan tanpa melanggar struktur tridiagonal, pada dasarnya karena variabel yang berbeda dapat memiliki tingkat "penyaringan" yang berbeda (kepastian positif ketat lokal). Skala x diagonal sederhana , misalnya, dapat menghilangkan setengah dari DOF 2 n - 1 dari A tetapi tidak pada setengah lainnya.A1b=0x2n1A

Secara intuitif, solusi untuk masalah ini akan membutuhkan pengaturan masalah sehingga jumlah skrining dapat diakumulasikan menjadi array ukuran linier dan kemudian entah bagaimana "dibatalkan" untuk sampai pada persamaan penghubung untuk triple yang diberikan.

O(n)O(1)

Geoffrey Irving
sumber

Jawaban:

2

b=0n(0,i,n1)0i<n

xi=aix0+bixn1

i<jijxn1

bjxi=aibjx0+bibjxn1bixj=ajbix0+bibjxn1bjxibixj=(aibjajbi)x0xi=aibjajbibjx0+bibjxj

x0(i,j,k)bj=0bj=0

Geoffrey Irving
sumber
Setelah menerapkan ini, saya dapat mengkonfirmasi bahwa (1) ia bekerja dalam aritmatika yang tepat dan (2) ini sangat tidak stabil. Secara intuitif, solusi ini melakukan ekstrapolasi fungsi eksponensial, yang memecah karakter interpolasi yang bagus dari masalah elips.
Geoffrey Irving
bj0nlogn
O(n)O(logn)
2

Saya ingin tahu apakah Anda dapat melakukan sesuatu yang bermanfaat dengan faktorisasi siklik-reduksi dari A (yang saya yakini masih berukuran O (n)), menggunakan kembali sebanyak mungkin blok yang akan tetap tidak berubah ketika memfaktorkan submatriks utama yang berdekatan dari A. Saya ragu itu memberi Anda O (1), tapi mungkin O (log n) ...

Robert Bridson
sumber
O(logn)
Tidak ada peluang amortisasi membantu Anda?
Robert Bridson
Ada banyak amortisasi lain yang terjadi, jadi sangat mungkin. Tapi saya belum tahu caranya.
Geoffrey Irving
Inilah yang saya perlu amortisasi biaya: cstheory.stackexchange.com/questions/18655/… .
Geoffrey Irving
Bagus! Seseorang memposting solusi yang bagus untuk pertanyaan itu, jadi saya tidak perlu lagi menjawab pertanyaan ini. Operasi multiplikasi semi-grup dalam pertanyaan itu menghilangkan variabel perantara.
Geoffrey Irving
1

Berikut upaya lain, yang lebih stabil daripada metode pembatalan tetapi masih belum terlalu baik.

AB=A1

Bij=bi+1bjdj+1dnδiδn

ijbidi,δiULLUAi<j<k

xj=(BjiBki)T(BiiBikBkiBkk)1(xixk)

ikik2×2

[1]: Gerard Meurant (1992), "Sebuah ulasan tentang kebalikan dari diagonal simetris dan blok matriks tridiagonal".

Geoffrey Irving
sumber