MOAB: Mesh Oriented datABase  (version 5.3.0)
TerminationCriterion.hpp
Go to the documentation of this file.
00001 /* *****************************************************************
00002     MESQUITE -- The Mesh Quality Improvement Toolkit
00003 
00004     Copyright 2004 Sandia Corporation and Argonne National
00005     Laboratory.  Under the terms of Contract DE-AC04-94AL85000
00006     with Sandia Corporation, the U.S. Government retains certain
00007     rights in this software.
00008 
00009     This library is free software; you can redistribute it and/or
00010     modify it under the terms of the GNU Lesser General Public
00011     License as published by the Free Software Foundation; either
00012     version 2.1 of the License, or (at your option) any later version.
00013 
00014     This library is distributed in the hope that it will be useful,
00015     but WITHOUT ANY WARRANTY; without even the implied warranty of
00016     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017     Lesser General Public License for more details.
00018 
00019     You should have received a copy of the GNU Lesser General Public License
00020     (lgpl.txt) along with this library; if not, write to the Free Software
00021     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022 
00023     diachin2@llnl.gov, djmelan@sandia.gov, mbrewer@sandia.gov,
00024     pknupp@sandia.gov, tleurent@mcs.anl.gov, tmunson@mcs.anl.gov
00025 
00026   ***************************************************************** */
00027 // -*- Mode : c++; tab-width: 3; c-tab-always-indent: t; indent-tabs-mode: nil; c-basic-offset: 3
00028 // -*-
00029 
00030 /*! \file TerminationCriterion.hpp
00031 
00032 Header file for the TerminationCriterion classes.
00033 
00034   \author Michael Brewer
00035   \author Thomas Leurent
00036   \date   Feb. 14, 2003
00037  */
00038 
00039 #ifndef TerminationCriterion_hpp
00040 #define TerminationCriterion_hpp
00041 
00042 #include "Mesquite.hpp"
00043 #include "MsqTimer.hpp"
00044 #include "Vector3D.hpp"
00045 
00046 #include <string>
00047 #include <vector>
00048 #include <fstream>
00049 
00050 namespace MBMesquite
00051 {
00052 class MsqError;
00053 class OFEvaluator;
00054 class PatchData;
00055 class PatchDataVerticesMemento;
00056 class Mesh;
00057 class MeshDomain;
00058 class MeshDomainAssoc;
00059 class Settings;
00060 class VertexMover;
00061 
00062 /*! \class TerminationCriterion
00063 
00064     \brief The TerminationCriterion class contains functionality to
00065     terminate the VertexMover's optimization.
00066 
00067     The Termination Criterion class has three roles.  It
00068     is used to terminate the optimization on a single patch; it
00069     is used to terminate the iterations over all patches in the
00070     mesh; and it is used to cull vertices from the optimization
00071     processes.  Thus, for each optimization, two TerminationCriterion
00072     objects are used.  The class contains five important member
00073     functions used in the VertexMover:  initialize(), reset(),
00074     terminate(), cull_vertices(), and cleanup().  These functions
00075     are each explained in detail below.  In general, the only one
00076     of these functions called directly from a concrete VertexMover
00077     is terminate() which allows the concrete VertexMover to determine
00078     when to stop producing new iterates on a given patch.  All other
00079     functionality is handled from the base VertexMover base class.
00080 
00081     There are several different types of termination criteria
00082     available. Multiple criteria types can be set on a given
00083     Termination Criterion object, and when this occurs, the
00084     optimization process will terminate whenever any of the
00085     criteria have been satisfied.
00086 
00087     The following is a brief description of how TerminationCriterion
00088     is used within Mesquite.  Functions called during QualityImprovement
00089     can be divided into three groups:
00090       reset_*      - Initialize data for an iteration
00091       accumulate_* - Update TC for changed data during iteration
00092       terminate    - Check if the termination criterion has been met.
00093     There are three different forms of the reset_* and accumulate_*
00094     functions which are called on the inner, outer, or both
00095     TerminationCriterion classes:
00096       *_outer      - Called on outer termination criterion.
00097       *_inner      - Called on inner termination criterion.
00098       *_patch      - Called on outer termination criterion for
00099                      each patch and on inner termination criterion
00100                      for each inner iteration.
00101 
00102     If implementing a new TerminationCriterion, the following rules
00103     should be followed.  If the value must be calculated on a global
00104     patch for the outer TC, then:
00105       o The functionality should be added to *_inner (yes, INNER)
00106       o The *_outer methods should be updated to call the *_inner
00107           with a global patch when your TC is requested.
00108       o The internal data for any such TC should be initialized
00109         in the reset_inner method.
00110     If the value for the outer criterion can be calculated from each
00111     local patch when iterating over the mesh with local patches, then:
00112       o The functionality should be added to *_patch
00113       o Any state values pertaining to the entire iteration must be
00114          initialized in reset_inner(..) and cleared in terminate()
00115       o Any patch-specific data should be initialized in reset_patch
00116       o Care should be taken that terminate() does not check
00117         uninitialized data if called before the first call to
00118         accumulate_patch()
00119 
00120 */
00121 class TerminationCriterion
00122 {
00123   public:
00124     //! checks the gradient \f$\nabla f \f$ of objective function
00125     //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$
00126     //! and stops when \f$\sqrt{\sum_{i=1}^{3N}\nabla f_i^2}<d\f$
00127     MESQUITE_EXPORT void add_absolute_gradient_L2_norm( double value );
00128 
00129     //! checks the gradient \f$\nabla f \f$ of objective function
00130     //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$
00131     //! and stops when \f$ \max_{i=1}^{3N} \nabla f_i < d \f$
00132     MESQUITE_EXPORT void add_absolute_gradient_inf_norm( double value );
00133 
00134     //! terminates on the j_th iteration when
00135     //! \f$\sqrt{\sum_{i=1}^{3N}\nabla f_{i,j}^2}<d\sqrt{\sum_{i=1}^{3N}\nabla f_{i,0}^2}\f$
00136     //!  That is, terminates when the norm of the gradient is smaller
00137     //!  than the specified fraction of the initial norm of the gradient.
00138     MESQUITE_EXPORT void add_relative_gradient_L2_norm( double value );
00139 
00140     //! terminates on the j_th iteration when
00141     //! \f$\max_{i=1 \cdots 3N}\nabla f_{i,j}<d \max_{i=1 \cdots 3N}\nabla f_{i,0}\f$
00142     //!  That is, terminates when the norm of the gradient is small
00143     //! than some scaling factor times the norm of the original gradient.
00144     //! (Using the infinity norm.)
00145     MESQUITE_EXPORT void add_relative_gradient_inf_norm( double value );
00146 
00147     //! Terminates when the objective function value is smaller than
00148     //! the given scalar value.
00149     MESQUITE_EXPORT void add_absolute_quality_improvement( double value );
00150 
00151     //! Terminates when the objective function value is smaller than
00152     //! the given scalar value times the original objective function
00153     //! value.
00154     MESQUITE_EXPORT void add_relative_quality_improvement( double value );
00155 
00156     //! Terminates when a the maximum distance moved by any vertex
00157     //! during the previous iteration is below the given value.
00158     MESQUITE_EXPORT void add_absolute_vertex_movement( double value );
00159 
00160     //! Terminates when a the maximum distance moved by any vertex
00161     //! during the previous iteration is below the given value
00162     //! times the maximum distance moved by any vertex over the
00163     //! entire course of the optimization.
00164     MESQUITE_EXPORT void add_relative_vertex_movement( double value );
00165 
00166     //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$
00167     //! and terminates when the maximum vertex movement of an iteration
00168     //! is less than delta.
00169     //!
00170     //! \f$ \beta \f$ is the passed value, \f$ a \f$
00171     //! is the average edge length of the initial mesh and \f$ \sigma \f$
00172     //! is the standard deviation of the edge lengths of the initial
00173     //! mesh.  The initial mesh values are (re)calcualted for each
00174     //! time the instruction queue is run.
00175     //!
00176     //!\param value \f$ beta \f$.  Must be in range (0,1), exclusive.
00177     MESQUITE_EXPORT void add_absolute_vertex_movement_edge_length( double value );
00178 
00179     //! Terminates when the decrease in the objective function value since
00180     //! the previous iteration is below the given value.
00181     MESQUITE_EXPORT void add_absolute_successive_improvement( double value );
00182 
00183     //! Terminates when the decrease in the objective function value since
00184     //! the previous iteration is below the given value times the
00185     //! decrease in the objective function value since the beginning
00186     //! of this optimization process.
00187     MESQUITE_EXPORT void add_relative_successive_improvement( double value );
00188 
00189     //! Terminates when the algorithm exceeds an allotted time limit
00190     //! (given in seconds).
00191     MESQUITE_EXPORT void add_cpu_time( double seconds );
00192 
00193     //! Terminates when the number of iterations exceeds a given integer.
00194     MESQUITE_EXPORT void add_iteration_limit( unsigned int max_iterations );
00195 
00196     //! Terminates when any vertex leaves the bounding box, defined
00197     //! by the given value, d.  That is, when the absolute value of
00198     //! a single coordinate of vertex's position exceeds d.
00199     MESQUITE_EXPORT void add_bounded_vertex_movement( double value );
00200 
00201     //! Terminates when the mesh is detected to be untangled.
00202     //! Uses the same approach as QualityAssessor,
00203     //! checks the tau values at all the sample points.
00204     MESQUITE_EXPORT void add_untangled_mesh();
00205 
00206     MESQUITE_EXPORT void remove_all_criteria();
00207 
00208     //! Cull when the objective function value is smaller than
00209     //! the given scalar value.
00210     MESQUITE_EXPORT void cull_on_absolute_quality_improvement( double limit );
00211     //! Cull when the objective function value is smaller than
00212     //! the given scalar value times the original objective function
00213     //! value.
00214     MESQUITE_EXPORT void cull_on_relative_quality_improvement( double limit );
00215     //! Cull when a the maximum distance moved by any vertex
00216     //! during the previous iteration is below the given value.
00217     MESQUITE_EXPORT void cull_on_absolute_vertex_movement( double limit );
00218     //! Cull when a the maximum distance moved by any vertex
00219     //! during the previous iteration is below the given value
00220     //! times the maximum distance moved by any vertex over the
00221     //! entire course of the optimization.
00222     MESQUITE_EXPORT void cull_on_relative_vertex_movement( double limit );
00223     //! Cull when the decrease in the objective function value since
00224     //! the previous iteration is below the given value.
00225     MESQUITE_EXPORT void cull_on_absolute_successive_improvement( double limit );
00226     //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$
00227     //! and culls when the vertex movement  is less than delta.
00228     //!
00229     //! \f$ \beta \f$ is the passed value, \f$ a \f$
00230     //! is the average edge length of the initial mesh and \f$ \sigma \f$
00231     //! is the standard deviation of the edge lengths of the initial
00232     //! mesh.  The initial mesh values are (re)calcualted for each
00233     //! time the instruction queue is run.
00234     //!
00235     //!\param value \f$ beta \f$.  Must be in range (0,1), exclusive.
00236     MESQUITE_EXPORT void cull_on_absolute_vertex_movement_edge_length( double value );
00237     //! Cull when the decrease in the objective function value since
00238     //! the previous iteration is below the given value times the
00239     //! decrease in the objective function value since the beginning
00240     //! of this optimization process.
00241     MESQUITE_EXPORT void cull_on_relative_successive_improvement( double limit );
00242 
00243     //! Cull for a global patch - sets soft fixed flags for vertices
00244     //! that touch elements that are culled by above flags.
00245     MESQUITE_EXPORT void cull_for_global_patch( bool val = true );
00246 
00247     //! Cull when the mesh is detected to be untangled.
00248     //! Uses the same approach as QualityAssessor,
00249     //! checks the tau values at all the sample points.
00250     MESQUITE_EXPORT void cull_untangled_mesh();
00251 
00252     MESQUITE_EXPORT void remove_culling();
00253 
00254     enum InnerOuterType
00255     {
00256         TYPE_UNKNOWN,
00257         TYPE_INNER,
00258         TYPE_OUTER
00259     };
00260 
00261     //! Constructor which does not take any arguements
00262     MESQUITE_EXPORT TerminationCriterion( std::string name = "", InnerOuterType innerOuterType = TYPE_UNKNOWN );
00263 
00264     //! Destructor
00265     MESQUITE_EXPORT ~TerminationCriterion(){};
00266 
00267     //! This function returns the current function value.
00268     /*! \todo Michael:  this function is not reliable.  It
00269       needs to be more robust.  How do we know whether
00270       currentOFValue got updated or not?  We may want to
00271       make sure that all the criteria get checked.*/
00272     MESQUITE_EXPORT double get_current_function_value()
00273     {
00274         return currentOFValue;
00275     }
00276 
00277     MESQUITE_EXPORT void set_debug_output_level( int i )
00278     {
00279         debugLevel = i;
00280     }
00281 
00282     enum TimeStepFileType
00283     {
00284         NOTYPE = 0,
00285         VTK,
00286         GNUPLOT
00287     };
00288 
00289     /**\brief Write mesh improvement animation
00290      *
00291      * Write mesh at each iteration such that the sequence of mesh files can be used
00292      * to produce an animation of the mesh through the quality improvement process.
00293      *
00294      * Files can be written either as VTK timesteps for viewing in a tool such as Paraview
00295      * or as GNU plot data files and a GNU plot script which, in combination with recent
00296      * versions of GNU plot, can be used to produce an animated GIF image.
00297      *
00298      * Writing of mesh steps can be disabled by calling this function with type == NOTYPE
00299      * and filename ==NULL.
00300      */
00301     MESQUITE_EXPORT void write_mesh_steps( const char* filename, TimeStepFileType type = VTK )
00302     {
00303         timeStepFileName = filename;
00304         timeStepFileType = type;
00305     }
00306 
00307     /*\brief Write data for generating plots of optimization process.
00308      *
00309      * Write data files in a format suitable for use with GNU plot and other applications.
00310      * The file will contain data corresponding to all termination criteria,
00311      * however, some values may be invalid if they are not calculated for
00312      * use in a termination criterion.
00313      */
00314     MESQUITE_EXPORT void write_iterations( const char* filename, MsqError& err );
00315 
00316     MESQUITE_EXPORT int get_iteration_count() const
00317     {
00318         return iterationCounter;
00319     }
00320 
00321     //! Clear any data accumulated during an outer iteration
00322     void reset_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& of, const Settings* settings, MsqError& err );
00323 
00324     //! Clear any data accumulated during an inner iteration
00325     void reset_inner( PatchData& pd, OFEvaluator& of, MsqError& err );
00326 
00327     //! Shared inner and outer initialization during inner loop
00328     void reset_patch( PatchData& pd, MsqError& err );
00329 
00330     //! Accumulate data during inner iteration
00331     void accumulate_inner( PatchData& pd, OFEvaluator& eval, MsqError& err );
00332 
00333     //! Accumulate data during inner iteration
00334     void accumulate_inner( PatchData& pd, double of_value, Vector3D* of_grads, MsqError& err );
00335 
00336     //! Common code for both inner and outer termination
00337     //! criteria during inner iteration.
00338     void accumulate_patch( PatchData& pd, MsqError& err );
00339 
00340     void accumulate_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& eval, const Settings* settings, MsqError& err );
00341 
00342     //! Check if termination criterion has been met
00343     MESQUITE_EXPORT bool terminate();
00344 
00345     //! Check if at least one termination criterion is set
00346     MESQUITE_EXPORT bool criterion_is_set();
00347 
00348     //! Function which determines whether this patch should be 'culled'
00349     bool cull_vertices( PatchData& pd, OFEvaluator& obj_ptr, MsqError& err );
00350 
00351     //! experimental, first cut at culling for global patches - not finished
00352     bool cull_vertices_global( PatchData& global_patch, Mesh* mesh, MeshDomain* domain, const Settings* settings,
00353                                OFEvaluator& of_eval, MsqError& err );
00354 
00355     //! Cleans up after the TerminationCriterion is finished.
00356     void cleanup( Mesh* ms, MeshDomain* domain, MsqError& err );
00357 
00358     void initialize_queue( MeshDomainAssoc* mesh_and_domain, const Settings* settings, MsqError& err );
00359 
00360     friend class VertexMover;
00361 
00362   protected:
00363     void write_timestep( PatchData& pd, const Vector3D* gradient, MsqError& err );
00364 
00365     static size_t count_inverted( PatchData& pd, MsqError& err );
00366 
00367     std::string par_string();  // for debug print of parallel rank
00368 
00369   private:
00370     // PRIVATE DATA MEMBERS
00371     long unsigned int terminationCriterionFlag;  //!< Bit flag of termination crit
00372     long unsigned int cullingMethodFlag;         /*!<Bit flag of criterion for culling*/
00373     // epsiloon used in culling methods.
00374     double cullingEps;
00375 
00376     bool cullingGlobalPatch; /*!<enable culling of pieces of a global patch*/
00377 
00378     // Data not specific to a single criterion
00379     double initialOFValue;
00380     double previousOFValue;
00381     double currentOFValue;
00382     double lowerOFBound;
00383 
00384     // Data specific to termination criterion 1 (gradient bounds)
00385     std::vector< Vector3D > mGrad;
00386     double initialGradL2NormSquared;
00387     double currentGradL2NormSquared;
00388     double gradL2NormAbsoluteEpsSquared;
00389     double gradL2NormRelativeEpsSquared;
00390     double initialGradInfNorm;
00391     double currentGradInfNorm;
00392     double gradInfNormAbsoluteEps;
00393     double gradInfNormRelativeEps;
00394     // Data specific to termination criterion 2 (KKT)
00395     //???????????????????????????????????????????
00396     // Data specific to termination criterion 3 (Quality Improvement)
00397     double qualityImprovementAbsoluteEps;
00398     double qualityImprovementRelativeEps;
00399     // Data specific to termination criterion 4 (inner iterations)
00400     int iterationBound;
00401     int iterationCounter;
00402     // Data specific to termination criterion 5 (cpu time)
00403     Timer mTimer;
00404     double timeBound;
00405     // Data specific to termination criterion 6 (vertex movement)
00406     PatchDataVerticesMemento* initialVerticesMemento;
00407     PatchDataVerticesMemento* previousVerticesMemento;  // if we want relative
00408     double vertexMovementAbsoluteEps;
00409     double vertexMovementRelativeEps;
00410     double vertexMovementAvgBeta;          //!< input beta value used to calculate \c vertexMovementAbsoluteAvg
00411     double vertexMovementAbsoluteAvgEdge;  //!< calculated constant for \c
00412                                            //!< VERTEX_MOVEMENT_ABS_EDGE_LENGTH
00413     double maxSquaredInitialMovement;
00414     double maxSquaredMovement;
00415 
00416     // Data specific to termination criterion 7 (successive improvement to F)
00417     double successiveImprovementsAbsoluteEps;
00418     double successiveImprovementsRelativeEps;
00419     // crit 8
00420     double boundedVertexMovementEps;
00421     int vertexMovementExceedsBound;
00422 
00423     // Data for untangled criterion
00424     size_t globalInvertedCount;  //!< number of inverted elements in entire mesh
00425     size_t patchInvertedCount;   //!< number of inverted elements in previously tested patch
00426 
00427     int debugLevel;
00428 
00429     //! Plot data
00430     std::ofstream plotFile;
00431 
00432     //! Base name for timestep files
00433     std::string timeStepFileName;
00434     TimeStepFileType timeStepFileType;
00435     std::string moniker;
00436     InnerOuterType innerOuterType;
00437 };
00438 
00439 }  // namespace MBMesquite
00440 
00441 #endif  // TerminationCriterion_hpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines