[Haskell-cafe] Re: Sparse vector operations

[Neal Alexander]

Grzegorz Chrupala wrote:
> Hi all,
> In a couple of my projects I have needed to perform operations on (very)
> sparse vectors.
> I came up with the attached simple module which defines a typeclass and
> implements instances for
> simple and nested (Int)Maps.
> Is this the right way to go about it? Am I reinventing some wheels?
> Comments welcome.
> Best,
> --
> 
> Grzegorz
> 
> http://www.nabble.com/file/p22247686/SparseVector.hs SparseVector.hs 

I've been working on a matrix/vector library over the last month.

The matrices are implemented as QuadTrees, using block decomposition 
techniques for various algorithms. Vectors were kind of an afterthought, 
but they are implemented as binary trees - the thought being that they 
would decompose symmetrically with matrices.

Sparsity comes free with this approach (more or less), and is already 
implemented. Divide and conquer based parallelism should fit nicely into 
the mix too, but i haven't got to that point.

 From what I've tested so far, the performance is about the same as 
hmatrix and the various other matrix libraries on hackage. I've been 
trying to implement stream fusion for it over the last couple of days, 
but haven't been able to get it working right - maybe Dons can offer 
some advice.

For testing purposes, the uvector fusion based flat-matrix addition is 
twice as fast:

add a b = mapU (uncurryU (+)) $ zipU a b


With the tree based code, profiling shows matrix (*) and (+) perform a 
decent amount of memory allocation, so fusion should provide a big win i 
think.