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. – Godric Seer May 4 '14 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. – Alex Shtof May 4 '14 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. – Chicoscience May 4 '14 at 10:15