Convert a matrix A in a sparse formats CSR, COO, etc

Question

I have a little problem, I would like to convert a matrix 10*10 in a CSR or COO sparse matrix/format. The matrix is:

 1.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00
-0.45  0.10 -0.45  0.00  0.00  0.00  0.00  0.00  0.00  0.00
 0.00 -0.45  0.10 -0.45  0.00  0.00  0.00  0.00  0.00  0.00
 0.00  0.00 -0.45  0.10 -0.45  0.00  0.00  0.00  0.00  0.00
 0.00  0.00  0.00 -0.45  0.10 -0.45  0.00  0.00  0.00  0.00
 0.00  0.00  0.00  0.00 -0.45  0.10 -0.45  0.00  0.00  0.00
 0.00  0.00  0.00  0.00  0.00 -0.45  0.10 -0.45  0.00  0.00
 0.00  0.00  0.00  0.00  0.00  0.00 -0.45  0.10 -0.45  0.00
 0.00  0.00  0.00  0.00  0.00  0.00  0.00 -0.45  0.10 -0.45
 0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  0.00  1.00

I am using the "CUSP" functions but it did not work, once tha matrix A I would like just to convert in other format. Can you help me?

Well I would like also to use this matrix to solve the system Ax=b, using bicgstab:

b=
   0.00000
   0.34202
   0.64279
   0.86603
   0.98481
   0.98481
   0.86603
   0.64279
   0.34202
   0.00000

My code for this is:

int n = 10, r;

cusp::coo_matrix<int,float,cusp::device_memory> A(n, n, 3*n - 4);
cusp::array1d<float, cusp::device_memory> x(A.num_rows, 0);
cusp::array1d<float, cusp::device_memory> b(A.num_rows, 1);

   b[0]=0.00000;
   b[1]=0.34202;
   b[2]=0.64279;
   b[3]=0.86603;
   b[4]=0.98481;
   b[5]=0.98481;
   b[6]=0.86603;
   b[7]=0.64279;
   b[8]=0.34202;
   b[9]=0.00000;

i=0;
// row 0
A.row_indices[i] = 0.0;
A.column_indices[i] = 0.0;
A.values[i] = 1.00;

++i;
// rows 1 through n - 2
for (r = 1; r != n - 1; ++r) {
  A.row_indices[i] = r;
  A.column_indices[i] = r - 1;
  A.values[i] = -0.45;
  ++i;
  A.row_indices[i] = r;
  A.column_indices[i] = r;
  A.values[i] = 0.10;
  ++i;
  A.row_indices[i] = r;
  A.column_indices[i] = r + 1;
  A.values[i] = -0.45;
  ++i;
}
// row n - 1
A.row_indices[i] = n - 1;
A.column_indices[i] = n - 1;
A.values[i] = 1.00;
++i;

// set stopping criteria:
//  iteration_limit    = 100
//  relative_tolerance = 1e-3
    cusp::verbose_monitor<ValueType> monitor(b, 100, 1e-3);

// set preconditioner (identity)
cusp::identity_operator<ValueType, MemorySpace> M(A.num_rows, A.num_rows);

// solve the linear system A x = b
cusp::krylov::bicgstab(A, x, b, monitor, M);

cusp::print(x);

The result using Octave should be something similar to:

   0.00000
   0.32441
   0.60970
   0.82144
   0.93411
   0.93411
   0.82144
   0.60970
   0.32441
   0.00000

But is also with negative numbers, so WRONG.

Answer 1

For COO, you have to set three array elements for each entry: the row and column indices as well as the value. You can create a matrix like the one you describe using code like this for COO:

int n = 10, i = 0, r;
cusp::csr_matrix<int,float,cusp::host_memory> A(n, n, 3*n - 4);
// row 0
A.row_indices[i] = 0;
A.column_indices[i] = 0;
A.values[i] = 1.00;
++i;
// rows 1 through n - 2
for (r = 1; r != n - 1; ++r) {
  A.row_indices[i] = r;
  A.column_indices[i] = r - 1;
  A.values[i] = -0.45;
  ++i;
  A.row_indices[i] = r;
  A.column_indices[i] = r;
  A.values[i] = 0.10;
  ++i;
  A.row_indices[i] = r;
  A.column_indices[i] = r + 1;
  A.values[i] = -0.45;
  ++i;
}
// row n - 1
A.row_indices[i] = n - 1;
A.column_indices[i] = n - 1;
A.values[i] = 1.00;
++i;

For CSR you have to specify a column and a value for every entry, and also the index of the first entry for every row including a one-past-the-end index for the one-past-the-end row. A similar piece of code for CSR:

int n = 10, i = 0, r = 0;
cusp::csr_matrix<int,float,cusp::host_memory> A(n, n, 3*n - 4);
// row 0
A.row_offsets[r] = i;
A.column_indices[i] = 0;
A.values[i] = 1.00;
++i;
// rows 1 through n - 2
for (++r; r != n - 1; ++r) {
  A.row_offsets[r] = i;
  A.column_indices[i] = r - 1;
  A.values[i] = -0.45;
  ++i;
  A.column_indices[i] = r;
  A.values[i] = 0.10;
  ++i;
  A.column_indices[i] = r + 1;
  A.values[i] = -0.45;
  ++i;
}
// row n - 1
A.row_offsets[r] = i;
A.column_indices[i] = r;
A.values[i] = 1.00;
++i;
++r;
A.row_offsets[r] = i;

To “convert” the matrix from some other format, you have to let us know in what form your original data is stored. Conversion from a cusp::array2d should work by simply passing that array to the constructor. In general, creating the matrix in sparse format in the first place like the code above does will provide better scalability.

Also note that your example matrix is arranged in diagonal bands, so cusp::dia_matrix would be better suited, both in terms of easy encoding and in terms of better performance. To create such a tridiagonal matrix, you can use the following code:

int n = 10, r = 0;
cusp::dia_matrix<int,float,cusp::host_memory> A(n, n, 3*n - 4, 3);
A.diagonal_offsets[0] = -1;
A.diagonal_offsets[1] = 0;
A.diagonal_offsets[2] = 1;
// row 0
A.values(r,0) = A.values(r,2) = 0.00;
A.values(r,1) = 1.00;
// rows 1 through n - 2
for (++r; r != n - 1; ++r) {
  A.values(r,0) = A.values(r,2) = -0.45;
  A.values(r,1) = 0.10;
}
// row n - 1
A.values(r,0) = A.values(r,2) = 0.00;
A.values(r,1) = 1.00;

About this linear equation you try to solve: could it be that octave is operating on a different matrix than the one you pasted into your question? Because with sage I get negative numbers in the result as well:

n = 10
d = dict()
d[(0,0)] = d[(n-1, n-1)] = 1
for r in range(1, n-1):
    d[(r, r-1)] = d[(r, r+1)] = -45/100
    d[(r,r)] = 1/10
A = matrix(RDF, n, n, d)
b = vector(RDF, [
   0.00000,
   0.34202,
   0.64279,
   0.86603,
   0.98481,
   0.98481,
   0.86603,
   0.64279,
   0.34202,
   0.00000,
   ])
for i in A.solve_right(b):
    print('{:+.5f}'.format(float(i)))

gives the following vector x:

+0.00000
-0.45865
-0.86197
-1.16132
-1.32062
-1.32062
-1.16132
-0.86197
-0.45865
+0.00000