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, Sep 27 '11 at 21:57

score 1 · Answer 1 · answered Sep 13 '11 at 05:45

1

Are you interested in parallel algorithms of this sort http://www.cs.cmu.edu/~scandal/cacm/node9.html

answered Sep 13 '11 at 05:45

grdvnl

636
6
9

score 1 · Accepted Answer · answered Sep 24 '11 at 10:11

1

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.

answered Sep 24 '11 at 10:11

Darren Engwirda

6,915
4
26
42

Thanks Darren, that's very pragmatic advice :) – KomodoDave Sep 30 '11 at 18:39

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

2 Answers2