Apa algoritma tercepat untuk menghitung peringkat matriks persegi panjang?

14

Diberi matriks (dengan asumsi ), apa algoritma tercepat untuk menghitung peringkat dan basis kolomnya?m×nmn

Saya sadar ini dapat diselesaikan melalui persimpangan matroid linier, yang menyiratkan algoritma deterministik waktu dan algoritma acak waktu . Apakah ada algoritma deterministik waktu yang lebih langsung mengurangi masalah (atau eliminasi Gaussian) menjadi penggandaan matriks?O(mn1.62)O(mnω1)O(mnω1)

Ho Yee Cheung
sumber

Jawaban:

6

Anda dapat membawa -matrix ke dalam bentuk eselon dalam waktu O ( n ω + ϵ ) untuk setiap ϵ > 0 . Lihat buku "Teori Kompleksitas Aljabar" oleh Bürgisser, Clausen, Shokrollahi, Bagian 16.5.2n×nO(nω+ϵ)ϵ>0

Sekarang Anda menerapkan prosedur ini kali untuk Anda m × n -matrix. Ini memberikan algoritma dengan operasi aritmatika O ( m n ω - 1 ) .m/nm×nO(mnω1)

Jika Anda membawa -matrix ke dalam bentuk eselon, maka itu berisi matriks nol ukuran n × n sesudahnya. Anda mengambil n × n -matrix yang tersisa, tambahkan n × n- blok baru dari matriks input Anda dan bawa ini ke bentuk eselon dan seterusnya.2n×nn×nn×nn×n

5501
sumber
1
Apakah Anda berarti membelah baris ke m / n kelompok? Bagaimana Anda menggabungkan hasil m / n untuk memberikan peringkat? Pertimbangkan dua baris dalam bentuk eselon dari kelompok berbeda yang keduanya memiliki 1 di kolom pertama, mereka mungkin memiliki peringkat 2 kan? mm/nm/n
Ho Yee Cheung
Apakah ada batas bawah untuk ini? Seperti apakah pangkat memiliki kekuatan komputasi?
Thomas Ahle