Sparse vector operations
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 -- View this message in context: http://www.nabble.com/Sparse-vector-operations-tp22247686p22247686.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
You might be duplicating the functionality of an existing library. There are existing libraries for vectors (though not sure if blas supports sparse vectors well?). http://hackage.haskell.org/cgi-bin/hackage-scripts/package/blas http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmatrix -- Don grzegorz.chrupala:
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 -- View this message in context: http://www.nabble.com/Sparse-vector-operations-tp22247686p22247686.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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.
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/
participants (3)
-
Don Stewart -
Grzegorz Chrupala -
Neal Alexander