Re: [ublas] faster inplace_solve implementation (triangular.hpp)

Subject: Re: [ublas] faster inplace_solve implementation (triangular.hpp)
From: Jörn Ungermann (j.ungermann_at_[hidden])
Date: 2010-03-17 18:05:55

On Wed, 2010-03-17 at 21:48 +0100, Gunter Winkler wrote:
> Jörn Ungermann schrieb:
> > Hello all!
> >
> > Abstract:
> > One of my use-cases is the solving of equations-systems defined by
> > sparse triangular matrices.
> > I found the performance of the inplace_solve routines in triangular.hpp
> > lacking for compressed_matrix<row_major> matrices. Upon inspection I
> > found that row_major matrices are currently parsed column-wise.
> Impressive performance.
Thanks. But it is actually quite easy: Never access a compressed_matrix
with the wrong iterator. It starts to really hurt from a certain problem
size onwards.

> Did you already have a look at the
> (experimental) implementations in cholesky.hpp from my examples page:
> http://guwi17.de/ublas/examples/
Yes, I actually use it for small the exact solution of "small" problems.
Thanks! But for our production use-case, I wrote a dedicated
Cholesky-decomposition, which takes advantage of the special structure
of the original matrix and can therefore work in O(n) time. This
implementation directly writes the results row-by-row into a row_major
compressed matrix and keeps a data structure that manually tracks the
non-zero entries of the root columnwise to speed up the access. This
enables the Cholesky-decomposition of our 1.000.000^2 matrices in a
couple of seconds. The result of the decomposition is then used as a
preconditioner for a PCG scheme, which is similar to the one on your
website (Please not that the matrix being decompositioned for the
preconditioning is not the system matrix).

> Regarding the test cases: [...]
Thanks for the heads up, I'll see what I can do. We use boost::test
ourselves and link against the library, which is pretty fast, but
naturally requires the precompiled library being available.

Kind regards,
Joern

------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------
Forschungszentrum Juelich GmbH
52425 Juelich
Sitz der Gesellschaft: Juelich
Eingetragen im Handelsregister des Amtsgerichts Dueren Nr. HR B 3498
Vorsitzende des Aufsichtsrats: MinDir'in Baerbel Brumme-Bothe
Geschaeftsfuehrung: Prof. Dr. Achim Bachem (Vorsitzender),
Dr. Ulrich Krafft (stellv. Vorsitzender), Prof. Dr.-Ing. Harald Bolt,
Prof. Dr. Sebastian M. Schmidt
------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------