1 /* ***************************************************************** 2 MESQUITE -- The Mesh Quality Improvement Toolkit 3 4 Copyright 2004 Sandia Corporation and Argonne National 5 Laboratory. Under the terms of Contract DE-AC04-94AL85000 6 with Sandia Corporation, the U.S. Government retains certain 7 rights in this software. 8 9 This library is free software; you can redistribute it and/or 10 modify it under the terms of the GNU Lesser General Public 11 License as published by the Free Software Foundation; either 12 version 2.1 of the License, or (at your option) any later version. 13 14 This library is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public License 20 (lgpl.txt) along with this library; if not, write to the Free Software 21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 22 23 diachin2@llnl.gov, djmelan@sandia.gov, mbrewer@sandia.gov, 24 pknupp@sandia.gov, tleurent@mcs.anl.gov, tmunson@mcs.anl.gov 25 26 ***************************************************************** */ 27 // -*- Mode : c++; tab-width: 3; c-tab-always-indent: t; indent-tabs-mode: nil; c-basic-offset: 3 -*- 28 29 /*! \file TerminationCriterion.hpp 30 31 Header file for the TerminationCriterion classes. 32 33 \author Michael Brewer 34 \author Thomas Leurent 35 \date Feb. 14, 2003 36 */ 37 38 39 #ifndef TerminationCriterion_hpp 40 #define TerminationCriterion_hpp 41 42 #include "Mesquite.hpp" 43 #include "MsqTimer.hpp" 44 #include "Vector3D.hpp" 45 46 #include <string> 47 #include <vector> 48 #include <fstream> 49 50 namespace MBMesquite 51 { 52 class MsqError; 53 class OFEvaluator; 54 class PatchData; 55 class PatchDataVerticesMemento; 56 class Mesh; 57 class MeshDomain; 58 class MeshDomainAssoc; 59 class Settings; 60 class VertexMover; 61 62 /*! \class TerminationCriterion 63 64 \brief The TerminationCriterion class contains functionality to 65 terminate the VertexMover's optimization. 66 67 The Termination Criterion class has three roles. It 68 is used to terminate the optimization on a single patch; it 69 is used to terminate the iterations over all patches in the 70 mesh; and it is used to cull vertices from the optimization 71 processes. Thus, for each optimization, two TerminationCriterion 72 objects are used. The class contains five important member 73 functions used in the VertexMover: initialize(), reset(), 74 terminate(), cull_vertices(), and cleanup(). These functions 75 are each explained in detail below. In general, the only one 76 of these functions called directly from a concrete VertexMover 77 is terminate() which allows the concrete VertexMover to determine 78 when to stop producing new iterates on a given patch. All other 79 functionality is handled from the base VertexMover base class. 80 81 There are several different types of termination criteria 82 available. Multiple criteria types can be set on a given 83 Termination Criterion object, and when this occurs, the 84 optimization process will terminate whenever any of the 85 criteria have been satisfied. 86 87 The following is a brief description of how TerminationCriterion 88 is used within Mesquite. Functions called during QualityImprovement 89 can be divided into three groups: 90 reset_* - Initialize data for an iteration 91 accumulate_* - Update TC for changed data during iteration 92 terminate - Check if the termination criterion has been met. 93 There are three different forms of the reset_* and accumulate_* 94 functions which are called on the inner, outer, or both 95 TerminationCriterion classes: 96 *_outer - Called on outer termination criterion. 97 *_inner - Called on inner termination criterion. 98 *_patch - Called on outer termination criterion for 99 each patch and on inner termination criterion 100 for each inner iteration. 101 102 If implementing a new TerminationCriterion, the following rules 103 should be followed. If the value must be calculated on a global 104 patch for the outer TC, then: 105 o The functionality should be added to *_inner (yes, INNER) 106 o The *_outer methods should be updated to call the *_inner 107 with a global patch when your TC is requested. 108 o The internal data for any such TC should be initialized 109 in the reset_inner method. 110 If the value for the outer criterion can be calculated from each 111 local patch when iterating over the mesh with local patches, then: 112 o The functionality should be added to *_patch 113 o Any state values pertaining to the entire iteration must be 114 initialized in reset_inner(..) and cleared in terminate() 115 o Any patch-specific data should be initialized in reset_patch 116 o Care should be taken that terminate() does not check 117 uninitialized data if called before the first call to 118 accumulate_patch() 119 120 */ 121 class TerminationCriterion 122 { 123 public: 124 125 //! checks the gradient \f$\nabla f \f$ of objective function 126 //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$ 127 //! and stops when \f$\sqrt{\sum_{i=1}^{3N}\nabla f_i^2}<d\f$ 128 MESQUITE_EXPORT void add_absolute_gradient_L2_norm( double value ); 129 130 //! checks the gradient \f$\nabla f \f$ of objective function 131 //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$ 132 //! and stops when \f$ \max_{i=1}^{3N} \nabla f_i < d \f$ 133 MESQUITE_EXPORT void add_absolute_gradient_inf_norm( double value ); 134 135 //!terminates on the j_th iteration when 136 //! \f$\sqrt{\sum_{i=1}^{3N}\nabla f_{i,j}^2}<d\sqrt{\sum_{i=1}^{3N}\nabla f_{i,0}^2}\f$ 137 //! That is, terminates when the norm of the gradient is smaller 138 //! than the specified fraction of the initial norm of the gradient. 139 MESQUITE_EXPORT void add_relative_gradient_L2_norm( double value ); 140 141 //!terminates on the j_th iteration when 142 //! \f$\max_{i=1 \cdots 3N}\nabla f_{i,j}<d \max_{i=1 \cdots 3N}\nabla f_{i,0}\f$ 143 //! That is, terminates when the norm of the gradient is small 144 //! than some scaling factor times the norm of the original gradient. 145 //! (Using the infinity norm.) 146 MESQUITE_EXPORT void add_relative_gradient_inf_norm( double value ); 147 148 //!Terminates when the objective function value is smaller than 149 //! the given scalar value. 150 MESQUITE_EXPORT void add_absolute_quality_improvement( double value ); 151 152 //!Terminates when the objective function value is smaller than 153 //! the given scalar value times the original objective function 154 //! value. 155 MESQUITE_EXPORT void add_relative_quality_improvement( double value ); 156 157 //!Terminates when a the maximum distance moved by any vertex 158 //! during the previous iteration is below the given value. 159 MESQUITE_EXPORT void add_absolute_vertex_movement( double value ); 160 161 //!Terminates when a the maximum distance moved by any vertex 162 //! during the previous iteration is below the given value 163 //! times the maximum distance moved by any vertex over the 164 //! entire course of the optimization. 165 MESQUITE_EXPORT void add_relative_vertex_movement( double value ); 166 167 //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$ 168 //! and terminates when the maximum vertex movement of an iteration 169 //! is less than delta. 170 //! 171 //! \f$ \beta \f$ is the passed value, \f$ a \f$ 172 //! is the average edge length of the initial mesh and \f$ \sigma \f$ 173 //! is the standard deviation of the edge lengths of the initial 174 //! mesh. The initial mesh values are (re)calcualted for each 175 //! time the instruction queue is run. 176 //! 177 //!\param value \f$ beta \f$. Must be in range (0,1), exclusive. 178 MESQUITE_EXPORT void add_absolute_vertex_movement_edge_length( double value ); 179 180 //!Terminates when the decrease in the objective function value since 181 //! the previous iteration is below the given value. 182 MESQUITE_EXPORT void add_absolute_successive_improvement( double value ); 183 184 //!Terminates when the decrease in the objective function value since 185 //! the previous iteration is below the given value times the 186 //! decrease in the objective function value since the beginning 187 //! of this optimization process. 188 MESQUITE_EXPORT void add_relative_successive_improvement( double value ); 189 190 //!Terminates when the algorithm exceeds an allotted time limit 191 //! (given in seconds). 192 MESQUITE_EXPORT void add_cpu_time( double seconds ); 193 194 //!Terminates when the number of iterations exceeds a given integer. 195 MESQUITE_EXPORT void add_iteration_limit( unsigned int max_iterations ); 196 197 //!Terminates when any vertex leaves the bounding box, defined 198 //! by the given value, d. That is, when the absolute value of 199 //! a single coordinate of vertex's position exceeds d. 200 MESQUITE_EXPORT void add_bounded_vertex_movement( double value); 201 202 //!Terminates when the mesh is detected to be untangled. 203 //! Uses the same approach as QualityAssessor, 204 //! checks the tau values at all the sample points. 205 MESQUITE_EXPORT void add_untangled_mesh(); 206 207 MESQUITE_EXPORT void remove_all_criteria(); 208 209 //!Cull when the objective function value is smaller than 210 //! the given scalar value. 211 MESQUITE_EXPORT void cull_on_absolute_quality_improvement( double limit ); 212 //!Cull when the objective function value is smaller than 213 //! the given scalar value times the original objective function 214 //! value. 215 MESQUITE_EXPORT void cull_on_relative_quality_improvement( double limit ); 216 //!Cull when a the maximum distance moved by any vertex 217 //! during the previous iteration is below the given value. 218 MESQUITE_EXPORT void cull_on_absolute_vertex_movement( double limit ); 219 //!Cull when a the maximum distance moved by any vertex 220 //! during the previous iteration is below the given value 221 //! times the maximum distance moved by any vertex over the 222 //! entire course of the optimization. 223 MESQUITE_EXPORT void cull_on_relative_vertex_movement( double limit ); 224 //!Cull when the decrease in the objective function value since 225 //! the previous iteration is below the given value. 226 MESQUITE_EXPORT void cull_on_absolute_successive_improvement( double limit ); 227 //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$ 228 //! and culls when the vertex movement is less than delta. 229 //! 230 //! \f$ \beta \f$ is the passed value, \f$ a \f$ 231 //! is the average edge length of the initial mesh and \f$ \sigma \f$ 232 //! is the standard deviation of the edge lengths of the initial 233 //! mesh. The initial mesh values are (re)calcualted for each 234 //! time the instruction queue is run. 235 //! 236 //!\param value \f$ beta \f$. Must be in range (0,1), exclusive. 237 MESQUITE_EXPORT void cull_on_absolute_vertex_movement_edge_length( double value ); 238 //!Cull when the decrease in the objective function value since 239 //! the previous iteration is below the given value times the 240 //! decrease in the objective function value since the beginning 241 //! of this optimization process. 242 MESQUITE_EXPORT void cull_on_relative_successive_improvement( double limit ); 243 244 //!Cull for a global patch - sets soft fixed flags for vertices 245 //! that touch elements that are culled by above flags. 246 MESQUITE_EXPORT void cull_for_global_patch( bool val=true ); 247 248 //!Cull when the mesh is detected to be untangled. 249 //! Uses the same approach as QualityAssessor, 250 //! checks the tau values at all the sample points. 251 MESQUITE_EXPORT void cull_untangled_mesh(); 252 253 MESQUITE_EXPORT void remove_culling(); 254 255 enum InnerOuterType { 256 TYPE_UNKNOWN, 257 TYPE_INNER, 258 TYPE_OUTER 259 }; 260 261 //!Constructor which does not take any arguements 262 MESQUITE_EXPORT TerminationCriterion(std::string name="", InnerOuterType innerOuterType=TYPE_UNKNOWN); 263 264 //!Destructor ~TerminationCriterion()265 MESQUITE_EXPORT ~TerminationCriterion(){}; 266 267 //!This function returns the current function value. 268 /*! \todo Michael: this function is not reliable. It 269 needs to be more robust. How do we know whether 270 currentOFValue got updated or not? We may want to 271 make sure that all the criteria get checked.*/ get_current_function_value()272 MESQUITE_EXPORT double get_current_function_value() 273 {return currentOFValue;} 274 set_debug_output_level(int i)275 MESQUITE_EXPORT void set_debug_output_level( int i ) 276 { debugLevel = i; } 277 278 enum TimeStepFileType { NOTYPE = 0, VTK, GNUPLOT }; 279 280 /**\brief Write mesh improvement animation 281 * 282 * Write mesh at each iteration such that the sequence of mesh files can be used 283 * to produce an animation of the mesh through the quality improvement process. 284 * 285 * Files can be written either as VTK timesteps for viewing in a tool such as Paraview 286 * or as GNU plot data files and a GNU plot script which, in combination with recent 287 * versions of GNU plot, can be used to produce an animated GIF image. 288 * 289 * Writing of mesh steps can be disabled by calling this function with type == NOTYPE 290 * and filename ==NULL. 291 */ write_mesh_steps(const char * filename,TimeStepFileType type=VTK)292 MESQUITE_EXPORT void write_mesh_steps( const char* filename, TimeStepFileType type = VTK ) 293 { timeStepFileName = filename; timeStepFileType = type; } 294 295 /*\brief Write data for generating plots of optimization process. 296 * 297 * Write data files in a format suitable for use with GNU plot and other applications. 298 * The file will contain data corresponding to all termination criteria, 299 * however, some values may be invalid if they are not calculated for 300 * use in a termination criterion. 301 */ 302 MESQUITE_EXPORT void write_iterations( const char* filename, MsqError& err ); 303 get_iteration_count() const304 MESQUITE_EXPORT int get_iteration_count( ) const 305 { return iterationCounter; } 306 307 308 //! Clear any data accumulated during an outer iteration 309 void reset_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& of, 310 const Settings* settings, MsqError& err ); 311 312 //! Clear any data accumulated during an inner iteration 313 void reset_inner( PatchData& pd, OFEvaluator& of, MsqError& err ); 314 315 //! Shared inner and outer initialization during inner loop 316 void reset_patch( PatchData& pd, MsqError& err ); 317 318 //! Accumulate data during inner iteration 319 void accumulate_inner( PatchData& pd, OFEvaluator& eval, MsqError& err ); 320 321 //! Accumulate data during inner iteration 322 void accumulate_inner( PatchData& pd, double of_value, Vector3D* of_grads, 323 MsqError& err ); 324 325 //! Common code for both inner and outer termination 326 //! criteria during inner iteration. 327 void accumulate_patch( PatchData& pd, MsqError& err ); 328 329 void accumulate_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& eval, 330 const Settings* settings, MsqError& err ); 331 332 //! Check if termination criterion has been met 333 MESQUITE_EXPORT bool terminate(); 334 335 //! Check if at least one termination criterion is set 336 MESQUITE_EXPORT bool criterion_is_set(); 337 338 339 //!Function which determines whether this patch should be 'culled' 340 bool cull_vertices(PatchData &pd, OFEvaluator& obj_ptr, MsqError &err); 341 342 //!experimental, first cut at culling for global patches - not finished 343 bool cull_vertices_global(PatchData &global_patch, 344 Mesh *mesh, MeshDomain *domain, const Settings *settings, 345 OFEvaluator& of_eval, 346 MsqError &err); 347 348 //!Cleans up after the TerminationCriterion is finished. 349 void cleanup(Mesh* ms, MeshDomain* domain, MsqError &err); 350 351 void initialize_queue( MeshDomainAssoc* mesh_and_domain, 352 const Settings* settings, 353 MsqError& err ); 354 355 friend class VertexMover; 356 357 protected: 358 359 void write_timestep( PatchData& pd, const Vector3D* gradient, MsqError& err ); 360 361 static size_t count_inverted( PatchData& pd, MsqError& err ); 362 363 std::string par_string(); // for debug print of parallel rank 364 365 private: 366 //PRIVATE DATA MEMBERS 367 long unsigned int terminationCriterionFlag;//!<Bit flag of termination crit 368 long unsigned int cullingMethodFlag;/*!<Bit flag of criterion for culling*/ 369 //epsiloon used in culling methods. 370 double cullingEps; 371 372 bool cullingGlobalPatch;/*!<enable culling of pieces of a global patch*/ 373 374 //Data not specific to a single criterion 375 double initialOFValue; 376 double previousOFValue; 377 double currentOFValue; 378 double lowerOFBound; 379 380 //Data specific to termination criterion 1 (gradient bounds) 381 std::vector<Vector3D> mGrad; 382 double initialGradL2NormSquared; 383 double currentGradL2NormSquared; 384 double gradL2NormAbsoluteEpsSquared; 385 double gradL2NormRelativeEpsSquared; 386 double initialGradInfNorm; 387 double currentGradInfNorm; 388 double gradInfNormAbsoluteEps; 389 double gradInfNormRelativeEps; 390 //Data specific to termination criterion 2 (KKT) 391 //??????????????????????????????????????????? 392 //Data specific to termination criterion 3 (Quality Improvement) 393 double qualityImprovementAbsoluteEps; 394 double qualityImprovementRelativeEps; 395 //Data specific to termination criterion 4 (inner iterations) 396 int iterationBound; 397 int iterationCounter; 398 //Data specific to termination criterion 5 (cpu time) 399 Timer mTimer; 400 double timeBound; 401 //Data specific to termination criterion 6 (vertex movement) 402 PatchDataVerticesMemento* initialVerticesMemento; 403 PatchDataVerticesMemento* previousVerticesMemento;//if we want relative 404 double vertexMovementAbsoluteEps; 405 double vertexMovementRelativeEps; 406 double vertexMovementAvgBeta; //!< input beta value used to calculate \c vertexMovementAbsoluteAvg 407 double vertexMovementAbsoluteAvgEdge; //!< calculated constant for \c VERTEX_MOVEMENT_ABS_EDGE_LENGTH 408 double maxSquaredInitialMovement; 409 double maxSquaredMovement; 410 411 //Data specific to termination criterion 7 (successive improvement to F) 412 double successiveImprovementsAbsoluteEps; 413 double successiveImprovementsRelativeEps; 414 //crit 8 415 double boundedVertexMovementEps; 416 int vertexMovementExceedsBound; 417 418 // Data for untangled criterion 419 size_t globalInvertedCount; //!< number of inverted elements in entire mesh 420 size_t patchInvertedCount; //!< number of inverted elements in previously tested patch 421 422 int debugLevel; 423 424 //! Plot data 425 std::ofstream plotFile; 426 427 //! Base name for timestep files 428 std::string timeStepFileName; 429 TimeStepFileType timeStepFileType; 430 std::string moniker; 431 InnerOuterType innerOuterType; 432 }; 433 434 } //namespace 435 436 437 #endif // TerminationCriterion_hpp 438