0
$\begingroup$

Is there an efficient storage format for general, non-symmetric sparse matrices for which one can find all non-zero entries in a given row or column in $O(d)$ time? ($d$ is the max number of non-zero entries in any row or column.)

If I store an $m \times n$ sparse matrix $A$ in the compressed row or ellpack formats, I can find all non-zero entries in a given row in $O(d)$ time, but finding all non-zero entries in a given column takes $O(m)$. Of course, I could store $A$ in compressed column format, in which case the column accesses would take $O(d)$ but the row accesses would take $O(n)$.

A blunt approach would be to store both formats, compressed row and column, for the same matrix, which of course entails double the memory. Can one do much better?

Best I can come up with: For square matrices, one can store it as a structurally symmetric matrix. If you want to find all entries in column j, you instead find all entries in row j and then remove the redundant ones.

$\endgroup$
1
$\begingroup$

You can store the matrix as usual, in row-compressed sparse format. Then for each column, you store which entries exist in the sparsity pattern. If you need the entries of a column, you can find out from this second data structures which entries exist, and you can then get the value from the row-wise (normal) data structure that stores the matrix.

This is essentially one integer per entry of the matrix for the column-wise storage (in addition to one integer per entry for the row-wise storage plus one floating point number for each entry). With 32-bit integers for the column or row entries, and 64-bit double precision for the numbers, this gives:

  • 12 bytes per entry for the regular row-wise data storage scheme
  • 16 bytes per entry if you also want to keep the column-wise information.

Accessing all entries in a column requires traversing a column in the column-wise data structure, which is ${\cal O}(d)$, and for each entry you find, you need to look it up in the row-wise format to get at the value, which will cost you ${\cal O}(\log d)$ for each entry. In total, that makes ${\cal O}(d \log d)$ to access all elements of a column.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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