Re: [boost] uBlas questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-06-30 15:01:12

From: "Toon Knapen" <toon.knapen_at_[hidden]>

> On Sunday 30 June 2002 12:06, David Abrahams wrote:
> >
> > I think I can shed some light on the next 2 questions. Carlos and I
used to
> > work together on simulation software. After much consideration, we
> > discovered that for some probelms, log(N) random-access to the elements
of
> > a sparse matrix row was much less-important than being able to control
the
> > order in which the elements appeared. Being able to choose a non-sorted
> > order allowed us to write the inner loop of our algorithm so that it
simply
> > marched through continguous addresses, writing data to consecutive
> > locations in memory. In fact, this loop never had to touch the sparse
> > matrix structure at all.
>
> Can you shed even more light on this. What storage format were you using
:
> Harwell-Boeing, compressed-sparse row, coordinate-format, ...

It was compressed-sparse row, but of course without the sorted indices.

> and what type of algorithm were you able to optimise due to the
'unsorted'
> storage.

Essentially there was a phase in the algorithm which had to fill up the
sparse storage with new numbers, and this was much faster if we could pick
the storage order according to our own criteria. The data was then used in
a matrix multiplication, but re-ordering the fill indices doesn't affect
that process at all if you're using scatter/gather, since scattering
associates distributes each datum to its appropriate place in the scatter
vector.

-Dave