  Runtime characteristics of sparse matrix computations and related processes
may be often improved by reducing memory footprints of involved matrices. Such
a reduction can be usually achieved when matrices are processed in a block-wise
manner. The presented study analysed memory footprints of 563 representative
benchmark sparse matrices with respect to their partitioning into
uniformly-sized blocks. Different block sizes and different ways of storing
blocks in memory were considered and statistically evaluated. Memory footprints
of partitioned matrices were additionally compared with lower bounds and with
the CSR storage format. The average measured memory savings against CSR in case
of single and double precision were 42.3 and 28.7 percents, the corresponding
worst-case savings 25.5 and 17.1 percents. Moreover, memory footprints of
partitioned matrices were in average 5 times closer to their lower bounds than
CSR. Based on the obtained results, generic suggestions for efficient
partitioning and storage of sparse matrices in a computer memory are provided.
