jabble
Class Multigrid

java.lang.Object
  jabble.Evolver
      jabble.Multigrid

Direct Known Subclasses:

FAS, FullMultigrid

public abstract class Multigrid
extends Evolver

Base class for Multigrid algorithms.

Implementing a Multigrid Evolver

To write an Multigrid Evolver, use one of the subclasses, like FullMultigrid (for linear operators) and FAS (for non-linear operators). Here are some suggestions that are always valid:

• Any Multigrid method implemented here will need at least an Evolver implemented with relaxation methods (such as Jacobi, Gauss-Seidel, ...). First implement such evolver and test it separately: if it doesn't (slowly) solve to solution, don't even start with Multigrid as it will only make the problem worse to debug
• Use FullMultigrid or FAS depending whether your operator is linear or not. We suggest you first test the V-Cycle evolver, which you can get with the getVCycleEvolver() of this class and then pass it to the ProblemSolver. You should test it by running for 5 to 10 iterations, and test that the error goes down logarithmically (until it reaches a minimum and stops)
• Now you are ready to use the actual Multigrid. You should only make one iteration: a second one would essentially start from scratch and give you the same result. To improve precision, you can play with the parameters of the V-Cycle and/or increase the number of V-Cycle iterations

The FullMultigrid algorithm

This class implement the FullMultigrid algorithm, which is described as follows.

Given Lu=f, where L is an elliptic differential operator, u the unknown field and f a given field, the Full Multigrid algorithm is defined as:

FMG(h, N, f ^h, b^h, v₁, v₂, n):

1. If N == 2, solve L^h u^h = f ^h and return u^h.
2. f ^2h = I^2h_h f ^h;
   restrict f ^h.
3. b^2h = I^*2h_h b^h;
   restrict boundary conditions.
4. u^2h = FMG(2h, N/2, f ^2h, b^2h, v₁, v₂, n);
   recursive call.
5. u^h = I ^h_2h u^2h;
   interpolate initial approximation, excluding boundary conditions.
6. Repeat n times: u^h = VCycle(u^h, h, N, f ^h, v₁, v₂);
   apply n V-Cycles.
7. Return u^h.

where:

• N is the number of points along one direction of the grid
• f ^h is the field quantized with step h, and f ^2h is the field quantized with step 2h (the coarser field, the field at the next level of multigrid)
• b^h is the boundary condition
• u^h is the solution field
• v₁ and v₂ are the parameters for the V-Cycle
• n is the number of times to repeat the V-Cycle
• I^2h_h is the restriction operator, that transform a fine field (with step h) to a coarse field (with step 2h). The restriction operator for f and b is in different in general.
• I ^h_2h is the prolongation operator.

In the Jabble framework, this class will take care of this algorithm and rely on the subclass to implement the V-Cycle. Therefore, usually you'll want to use one of the classes that inherit from this. The parameters of the algorithm can be found as bean properties:

• v₁ and v₂ correspond to the bean properties nIterationsPreRestriction and nIterationsPostProlongation. The subclasses that implement the V-Cycle are bound to honor them. Defaults are 2 and 1 respecively.
• n corresponds to the bean property nVCycleIterations. The default is 1.
• The exact solution (step 1) is actually delegated to the VCycle class. For step one the Multigrid will simply call the V-Cycle, which will call the exact Evolver.

Implementing the V-Cycle

To implement the V-Cycle, one needs to implement the vCycleResitrict and vCycleProlong methods. In those function one would decide how to transfer the fields from one level to the other during a V-Cycle. The rest is already in place. There are few things one is expected to honor:

• The names of the fields are stored in the f and u member variable
• The restrict and prolong operators to be used are stored in the vCycleRestrictOperator and vCycleProlongOperator
• All the parameters for the V-Cycle available as bean properties should be honored
• The relaxation and exact solution evolvers are also available as bean properties and should be honored

We suggest one looks at the source of the subclasses already bundled with Jabble as examples and guidance.

Reference:

• Irad Yavneh, Why Multigrid Methods are so efficient, Computing in Science & Engineering, Nov/Dec 2006
• Numerical Recipies in C, 19.6

Nested Class Summary

class

Multigrid.VCycle

Field Summary

protected java.lang.String	f
protected java.lang.String	u
protected MultigridOperation	vCycleProlongOperator
protected MultigridOperation	vCycleRestrictOperator

Fields inherited from class jabble.Evolver

constantsMap, dDirs, fieldArrayMap, fieldMap, grid, stopTrigger

Constructor Summary

Multigrid(Evolver evolver, java.lang.String u, java.lang.String f)
Creates a new MultiGrid evolver on top of the given evolver.

Method Summary

protected void	calculateNewFields() Implements the multi grid method.
void	evolve(java.util.List<Slice> slices) Evolves the data in the list of slices of one time step.
int	evolve(java.util.List<Slice> slices, int maxIterations, Trigger stopTrigger) Evolves the slices using multi grid methods and the evolver given through the constructor.
Evolver	getExactSolutionEvolver()
int	getNIterationsExact()
int	getNIterationsPostPrologation()
int	getNIterationsPreRestriction()
int	getNPreviousSlicesNeeded() Returns the number of slices needed for the previous time steps.
int	getNVCycleIterations()
Evolver	getRelaxationEvolver()
Evolver	getVCycleEvolver()
protected void	prolong(java.util.List<Slice> coarseSlices, java.util.List<Slice> fineSlices)
protected void	restrict(java.util.List<Slice> coarseSlices, java.util.List<Slice> fineSlices)
void	setNIterationsExact(int nIterationsExact)
void	setNIterationsPostPrologation(int nIterationsPostPrologation)
void	setNIterationsPreRestriction(int nIterationsPreRestriction)
void	setNVCycleIterations(int nVCycleIterations)
protected void	setupRestrictSlices(java.util.List<Slice> fineSlices)
java.lang.String	toString() The String representation of the MultiGrid evolver, which include the toString() of the wrapped evolver.
protected abstract void	vCycleProlong(java.util.List<Slice> coarseSlices, java.util.List<Slice> fineSlices)
protected abstract void	vCycleRestrict(java.util.List<Slice> coarseSlices, java.util.List<Slice> fineSlices)

Methods inherited from class jabble.Evolver

evolve, initializeFieldArray, initializeFieldArray, skipBoundaryPoint

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

u

protected java.lang.String u

f

protected java.lang.String f

vCycleRestrictOperator

protected MultigridOperation vCycleRestrictOperator

vCycleProlongOperator

protected MultigridOperation vCycleProlongOperator

Constructor Detail

Multigrid

public Multigrid(Evolver evolver,
                 java.lang.String u,
                 java.lang.String f)

Creates a new MultiGrid evolver on top of the given evolver.

Parameters:

evolver - this evolver will be used by MultiGrid to actually solve the equations

Method Detail

getNPreviousSlicesNeeded

public int getNPreviousSlicesNeeded()

Description copied from class: Evolver

Returns the number of slices needed for the previous time steps. For example, if it returns 2 it means that 2 slices in the past are needed by this evolver (say because it needs to calculate a second derivative in time). The evolver will of course need one slice more, that will correspond to the slice that will be used for to store the value of the next iteration.

The value is calculated by looking at the fields declared within the evolver. So if a subclass will declare a previous2Phi, this method will return 2, provided no other older fields where declared.

Overrides:

getNPreviousSlicesNeeded in class Evolver

Returns:

the number of past slices needed

restrict

protected void restrict(java.util.List<Slice> coarseSlices,
                        java.util.List<Slice> fineSlices)

prolong

protected void prolong(java.util.List<Slice> coarseSlices,
                       java.util.List<Slice> fineSlices)

evolve

public void evolve(java.util.List<Slice> slices)

Description copied from class: Evolver

Evolves the data in the list of slices of one time step.

An EllipticSolver will work by continuing to refine the solution at each iteration over the Grid. At each iteration, the solver will determine what was the best improvement (that is F[n](P) - F[n-1](P)) and if it's less than the truncation error it will return. The solver will not go past the maxIterations limit.

The solver will return the solution by modifying the data contained in the Slice, or by removing and adding Fields accordingly.

Overrides:

evolve in class Evolver

Parameters:

slices - The slices containing the data to work on; first slice is the most recent in time of iterations performed by the solver.

evolve

public int evolve(java.util.List<Slice> slices,
                  int maxIterations,
                  Trigger stopTrigger)

Evolves the slices using multi grid methods and the evolver given through the constructor.

Overrides:

evolve in class Evolver

Parameters:

slices - the slices with the data to evolve

maxIterations - the maximum number of iterations (on any grid)

stopTrigger - stop condition for the evolver

Returns:

the number of iteration actually performed

calculateNewFields

protected void calculateNewFields()

Implements the multi grid method.

Specified by:

calculateNewFields in class Evolver

toString

public java.lang.String toString()

The String representation of the MultiGrid evolver, which include the toString() of the wrapped evolver.

Overrides:

toString in class java.lang.Object

Returns:

String representation of the evolver

getNIterationsExact

public int getNIterationsExact()

setNIterationsExact

public void setNIterationsExact(int nIterationsExact)

getNIterationsPostPrologation

public int getNIterationsPostPrologation()

setNIterationsPostPrologation

public void setNIterationsPostPrologation(int nIterationsPostPrologation)

getNIterationsPreRestriction

public int getNIterationsPreRestriction()

setNIterationsPreRestriction

public void setNIterationsPreRestriction(int nIterationsPreRestriction)

setNVCycleIterations

public void setNVCycleIterations(int nVCycleIterations)

getNVCycleIterations

public int getNVCycleIterations()

getRelaxationEvolver

public Evolver getRelaxationEvolver()

getExactSolutionEvolver

public Evolver getExactSolutionEvolver()

getVCycleEvolver

public Evolver getVCycleEvolver()

setupRestrictSlices

protected void setupRestrictSlices(java.util.List<Slice> fineSlices)

vCycleRestrict

protected abstract void vCycleRestrict(java.util.List<Slice> coarseSlices,
                                       java.util.List<Slice> fineSlices)

vCycleProlong

protected abstract void vCycleProlong(java.util.List<Slice> coarseSlices,
                                      java.util.List<Slice> fineSlices)