Matrix multiplication using pairs

Question

Hi,

I am looking into alternate ways to do a Matrix Multiplication. Instead of storing my matrix as a two-dimensional array, I am using a vector such as

vector<pair<pair<int,int >,int > > 

to store my matrix. The pair within my pair (pair) stores my indices (i,j) and the other int stores the value for the given (i,j) pair. I thought I might have some luck implementing my sparse array this way.

The problem is when I try to multiply this matrix with itself.

If this was a 2-d array implementation, I would have multiplied the matrix as follows:

   for(i=0; i<row1; i++)
    {
        for(j=0; j<col1; j++)
        {
          C[i][j] = 0;
         for(k=0; k<col2; k++) 
           C[i][j] += A[i][j] * A[j][k];
      }
    }

Can somebody point out a way to achieve the same result using my vector of 'pair of pairs'?

Thanks

Answer 1

So far you can store one value at one location. If you want to store several nonzero entries in the matrix, you will need more pairs of pairs in a larger structure.

map<pair<int, int>, int> would be the next logical step. Now you can iterate over rows because the first coordinate is more significant in the map's sorting order.

To iterate over columns, reverse that precedence:

typedef pair<int, int> mx_coord;
struct reverse_compare {
    bool operator() (mx_coord const &l, mx_coord const &r) const
        { return l.second < r.second? true :
                 r.second < l.second? false : l.first < r.first; }
};

typedef map< mx_coord, int > matrix;
typedef map< mx_coord, int, reverse_compare > matrix_transpose;

To multiply A by B, transpose B and iterate over A and B, multiplying any elements whose less-significant coordinates match, as the ordering naturally lets you go line-by-line and column-by-column.

To transpose B:

matrix_transpose b_t( b.begin(), b.end() ); // complexity: n log n