Saya bertanya-tanya apakah algoritma Thomas adalah cara tercepat (dapat dibuktikan?) Untuk menyelesaikan sistem tridiagonal simetris dominan diagonal dalam hal kompleksitas algoritmik (tidak mencari paket implementasi seperti LAPACK dll). Saya tahu bahwa kedua algoritma Thomas dan multigrid adalah kompleksitas, tetapi mungkin faktor konstan untuk multigrid kurang? Rasanya bagi saya multigrid tidak bisa lebih cepat tetapi saya tidak positif.
Catatan: Saya sedang mempertimbangkan kasus di mana matriksnya sangat besar. Baik metode langsung atau berulang dapat diterima.
Jawaban singkatnya adalah bahwa algoritma Thomas akan lebih cepat daripada skema iteratif untuk hampir semua kasus. Pengecualian mungkin akan menerapkan iterasi tunggal dari skema iteratif yang sangat sederhana seperti Gauss-Seidel, tetapi ini sangat tidak mungkin untuk memberikan solusi yang dapat diterima. Juga, ini mengabaikan masalah pemrosesan paralel.
sumber
Multigrid loop bahkan pada single core dapat di-vectorizable oleh optimizer. Jadi, sementara hitungan operasi dapat membantu, kita tidak boleh lupa bahwa bahkan di dunia serial, prosesor memiliki paralelisme vektor, dan karenanya waktu-ke-solusi mungkin tidak persis seperti yang kami prediksi dari analisis biaya.
sumber