# sparse matrix format with fast row and column access

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.

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.