CODEWITHSUNDEEP
c++matrixvector
user906357
user906357

Reputation: 4685

Matrix vector multiplication CCS c++

I am trying to multiply a matrix and a vector with the matrix in Compressed Column Storage. The matrix is :

0   3   0   
4   0   0   
2   0   0

here is the CCS form:

[ 4 2 3 ]
[ 2 3 1 ]
[ 1 3 4 4 ]

The vector is:

[ 1 3 4 ]

So the product should be

[ 9 4 2 ]

Here is the function I am trying to create

vector<int> multiply(vector<int> val,vector<int> col,vector<int> row,vector<int> v, int r){

    vector<int> x(v.size());
    for (int j=0; j<r; j++) {
        for (int i=col[j]-1; i<col[j+1]-1; i++) {
            cout<<"\n"<<val[i]<<"*"<<v[j]<<"\n";
            x[j]+= val[i]*v[j];
        }
    }
    return x;
}

But this returns

[ 6 9 0 ]

This is the closest I've gotten to the real solution, how can I fix this?

Upvotes: 1

Views: 665

Answers (1)

hansod1
hansod1

Reputation: 324

I would think about this as driven by the col_ptr vector.

1.) I wasn't sure what value(s) r could take, so I removed it, as we don't need that information to solve the problem 2.) I should note that I have not compiled this, but I believe the algorithm is correct 3.) There are some obvious ways to optimize the memory usage of this code, but I left those variables in to help explain the process. 4.) The main problem with the code you posted is that it doesn't seem to use the row array to tell us which row the value is in!

vector<int> multiply(vector<int> val,vector<int> col,vector<int> row,vector<int> v) {
   vector<int> x(v.size());
   //we may need to initialize x as all zeroes, I forget
   int col_size = col.size();
   int column_idx = 0;
   for (int j=0; j<col_size-1; j++) {
      //j indicates where the columns start going!
      //columns end prior to the next column start
      //val_index is where we need to start in the val array, for this column
      int val_index_start = col[j]-1; //this is redunda
      //we keep traversing forward until the next column starts
      int next_column_start = col[j+1]-1;
      for (int k=val_index_start; k < next_column_start && k < v.size(); k++) {
        int row_of_cell = row[k] - 1;
        int column_of_cell = column_idx;
        int product = v[column_idx]*val[k];
        x[row_of_cell] += product;
      }
      column_idx++;
   }
   return x;
}

Upvotes: 1

Related Questions