Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Block Compressed Row Storage

  1. Apr 1, 2010 #1
    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.
     
  2. jcsd
  3. Apr 1, 2010 #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.
     
  4. Apr 7, 2010 #3
    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: May 4, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook