PyAMG on nonlinear problems

[David Huard]

Hi all,

I'm a AMG newbie trying to solve a non linear problem using AMG as a
preconditioner. For the moment, a simple SOR preconditioner seems to
fare better than the AMG preconditioner, which initially surprised me.
I may be doing something wrong so I thought I'd ask the list for some
guidance and feedback.

The problem is the 2D driven cavity flow in velocity-vorticity
formulation. The ultimate goal is to apply the same solvers to sea ice
dynamics, but I thought I'd start out with a simpler problem with
similar characteristics (very local fronts).

I have defined a system of equations F(x) = 0, which I can split in a
linear and nonlinear part: F(x) = P * x + A(x)

I solve the system using JFNK: I solve iteratively J(x) dx = -F(x^k)
for dx using FGMRES with an SOR preconditioner based on P.

I replaced the SOR preconditioner by an AMG preconditioner (I tried
ruge-stuben, smoothed_aggregation_solver and the adaptive_sa_solver)
but none of them converges faster than SOR, so I'm thinking that they
are not really meant to be used in this context. What's the
recommended strategy to use ML preconditioning on nonlinear problems ?

Many thanks,

David Huard

P.S. I can post the code if someone is interested to look at it.

[Nathan Bell]

On Wed, Apr 29, 2009 at 10:03 PM, David Huard <david...@gmail.com> wrote:
>
> I solve the system using JFNK: I solve iteratively J(x) dx = -F(x^k)
> for dx using FGMRES with an SOR preconditioner based on P.
>
> I replaced the SOR preconditioner by an AMG preconditioner (I tried
> ruge-stuben, smoothed_aggregation_solver and the adaptive_sa_solver)
> but none of them converges faster than SOR, so I'm thinking that they
> are not really meant to be used in this context. What's the
> recommended strategy to use ML preconditioning on nonlinear problems ?

I don't have an answer for you right now, but I thought I'd share this
link for context:
http://www.cs.odu.edu/~keyes/papers/jfnk.pdf

--
Nathan Bell wnb...@gmail.com
http://graphics.cs.uiuc.edu/~wnbell/

[David Huard]

On Apr 29, 10:10 pm, Nathan Bell <wnb...@gmail.com> wrote:

> On Wed, Apr 29, 2009 at 10:03 PM, David Huard <david.hu...@gmail.com> wrote:
>
> > I solve the system using JFNK: I solve iteratively J(x) dx = -F(x^k)
> > for dx using FGMRES with an SOR preconditioner based on P.
>
> > I replaced the SOR preconditioner by an AMG preconditioner (I tried
> > ruge-stuben, smoothed_aggregation_solver and the adaptive_sa_solver)
> > but none of them converges faster than SOR, so I'm thinking that they
> > are not really meant to be used in this context. What's the
> > recommended strategy to use ML preconditioning on nonlinear problems ?
>
> I don't have an answer for you right now, but I thought I'd share this
> link for context:http://www.cs.odu.edu/~keyes/papers/jfnk.pdf
>

Indeed, that's a very good introductory paper. I'm new to the solver
business and I don't know what it common knowledge and what's not.
Sorry if I left out a lot of background. What papers would you
recommend for an overview of the different algorithms to compute the
strength of connections ?


> --
> Nathan Bell wnb...@gmail.comhttp://graphics.cs.uiuc.edu/~wnbell/

[Bartek Sawicki]

How many unknowns do you have?
My engineering experience is that for problems smaller than 500k,
Krylov solvers with classic preconditioners like
ICC, SOR, or Jacobi are usually faster that multigrid preconditioners.
On the opposite site are small problems (< 10k unknowns) where direct
solvers are usually unbeatable.

cheers,
BArtosz

[Jacob Schroder]

Strength-of-connection features prominently in PyAMG. You have 4
choices when setting the "strength" parameter during the solver
generation phase.

The two classic strength measures are
(1) strength="classical", which refers to the Ruge-Stuben style measure.

The AMG chapter covers this in "A Multigrid Tutorial" by
Briggs, Henson and McCormick

And this paper, pages 99-100, covers this,
J. W. RUGE AND K. STÜBEN, Algebraic multigrid, in Multigrid Methods,
Vol. 3 of Frontiers Appl. Math., SIAM, Philadelphia, PA, 1987,
pp. 73–130.

(2) strength="symmetric", which refers to the SA style measure.

This paper covers SA in general and this strength measure.
Vanek, P. and Mandel, J. and Brezina, M.,
"Algebraic Multigrid by Smoothed Aggregation for
Second and Fourth Order Elliptic Problems",
Computing, vol. 56, no. 3, pp. 179--196, 1996.
http://citeseer.ist.psu.edu/vanek96algebraic.html

Then there are two newer measures in PyAMG,
(3) strength = "ode", which is a new measure and I would argue is the
most robust.

There isn't a publication for it yet, but you can look at this
presentation,
http://www.cse.illinois.edu/~jschrod3/docs/Copper2008.pdf

(4) strength = "energy_based" which is also a new measure, but the
current implementation
is really slow. It's currently only good for
toy problems, < 2,000 dofs.

Here's a reference,
Brannick, Brezina, MacLachlan, Manteuffel, McCormick.
"An Energy-Based AMG Coarsening Strategy",
Numerical Linear Algebra with Applications,
vol. 13, pp. 133-148, 2006.

If you think that strength-of-connection is really hurting your
performance, then I would suggest trying the ode measure with k=2 or
k=4. You could also try toggling the drop tolerances for the classic
strength measures.

Hope this helps,

Jacob

[Jacob Schroder]

One other thing, if your matrix is an M-matrix, then the classic
measures should do fine. If you don't have an M-matrix, then the
theory behind the classic measures breaks down. In that case
strength='ode' is probably a safer, but more expensive, option.

Jacob

[David Huard]

On Apr 30, 12:20 pm, Bartek Sawicki <sawic...@gmail.com> wrote:
> How many unknowns do you have?

In the target problem, I'll have about 300k unknowns.

> My engineering experience is that for problems smaller than 500k,
> Krylov solvers with classic preconditioners like
> ICC, SOR, or Jacobi are usually faster that multigrid preconditioners.
> On the opposite site are small problems (< 10k unknowns) where direct
> solvers are usually unbeatable.

That's good to know. We have a model that can be run at different
resolutions, and while JFNK with a line SOR works very well for the
coarse resolution versions, it converges rather slowly on the finest
resolution grid. What we see is that the solver has a hard time
finding the correct location for the thin shear lines that criss-cross
the ice. I thought that maybe a MG solver would help find the global
balance more quickly and that in turn would help solve the fine scale
features.


Thanks,

David
>
> cheers,
> BArtosz

[David Huard]

The thing is, I don't know what's hurting the performance. There are a
lot of possibilities and I'm still groping to find what is significant
and what's a distraction. I'll try your suggestion and let you know
how it goes.

> Hope this helps,
>

It really does, thanks. If I manage to get it to work successfully,
I'm planning to clean the code and submit this as an example for
pyamg.

> Jacob