Sparse Matrix Multiplication

Sparse Matrix is a special matrix that most elements are zero. While processing sparse matrix in computer, to save space and running time, we only need to store those nonzero elements into a two dimension array.

 A = | 1 0 0|          | 7 0 0|  
     |-1 0 3|      B = | 0 0 0|
                       | 0 0 1|

      | 1 0 0|    |7 0 0|   | 7 0 0|
AXB = |-1 0 3| X  |0 0 0| = |-7 0 3| 
                  |0 0 1|

For A, it represents by a sequential array that for each row,only have the nonzero pair value that contains column and value:

A = [[0,1],              row 0, column 0 has value 1,
     [0,-1],[2,3]]       row 1, column 0 is -1, column is 3

Then multiply this dense vectors

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s