7.22 Package FL.ITERATION

The FL.ITERATION package includes the definition for the abstract classes <solver>, <iterative-solver>, as well as the generic functions iterate and solve which constitutes the interface for linear and non-linear solving. Both functions work on a blackboard which is passed together with the iteration used as argument.

Several instances of iterative solvers are implemented, e.g. Gauss-Seidel, SOR, ILU (in linit.lisp) and CG (in krylow.lisp). A larger block of code is contained in a separate package FL.MULTIGRID and contains the multigrid iteration. From this class, an algebraic multigrid iteration is derived in amg.lisp and a geometric multigrid iteration in a separate file geomg.lisp and package FL.GEOMG.

Variable: *CPU-TIME-OBSERVE*

Observe CPU time during an iteration. This should be used as element in the observe list of an iteration.

Variable: *DISCRETE-ITERATIVE-SOLVER-OBSERVE*

Standard observe quantities for iterative solvers.

Variable: *ITERATION-DEPTH*

Depth of nested iteration.

Variable: *OUTPUT-DEPTH*

Maximum iteration depth for which status output is done.

Variable: *STEP-OBSERVE*

Observe step number during an iteration. This should be used as element in the observe list of an iteration.

Class: <BI-CGSTAB>

Preconditioned Bi-CGStab iteration

Superclasses: <PRECONDITIONED-KRYLOW>

Class: <BLOCK-ITERATION>

Subspace correction scheme generated by collecting overlapping blocks of unknowns.

Superclasses: <LINEAR-ITERATION>

Direct slots:

• INNER-ITERATION: Iteration which is used to solve for each block.
• ORDERING: Self-explanatory.
• STORE-P: T if diagonal can be stored.

Class: <CG>

Preconditioned conjugate gradient iteration

Superclasses: <PRECONDITIONED-KRYLOW>

Class: <CUSTOM-PSC>

PSC with custom BLOCK-SETUP function slot.

Superclasses: <SETUP-BLOCKS-MIXIN> <PSC>

Class: <CUSTOM-SSC>

SSC with custom BLOCK-SETUP function slot.

Superclasses: <SETUP-BLOCKS-MIXIN> <SSC>

Class: <FUNCTION>

The <function> class is an abstract class for a general function. This function will usually accept vector arguments, the dimensions of domain and image are fixed when defining the function. If the function is differentiable, the gradient matrix can be obtained by evaluating the gradient slot.

Direct slots:

• DOMAIN-DIMENSION: Self-explanatory.
• IMAGE-DIMENSION: Self-explanatory.

Class: <GAUSS-SEIDEL>

The Gauss-Seidel iteration is SOR with omega=1.

Superclasses: <SOR>

Class: <GRADIENT-METHOD>

Gradient-method. Better use CG.

Superclasses: <LINEAR-ITERATION>

Class: <ILU>

Incomplete LU iteration. omega is the modification parameter, eta is the diagonal enhancement.

Superclasses: <LINEAR-ITERATION>

Direct slots:

• OMEGA: Self-explanatory.
• ETA: Self-explanatory.
• ORDERING: Self-explanatory.

Class: <ITERATION>

The iteration base class.

Superclasses: PROPERTY-MIXIN

Direct slots:

• OBSERVE: The initform depends on the subclass.
• OUTPUT: A boolean indicating if output is to be done.
• SUCCESS-IF: A form specifying a success criterion.
• FAILURE-IF: A form specifying a failure criterion.
• START-TIME: Start time of the iteration.
• SUCCESS-IF-FN: Compiled success-if form.
• FAILURE-IF-FN: Compiled failure-if form.

Class: <ITERATIVE-SOLVER>

Base class of all iterative solvers and solution strategies.

Superclasses: <ITERATION> <SOLVER>

Class: <ITERATOR>

An <iterator> object contains functions doing iteration work or flags indicating which work has or has not to be done for calling that iterator. It is generated by the generic function make-iterator.

Superclasses: PROPERTY-MIXIN

Direct slots:

• MATRIX: The matrix on which the iterator is working.
• INITIALIZE: NIL or an initialization function which is called with the solution, rhs, and residual as arguments.
• INITIALIZEDP: Flag, if initialization has been done.
• ITERATE: A function of the arguments solution, rhs, and residual which performs an update step.
• RESIDUAL-BEFORE: T if the residual has to be up-to-date before the iteration step.
• RESIDUAL-AFTER: T if the residual is updated through the iteration step.

Class: <LINEAR-ITERATION>

The <linear-iteration> class. Linear iterations are e.g. <gauss-seidel> or <multigrid>.

Direct slots:

• DAMP: Self-explanatory.
• STORE-P: Store decomposition for multiple applications.

Class: <LINEAR-SOLVER>

Class for linear iterative solvers.

Superclasses: <DISCRETE-ITERATIVE-SOLVER>

Direct slots:

• ITERATION: The inner iteration.

Class: <LU>

A linear iteration interface for the LU exact solver.

Superclasses: <LINEAR-ITERATION>

Direct slots:

• STORE-P: Store decomposition for multiple applications.

Class: <MULTI-ITERATION>

One step of this iteration performs nr-steps of the base iteration.

Superclasses: <LINEAR-ITERATION>

Direct slots:

• BASE: Base iteration.
• NR-STEPS: Number of steps with which the base iteration is performed.

Class: <NEWTON>

Class for the Newton iteration.

Superclasses: <NONLINEAR-SOLVER>

Direct slots:

• STEP-CONTROL: NIL means that no step-control is done. If step-control is a number, then it denotes the maximum number of halving steps which is tried before giving up.

Class: <PARALLEL-SOR>

A parallel version of SOR.

Superclasses: <SOR>

Class: <PSC>

Parallel subspace correction scheme.

Superclasses: <BLOCK-ITERATION>

Class: <SAFE-LINEAR-SOLVER>

If failure occurs, object of this class try an alternative iteration. Usually this will be a direct decomposition.

Superclasses: <LINEAR-SOLVER>

Direct slots:

• FALLBACK: The fallback iteration.
• FALLBACK-P: Self-explanatory.

Class: <SOLVER>

The base class of linear, nonlinear and whatever iterative solvers.

Direct slots:

• OUTPUT: Self-explanatory.

Class: <SPECIAL-SOLVER>

If you happen to have a problem-adapted solver given as a function, you may use this base class.

Superclasses: <ITERATIVE-SOLVER>

Direct slots:

• SOLVER-FUNCTION: Self-explanatory.

Class: <SSC>

Successive subspace correction scheme.

Superclasses: <BLOCK-ITERATION>

Direct slots:

• OMEGA: Self-explanatory.

Function: BLOCKS VEC

Returns a dictionary mapping keys to entries for vec.

Function: COMPUTE-RESIDUAL A X B R

Compute the residual r=b-Ax.

Function: EVALUATE F X

Generic evaluation of functions on an argument. Numbers and arrays are treated as constants. Special evaluation is defined for multivariate polynomials on vectors and for <function> objects.

Function: EVALUATE-GRADIENT F X

Generic evaluation of gradients of differentiable functions.

Function: FINALLY ITER BLACKBOARD

Performs final operations.

Function: INITIALLY ITER BLACKBOARD

Performs initial operations.

Function: INTERMEDIATE ITER BLACKBOARD

Is called after initialization and after each step.

Function: INTERVAL-METHOD FUNC A B ACCURACY

Finds zeros of functions in 1d by the interval method.

Function: ITER-FORMAT STREAM CONTROL-STRING &REST ARGS

Iteration output should be made using this function which respects *iteration-depth* and *output-depth*.

Function: ITERATE ITER BLACKBOARD

Iterates on the data in the blackboard according to the iteration iter.

Function: LINSOLVE MAT RHS &KEY SOL RES OUTPUT ITERATION (RESIDUAL-NORM (FUNCTION L2-NORM)) (THRESHOLD 1.0e-12) REDUCTION (MAXSTEPS 100) SUCCESS-IF FAILURE-IF &ALLOW-OTHER-KEYS

Old and deprecated interface for solving linear problems.

Function: LU-SOLVER &KEY (OUTPUT NIL OUTPUT-P)

LU decomposition without pivoting.

Function: MAKE-ITERATOR LINIT MAT

Constructs an iterator object given a linear iteration and a matrix.

Function: NEXT-STEP ITER BLACKBOARD

Does a step of the iteration.

Function: PRODUCT-ITERATOR ITERATOR NR-STEPS

Returns an iterator which does several steps of the given iterator.

Function: SETUP-BLOCKS BLOCKIT MATRIX

Setup routine for determining the blocking of unknowns. Returns a list of blocks where each block is a vector of keys. May return a second value which is a list of pair. Each pair is of the form start-index/end-index and can be used to filter out different fe components.

Function: SOLVE SOLVER &OPTIONAL BLACKBOARD

Solve a problem specified on the blackboard. Returns a modified blackboard. The returned blackboard is guaranteed to contain at least the fields :solution and :status. :status is one of the values :success or :failure.

SOLVE can also be called as (SOLVE blackboard) and will then try to figure out a suitable solver itself.

Function: TERMINATE-P ITER BLACKBOARD

Tests terminating conditions. Returns either NIL or :success or :failure.