Boost logo

Ublas :

From: Karl Meerbergen (karl.meerbergen_at_[hidden])
Date: 2008-03-06 12:17:27


It is not my intention to give a course on numerical linear algebra. You
cannot make strong statements about which method is best, since their
performance is problem dependent.

For many problems, for sure 2D but even 3D discretizations of
differential equations leading to positive definite or unsymmetric
problems, direct methods perform very well for up to 100,000 unknowns or
even larger. If I recall well from a previous e-mail there would only be
10 non-zeros per row. This is very few. So, I do not see a problem for
using a direct method. It is always good to try direct methods first,
since you do not know whether an iterative method will work, even if the
matrix is positive definite.

O(n) complexity is usually only attained by multigrid methods. So, CG is
useless in this respect, even with IC preconditioning.



Also your statement on ILU is strange
Jens Seidel wrote:
> 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.
> Jens
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]