Debian Codegraph @

include/deal.II/lac/solver_fire.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2017 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_solver_fire_h
16 #define dealii_solver_fire_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/logstream.h>
22 #include <deal.II/base/template_constraints.h>
23
24 #include <deal.II/lac/diagonal_matrix.h>
25 #include <deal.II/lac/solver.h>
26
27 #include <functional>
28
29
30 DEAL_II_NAMESPACE_OPEN
31
32
33 /**
34 * @addtogroup Solvers
35 * @{
36 */
37
38 /**
39 * FIRE (Fast Inertial Relaxation Engine) for minimization of (potentially
40 * non-linear) objective function $E(\mathbf x)$, $\mathbf x$ is a vector of
41 * $n$ variables ($n$ is the number of variables of the objective function).
42 * Like all other solver classes, it can work on any kind of vector and matrix
43 * as long as they satisfy certain requirements (for the requirements on
44 * matrices and vectors in order to work with this class, see the documentation
45 * of the Solver base class). The type of the solution vector must be passed as
46 * template argument, and defaults to dealii::Vector<double>.
47 *
48 * FIRE is a damped dynamics method described in
49 * <a href="https://doi.org/10.1103/PhysRevLett.97.170201">Structural
50 * Relaxation Made Simple</a> by Bitzek et al. 2006, typically used to find
51 * stable equilibrium configurations of atomistic systems in computational
52 * material science. Starting from a given initial configuration of the
53 * atomistic system, the algorithm relies on inertia to obtain (nearest)
54 * configuration with least potential energy.
55 *
56 * Notation:
57 * - The global vector of unknown variables: $\mathbf x$.
58 * - Objective function: $E(\mathbf x)$.
59 * - Rate of change of unknowns: $\mathbf v$.
60 * - Gradient of the objective
61 * function w.r.t unknowns: $\mathbf g = \nabla E(\mathbf x)$.
62 * - Mass matrix: $\mathbf M$.
63 * - Initial guess of unknowns: $\mathbf x_0$.
64 * - Time step: $\Delta t$.
65 *
66 * Given initial values for $\Delta t$, $\alpha = \alpha_0$, $\epsilon$,
67 * $\mathbf x = \mathbf x_0$ and $\mathbf v= \mathbf 0$ along with a given mass
68 * matrix $\mathbf M$, FIRE algorithm is as follows,
69 * 1. Calculate $\mathbf g = \nabla E(\mathbf x)$ and check for convergence
70 * ($\mathbf g \cdot \mathbf g < \epsilon^2 $).
71 * 2. Update $\mathbf x$ and $V$ using simple (forward) Euler integration step,
72 * <BR>
73 * $\mathbf x = \mathbf x + \Delta t \mathbf v$, <BR>
74 * $\mathbf v = \mathbf v + \Delta t \mathbf M^{-1} \cdot \mathbf g$.
75 * 3. Calculate $p = \mathbf g \cdot \mathbf v$.
76 * 4. Set $\mathbf v = (1-\alpha) \mathbf v
77 * + \alpha \frac{|\mathbf v|}{|\mathbf g|} \mathbf g$.
78 * 5. If $p<0$ and number of steps since $p$ was last negative is larger
79 * than certain value, then increase time step $\Delta t$ and decrease
80 * $\alpha$.
81 * 6. If $p>0$, then decrease the time step, freeze the system i.e.,
82 * $\mathbf v = \mathbf 0$ and reset $\alpha = \alpha_0$.
83 * 7. Return to 1.
84 *
85 * Also see
86 * <a href="http://onlinelibrary.wiley.com/doi/10.1002/pamm.201110246/full">
87 * Energy-Minimization in Atomic-to-Continuum Scale-Bridging Methods </a> by
88 * Eidel et al. 2011.
89 */
90 template <typename VectorType = Vector<double>>
91 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
92 class SolverFIRE : public SolverBase<VectorType>
93 {
94 public:
95 /**
96 * Standardized data struct to pipe additional data to the solver.
97 */
98 struct AdditionalData
99 {
100 /**
101 * Constructor. By default, set the initial time step for the (forward)
102 * Euler integration step to 0.1, the maximum time step to 1 and the
103 * maximum change allowed in any variable (per iteration) to 1.
104 */
105 explicit AdditionalData(const double initial_timestep = 0.1,
106 const double maximum_timestep = 1,
107 const double maximum_linfty_norm = 1);
108
109 /**
110 * Initial time step for the (forward) Euler integration step.
111 */
112 const double initial_timestep;
113
114 /**
115 * Maximum time step for the (forward) Euler integration step.
116 */
117 const double maximum_timestep;
118
119 /**
120 * Maximum change allowed in any variable of the objective function.
121 */
122 const double maximum_linfty_norm;
123 };
124
125 /**
126 * Constructor.
127 */
128 SolverFIRE(SolverControl &solver_control,
129 VectorMemory<VectorType> &vector_memory,
130 const AdditionalData &data = AdditionalData());
131
132 /**
133 * Constructor. Use an object of type GrowingVectorMemory as a default to
134 * allocate memory.
135 */
136 SolverFIRE(SolverControl &solver_control,
137 const AdditionalData &data = AdditionalData());
138
139 /**
140 * Obtain a set of variables @p x that minimize an objective function
141 * described by the polymorphic function wrapper @p compute, with a given
142 * preconditioner @p inverse_mass_matrix and initial @p x values.
143 * The function @p compute returns the objective function's value and updates
144 * the objective function's gradient (with respect to the variables) when
145 * passed in as first argument based on the second argument-- the state of
146 * variables.
147 */
148 template <typename PreconditionerType = DiagonalMatrix<VectorType>>
149 void
150 solve(const std::function<double(VectorType &, const VectorType &)> &compute,
151 VectorType &x,
152 const PreconditionerType &inverse_mass_matrix);
153
154 /**
155 * Solve for x that minimizes $E(\mathbf x)$ for the <EM>special case</EM>
156 * when $E(\mathbf x)
157 * = \frac{1}{2} \mathbf x^{T} \mathbf A \mathbf x - \mathbf x^{T} \mathbf b$.
158 */
159 template <typename MatrixType, typename PreconditionerType>
160 DEAL_II_CXX20_REQUIRES(
161 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
162 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
163 void solve(const MatrixType &A,
164 VectorType &x,
165 const VectorType &b,
166 const PreconditionerType &preconditioner);
167
168 protected:
169 /**
170 * Interface for derived class. This function gets the current iteration
171 * @p x (variables), @p v (x's time derivative) and @p g (the gradient) in
172 * each step.
173 * It can be used for graphical output of the convergence history.
174 */
175 virtual void
176 print_vectors(const unsigned int,
177 const VectorType &x,
178 const VectorType &v,
179 const VectorType &g) const;
180
181 /**
182 * Additional data to the solver.
183 */
184 const AdditionalData additional_data;
185 };
186
187 /** @} */
188
189 /*------------------------- Implementation ----------------------------*/
190
191 #ifndef DOXYGEN
192
193 template <typename VectorType>
194 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
195 SolverFIRE<VectorType>::AdditionalData::AdditionalData(
196 const double initial_timestep,
197 const double maximum_timestep,
198 const double maximum_linfty_norm)
199 : initial_timestep(initial_timestep)
200 , maximum_timestep(maximum_timestep)
201 , maximum_linfty_norm(maximum_linfty_norm)
202 {
203 AssertThrow(initial_timestep > 0. && maximum_timestep > 0. &&
204 maximum_linfty_norm > 0.,
205 ExcMessage("Expected positive values for initial_timestep, "
206 "maximum_timestep and maximum_linfty_norm but one "
207 "or more of the these values are not positive."));
208 }
209
210
211
212 template <typename VectorType>
213 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
214 SolverFIRE<VectorType>::SolverFIRE(SolverControl &solver_control,
215 VectorMemory<VectorType> &vector_memory,
216 const AdditionalData &data)
217 : SolverBase<VectorType>(solver_control, vector_memory)
218 , additional_data(data)
219 {}
220
221
222
223 template <typename VectorType>
224 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
225 SolverFIRE<VectorType>::SolverFIRE(SolverControl &solver_control,
226 const AdditionalData &data)
227 : SolverBase<VectorType>(solver_control)
228 , additional_data(data)
229 {}
230
231
232
233 template <typename VectorType>
234 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
235 template <typename PreconditionerType>
236 void SolverFIRE<VectorType>::solve(
237 const std::function<double(VectorType &, const VectorType &)> &compute,
238 VectorType &x,
239 const PreconditionerType &inverse_mass_matrix)
240 {
241 LogStream::Prefix prefix("FIRE");
242
243 // FIRE algorithm constants
244 const double DELAYSTEP = 5;
245 const double TIMESTEP_GROW = 1.1;
246 const double TIMESTEP_SHRINK = 0.5;
247 const double ALPHA_0 = 0.1;
248 const double ALPHA_SHRINK = 0.99;
249
250 using real_type = typename VectorType::real_type;
251
252 typename VectorMemory<VectorType>::Pointer v(this->memory);
253 typename VectorMemory<VectorType>::Pointer g(this->memory);
254
255 // Set velocities to zero but not gradients
256 // as we are going to compute them soon.
257 v->reinit(x, false);
258 g->reinit(x, true);
259
260 // Refer to v and g with some readable names.
261 VectorType &velocities = *v;
262 VectorType &gradients = *g;
263
264 // Update gradients for the new x.
265 compute(gradients, x);
266
267 unsigned int iter = 0;
268
269 SolverControl::State conv = SolverControl::iterate;
270 conv = this->iteration_status(iter, gradients * gradients, x);
271 if (conv != SolverControl::iterate)
272 return;
273
274 // Refer to additional data members with some readable names.
275 const auto &maximum_timestep = additional_data.maximum_timestep;
276 double timestep = additional_data.initial_timestep;
277
278 // First scaling factor.
279 double alpha = ALPHA_0;
280
281 unsigned int previous_iter_with_positive_v_dot_g = 0;
282
283 while (conv == SolverControl::iterate)
284 {
285 ++iter;
286 // Euler integration step.
287 x.add(timestep, velocities); // x += dt * v
288 inverse_mass_matrix.vmult(gradients, gradients); // g = M^{-1} * g
289 velocities.add(-timestep, gradients); // v -= dt * h
290
291 // Compute gradients for the new x.
292 compute(gradients, x);
293
294 const real_type gradient_norm_squared = gradients * gradients;
295 conv = this->iteration_status(iter, gradient_norm_squared, x);
296 if (conv != SolverControl::iterate)
297 break;
298
299 // v_dot_g = V * G
300 const real_type v_dot_g = velocities * gradients;
301
302 if (v_dot_g < 0.)
303 {
304 const real_type velocities_norm_squared = velocities * velocities;
305
306 // Check if we divide by zero in DEBUG mode.
307 Assert(gradient_norm_squared > 0., ExcInternalError());
308
309 // beta = - alpha |V|/|G|
310 const real_type beta =
311 -alpha * std::sqrt(velocities_norm_squared / gradient_norm_squared);
312
313 // V = (1-alpha) V + beta G.
314 velocities.sadd(1. - alpha, beta, gradients);
315
316 if (iter - previous_iter_with_positive_v_dot_g > DELAYSTEP)
317 {
318 // Increase timestep and decrease alpha.
319 timestep = std::min(timestep * TIMESTEP_GROW, maximum_timestep);
320 alpha *= ALPHA_SHRINK;
321 }
322 }
323 else
324 {
325 // Decrease timestep, reset alpha and set V = 0.
326 previous_iter_with_positive_v_dot_g = iter;
327 timestep *= TIMESTEP_SHRINK;
328 alpha = ALPHA_0;
329 velocities = 0.;
330 }
331
332 real_type vmax = velocities.linfty_norm();
333
334 // Change timestep if any dof would move more than maximum_linfty_norm.
335 if (vmax > 0.)
336 {
337 const double minimal_timestep =
338 additional_data.maximum_linfty_norm / vmax;
339 if (minimal_timestep < timestep)
340 timestep = minimal_timestep;
341 }
342
343 print_vectors(iter, x, velocities, gradients);
344
345 } // While we need to iterate.
346
347 // In the case of failure: throw exception.
348 if (conv != SolverControl::success)
349 AssertThrow(false,
350 SolverControl::NoConvergence(iter, gradients * gradients));
351 }
352
353
354
355 template <typename VectorType>
356 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
357 template <typename MatrixType, typename PreconditionerType>
358 DEAL_II_CXX20_REQUIRES(
359 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
360 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
361 void SolverFIRE<VectorType>::solve(const MatrixType &A,
362 VectorType &x,
363 const VectorType &b,
364 const PreconditionerType &preconditioner)
365 {
366 std::function<double(VectorType &, const VectorType &)> compute_func =
367 [&](VectorType &g, const VectorType &x) -> double {
368 // Residual of the quadratic form $ \frac{1}{2} xAx - xb $.
369 // G = b - Ax
370 A.residual(g, x, b);
371
372 // Gradient G = Ax -b.
373 g *= -1.;
374
375 // The quadratic form $\frac{1}{2} xAx - xb $.
376 return 0.5 * A.matrix_norm_square(x) - x * b;
377 };
378
379 this->solve(compute_func, x, preconditioner);
380 }
381
382
383
384 template <typename VectorType>
385 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
386 void SolverFIRE<VectorType>::print_vectors(const unsigned int,
387 const VectorType &,
388 const VectorType &,
389 const VectorType &) const
390 {}
391
392
393
394 #endif // DOXYGEN
395
396 DEAL_II_NAMESPACE_CLOSE
397
398 #endif