NOX::Epetra::FiniteDifferenceColoring Class Reference

Concrete implementation for creating an Epetra_RowMatrix Jacobian via finite differencing of the residual using coloring. More...

#include <NOX_Epetra_FiniteDifferenceColoring.H>

Inheritance diagram for NOX::Epetra::FiniteDifferenceColoring:

Inheritance graph
[legend]
Collaboration diagram for NOX::Epetra::FiniteDifferenceColoring:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 FiniteDifferenceColoring (Teuchos::ParameterList &printingParams, const Teuchos::RCP< Interface::Required > &i, const NOX::Epetra::Vector &initialGuess, const Teuchos::RCP< Epetra_MapColoring > &colorMap, const Teuchos::RCP< vector< Epetra_IntVector > > &columns, bool parallelColoring=false, bool distance1=false, double beta=1.0e-6, double alpha=1.0e-4)
 Constructor with output control.
 FiniteDifferenceColoring (Teuchos::ParameterList &printingParams, const Teuchos::RCP< Interface::Required > &i, const NOX::Epetra::Vector &initialGuess, const Teuchos::RCP< Epetra_CrsGraph > &rawGraph, const Teuchos::RCP< Epetra_MapColoring > &colorMap, const Teuchos::RCP< vector< Epetra_IntVector > > &columns, bool parallelColoring=false, bool distance1=false, double beta=1.0e-6, double alpha=1.0e-4)
 Constructor with output control.
virtual ~FiniteDifferenceColoring ()
 Pure virtual destructor.
virtual bool computeJacobian (const Epetra_Vector &x, Epetra_Operator &Jac)
 Compute Jacobian given the specified input vector, x. Returns true if computation was successful.
virtual bool computeJacobian (const Epetra_Vector &x)
 Compute Jacobian given the specified input vector, x. Returns true if computation was successful.
virtual void createColorContainers ()
 Output the coloring map, index map and underlying matrix.

Protected Types

enum  ColoringType { NOX_SERIAL, NOX_PARALLEL }

Protected Attributes

ColoringType coloringType
 Enum flag for type of coloring being used.
bool distance1
 bool flag for specifying special case of distance-1 coloring
Teuchos::RCP< const
Epetra_MapColoring > 
colorMap
 Color Map created by external algorithm.
Teuchos::RCP< vector
< Epetra_IntVector > > 
columns
 vector of Epetra_IntVectors containing columns corresponding to a given row and color
int numColors
 Number of colors in Color Map.
int maxNumColors
 Max Number of colors on all procs in Color Map.
int * colorList
 List of colors in Color Map.
list< int > listOfAllColors
 List of colors in Color Map.
std::map< int, int > colorToNumMap
 Inverse mapping from color id to its position in colorList.
Epetra_Map * cMap
 Coloring Map created by external algorithm.
Epetra_Import * Importer
 Importer needed for mapping Color Map to unColored Map.
Epetra_Vector * colorVect
 Color vector based on Color Map containing perturbations.
Epetra_Vector * betaColorVect
 Color vector based on Color Map containing beta value(s).
Epetra_Vector * mappedColorVect
 Color vector based on unColorred Map containing perturbations.
Epetra_Vector * xCol_perturb
 Perturbed solution vector based on column map.
const Epetra_BlockMap * columnMap
 Overlap Map (Column Map of Matrix Graph) needed for parallel.
Epetra_Import * rowColImporter
 An Import object needed in parallel to map from row-space to column-space.


Detailed Description

Concrete implementation for creating an Epetra_RowMatrix Jacobian via finite differencing of the residual using coloring.

The Jacobian entries are calculated via 1st or 2nd order finite differencing. This requires $ N + 1 $ or $ 2N + 1 $ calls to computeF(), respectively, where $ N $ is the number of colors.

\[ J_{ij} = \frac{\partial F_i}{\partial x_j} = \frac{F_i(x+\delta\mathbf{e}_j) - F_i(x)}{\delta} \]

where $J$ is the Jacobian, $F$ is the function evaluation, $x$ is the solution vector, and $\delta$ is a small perturbation to the $x_j$ entry.

Instead of perturbing each $ N_{dof} $ problem degrees of freedom sequentially and then evaluating all $ N_{dof} $ functions for each perturbation, coloring allows several degrees of freedom (all belonging to the same color) to be perturbed at the same time. This reduces the total number of function evaluations needed to compute $\mathbf{J}$ from $ N_{dof}^2 $ as is required using FiniteDifference to $ N\cdot N_{dof} $, often representing substantial computational savings.

Coloring is based on a user-supplied color map generated using an appropriate algorithm, eg greedy-algorithm - Y. Saad, "Iterative Methods for Sparse Linear Systems, 2nd ed.," chp. 3, SIAM, 2003.. Use can be made of the coloring algorithm provided by the EpetraExt package in Trilinos. The 1Dfem_nonlinearColoring and Brusselator example problems located in the nox/epetra-examples subdirectory demonstrate use of the EpetraExt package, and the 1Dfem_nonlinearColoring directory also contains a stand-alone coloring algorithm very similar to that in EpetraExt.

The perturbation, $ \delta $, is calculated using the following equation:

\[ \delta = \alpha * | x_j | + \beta \]

where $ \alpha $ is a scalar value (defaults to 1.0e-4) and $ \beta $ is another scalar (defaults to 1.0e-6).

Since both FiniteDifferenceColoring and FiniteDifference inherit from the Epetra_RowMatrix class, they can be used as preconditioning matrices for AztecOO preconditioners.

As for FiniteDifference, 1st order accurate Forward and Backward differences as well as 2nd order accurate Centered difference can be specified using setDifferenceMethod with the appropriate enumerated type passed as the argument.

Using FiniteDifferenceColoring in Parallel

Two ways of using this class in a distributed parallel environment are currently supported. From an application standpoint, the two approaches differ only in the status of the solution iterate used in the residual fill. If an object of this class is contructed with parallelColoring = true the solution iterate will be passe back in a non-ghosted form. On the contrary, setting this parameter to false in the constructor will cause the solution iterate to be in a ghosted form when calling back for a residual fill. When using the second approach, the user should be aware that the perturbed vector used to compute residuals has already been scattered to a form consistent with the column space of the Epetra_CrsGraph. In practice, this means that the perturbed vector used by computeF() has already been scattered to a ghosted or overlapped state. The application should then not perform this step but rather simply use the vector provided with the possible exception of requiring a local index reordering to bring the column-space based vector in sync with a potentially different ghosted index ordering. See the Brusselator and 1Dfem_nonlinearColoring example problems for details.

Special Case for Approximate Jacobian Construction

Provision is made for a simplified and cheaper use of coloring that currently provides only for the diagonal of the Jacobian to be computed. This is based on using a first-neighbors coloring of the original Jacobian graph using the Epetra_Ext MapColoring class with the distance1 argument set to true. This same argument should also be set to true in the constructor to this class. The result will be a diagonal Jacobian filled in a much more efficient manner.

Definition at line 144 of file NOX_Epetra_FiniteDifferenceColoring.H.


Constructor & Destructor Documentation

FiniteDifferenceColoring::FiniteDifferenceColoring ( Teuchos::ParameterList &  printingParams,
const Teuchos::RCP< Interface::Required > &  i,
const NOX::Epetra::Vector initialGuess,
const Teuchos::RCP< Epetra_MapColoring > &  colorMap,
const Teuchos::RCP< vector< Epetra_IntVector > > &  columns,
bool  parallelColoring = false,
bool  distance1 = false,
double  beta = 1.0e-6,
double  alpha = 1.0e-4 
)

Constructor with output control.

Definition at line 60 of file NOX_Epetra_FiniteDifferenceColoring.C.

References coloringType, createColorContainers(), and NOX::Epetra::FiniteDifference::label.

FiniteDifferenceColoring::FiniteDifferenceColoring ( Teuchos::ParameterList &  printingParams,
const Teuchos::RCP< Interface::Required > &  i,
const NOX::Epetra::Vector initialGuess,
const Teuchos::RCP< Epetra_CrsGraph > &  rawGraph,
const Teuchos::RCP< Epetra_MapColoring > &  colorMap,
const Teuchos::RCP< vector< Epetra_IntVector > > &  columns,
bool  parallelColoring = false,
bool  distance1 = false,
double  beta = 1.0e-6,
double  alpha = 1.0e-4 
)

Constructor with output control.

Definition at line 94 of file NOX_Epetra_FiniteDifferenceColoring.C.

References coloringType, createColorContainers(), and NOX::Epetra::FiniteDifference::label.

FiniteDifferenceColoring::~FiniteDifferenceColoring (  )  [virtual]

Pure virtual destructor.

Definition at line 129 of file NOX_Epetra_FiniteDifferenceColoring.C.

References betaColorVect, cMap, colorVect, Importer, mappedColorVect, rowColImporter, and xCol_perturb.


Member Function Documentation

bool FiniteDifferenceColoring::computeJacobian ( const Epetra_Vector &  x,
Epetra_Operator &  Jac 
) [virtual]

bool FiniteDifferenceColoring::computeJacobian ( const Epetra_Vector &  x  )  [virtual]

Compute Jacobian given the specified input vector, x. Returns true if computation was successful.

Reimplemented from NOX::Epetra::FiniteDifference.

Definition at line 140 of file NOX_Epetra_FiniteDifferenceColoring.C.

References computeJacobian().

void FiniteDifferenceColoring::createColorContainers (  )  [virtual]

Output the coloring map, index map and underlying matrix.

Create containers for using color and index maps in parallel coloring

Definition at line 335 of file NOX_Epetra_FiniteDifferenceColoring.C.

References colorList, colorMap, colorToNumMap, listOfAllColors, maxNumColors, and numColors.

Referenced by FiniteDifferenceColoring().


Member Data Documentation

Enum flag for type of coloring being used.

Definition at line 193 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and FiniteDifferenceColoring().

bool flag for specifying special case of distance-1 coloring

Definition at line 196 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian().

Teuchos::RCP<const Epetra_MapColoring> NOX::Epetra::FiniteDifferenceColoring::colorMap [protected]

Color Map created by external algorithm.

Definition at line 199 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and createColorContainers().

Teuchos::RCP< vector<Epetra_IntVector> > NOX::Epetra::FiniteDifferenceColoring::columns [protected]

vector of Epetra_IntVectors containing columns corresponding to a given row and color

Definition at line 202 of file NOX_Epetra_FiniteDifferenceColoring.H.

Number of colors in Color Map.

Definition at line 205 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by createColorContainers().

Max Number of colors on all procs in Color Map.

Definition at line 208 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by createColorContainers().

List of colors in Color Map.

Definition at line 211 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and createColorContainers().

List of colors in Color Map.

Definition at line 214 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and createColorContainers().

Inverse mapping from color id to its position in colorList.

Definition at line 217 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and createColorContainers().

Coloring Map created by external algorithm.

Definition at line 220 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

Importer needed for mapping Color Map to unColored Map.

Definition at line 223 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

Color vector based on Color Map containing perturbations.

Definition at line 226 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

Color vector based on Color Map containing beta value(s).

Definition at line 229 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

Color vector based on unColorred Map containing perturbations.

Definition at line 232 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

Perturbed solution vector based on column map.

Definition at line 235 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().

const Epetra_BlockMap* NOX::Epetra::FiniteDifferenceColoring::columnMap [protected]

Overlap Map (Column Map of Matrix Graph) needed for parallel.

Definition at line 238 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian().

An Import object needed in parallel to map from row-space to column-space.

Definition at line 241 of file NOX_Epetra_FiniteDifferenceColoring.H.

Referenced by computeJacobian(), and ~FiniteDifferenceColoring().


The documentation for this class was generated from the following files:

Generated on Wed Oct 21 14:28:45 2009 for Nonlinear Solver Project by  doxygen 1.5.9