Geek Answers Handbook

Finding a C / C ++ interface to efficiently compute a huge sparse matrix in Linux

I am looking for a C / C ++ interface to efficiently compute a huge sparse matrix in Linux. The matrix can be millions of times millions / thousand. I checked several existing libraries, but it seems that none of them satisfy all my requirements,

1, I need to create a sparse matrix by dynamically adding elements to it. (not for SparseLib ++)

2, I also need to create a sparse diagonal matrix so that I can scale the columns of another sparse matrix with different scalars. (no library was found for this, and maybe there is another way to scale the sparse matrix in columns)

3, It must support the operations of the matrix times the matrix / vector (many libraries support these basic operations)

4, It must support input multiplication or separation between two sparse matrices or vectors, for example. * or. / in MATLAB (no library was found for this, and I need this operation to cut out some records of one sparse matrix with another sparse matrix)

5, matrix inversion or linear solver. (Most libraries provide a solver for a linear system)

I originally used scipy in Python to implement my algorithm. Python consumes too much memory and it is slow, and so I would like to convert my program to C.

Thanks.

-1
source share
5 answers

I would recommend CSparse Tim Davis.

+2
source

I was very pleased with the use of Intel MKL .

+1
source

Alas, most sparse matrix libraries use a format that makes it very difficult to set elements dynamically (google for Compressed Sparse Row, which is the most common format).

As you said, most libraries provide you with all your requirements, except # 1. For # 2, this is usually easy once you understand the storage format.

Intel MKL provides a PARDISO solver that does not impose a format, it only requires that you can execute matrix / vector products: you call the solver in a loop, get the return code from it and do what it does (multiply by A, check the termination condition , preliminary preparation,...). This way, you can use any storage scheme you need. This is useful when you do not want to store the matrix, for example, or if you have a funky storage format.

Your requirements (especially # 1) are a great candidate for sparse quadrant matrices . However, I do not know any good implementation of this. If you manage to encode it / find an implementation, I would be grateful.

+1
source

Have you watched LinBox ? It supports several sparse matrix storage formats, some of which allow you to set records after creating a matrix:

// set m[i,j] to a m.refEntry(i, j) = a;

I'm not sure that your requirement 4. is met outside the box, but it can be easily encoded using the refEntry method.

+1
source

Try TAUCS or MUMPS .

I personally tried TAUCS for the project, solving resolved matrices of the order of a million x million in image processing, using this to give you an indication of the size that it can handle.

I agree with Alexander that these packages come with their own “format” for encoding a sparse matrix, but this is inevitable because you have to tell the solver where the nonzero elements are. But from the bright side they are not difficult to recognize. TAUCS, by the way, uses the compressed column storage format (CCS). By the way, what Alexandre refers to, perhaps it's a compressed string store (CRS). I think another popular format that explicitly encodes the value of an element with the (i, j) "location" of the element in the matrix, but that’s something like that.

See www.matrixprogramming.com for more information on these packages.

0
source

More articles:


All Articles