[Haskell-cafe] Re: Sparse vector operations
relapse.dev at gmx.com
Fri Feb 27 14:55:51 EST 2009
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.
> 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
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
More information about the Haskell-Cafe