Solving linear systems with vectorz

[AntoineBrunet]

I am trying to solve a sparse linear system with Vectorz, but it seems to lack some basic algorithms to do it efficiently.

I want to solve Ku=F, where K is a sparse matrix and F a dense vector.
The classic way to solve this system is to get a decomposition of K, let's say K=LU, and then solve the easy triangular problems Ly=F and Uu=y.

I am not sure the implemented factorizations in Vectorz are optimized for sparse matrix (it seems the implementations are coming from a dense matrix manipulation library), but most importantly Vectorz seems to lack forward and backward substitution algorithms to solve triangular problems.

[mikera]

Hi Antoine,

This functionality is still work in progress - we are working on at least three different areas to get this working in a general way:

• Improving sparse vector / matrix capabilities. Vectorz was originally a mostly dense library, but the sparse capabilities are being added over time.
• Porting linear algebra code (mostly dense code from EJML, since it is fast and license-compatible)
• Creating a set of decomposition / algorithm code (in /mikera/matrixx/algo and various sub-packages

I can certainly see the value of generic sparse forward and backward substitution algorithms. Let me take a quick look and see how easy these are to put in, it's probably a very quick job....

Contributions welcome of course! The development if Vectorz is largely driven by what people want to use and/or feel motivated to contribute. Happy to accept PRs in this area.

[AntoineBrunet]

Thank you for your quick answer. I would be glad to help test these functions, comparing the results with la4j, which already has an implementation for this.

I can also debug or implement new methods if vectorz turns out to be efficient enough for my needs.

[mikera]

Vectorz should be plenty efficient - the internal data representations are about as efficient as you can get.

We certainly need some additional implementation and fine tuning on some of the linear algebra algorithms, but the after that we should be one of the fastest pure JVM libraries (if we aren't, I'm happy to consider that a defect to be fixed....)

[mikera]

@prasant94 - can you take a look at this? Is there an easy way to give an example of how to solve this kind of thing using your GSoC work?

[mikera]

@AntoineBrunet are you still looking at this? We have greatly improved sparse matrix support in the latest release. We don't yet have a sparse solver, but I still still think this would be a valuable addition.

[AntoineBrunet]

I will check it out as soon as I find the time to do it. I am interested in the banded sparse matrix implementation. My current solver is a simple conjugate gradient solver, which uses only matrix-vectors multiplication, so it should be easy enough to get it working.