Saya mencari makalah survei atau buku yang membahas hasil tentang kompleksitas ruang dari operasi aljabar linear umum seperti peringkat matriks, perhitungan nilai eigen, dll. Saya menekankan bagian "kompleksitas ruang" yang berarti kompleksitas ruang kerja, daripada kompleksitas waktu karena itu lebih mudah untuk melacak hasil waktu. Saya menghargai referensi apa pun dalam masalah ini.
Terima kasih.
Jawaban:
Versi keputusan banyak masalah umum dalam aljabar linier atas bilangan bulat (atau rasional) berada di kelas , lihat makalahDET
Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Struktur dan Pentingnya Kelas Logspace-MOD. Teori Sistem Matematika 25 (3): 223-237 (1992)
terkandung dalam D S P A C E ( log 2 ) .DET DSPACE(log2)
Menghitung nilai eigen sedikit lebih rumit:
1) Dalam , seseorang dapat menghitung koefisien dari polinomial karakteristik.DSPACE(log2)
2) Kemudian Anda dapat menggunakan algoritma paralel dengan Reif dan Neff untuk menghitung perkiraan nilai eigen. Algoritme berjalan pada CREW-PRAM dalam waktu logaritmik dengan banyak prosesor secara polinomi, sehingga dapat disimulasikan dengan ruang poli-logaritmik. (Ini tidak secara eksplisit dinyatakan dalam makalah, tetapi PRAM mereka harus seragam log-ruang.) Ruang yang digunakan adalah polylogarithmic dalam ukuran matriks input dan presisi . Precision p berarti Anda mendapatkan perkiraan hingga kesalahan aditif 2 - p .p p 2−p
Ini adalah gabungan fungsi yang dapat dihitung dalam ruang poli-logaritmik. (Kaset output hanya untuk menulis dan oneway.)
C. Andrew Neff, John H. Reif: Algoritma Efisien untuk Masalah Roots Kompleks. J. Complexity 12 (2): 81-115 (1996)
sumber
sumber