1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Godric Seer
    Commented May 4, 2014 at 2:21
  • $\begingroup$ 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. $\endgroup$
    – Alex Shtoff
    Commented May 4, 2014 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – Chicoscience
    Commented May 4, 2014 at 10:15

1 Answer 1

Reset to default
1
$\begingroup$

1) you could use a smaller data type for the index (e.g. a 2-byte integer)

2) if you know your sub-matrices have the same relative indices, e.g. rows are always something like (i, i+a, i+b, i+c), you only have to store the index to element (1,1)

3) similarly, if your sub-matrices are limited in relative index, e.g. your rows are (a, b, c, d) where d-a < 256, you could store the index to element (1,1), then use bytes for the offsets from that element

Improve this answer
$\endgroup$
1
  • $\begingroup$ I like your ideas 1 and 3. Idea 2 unfortunately cannot be applied since the rows and columns may be any combination, not necessarily relative related. $\endgroup$
    – Chicoscience
    Commented May 4, 2014 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.