[Haskell-cafe] Re: Sparse vector operations
relapse.dev at gmx.com
Fri Feb 27 15:16:17 EST 2009
Neal Alexander wrote:
> 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
> 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
Forgot to link the code:
More information about the Haskell-Cafe