search

vkostyukov / la4j

Linear Algebra for Java
http://la4j.org
Apache License 2.0
373 stars 107 forks source link

RPA - Randomized Parallel Algorithm for LS solving with O(n^2) runtime #19

Open vkostyukov opened 11 years ago

vkostyukov commented 11 years ago

Here is draft: http://arxiv.org/pdf/1209.3995.pdf

This is an inovative algorithgm designed in 2012 by Joerg Fliege. It would be awesome if la4j provided a support for this approach.

BTW, Gaussian Ellimination (that uses by default in la4j) works for O(n^3)

aash commented 11 years ago

Me and jakrin are going to work it out.

vkostyukov commented 11 years ago

This is awesome news! Hope you luck, guys! I'm guessing this will be the first Java implementation arround.

yuronew commented 11 years ago

It's really cool. Are you guys @aash nd @jakrin still working on it?

aash commented 11 years ago

Yep, we stumbled at correctness problem in parallel code.

aash commented 11 years ago

After thorough review of the paper I can conclude that latter method is a kind of iterative solvers, which possible has better convergence than Jacobi one. But I could not achieve satisfactory results in my C prototype. I will put it in my branch for public review. One head is nice, but two is much better!

Other point is to implement various kinds of iterative solvers, and make parallel those which already exist. Hey, whats the point not to use java.util.concurrent in this library?

vkostyukov commented 11 years ago

Hi Alexey @aash,

Thank you for the update! You can push the code in some GitHub repo or Gist so we can review it together. Regarding j.u.c.*. The la4j is a single-threaded library by design. But now, I'm in the middle of thinking how to bring concurrency into the la4j. This is a huge step for such project. And we have to to it iterativelly. This first step is to make a sequential engine availvable for la4j. The next step - make it parallel. I've described this idea in the issue #56 and this blog post.

Thus everything is going according to the plan. The la4j 0.6.0 will contain a parallel engine based on F-J Framework.