Apa cara terbaik untuk menentukan jumlah bukan nol dalam perkalian matriks jarang?

Saya bertanya-tanya apakah ada metode cepat dan efisien untuk menemukan jumlah bukan nol di muka untuk operasi perkalian matriks jarang dengan asumsi kedua matriks dalam format CSC atau CSR.

Saya tahu ada satu dalam paket smmp tapi saya butuh sesuatu yang sudah diimplementasikan dalam C atau C ++.

Bantuan apa pun akan dihargai. Terima kasih sebelumnya.

Anda bisa mensimulasikan produk matriks-matriks dengan membentuk produk dari dua pola sparsity - yaitu, Anda menganggap pola sparsity (yang disimpan dalam array terpisah dalam format CSR) sebagai matriks yang berisi nol atau satu di setiap entri. Melakukan produk simulasi ini hanya mengharuskan Anda untuk membentuk danoperasi pada nol dan satu ini dan dengan demikian jauh lebih cepat daripada produk matriks-matriks yang sebenarnya - pada kenyataannya, yang harus Anda lakukan adalah melalui baris dan kolom dari dua matriks dan memverifikasi bahwa setidaknya ada satu entri dalam baris dan kolom yang Anda kalikan dengan di mana kedua matriks tidak nol. Ini adalah operasi yang murah - jauh lebih murah dalam hal apa pun daripada benar-benar harus melakukan perkalian floating point dalam produk aktual yang tidak hanya mengharuskan Anda untuk melakukan aritmatika floating point (mahal) tetapi juga membaca dalam angka floating point aktual dari memori ( bahkan lebih mahal, tetapi Anda tidak perlu itu ketika mengalikan pola sparsity karena nilai-nilai non-nol dari matriks disimpan secara terpisah dalam CSR).

Saya benar-benar menulis kode asli di Matlab untuk A * B, baik A dan B jarang. Pra-alokasi ruang untuk hasilnya memang bagian yang menarik. Kami mengamati apa yang Godric tunjukkan - bahwa mengetahui jumlah nonzeros di AB sama mahalnya dengan menghitung AB.

Kami melakukan implementasi awal Matlab yang jarang sekitar tahun 1990, sebelum makalah Edith Cohen yang memberikan cara praktis dan cepat pertama untuk memperkirakan ukuran AB secara akurat. Kami mengumpulkan estimator ukuran lebih rendah, dan jika kami kehabisan ruang di pertengahan perhitungan, menggandakan alokasi dan menyalin hasil yang dihitung sebagian.

Saya tidak tahu apa yang ada di Matlab sekarang.

Kemungkinan lain adalah menghitung AB satu kolom pada satu waktu. Setiap kolom dapat disimpan sementara dalam akumulator jarang (lihat kertas Matlab jarang untuk penjelasannya), dan ruang yang dialokasikan untuk menampung ukuran kolom hasil yang diketahui dengan tepat. Hasilnya akan dalam bentuk kolom terkompresi jarang tersebar - setiap kolom dalam CSC tetapi tidak ada persentuhan antar kolom - menggunakan 2 vektor numcol panjang (mulai col, panjang col), bukan satu, sebagai meta-data. Ini adalah bentuk penyimpanan yang layak untuk dilihat; ia memiliki kekuatan lain - Anda dapat menumbuhkan kolom tanpa merealokasi seluruh matriks.

Makalah ini menjelaskan suatu algoritma untuk memperkirakan ukuran resultan dari produk matriks dua matriks jarang.

Masalah dengan menemukan jumlah entri non-nol yang tepat dalam perkalian matriks jarang adalah bahwa setiap elemen dalam resultan bergantung pada interaksi dua vektor, yang keduanya kemungkinan mengandung setidaknya beberapa elemen bukan nol. Oleh karena itu, untuk menghitung angka Anda perlu mengevaluasi operasi logis pada sepasang vektor untuk setiap elemen dalam resultan. Masalahnya adalah ini membutuhkan sejumlah operasi yang mirip dengan jumlah operasi yang diperlukan untuk menghitung produk matriks itu sendiri. Dalam komentar saya, saya menyebutkan kemungkinan untuk mengeksploitasi struktur tertentu dalam elemen non-nol dari matriks asli, namun eksploitasi yang sama dapat digunakan untuk mengurangi pekerjaan yang dilakukan dalam perkalian matriks juga.

Anda mungkin akan lebih baik menggunakan kertas di atas untuk memperkirakan kebutuhan memori secara berlebihan, melakukan penggandaan dan kemudian memotong memori yang dialokasikan, atau memindahkan matriks yang dihasilkan ke array yang berukuran lebih tepat. Juga, produk matriks jarang bukan kejadian langka, dan saya hampir menjamin bahwa masalah ini telah dipecahkan sebelumnya. Sedikit menggali ke dalam beberapa sumber terbuka, perpustakaan matriks jarang akan mengarahkan Anda ke algoritma yang mereka gunakan untuk mengalokasikan memori.

Untuk CSR atau CSC, apakah Anda dijamin bahwa array elemen matriks Anda sudah tidak memiliki nol? Dalam hal ini mudah untuk mengetahui berapa banyak elemen yang tidak nol, dengan menggunakan sesuatu yang mirip dengan:

int nnz = sizeof(My_Array)/sizeof(long int);

Namun jika ini bukan masalahnya (sepertinya agak terlalu mudah) yang bisa Anda coba adalah pengurangan . Jika susunan elemen matriks Anda sangat besar, ini mungkin cara yang paling efisien untuk menghitung jumlah elemen bukan nol. Banyak pustaka C / C ++ paralel seperti Thrust (pustaka CUDA) atau OpenCL (yang Anda tidak perlu menggunakan GPU) memiliki dukungan untuk pengurangan bersyarat - untuk setiap elemen, tambahkan hasilnya Condition(Element). Jika Anda mengatur kondisi ke Element != 0maka Anda akan menambahkan jumlah elemen bukan nol. Anda juga mungkin ingin menghapus elemen bernilai nol dari array elemen Anda, array indeks baris / kolom, dan menyesuaikan kolom / pointer baris Anda.

Cara paling sederhana untuk mengimplementasikan CSR adalah dengan mencoba

std::vector< std::map<int, complex<float>> > 

untuk mewakili matriks Anda. Dalam hal ini Anda tidak akan benar-benar khawatir tentang jumlah elemen yang tidak nol, semua diakses melalui

std::map< int, complex<float> >::iterator

di setiap baris. Terbaik ..