Re: Is there any method to improve the precision of AMG?


In article <30194394.1193369527467.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
tangtang <tangzhanghong98@xxxxxxxxx> writes:
Hello all,

I am a beginner of AMG. I have posted a message in

http://softwarecommunity.intel.com/isn/Community/en-US/forums/thread/30242425.aspx

My task is to solve very large sparse matrices by AMG or
AMG-preconditioned iterative methods.
Currently the matrix is generated from the FEM (unstructured mesh)
driven by Possion equations. By numerical tests I found that the
relative residual ||b-A*x||/||b|| could reach to an expected range
(for example, 1.e-10) when the number of unknowns is only about
100,000. However, when the number of unknowns reaches to more than
1,000,000, all AMG-preconditioned iterative methods failed to
converge to the expected value. But even such a large system, the
ILU(0)-preconditioned iterative methods can obtain such a precision for
thousands of iterations.

the precision obtainable under roundoff
for iterative methods depends on the contraction
constant of the method (??? is yours <1 independent on N ??? )
and the condition of the system.
as soon as the theoretical error reduction in the solution is compensated
for by the roundoff involved in one iteration, no improvement is any longer
obtainable.
(In many textbooks nonsense is written about this
and special fallacious
"tests" performed with special integer matrices and integer right hand sides
where the roundoff behaviour is quite special)


with increasing N (decreasing mesh h) the condition number of your matrix
grows like 1/h^2. the residual will stop to decrease if the solution comes
into the range of cond(A)*eps
and case of the preconditioner, this applies to the preconditioned matrix
10^(-10) seems a bit ambitious if eps=2.2*10^(-16)


My question is:
1. Is it possible for the AMG based solver to obtain such precision and is there any method to do so?

2. Except the tests I posted in my former message, I also did the following tests:

According to the theory of float point error,
fl(a*b)=a*b+eps*a*b
fl(a+b)=a+b+eps*(a+b)

where fl is the float point operator and eps is somewhat related to the machine precision.

I tried to do some process to the matrix:
1) scale the matrix's elements to a small value to decrease the float point error in the latter iteration;
2) solve the system
A'*x'=b'
where
A'=D^(-1/2)*A*D^(-1/2),
D is the diagonal elements of A,
x'=D^(1/2)*x,
b'=D^(-1/2)*b.

However, by the first method, the result has no improvement;
the result of second method is surprised to me:
at this time the iterative methods don't converge,
even for very small system.
first: obvious: if you scale the problem , at best by a power of two _nothing
changes_ , not even the roundoff errors.
second: unbelievable: (if you used the same preconditoner subsequently)
a positive symmetric matrix is optimally scaled by diagonal matrices
up to a factor sqrt(n) if its diagonal is the unit matrix (->van der Sluis)
your diagonal transform is well known and one standard preconditioner
which can be used blindly. but clearly, in case of the poisson problem
with uniform mesh it can have no effect, but should have also no bad effect


So could anyone analyze the methods I tested and give me some suggestion?


Thanks,
Zhanghong Tang
hth
peter
.

Relevant Pages

  • Re: iterative vs. direct methods for linear systems
    ... The popular opinion is that iterative methods will only be competitive ... The main problem is that without a good preconditioner, ... there is a comparison between a direct and iterative solver for some ...
    (sci.math.num-analysis)
  • Re: iterative vs. direct methods for linear systems
    ... The popular opinion is that iterative methods will only be competitive ... This statement should be opposite. ... The main problem is that without a good preconditioner, ... there is a comparison between a direct and iterative solver for some ...
    (sci.math.num-analysis)
  • Re: iterative vs. direct methods for linear systems
    ... Iterative methods are sensitive to the spectrum ... it is hard to say in advance what a preconditioner to use. ... course, provided one has a lot of memory, but memory nowadays is chip. ... On the other hand, there is also multigrid. ...
    (sci.math.num-analysis)