Boost logo

Ublas :

From: Jens Seidel (jensseidel_at_[hidden])
Date: 2008-03-06 10:46:45

On Thu, Mar 06, 2008 at 04:24:49PM +0100, Karl Meerbergen wrote:
> Jens Seidel wrote:
> >On Thu, Mar 06, 2008 at 03:54:10PM +0100, Jonas wrote:
> >How much do n and m differ? If both are of the order 10^5 than it is
> >already too large for Cholesky or Gaussian elimination.
> This is, of course, only true for dense or highly dense matrices.
> Both Umfpack and MUMPS (for which bindings exist) such factorizations
> are feasible.

You could be right. Nevertheless I would not recommend to solve a system
of this size with Cholesky! Even a sparse matrix with n=10.000 and a
proper node renumbering via Cuthill-McKee algorithm to reduce the
bandwith will take a lot of time and consumes a lot of memory
(because of the fill in).

Incomplete factorisations are probably useless if not used as
preconditioner for solvers as CG (which requirements are not fullfilled).
> There are also sparse QR factorizations which are excellent for
> overdetermined systems, but I have no experience with them and no idea
> about free software.

I'm sure you will also get a fill in and will require really a lot of
memory. Please note that in the ideal world one could expect a solver
to need only linear time in the number of unknowns. QR and Cholesky
have a much, much higher complexity.