how to represent Sparse Matrices
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&amp;A\end{bmatrix}$ or $\begin{bmatrix}A\\B&amp;A\\&amp;B&amp;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.