edu.jhu.cs.cisst.algorithms.optimize.fmg
Class FMG

java.lang.Object
  java.util.Observable
      edu.jhu.cs.cisst.algorithms.optimize.fmg.FMG

public class FMG
extends java.util.Observable

A class that implements the Full Multigrid (FMG) algorithm for the solution of a linear elliptic partial differential equation (PDE) on a regular cubic grid in 3D.

The FMG algorithm solves a PDE by discretizing it on several grids of different coarseness corresponding to different levels. The grids at different levels are positioned in such a way that the corners of their boundaries are superimposed. This has the effect that every new grid level shares some grid elements with the next coarser grid and introduces new grid elements that lie exactly between the grid elements of the next coarser grid.

The FMG algorithm starts by solving the PDE on the coarsest grid and then decends to the finest grid by interpolating stepwise from a coarse grid to the next finer grid. At each grid level (except the coarsest) the FMG algorithm employs the Multigrid (MG) algorithm possibly several times to improve the solution on this level.

The MG algorithm improves an approximate solution of the PDE on a certain grid level by pre-smoothing the solution with a conventional relaxation algorithm, restricting the problem (in principle) to the next coarser grid level, obtaining an improved solution to this coarse grid problem by (recursively) calling the MG algorithm possibly several times at that level, interpolating the solution at the coarse grid to the fine grid thereby correcting the fine grid solution, and finally post-smoothing the solution.

There have been several modifications made to this solver to make it more flexible:
1) Grids can now have arbitrary dimensions instead of being a cubic volume of power 2.
2) The resolution levels can be arbitrary and not necessarily powers of 2.
3) The coarsest level at which the PDE is solved does not have to be 3x3x3, but the PDE must specify its own direct solver.
- Blake

Author:

Gerald Loeffler (Gerald.Loeffler@univie.ac.at)

Constructor Summary

FMG(PDE pde, Smoother smoother, Restrictor restrictor, Interpolator interpolator, Solver solver, ConstBoundaryGrid solutionPrototype, ConstBoundaryGrid correctionPrototype, SolverResolutionLevels resolutions)
construct an FMG object that will be able to solve a linear elliptic PDE using the FMG algorithm on a regular cubic grid in 3D.

Method Summary

protected NoBoundaryGrid	calcResidual(ConstBoundaryGrid u, ConstNoBoundaryGrid f) calculate the residual of an approximate solution to a PDE.
protected void	calcResidualProper(NoBoundaryGrid r, ConstBoundaryGrid u, ConstNoBoundaryGrid f, int myNum, int totalNum) implements the parallel part of calcResidual().
protected BoundaryGrid	mg(ConstBoundaryGrid u, ConstNoBoundaryGrid f, int coarsestLevel, int numPresmooth, int numPostsmooth, int cyclingStrategy) performs the Multigrid algorithm which is at the heart of the FMG algorithm.
ConstBoundaryGrid	solve(int numPresmooth, int numPostsmooth, int cyclingStrategy, int numMultiGrid) the body fo the FMG Algorithm that executes in its own thread.
void	solveParallel(int numPresmooth, int numPostsmooth, int cyclingStrategy, int numMultiGrid) starts the FMG Algorithm with the given parameters in a separate thread and returns immediately.
BoundaryGrid	waitForResult() blocks the current thread until the FMG algorithm which is executing in a different thread has finished and then returns the solution of the PDE.

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

Methods inherited from class java.lang.Object

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

Constructor Detail

FMG

public FMG(PDE pde,
           Smoother smoother,
           Restrictor restrictor,
           Interpolator interpolator,
           Solver solver,
           ConstBoundaryGrid solutionPrototype,
           ConstBoundaryGrid correctionPrototype,
           SolverResolutionLevels resolutions)

construct an FMG object that will be able to solve a linear elliptic PDE using the FMG algorithm on a regular cubic grid in 3D.

The FMG algorithm employs several sub-algorithms that must be specified as arguments to the constructor and can not be changed afterwards. Thus a specific FMG object will allways employ these sub-algorithms. However, the details of the FMG algorithm itself must be specified when calling the fmg() method and can thus be changed with every invocation of this method.

Parameters:

pde - an object representing the PDE to solve

smoother - an object encapsulating the smoothing algorithm to use

restrictor - an object encapsulating the restriction algorithm to use

interpolator - an object encapsulating the interpolation method to use

solver - an object encapsulating the algorithm to use for solving the PDE on the coarsest level

solutionPrototype - a prototype object from which the exact type of the desired solution will be deduced. By selecting a proper subclass of BoundaryGrid for this prototype object, the boundary conditions that the solution must satisfy are selected. The state of the prototype object is irrelevant because only its type is used.

correctionPrototype - the correction prototype

resolutions - the resolutions

Method Detail

solveParallel

public void solveParallel(int numPresmooth,
                          int numPostsmooth,
                          int cyclingStrategy,
                          int numMultiGrid)
                   throws FMGAlreadyExecutingException

starts the FMG Algorithm with the given parameters in a separate thread and returns immediately.

At any time there can be only one instance of the FMG algorithm executing. Hence if this method is called while the FMG algorithm is already running, an exception is thrown.

There are two independent ways of receiving the result of the FMG algorithm that this method produces. The first is to call waitForResult() which blocks the thread that is calling it until the result is available and then returns it. The second is by registering one or more java.util.Observer objects with this object (via addObserver()) which will be notified as soon as the result is available (their update() method will be called with the result of type BoundaryGrid as the second (the arg) argument).

Parameters:

numPresmooth - the number of pre-smoothing steps to perform ( > 0)

numPostsmooth - the number of post-smoothing steps to perform ( >= 0)

cyclingStrategy - the cycling strategy to use ( > 0). A value of 1 results in V-cycles, a value of 2 in W-cycles. This gives the number of times the MG algorithm recursively calls itself to solve the coarse grid problem.

numMultiGrid - the number of invocations of the MG algorithm per level of the FMG algorithm ( > 0)

Throws:

FMGAlreadyExecutingException - the FMG already executing exception

FMGAlreadyExecutingException - fmg() has already been called for this object and is still executing

See Also:

Observer

waitForResult

public BoundaryGrid waitForResult()
                           throws FMGNotExecutingException

blocks the current thread until the FMG algorithm which is executing in a different thread has finished and then returns the solution of the PDE.

If the FMG algorithm is not currently executing or has not just delivered a result an exception is thrown. In other words, call waitForResult() only after calling fmg().

This method can be called only once for every invocation of fmg().

Returns:

the solution of the PDE

Throws:

FMGNotExecutingException - the FMG not executing exception

FMGNotExecutingException - method fmg() has not been called before and hence the FMG algorithm is not executing or has not just delivered a result

solve

public ConstBoundaryGrid solve(int numPresmooth,
                               int numPostsmooth,
                               int cyclingStrategy,
                               int numMultiGrid)

the body fo the FMG Algorithm that executes in its own thread.

This method is called from FMGThread.run() which in turn is indirectly called from FMG.fmg().

The parameters of this method are identical to the parameters of method fmg(). The result of this method (which is the result of the FMG algorithm and hence a grid of type BoundaryGrid) is returned via the notification mechanism to all observers that have been registered with this object.

See Also:

solveParallel(int, int, int, int)

mg

protected BoundaryGrid mg(ConstBoundaryGrid u,
                          ConstNoBoundaryGrid f,
                          int coarsestLevel,
                          int numPresmooth,
                          int numPostsmooth,
                          int cyclingStrategy)

performs the Multigrid algorithm which is at the heart of the FMG algorithm.

Given an approximate solution of the PDE on a grid the Multigrid algorithm finds a better solution on that grid by pre-smoothing, going to the next coarser grid and approximately solving there, going back to the original grid, and finally post-smoothing.

Parameters:

u - the approximate solution an a grid at a certain level

f - the right hand side of the PDE at a grid at the same level as u

coarsestLevel - the coarsest level to which the Multigrid algorithm should recursively go (0 < coarsestLevel <= level of u and f)

numPresmooth - the number of pre-smoothing steps to perform ( > 0)

numPostsmooth - the number of post-smoothing steps to perform ( >= 0)

cyclingStrategy - the cycling strategy to use ( > 0). A value of 1 results in V-cycles, a value of 2 in W-cycles. This gives the number of times the MG algorithm recursively calls itself to solve the coarse grid problem.

Returns:

an improved approximate solution on a grid of the same size as u

calcResidual

protected NoBoundaryGrid calcResidual(ConstBoundaryGrid u,
                                      ConstNoBoundaryGrid f)

calculate the residual of an approximate solution to a PDE.

If Ax = f is the PDE and u is an approximation to the true solution x, then the residual r is defined as r = f - Au and is hence a 3-dimensional function sampled on a regular cubic grid without a boundary (because f is in our scheme without a boundary, too).

Parameters:

u - the approximate solution to the PDE whose residual is to be calculated

f - the right hand side (source term) of the PDE

Returns:

the residual of the given approximate solution on a grid of the size in question

calcResidualProper

protected void calcResidualProper(NoBoundaryGrid r,
                                  ConstBoundaryGrid u,
                                  ConstNoBoundaryGrid f,
                                  int myNum,
                                  int totalNum)

implements the parallel part of calcResidual().

Parameters:

r - the r

u - the u

f - the f

myNum - the my num

totalNum - the total num