# Most memory-efficient way to store a list of numbers

My problem deals with a large $n \times m$ matrix from which I extract and store several square $k \times k$ submatrices. The original matrix may be very large, and I may need to store many thousands of different $k \times k$ submatrices.

All I need to store is two list of integers, the indices for both rows and columns. For example, it could be a $4 \times 4$ matrix with rows $1, 10, 22, 44$ and columns $10, 90, 110, 111$. If I store all numbers then if I store $10000$ matrices I need to keep $20000k$ numbers in memory, and if possible I would like to avoid that.

Any ideas on how I can reduce the storage requirement for a list of indices, or two lists of indices?

Thank you very much.

• I don't think you can do much better than just storing the rows and cols for arbitrary sub matrices. If you think there is some pattern though, look here for some ideas. May 4, 2014 at 2:21
• Do you really need to store the sub-matrices? If they are read-only, and your original $n \times m$ matrix is dense, you can use a technique used in image processing - store a pointer to the the top-left corner of your sub-matrix and the width of the original matrix. Google "stride" for more details. May 4, 2014 at 7:32
• Dear Goldric, thanks for the ideas. Alex, the problem with this approach is that the list of rows and columns are not continuous, like in the example I gave above, so it is not enough to store the pointer to the first row/column. May 4, 2014 at 10:15