Discussion:
[問題] 產生稀疏矩陣及稀疏矩陣相乘?
(时间太久无法回复)
臨兵鬥者皆陣列在前
2007-08-08 13:35:03 UTC
Permalink
如題,最近因為研究需要,要測試電腦是否有辦法計算兩個一萬X一萬的矩陣相乘

普通的矩陣好像不行吧....不過我要測的是稀疏矩陣

好像C/C++跟Fortran都有支援稀疏矩陣的算法

不過我只會java 所以來請教一下各位了orz


1.如何產生稀疏矩陣?

因為我才剛學java沒多久,所以用了能想到最直覺的方法,
也就是跑兩次巢狀迴圈,第一次給random值(0~1),這麼一來應該會有一半左右的值為0
接著第二次巢狀迴圈把原本矩陣中為1的值再給一次random值(0~9),
這麼一來最簡單的稀疏矩陣寫法便完成了orz

請問有更好的寫稀疏矩陣的方法嗎?一半以上的值為0的矩陣應該就是稀疏矩陣了吧


2.兩個矩陣相乘的寫法??

如果只是 data3[i][j] == data1[i][j]*data2[i][j] 這樣的話我是會寫啦
不過矩陣相乘應該不是這樣乘的吧orz,請問矩陣相乘的程式怎麼寫呢?


3.兩個大量稀疏矩陣相乘的寫法?

會寫矩陣相乘的程式後,接下來就是要處理稀疏矩陣了;因為稀疏矩陣有許多零值的關係
所以一般情況下應該有一些方法可以來縮減資料量,以達成大量稀疏矩陣的相乘

一般矩陣的話,兩個一萬X一萬矩陣相乘電腦應該就爆了吧orz
如果是稀疏矩陣的話,不知道有什麼方法可以順利計算出來呢??



http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/SparseMatrix.htm

上面這個網站有介紹稀疏矩陣與索引陣列之間的轉換,也有java程式可以看
不過給的卻是把已知索引陣列轉成稀疏矩陣的程式orz
所以我自己又寫了一個相反過來的程式,也就是把稀疏矩陣轉成索引陣列的程式
網頁說轉成索引陣列可以利用較少的記憶體空間儲存完整的矩陣資訊

這樣的方法可以幫助用來計算稀疏矩陣嗎? 因為計算時還是要轉回來吧
所以感覺對"計算"好像沒有很大幫助orz



抱歉問題很多 麻煩java高手們解惑了




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.212.147
※ 編輯: kians 來自: 61.230.212.147 (08/08 21:37)
._.
2007-08-08 14:05:19 UTC
Permalink
※ 引述《kians (臨兵鬥者皆陣列在前)》之銘言:
: 如題,最近因為研究需要,要測試電腦是否有辦法計算兩個一萬X一萬的矩陣相乘
: 普通的矩陣好像不行a....不過我要測的是稀疏矩陣
: 好像C/C++跟Fortran都有支援稀疏矩陣的算法
: 不過我只會java 所以來請教一下各位了orz
: 1.如何產生稀疏矩陣?
: 因為我才剛學java沒多久,所以用了能想到最直覺的方法,
: 也就是跑兩次巢狀迴圈,第一次給random值(0~1),這麼一來應該會有一半左右的值為0
: 接著第二次巢狀迴圈把原本矩陣中為1的值再給一次random值(0~9),
: 這麼一來最簡單的稀疏矩陣寫法便完成了orz
: 請問有更好的寫稀疏矩陣的方法嗎?一半以上的值為0的矩陣應該就是稀疏矩陣了吧

void laranda(int x, int y, int howsparse, int howlarge) {
Random ran = new Random();
int iamblow = ran.nextInt(howsparse);
for(int i = 0; i < x; i++) {
for(int j = 0; j < y; j++) {
iamblow--;
if(iamblow < 0) {
iamblow = ran.nextInt(howsparse);
shamewagogi[i][j] = ran.nextInt(howlarge)
}
}
}
}

大概不能跑吧? 反正簡單來說就是差個倒數炸彈, 爆了就看傷亡數字這樣.

: 2.兩個矩陣相乘的寫法??
: 如果只是 data3[i][j] == data1[i][j]*data2[i][j] 這樣的話我是會寫啦
: 不過矩陣相乘應該不是這樣乘的吧orz,請問矩陣相乘的程式怎麼寫呢?

我 google 了一下矩陣相乘, 因為其實我沒玩過

第一個連結告訴我說三個 for 迴圈就好了..

第二個連結告訴我說這個東西我短時間用不到, 所以我就沒細看了..

http://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95

: 3.兩個大量稀疏矩陣相乘的寫法?
(中略)
: 這樣的方法可以幫助用來計算稀疏矩陣嗎? 因為計算時還是要轉回來吧
: 所以感覺對"計算"好像沒有很大幫助orz
: 抱歉問題很多 麻煩java高手們解惑了

沒有必要一定要轉回來阿..

以兩層 hashmap 的情況來說的話...

你可以用 Iterator 去兩個對繞...

..

我這樣會不會黑話太嚴重了?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.25.148.49
台大我回來了!
2007-08-08 15:52:00 UTC
Permalink
�� �ޭz�mkians (�{�L���̬Ұ}�C�b�e)�n���ʨ��G
: 3.���Ӥj�q�}���x�}�ۭ����g�k?
: �|�g�x�}�ۭ����{����,���U�ӴN�O�n�B�z�}���x�}�F;�]���}���x�}���\�h�s�Ȫ����Y
: �ҥH�@�뱡�p�U��Ӧ��@�Ǥ��k�i�H���Y�����ƶq,�H�F���j�q�}���x�}���ۭ�
: �@���x�}����,���Ӥ@�UX�@�U�x�}�ۭ��q����ӴN�z�F�aorz
�^�o�I

(1) ���ެO���O�}���x�} �n�ΤT�hfor�j���]���ܨ����IJv��Ӯt���h
���h�}���x�}�h�@�ӧ��䤤�@�ӱqrow major���ǧ令column major����
�o�|�y�L�[�t�@�U�N�O
���L�}���x�}���������k���g�k �|�񴶳q���T�hfor�y��
(�]�N�O�R���Q�ε}���x�}���S��: 0�@��)

(2) (��ӬO�ӫܭ��n���@�I)
�}���x�}���}���x�}���@�w�O�ӵ}���x�}...
���ݤ@�I���Ҥl�Ҧp
[1 0 0 0 0] [1 1 1 1 1] [1 1 1 1 1]
[1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
[1 0 0 0 0] x [0 0 0 0 0] = [1 1 1 1 1]
[1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
[1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
�e���ӫܵ}���a? �i�ĤT�ӫo�@�I�]���}��...
�ҥH�̫��A�٬O�o�n�@�Ӥ@�U���@�U�����q�x�}�Ӧs����
(���M�����O�ݧA�����ӵ}���x�}��0����G)
������ij�ݦ��S�����k�䭼�����X���G

--
�n���o���I���Mjava�Sԣ��...|||
--
�ܻ�����C/C++�]���O�y������ �n��������ӬO���L�M���a

--
�Ե^�G�u�e���I�A�u���N�o�˳Q���輤�����l�޹L�h�F��?!�v
���G�u�u�n���ۤk���\�X�ˤ���ˤl�A�Ҧ����n���O�N�����K�A���G�@�I�����a�ڡC�v
�Ե^�G�u���D�A�S���k�H���L�Y�F��?!�v
���G(�_�M�D)�u�S���C�b�`���Y���B�ͬ��Y�����ǥ����e�A�S�����تF���C�v
�С�������Ƿǵȸ������Ƿǵ �ĤG��

--
�� �o�H��: ���������~�{(ptt.cc)
�� From: 219.84.44.21
2007-08-17 11:02:36 UTC
Permalink
Post by 臨兵鬥者皆陣列在前
如題,最近因為研究需要,要測試電腦是否有辦法計算兩個一萬X一萬的矩陣相乘
普通的矩陣好像不行吧....不過我要測的是稀疏矩陣
好像C/C++跟Fortran都有支援稀疏矩陣的算法
matlab有支援,而且好像有內建的產生sparse matrix的方式
Post by 臨兵鬥者皆陣列在前
不過我只會java 所以來請教一下各位了orz
1.如何產生稀疏矩陣?
因為我才剛學java沒多久,所以用了能想到最直覺的方法,
也就是跑兩次巢狀迴圈,第一次給random值(0~1),這麼一來應該會有一半左右的值為0
接著第二次巢狀迴圈把原本矩陣中為1的值再給一次random值(0~9),
這麼一來最簡單的稀疏矩陣寫法便完成了orz
請問有更好的寫稀疏矩陣的方法嗎?一半以上的值為0的矩陣應該就是稀疏矩陣了吧
印像中有三分之二以上為零比較算吧…
因為如果用陣列索引表示法的話要存矩陣的列、行、值
等於原本一個位置要存三個值

我工作用到的是lanczos算矩陣本徵值
其中只有用到矩陣乘向量,用陣列索引表示法乘的確會快很多
但前提是我的sparse大概至少有十分之一以上為零
我是用c++寫,不過c++也沒什麼內建的東西可以處理這個吧
用stl的vector倒是滿好實作sparse matrix的計算的
Post by 臨兵鬥者皆陣列在前
2.兩個矩陣相乘的寫法??
如果只是 data3[i][j] == data1[i][j]*data2[i][j] 這樣的話我是會寫啦
不過矩陣相乘應該不是這樣乘的吧orz,請問矩陣相乘的程式怎麼寫呢?
就用索引表示法吧,有值的位置再去乘,會快非常多…至少就我的case
用一千萬乘一千萬的矩陣去乘一個一千萬的向量還滿快的
Post by 臨兵鬥者皆陣列在前
3.兩個大量稀疏矩陣相乘的寫法?
會寫矩陣相乘的程式後,接下來就是要處理稀疏矩陣了;因為稀疏矩陣有許多零值的關係
所以一般情況下應該有一些方法可以來縮減資料量,以達成大量稀疏矩陣的相乘
一般矩陣的話,兩個一萬X一萬矩陣相乘電腦應該就爆了吧orz
如果是稀疏矩陣的話,不知道有什麼方法可以順利計算出來呢??
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/SparseMatrix.htm
上面這個網站有介紹稀疏矩陣與索引陣列之間的轉換,也有java程式可以看
不過給的卻是把已知索引陣列轉成稀疏矩陣的程式orz
所以我自己又寫了一個相反過來的程式,也就是把稀疏矩陣轉成索引陣列的程式
網頁說轉成索引陣列可以利用較少的記憶體空間儲存完整的矩陣資訊
這樣的方法可以幫助用來計算稀疏矩陣嗎? 因為計算時還是要轉回來吧
計算時不用轉回來…
Post by 臨兵鬥者皆陣列在前
所以感覺對"計算"好像沒有很大幫助orz
抱歉問題很多 麻煩java高手們解惑了
--
生命的情節是可以安排的

你可以在茉莉香的清晨微笑醒來

也可以在玫瑰紅的黃昏入睡
我們原是自己的造夢者
--
╔═══╗ ┼────────────────────────╮
║狂狷 ║ │* Origin:[ 狂 狷 年 少 ] whshs.cs.nccu.edu.tw ╰─╮
║ 年少║ ┼╮ < IP:140.119.164.252 > ╰─╮
╚╦═╦╝  ╰  * From:61-64-172-148-adsl-tpe.dynamic.so-net.net.
 ─╨─╨─ KGBBS ─ ◎ 遨翔"BBS"的狂狷不馴;屬於年少的輕狂色彩 ◎ 
Loading...