C/C++ How can I implement BCRS 2x2 format for sparse matrices in C++?

[dinaharchery]

Hello All,

I am trying to learn matrix compression algorithms for sparse matrices. I understand the Compressed Row Storage (CRS) format but I am having difficulty with the Block Compressed Row Storage (BCRS) format - where the size of the sub-block(s) are 2x2.

Can anyone please point me to an algorithm/code for implementing BCRS 2x2? I am looking to take a standard 2-D floating-point matrix in C++ and converting it to the BCRS 2x2 format as well as Matrix-Vector multiplication using the BCRS 2x2 format.

I know there are a lot of programs for this out there but I really would like know the algorithm myself, so that I can learn this rather than re-implement someone elses code - although at this point I will take what I can get.

Thanks.

 

[dinaharchery]

Well, I seemed to have figured-out the issue of programming a Matrix-Vector multiplication on sparse matrices using both Compressed Row Storage and Block Compressed Row Storage formats. I have a bigger question now though.

Regardless of the size of my sparse matrix (randomly generated values), Block Compressed Row Storage (with 2x2 sub-blocks) seems to perform worse than the standard Compressed Row Storage format. Is this something that I should expect or is something else going on? If it is to be expected, does this increase in computational time occur because of the potential for increased floating-point operations? If not, why?

Thanks again.

 

[MichielM]

How do you define 'performance'. If you mean the computational time, then yes BCRS is worse then CRS because it is 'harder' to find a specific matrix element.

Remember: sparse matrix storage modes are SPACE-savers, not TIME-savers

Have you tried http://www.nr.com/oldverswitcher.html" , you can freely access the obsolete versions and read about the algorithm to code specific storage formats.

Also http://www.cs.utk.edu/~dongarra/etemplates/node372.html" might be helpful