Reference for lowest order complexity of sparse symmetric matrix premultiplying full vector

Question

In a paper I'm writing I make use of an n x n matrix multiplying a dense vector of dimension n. In its natural form, this matrix has O(n^2) space complexity and the multiplication takes time O(n^2).

However, it is known that the matrix is symmetric, and has zero values along its diagonal. The matrix is also highly sparse: the majority of non-diagonal entries are zero.

Could anyone link me to an algorithm/paper/data structure which uses a sparse symmetric matrix representation to approach O(nlogn) or maybe even O(n), in cases of high sparsity?

To be perfectly clear: the matrix is sparse and the vector is dense, correct? — Iterator

Darren Engwirda Darren Engwirda · Accepted Answer · 2011-09-24T10:11:07

I would have a look at the csparse library by Tim Davis. There's also a corresponding book that describes a whole range of sparse matrix algorithms.

In the sparse case the A*x operation can be made to run in O(|A|) complexity - i.e. linear in the number of non-zero elements in the matrix.

Reference for lowest order complexity of sparse symmetric matrix premultiplying full vector

2 Answers