Jadi, saya punya sekitar 100-200 matriks boolean persegi yang sangat jarang dengan panjang sisi ~ beberapa lusin, dan saya perlu menghitung produk mereka. Saya tahu bahwa jika saya mengalikannya secara seri, produk biasanya akan tetap jarang di setiap langkah.
Apakah ada algoritma produk rantai matriks yang bekerja sangat cepat dalam kasus ini?
Pada level yang lebih tinggi, masalahnya adalah menghitung komposisi serangkaian pemetaan satu-ke-banyak pada grafik yang cukup kecil (fungsi transisi NFA), di mana sebagian besar elemen dipetakan tidak lebih dari 0-3.
(harap dicatat bahwa ini bukan masalah "produk rantai matriks" yang biasa, karena semua matriks memiliki ukuran yang sama dan saya tidak harus memilih tanda kurung yang optimal)
Jawaban:
Ini terlalu lama untuk menjadi komentar - Saya ingin tahu apakah matriks-matriks itu memiliki struktur yang membuat mereka berperilaku berbeda dari matriks acak. Produk matriks jarang acak menjadi nol atau menjadi non-jarang dengan cepat.
Berikut adalah eksperimen sederhana - ambil 200 matriks biner acak 50x50, dan plot jumlah non-nol sebagai fungsi dari jumlah matriks dikalikan. Plot di bawah ini menunjukkan standar deviasi selama 2000 kali. Plot pertama untuk sparsity 2%, plot kedua untuk 3%
(sumber: yaroslavvb.com ) (sumber: yaroslavvb.com )
ini memakan waktu 3 menit di laptop saya menggunakan perkalian matriks standar
sumber