I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.
Could you please suggest me some other way to store/represent sparse matrices?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Could you be more specific about what problem you are trying to solve, and why Compressed Column Storage isn't sufficient? Otherwise: en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix $\endgroup$– Wandering LogicMay 14, 2013 at 17:28
-
$\begingroup$ This question isn't a good fit for this site. Instead, you should narrow down the question to make specific about what your requirements or evaluation criteria are, and why you are looking for something different. This site isn't a good place to ask for a list of all known ways of storing sparse matrices. However, a question that says "I am looking for a sparse matrix representation with properties P, Q, and R; compressed column storage provides P but not Q or R" would be a much better fit. $\endgroup$– D.W. ♦Mar 14, 2014 at 15:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As already indicated in the comments, the wikipedia article about Sparse matrix, Band matrix, and Skyline matrix cover the topic of the question quite well. Also, the computational science stackexchange site might be a better fit for such questions in general.
One might perhaps add that band matrices can't handle low rank modifications directly, so that one might want to use the Sherman–Morrison–Woodbury formula in this case. For the other representations, it is normally more beneficial to incorporate low rank modifications directly into the matrix via additional rows and columns, see below.
Some information about representations of Sparse matrices
A general Sparse matrix can be represented as a bipartite graph. This representation is useful for applying combinatorial algorithms like the Dulmage-Mendelsohn decomposition during preprocessing. In this case however, it is likely that you actually have a matrix pencil $A+\epsilon B$, which is important to know for the combinatorial algorithm, because this indicates which elements are expected to be small. A quick'n dirty fix is to apply the combinatorial algorithm to a related block Toeplitz matrix like $\begin{bmatrix}A\\B&A\end{bmatrix}$ or $\begin{bmatrix}A\\B&A\\&B&A\end{bmatrix}$ instead, but this is starting to get off-topic now.
If a "fixed" mapping between rows and columns is available, it makes sense to specify the symmetry type of the matrix as "general", "symmetric", "skew-symmetric" or, "Hermitian". If the symmetry type is more specialized than "general", then the matrix can be represented by a undirected graph, otherwise a directed graph can be used.
Note that these representations also apply to block-matrices (i.e. both the row indices and the column indices are partitioned into subsets), and encoding some a-priory information into such a block-structure can be a good idea both for speed and robustness.
I could also explain here how low rank modifications fit into such a general framework, but this section is already quite long. Often one can incorporate low rank modifications by just adding the corresponding row and column vectors as additional rows and columns with a small identity matrix between them. The advantage here is that the sparsity pattern of the original matrix is preserved.
