Block Compressed Row Storage

  • #1

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
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.
 
  • #3
23
0
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" [Broken], 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" [Broken] might be helpful
 
Last edited by a moderator:

Related Threads on Block Compressed Row Storage

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
10
Views
780
  • Last Post
Replies
12
Views
882
  • Last Post
Replies
2
Views
2K
Replies
7
Views
865
Replies
2
Views
2K
Replies
9
Views
4K
Replies
1
Views
3K
Top