Branch data Line data Source code
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 : : [email protected], [email protected], [email protected],
24 : : [email protected], [email protected], [email protected]
25 : :
26 : : ***************************************************************** */
27 : : // -*- Mode : c++; tab-width: 3; c-tab-always-indent: t; indent-tabs-mode: nil; c-basic-offset: 3
28 : : // -*-
29 : :
30 : : /*! \file TerminationCriterion.hpp
31 : :
32 : : Header file for the TerminationCriterion classes.
33 : :
34 : : \author Michael Brewer
35 : : \author Thomas Leurent
36 : : \date Feb. 14, 2003
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 : : //! checks the gradient \f$\nabla f \f$ of objective function
125 : : //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$
126 : : //! and stops when \f$\sqrt{\sum_{i=1}^{3N}\nabla f_i^2}<d\f$
127 : : MESQUITE_EXPORT void add_absolute_gradient_L2_norm( double value );
128 : :
129 : : //! checks the gradient \f$\nabla f \f$ of objective function
130 : : //! \f$f : I\!\!R^{3N} \rightarrow I\!\!R \f$ against a double \f$d\f$
131 : : //! and stops when \f$ \max_{i=1}^{3N} \nabla f_i < d \f$
132 : : MESQUITE_EXPORT void add_absolute_gradient_inf_norm( double value );
133 : :
134 : : //! terminates on the j_th iteration when
135 : : //! \f$\sqrt{\sum_{i=1}^{3N}\nabla f_{i,j}^2}<d\sqrt{\sum_{i=1}^{3N}\nabla f_{i,0}^2}\f$
136 : : //! That is, terminates when the norm of the gradient is smaller
137 : : //! than the specified fraction of the initial norm of the gradient.
138 : : MESQUITE_EXPORT void add_relative_gradient_L2_norm( double value );
139 : :
140 : : //! terminates on the j_th iteration when
141 : : //! \f$\max_{i=1 \cdots 3N}\nabla f_{i,j}<d \max_{i=1 \cdots 3N}\nabla f_{i,0}\f$
142 : : //! That is, terminates when the norm of the gradient is small
143 : : //! than some scaling factor times the norm of the original gradient.
144 : : //! (Using the infinity norm.)
145 : : MESQUITE_EXPORT void add_relative_gradient_inf_norm( double value );
146 : :
147 : : //! Terminates when the objective function value is smaller than
148 : : //! the given scalar value.
149 : : MESQUITE_EXPORT void add_absolute_quality_improvement( double value );
150 : :
151 : : //! Terminates when the objective function value is smaller than
152 : : //! the given scalar value times the original objective function
153 : : //! value.
154 : : MESQUITE_EXPORT void add_relative_quality_improvement( double value );
155 : :
156 : : //! Terminates when a the maximum distance moved by any vertex
157 : : //! during the previous iteration is below the given value.
158 : : MESQUITE_EXPORT void add_absolute_vertex_movement( double value );
159 : :
160 : : //! Terminates when a the maximum distance moved by any vertex
161 : : //! during the previous iteration is below the given value
162 : : //! times the maximum distance moved by any vertex over the
163 : : //! entire course of the optimization.
164 : : MESQUITE_EXPORT void add_relative_vertex_movement( double value );
165 : :
166 : : //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$
167 : : //! and terminates when the maximum vertex movement of an iteration
168 : : //! is less than delta.
169 : : //!
170 : : //! \f$ \beta \f$ is the passed value, \f$ a \f$
171 : : //! is the average edge length of the initial mesh and \f$ \sigma \f$
172 : : //! is the standard deviation of the edge lengths of the initial
173 : : //! mesh. The initial mesh values are (re)calcualted for each
174 : : //! time the instruction queue is run.
175 : : //!
176 : : //!\param value \f$ beta \f$. Must be in range (0,1), exclusive.
177 : : MESQUITE_EXPORT void add_absolute_vertex_movement_edge_length( double value );
178 : :
179 : : //! Terminates when the decrease in the objective function value since
180 : : //! the previous iteration is below the given value.
181 : : MESQUITE_EXPORT void add_absolute_successive_improvement( double value );
182 : :
183 : : //! Terminates when the decrease in the objective function value since
184 : : //! the previous iteration is below the given value times the
185 : : //! decrease in the objective function value since the beginning
186 : : //! of this optimization process.
187 : : MESQUITE_EXPORT void add_relative_successive_improvement( double value );
188 : :
189 : : //! Terminates when the algorithm exceeds an allotted time limit
190 : : //! (given in seconds).
191 : : MESQUITE_EXPORT void add_cpu_time( double seconds );
192 : :
193 : : //! Terminates when the number of iterations exceeds a given integer.
194 : : MESQUITE_EXPORT void add_iteration_limit( unsigned int max_iterations );
195 : :
196 : : //! Terminates when any vertex leaves the bounding box, defined
197 : : //! by the given value, d. That is, when the absolute value of
198 : : //! a single coordinate of vertex's position exceeds d.
199 : : MESQUITE_EXPORT void add_bounded_vertex_movement( double value );
200 : :
201 : : //! Terminates when the mesh is detected to be untangled.
202 : : //! Uses the same approach as QualityAssessor,
203 : : //! checks the tau values at all the sample points.
204 : : MESQUITE_EXPORT void add_untangled_mesh();
205 : :
206 : : MESQUITE_EXPORT void remove_all_criteria();
207 : :
208 : : //! Cull when the objective function value is smaller than
209 : : //! the given scalar value.
210 : : MESQUITE_EXPORT void cull_on_absolute_quality_improvement( double limit );
211 : : //! Cull when the objective function value is smaller than
212 : : //! the given scalar value times the original objective function
213 : : //! value.
214 : : MESQUITE_EXPORT void cull_on_relative_quality_improvement( double limit );
215 : : //! Cull when a the maximum distance moved by any vertex
216 : : //! during the previous iteration is below the given value.
217 : : MESQUITE_EXPORT void cull_on_absolute_vertex_movement( double limit );
218 : : //! Cull when a the maximum distance moved by any vertex
219 : : //! during the previous iteration is below the given value
220 : : //! times the maximum distance moved by any vertex over the
221 : : //! entire course of the optimization.
222 : : MESQUITE_EXPORT void cull_on_relative_vertex_movement( double limit );
223 : : //! Cull when the decrease in the objective function value since
224 : : //! the previous iteration is below the given value.
225 : : MESQUITE_EXPORT void cull_on_absolute_successive_improvement( double limit );
226 : : //! Calculates a constant \f$ \delta = \beta \times (a - \sigma) \f$
227 : : //! and culls when the vertex movement is less than delta.
228 : : //!
229 : : //! \f$ \beta \f$ is the passed value, \f$ a \f$
230 : : //! is the average edge length of the initial mesh and \f$ \sigma \f$
231 : : //! is the standard deviation of the edge lengths of the initial
232 : : //! mesh. The initial mesh values are (re)calcualted for each
233 : : //! time the instruction queue is run.
234 : : //!
235 : : //!\param value \f$ beta \f$. Must be in range (0,1), exclusive.
236 : : MESQUITE_EXPORT void cull_on_absolute_vertex_movement_edge_length( double value );
237 : : //! Cull when the decrease in the objective function value since
238 : : //! the previous iteration is below the given value times the
239 : : //! decrease in the objective function value since the beginning
240 : : //! of this optimization process.
241 : : MESQUITE_EXPORT void cull_on_relative_successive_improvement( double limit );
242 : :
243 : : //! Cull for a global patch - sets soft fixed flags for vertices
244 : : //! that touch elements that are culled by above flags.
245 : : MESQUITE_EXPORT void cull_for_global_patch( bool val = true );
246 : :
247 : : //! Cull when the mesh is detected to be untangled.
248 : : //! Uses the same approach as QualityAssessor,
249 : : //! checks the tau values at all the sample points.
250 : : MESQUITE_EXPORT void cull_untangled_mesh();
251 : :
252 : : MESQUITE_EXPORT void remove_culling();
253 : :
254 : : enum InnerOuterType
255 : : {
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
265 : 1090 : 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.*/
272 : : MESQUITE_EXPORT double get_current_function_value()
273 : : {
274 : : return currentOFValue;
275 : : }
276 : :
277 : 34 : MESQUITE_EXPORT void set_debug_output_level( int i )
278 : : {
279 : 34 : debugLevel = i;
280 : 34 : }
281 : :
282 : : enum TimeStepFileType
283 : : {
284 : : NOTYPE = 0,
285 : : VTK,
286 : : GNUPLOT
287 : : };
288 : :
289 : : /**\brief Write mesh improvement animation
290 : : *
291 : : * Write mesh at each iteration such that the sequence of mesh files can be used
292 : : * to produce an animation of the mesh through the quality improvement process.
293 : : *
294 : : * Files can be written either as VTK timesteps for viewing in a tool such as Paraview
295 : : * or as GNU plot data files and a GNU plot script which, in combination with recent
296 : : * versions of GNU plot, can be used to produce an animated GIF image.
297 : : *
298 : : * Writing of mesh steps can be disabled by calling this function with type == NOTYPE
299 : : * and filename ==NULL.
300 : : */
301 : 1 : MESQUITE_EXPORT void write_mesh_steps( const char* filename, TimeStepFileType type = VTK )
302 : : {
303 : 1 : timeStepFileName = filename;
304 : 1 : timeStepFileType = type;
305 : 1 : }
306 : :
307 : : /*\brief Write data for generating plots of optimization process.
308 : : *
309 : : * Write data files in a format suitable for use with GNU plot and other applications.
310 : : * The file will contain data corresponding to all termination criteria,
311 : : * however, some values may be invalid if they are not calculated for
312 : : * use in a termination criterion.
313 : : */
314 : : MESQUITE_EXPORT void write_iterations( const char* filename, MsqError& err );
315 : :
316 : 1 : MESQUITE_EXPORT int get_iteration_count() const
317 : : {
318 : 1 : return iterationCounter;
319 : : }
320 : :
321 : : //! Clear any data accumulated during an outer iteration
322 : : void reset_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& of, const Settings* settings, MsqError& err );
323 : :
324 : : //! Clear any data accumulated during an inner iteration
325 : : void reset_inner( PatchData& pd, OFEvaluator& of, MsqError& err );
326 : :
327 : : //! Shared inner and outer initialization during inner loop
328 : : void reset_patch( PatchData& pd, MsqError& err );
329 : :
330 : : //! Accumulate data during inner iteration
331 : : void accumulate_inner( PatchData& pd, OFEvaluator& eval, MsqError& err );
332 : :
333 : : //! Accumulate data during inner iteration
334 : : void accumulate_inner( PatchData& pd, double of_value, Vector3D* of_grads, MsqError& err );
335 : :
336 : : //! Common code for both inner and outer termination
337 : : //! criteria during inner iteration.
338 : : void accumulate_patch( PatchData& pd, MsqError& err );
339 : :
340 : : void accumulate_outer( Mesh* ms, MeshDomain* dm, OFEvaluator& eval, const Settings* settings, MsqError& err );
341 : :
342 : : //! Check if termination criterion has been met
343 : : MESQUITE_EXPORT bool terminate();
344 : :
345 : : //! Check if at least one termination criterion is set
346 : : MESQUITE_EXPORT bool criterion_is_set();
347 : :
348 : : //! Function which determines whether this patch should be 'culled'
349 : : bool cull_vertices( PatchData& pd, OFEvaluator& obj_ptr, MsqError& err );
350 : :
351 : : //! experimental, first cut at culling for global patches - not finished
352 : : bool cull_vertices_global( PatchData& global_patch, Mesh* mesh, MeshDomain* domain, const Settings* settings,
353 : : OFEvaluator& of_eval, MsqError& err );
354 : :
355 : : //! Cleans up after the TerminationCriterion is finished.
356 : : void cleanup( Mesh* ms, MeshDomain* domain, MsqError& err );
357 : :
358 : : void initialize_queue( MeshDomainAssoc* mesh_and_domain, const Settings* settings, MsqError& err );
359 : :
360 : : friend class VertexMover;
361 : :
362 : : protected:
363 : : void write_timestep( PatchData& pd, const Vector3D* gradient, MsqError& err );
364 : :
365 : : static size_t count_inverted( PatchData& pd, MsqError& err );
366 : :
367 : : std::string par_string(); // for debug print of parallel rank
368 : :
369 : : private:
370 : : // PRIVATE DATA MEMBERS
371 : : long unsigned int terminationCriterionFlag; //!< Bit flag of termination crit
372 : : long unsigned int cullingMethodFlag; /*!<Bit flag of criterion for culling*/
373 : : // epsiloon used in culling methods.
374 : : double cullingEps;
375 : :
376 : : bool cullingGlobalPatch; /*!<enable culling of pieces of a global patch*/
377 : :
378 : : // Data not specific to a single criterion
379 : : double initialOFValue;
380 : : double previousOFValue;
381 : : double currentOFValue;
382 : : double lowerOFBound;
383 : :
384 : : // Data specific to termination criterion 1 (gradient bounds)
385 : : std::vector< Vector3D > mGrad;
386 : : double initialGradL2NormSquared;
387 : : double currentGradL2NormSquared;
388 : : double gradL2NormAbsoluteEpsSquared;
389 : : double gradL2NormRelativeEpsSquared;
390 : : double initialGradInfNorm;
391 : : double currentGradInfNorm;
392 : : double gradInfNormAbsoluteEps;
393 : : double gradInfNormRelativeEps;
394 : : // Data specific to termination criterion 2 (KKT)
395 : : //???????????????????????????????????????????
396 : : // Data specific to termination criterion 3 (Quality Improvement)
397 : : double qualityImprovementAbsoluteEps;
398 : : double qualityImprovementRelativeEps;
399 : : // Data specific to termination criterion 4 (inner iterations)
400 : : int iterationBound;
401 : : int iterationCounter;
402 : : // Data specific to termination criterion 5 (cpu time)
403 : : Timer mTimer;
404 : : double timeBound;
405 : : // Data specific to termination criterion 6 (vertex movement)
406 : : PatchDataVerticesMemento* initialVerticesMemento;
407 : : PatchDataVerticesMemento* previousVerticesMemento; // if we want relative
408 : : double vertexMovementAbsoluteEps;
409 : : double vertexMovementRelativeEps;
410 : : double vertexMovementAvgBeta; //!< input beta value used to calculate \c vertexMovementAbsoluteAvg
411 : : double vertexMovementAbsoluteAvgEdge; //!< calculated constant for \c
412 : : //!< VERTEX_MOVEMENT_ABS_EDGE_LENGTH
413 : : double maxSquaredInitialMovement;
414 : : double maxSquaredMovement;
415 : :
416 : : // Data specific to termination criterion 7 (successive improvement to F)
417 : : double successiveImprovementsAbsoluteEps;
418 : : double successiveImprovementsRelativeEps;
419 : : // crit 8
420 : : double boundedVertexMovementEps;
421 : : int vertexMovementExceedsBound;
422 : :
423 : : // Data for untangled criterion
424 : : size_t globalInvertedCount; //!< number of inverted elements in entire mesh
425 : : size_t patchInvertedCount; //!< number of inverted elements in previously tested patch
426 : :
427 : : int debugLevel;
428 : :
429 : : //! Plot data
430 : : std::ofstream plotFile;
431 : :
432 : : //! Base name for timestep files
433 : : std::string timeStepFileName;
434 : : TimeStepFileType timeStepFileType;
435 : : std::string moniker;
436 : : InnerOuterType innerOuterType;
437 : : };
438 : :
439 : : } // namespace MBMesquite
440 : :
441 : : #endif // TerminationCriterion_hpp
|
