Block-Structured AMR Software Framework
Loading...
Searching...
No Matches
AMReX_GMRES.H
Go to the documentation of this file.
1#ifndef AMREX_GMRES_H_
2#define AMREX_GMRES_H_
3#include <AMReX_Config.H>
4
5#include <AMReX_BLProfiler.H>
6#include <AMReX_Print.H>
7#include <AMReX_TableData.H>
8#include <AMReX_Vector.H>
9#include <cmath>
10#include <limits>
11#include <memory>
12
13namespace amrex {
14
20
86template <typename V, typename M>
87class GMRES
88{
89public:
90
91 using RT = typename M::RT; // double or float
92
95
104 void define (M& linop);
105
119 void solve (V& a_sol, V const& a_rhs, RT a_tol_rel, RT a_tol_abs, int a_its=-1);
120
123 void setInitialGuessNonzero (bool flag) { m_nonzero_guess = flag; }
124
126 void setVerbose (int v) { m_verbose = v; }
127
135 void setFlexible (bool flag) { m_flexible = flag; }
137 [[nodiscard]] bool getFlexible () const { return m_flexible; }
138
144 void setRestartLength (int rl);
145
151 void setMaxIters (int niters) { m_maxiter = niters; }
152
154 [[nodiscard]] int getNumIters () const { return m_its; }
155
157 [[nodiscard]] int getStatus () const { return m_status; }
158
160 [[nodiscard]] RT getResidualNorm () const { return m_res; }
161
163 [[nodiscard]] RT getInitialResidualNorm () const { return m_rnorm0; }
164
165private:
166 void clear ();
167 void allocate_scratch ();
168 void cycle (V& a_xx, int& a_status, int& a_itcount, RT& a_rnorm0, int a_maxiter);
169 void build_solution (V& a_xx, int it);
170 void compute_residual (V& a_rr, V const& a_xx, V const& a_bb);
171
172 [[nodiscard]] bool converged (RT r0, RT r) const;
173
174 void gram_schmidt_orthogonalization (int it);
175 void update_hessenberg (int it, bool happyend, RT& res);
176
177 int m_verbose = 0;
178 int m_maxiter = 2000;
179 int m_its = 0;
180 int m_status = -1;
181 int m_restrtlen = 30;
182 bool m_nonzero_guess = false;
183 bool m_flexible = false;
184 RT m_res = std::numeric_limits<RT>::max();
185 RT m_rnorm0 = std::numeric_limits<RT>::max();
186 RT m_rtol = RT(0);
187 RT m_atol = RT(0);
188 Vector<RT> m_hh_1d;
189 Vector<RT> m_hes_1d;
190 Table2D<RT> m_hh;
191 Table2D<RT> m_hes;
192 Vector<RT> m_grs;
193 Vector<RT> m_cc;
194 Vector<RT> m_ss;
195 std::unique_ptr<V> m_v_tmp_rhs;
196 std::unique_ptr<V> m_v_tmp_lhs;
197 Vector<V> m_vv;
198 Vector<V> m_zz; // preconditioned vectors, FGMRES only
199 M* m_linop = nullptr;
200};
201
202template <typename V, typename M>
204{
205 allocate_scratch();
206}
207
208template <typename V, typename M>
209void GMRES<V,M>::allocate_scratch ()
210{
211 int rs = m_restrtlen;
212
213 m_hh_1d.resize(std::size_t(rs + 2) * (rs + 1));
214 m_hh = Table2D<RT>(m_hh_1d.data(), {0,0}, {rs+1,rs}); // (0:rs+1,0:rs)
215
216 m_hes_1d.resize(std::size_t(rs + 2) * (rs + 1));
217 m_hes = Table2D<RT>(m_hes_1d.data(), {0,0}, {rs+1,rs}); // (0:rs+1,0:rs)
218
219 m_grs.resize(rs + 2);
220 m_cc.resize(rs + 1);
221 m_ss.resize(rs + 1);
222}
223
224template <typename V, typename M>
226{
227 if (m_restrtlen != rl) {
228 m_restrtlen = rl;
229 allocate_scratch();
230 m_vv.clear();
231 m_zz.clear();
232 }
233}
234
235template <typename V, typename M>
236void GMRES<V,M>::define (M& linop)
237{
238 clear();
239 m_linop = &linop;
240}
241
242template <typename V, typename M>
243void GMRES<V,M>::clear ()
244{
245 m_its = 0;
246 m_status = -1;
247 m_res = std::numeric_limits<RT>::max();
248 m_v_tmp_rhs.reset();
249 m_v_tmp_lhs.reset();
250 m_vv.clear();
251 m_zz.clear();
252 m_linop = nullptr;
253}
254
255template <typename V, typename M>
256bool GMRES<V,M>::converged (RT r0, RT r) const
257{
258 return (r < r0*m_rtol) || (r < m_atol);
259}
260
261template <typename V, typename M>
262void GMRES<V,M>::solve (V& a_sol, V const& a_rhs, RT a_tol_rel, RT a_tol_abs, int a_its)
263{
264 BL_PROFILE("GMRES::solve()");
265
266 AMREX_ALWAYS_ASSERT(m_linop != nullptr);
267
268 auto t0 = amrex::second();
269
270 if (m_v_tmp_rhs == nullptr) {
271 m_v_tmp_rhs = std::make_unique<V>(m_linop->makeVecRHS());
272 }
273 if (m_v_tmp_lhs == nullptr) {
274 m_v_tmp_lhs = std::make_unique<V>(m_linop->makeVecLHS());
275 }
276 if (m_vv.empty()) {
277 m_vv.reserve(m_restrtlen+1);
278 for (int i = 0; i < 2; ++i) { // to save space, start with just 2
279 m_vv.emplace_back(m_linop->makeVecRHS());
280 }
281 }
282
283 m_rtol = a_tol_rel;
284 m_atol = a_tol_abs;
285
286 if (a_its < 0) { a_its = m_maxiter; }
287
288 auto rnorm0 = RT(0);
289
290 if (m_nonzero_guess) {
291 compute_residual(m_vv[0], a_sol, a_rhs);
292 } else {
293 m_linop->assign(m_vv[0], a_rhs);
294 m_linop->setToZero(a_sol);
295 }
296
297 m_its = 0;
298 m_status = -1;
299 cycle(a_sol, m_status, m_its, rnorm0, a_its);
300
301 while (m_status == -1 && m_its < a_its) {
302 compute_residual(m_vv[0], a_sol, a_rhs);
303 cycle(a_sol, m_status, m_its, rnorm0, a_its);
304 }
305
306 if (m_status == -1 && m_its >= a_its) { m_status = 1; }
307 m_rnorm0 = rnorm0;
308
309 m_v_tmp_rhs.reset();
310 m_v_tmp_lhs.reset();
311 m_vv.clear();
312 m_zz.clear();
313
314 auto t1 = amrex::second();
315 if (m_verbose > 0) {
316 amrex::Print() << "GMRES: Solve Time = " << t1-t0 << '\n';
317 }
318}
319
320template <typename V, typename M>
321void GMRES<V,M>::cycle (V& a_xx, int& a_status, int& a_itcount, RT& a_rnorm0, int a_maxiter)
322{
323 BL_PROFILE("GMRES::cycle()");
324
325 m_res = m_linop->norm2(m_vv[0]);
326 m_grs[0] = m_res;
327
328 if (m_res == RT(0.0)) {
329 a_status = 0;
330 return;
331 }
332
333 m_linop->scale(m_vv[0], RT(1.0)/m_res);
334
335 if (a_itcount == 0) { a_rnorm0 = m_res; }
336
337 a_status = converged(a_rnorm0,m_res) ? 0 : -1;
338
339 int it = 0;
340 while (it < m_restrtlen && a_itcount < a_maxiter)
341 {
342 if (m_verbose > 1) {
343 amrex::Print() << "GMRES: iter = " << a_itcount
344 << ", residual = " << m_res << ", " << m_res/a_rnorm0
345 << " (rel.)\n";
346 }
347
348 if (a_status == 0) { break; }
349
350 while (m_vv.size() < it+2) {
351 m_vv.emplace_back(m_linop->makeVecRHS());
352 }
353
354 if (m_flexible) {
355 if (m_zz.empty()) { m_zz.reserve(m_restrtlen); }
356 while (m_zz.size() < it+1) {
357 m_zz.emplace_back(m_linop->makeVecLHS());
358 }
359 }
360
361 auto const& vv_it = m_vv[it ];
362 auto & vv_it1 = m_vv[it+1];
363 auto & zz_it = m_flexible ? m_zz[it] : *m_v_tmp_lhs;
364
365 m_linop->precond(zz_it, vv_it);
366 m_linop->apply(vv_it1, zz_it);
367
368 gram_schmidt_orthogonalization(it);
369
370 auto tt = m_linop->norm2(vv_it1);
371
372 auto const sml = RT((sizeof(RT) == 8) ? 1.e-99 : 1.e-30);
373 bool happyend = (tt < sml);
374 if (!happyend) {
375 m_linop->scale(vv_it1, RT(1.0)/tt);
376 }
377
378 m_hh (it+1,it) = tt;
379 m_hes(it+1,it) = tt;
380
381 update_hessenberg(it, happyend, m_res);
382
383 ++it;
384 ++a_itcount;
385 a_status = converged(a_rnorm0, m_res) ? 0 : -1;
386 if (happyend) { break; }
387 }
388
389 if ((m_verbose > 1) && (a_status != 0 || a_itcount >= a_maxiter)) {
390 amrex::Print() << "GMRES: iter = " << a_itcount
391 << ", residual = " << m_res << ", " << m_res/a_rnorm0
392 << " (rel.)\n";
393 }
394
395 build_solution(a_xx, it-1);
396}
397
398template <typename V, typename M>
399void GMRES<V,M>::gram_schmidt_orthogonalization (int const it)
400{
401 // Two unmodified Gram-Schmidt Orthogonalization
402
403 BL_PROFILE("GMRES::GramSchmidt");
404
405 auto& vv_1 = m_vv[it+1];
406
407 Vector<RT> lhh(it+1);
408
409 for (int j = 0; j <= it; ++j) {
410 m_hh (j,it) = RT(0.0);
411 m_hes(j,it) = RT(0.0);
412 }
413
414 for (int ncnt = 0; ncnt < 2 ; ++ncnt)
415 {
416 for (int j = 0; j <= it; ++j) {
417 lhh[j] = m_linop->dotProduct(vv_1, m_vv[j]);
418 }
419
420 for (int j = 0; j <= it; ++j) {
421 m_linop->increment(vv_1, m_vv[j], -lhh[j]);
422 m_hh (j,it) += lhh[j];
423 m_hes(j,it) -= lhh[j];
424 }
425 }
426}
427
428template <typename V, typename M>
429void GMRES<V,M>::update_hessenberg (int it, bool happyend, RT& res)
430{
431 BL_PROFILE("GMRES::update_hessenberg()");
432
433 for (int j = 1; j <= it; ++j) {
434 auto tt = m_hh(j-1,it);
435 m_hh(j-1,it) = m_cc[j-1] * tt + m_ss[j-1] * m_hh(j,it);
436 m_hh(j ,it) = m_cc[j-1] * m_hh(j,it) - m_ss[j-1] * tt;
437 }
438
439 if (!happyend)
440 {
441 auto tt = std::sqrt(m_hh(it,it)*m_hh(it,it) + m_hh(it+1,it)*m_hh(it+1,it));
442 m_cc[it] = m_hh(it ,it) / tt;
443 m_ss[it] = m_hh(it+1,it) / tt;
444 m_grs[it+1] = - (m_ss[it] * m_grs[it]);
445 m_grs[it ] = m_cc[it] * m_grs[it];
446 m_hh(it,it) = m_cc[it] * m_hh(it,it) + m_ss[it] * m_hh(it+1,it);
447 res = std::abs(m_grs[it+1]);
448 }
449 else
450 {
451 res = RT(0.0);
452 }
453}
454
455template <typename V, typename M>
456void GMRES<V,M>::build_solution (V& a_xx, int const it)
457{
458 BL_PROFILE("GMRES:build_solution()");
459
460 if (it < 0) { return; }
461
462 if (m_hh(it,it) != RT(0.0)) {
463 m_grs[it] /= m_hh(it,it);
464 } else {
465 m_grs[it] = RT(0.0);
466 }
467
468 for (int ii = 1; ii <= it; ++ii) {
469 int k = it - ii;
470 auto tt = m_grs[k];
471 for (int j = k+1; j <= it; ++j) {
472 tt -= m_hh(k,j) * m_grs[j];
473 }
474 m_grs[k] = tt / m_hh(k,k);
475 }
476
477 if (m_flexible) {
478 // x += Z y, with Z the stored preconditioned vectors
479 for (int ii = 0; ii < it+1; ++ii) {
480 m_linop->increment(a_xx, m_zz[ii], m_grs[ii]);
481 }
482 } else {
483 // x += P^{-1} V y, valid only if P^{-1} is the same in all iterations
484 m_linop->setToZero(*m_v_tmp_rhs);
485 for (int ii = 0; ii < it+1; ++ii) {
486 m_linop->increment(*m_v_tmp_rhs, m_vv[ii], m_grs[ii]);
487 }
488
489 m_linop->precond(*m_v_tmp_lhs, *m_v_tmp_rhs);
490 m_linop->increment(a_xx, *m_v_tmp_lhs, RT(1.0));
491 }
492}
493
494template <typename V, typename M>
495void GMRES<V,M>::compute_residual (V& a_rr, V const& a_xx, V const& a_bb)
496{
497 BL_PROFILE("GMRES::compute_residual()");
498 m_linop->assign(*m_v_tmp_lhs, a_xx);
499 m_linop->apply(*m_v_tmp_rhs, *m_v_tmp_lhs);
500 m_linop->linComb(a_rr, RT(1.0), a_bb, RT(-1.0), *m_v_tmp_rhs);
501}
502
503}
504#endif
#define BL_PROFILE(a)
Definition AMReX_BLProfiler.H:593
#define AMREX_ALWAYS_ASSERT(EX)
Definition AMReX_BLassert.H:50
int getNumIters() const
Number of iterations executed by the last solve().
Definition AMReX_GMRES.H:154
void solve(V &a_sol, V const &a_rhs, RT a_tol_rel, RT a_tol_abs, int a_its=-1)
Solve the linear system.
Definition AMReX_GMRES.H:262
RT getInitialResidualNorm() const
Initial residual 2-norm from the last solve().
Definition AMReX_GMRES.H:163
void define(M &linop)
Bind the solver to a linear operator.
Definition AMReX_GMRES.H:236
void setVerbose(int v)
Set verbosity level v (0 = silent).
Definition AMReX_GMRES.H:126
void setMaxIters(int niters)
Cap the number of iterations performed by solve().
Definition AMReX_GMRES.H:151
void setRestartLength(int rl)
Set the Krylov restart length.
Definition AMReX_GMRES.H:225
void setFlexible(bool flag)
Use flexible GMRES (FGMRES) (default: false).
Definition AMReX_GMRES.H:135
bool getFlexible() const
Whether flexible GMRES is in use.
Definition AMReX_GMRES.H:137
RT getResidualNorm() const
Final residual 2-norm from the last solve().
Definition AMReX_GMRES.H:160
GMRES()
Construct a GMRES solver with the default restart length.
Definition AMReX_GMRES.H:203
void setInitialGuessNonzero(bool flag)
Definition AMReX_GMRES.H:123
int getStatus() const
Status flag from the last solve() (0 success, >0 failure).
Definition AMReX_GMRES.H:157
typename M::RT RT
Definition AMReX_GMRES.H:91
This class provides the user with a few print options.
Definition AMReX_Print.H:35
This class is a thin wrapper around std::vector. Unlike vector, Vector::operator[] provides bound che...
Definition AMReX_Vector.H:29
Definition AMReX_Amr.cpp:50
double second() noexcept
Definition AMReX_Utility.cpp:874
Definition AMReX_TableData.H:97