[Haskell-cafe] Re: Sparse vector operations

Neal Alexander 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.
>> 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.

Forgot to link the code:

http://community.haskell.org/~hexpuem/bdMatrix/



More information about the Haskell-Cafe mailing list