// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_ISTL_GSETC_HH #define DUNE_ISTL_GSETC_HH #include #include #include #include #include #include #include "multitypeblockvector.hh" #include "multitypeblockmatrix.hh" #include "istlexception.hh" /*! \file \brief Simple iterative methods like Jacobi, Gauss-Seidel, SOR, SSOR, etc. in a generic way */ namespace Dune { /** * @defgroup ISTL_Kernel Block Recursive Iterative Kernels * @ingroup ISTL_SPMV * * Generic iterative kernels for the solvers which work on the block recursive * structure of the matrices and vectors. * @addtogroup ISTL_Kernel * @{ */ //============================================================ // parameter types //============================================================ //! compile-time parameter for block recursion depth template struct BL { enum {recursion_level = l}; }; enum WithDiagType { withdiag=1, nodiag=0 }; enum WithRelaxType { withrelax=1, norelax=0 }; //============================================================ // generic triangular solves // consider block decomposition A = L + D + U // we can invert L, L+D, U, U+D // we can apply relaxation or not // we can recurse over a fixed number of levels //============================================================ // template meta program for triangular solves template struct algmeta_btsolve { template static void bltsolve (const M& A, X& v, const Y& d, const K& w) { // iterator types typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; // local solve at each block and immediate update rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { bblock rhs(d[i.index()]); coliterator j; for (j=(*i).begin(); j.index()::bltsolve(*j,v[i.index()],rhs,w); } } template static void butsolve (const M& A, X& v, const Y& d, const K& w) { // iterator types typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; // local solve at each block and immediate update rowiterator rendi=A.beforeBegin(); for (rowiterator i=A.beforeEnd(); i!=rendi; --i) { bblock rhs(d[i.index()]); coliterator j; for (j=(*i).beforeEnd(); j.index()>i.index(); --j) (*j).mmv(v[j.index()],rhs); algmeta_btsolve::butsolve(*j,v[i.index()],rhs,w); } } }; // recursion end ... template<> struct algmeta_btsolve<0,withdiag,withrelax> { template static void bltsolve (const M& A, X& v, const Y& d, const K& w) { A.solve(v,d); v *= w; } template static void butsolve (const M& A, X& v, const Y& d, const K& w) { A.solve(v,d); v *= w; } }; template<> struct algmeta_btsolve<0,withdiag,norelax> { template static void bltsolve (const M& A, X& v, const Y& d, const K& /*w*/) { A.solve(v,d); } template static void butsolve (const M& A, X& v, const Y& d, const K& /*w*/) { A.solve(v,d); } }; template<> struct algmeta_btsolve<0,nodiag,withrelax> { template static void bltsolve (const M& /*A*/, X& v, const Y& d, const K& w) { v = d; v *= w; } template static void butsolve (const M& /*A*/, X& v, const Y& d, const K& w) { v = d; v *= w; } }; template<> struct algmeta_btsolve<0,nodiag,norelax> { template static void bltsolve (const M& /*A*/, X& v, const Y& d, const K& /*w*/) { v = d; } template static void butsolve (const M& /*A*/, X& v, const Y& d, const K& /*w*/) { v = d; } }; // user calls // default block recursion level = 1 //! block lower triangular solve template void bltsolve (const M& A, X& v, const Y& d) { typename X::field_type w=1; algmeta_btsolve<1,withdiag,norelax>::bltsolve(A,v,d,w); } //! relaxed block lower triangular solve template void bltsolve (const M& A, X& v, const Y& d, const K& w) { algmeta_btsolve<1,withdiag,withrelax>::bltsolve(A,v,d,w); } //! unit block lower triangular solve template void ubltsolve (const M& A, X& v, const Y& d) { typename X::field_type w=1; algmeta_btsolve<1,nodiag,norelax>::bltsolve(A,v,d,w); } //! relaxed unit block lower triangular solve template void ubltsolve (const M& A, X& v, const Y& d, const K& w) { algmeta_btsolve<1,nodiag,withrelax>::bltsolve(A,v,d,w); } //! block upper triangular solve template void butsolve (const M& A, X& v, const Y& d) { typename X::field_type w=1; algmeta_btsolve<1,withdiag,norelax>::butsolve(A,v,d,w); } //! relaxed block upper triangular solve template void butsolve (const M& A, X& v, const Y& d, const K& w) { algmeta_btsolve<1,withdiag,withrelax>::butsolve(A,v,d,w); } //! unit block upper triangular solve template void ubutsolve (const M& A, X& v, const Y& d) { typename X::field_type w=1; algmeta_btsolve<1,nodiag,norelax>::butsolve(A,v,d,w); } //! relaxed unit block upper triangular solve template void ubutsolve (const M& A, X& v, const Y& d, const K& w) { algmeta_btsolve<1,nodiag,withrelax>::butsolve(A,v,d,w); } // general block recursion level >= 0 //! block lower triangular solve template void bltsolve (const M& A, X& v, const Y& d, BL /*bl*/) { typename X::field_type w=1; algmeta_btsolve::bltsolve(A,v,d,w); } //! relaxed block lower triangular solve template void bltsolve (const M& A, X& v, const Y& d, const K& w, BL /*bl*/) { algmeta_btsolve::bltsolve(A,v,d,w); } //! unit block lower triangular solve template void ubltsolve (const M& A, X& v, const Y& d, BL /*bl*/) { typename X::field_type w=1; algmeta_btsolve::bltsolve(A,v,d,w); } //! relaxed unit block lower triangular solve template void ubltsolve (const M& A, X& v, const Y& d, const K& w, BL /*bl*/) { algmeta_btsolve::bltsolve(A,v,d,w); } //! block upper triangular solve template void butsolve (const M& A, X& v, const Y& d, BL /*bl*/) { typename X::field_type w=1; algmeta_btsolve::butsolve(A,v,d,w); } //! relaxed block upper triangular solve template void butsolve (const M& A, X& v, const Y& d, const K& w, BL /*bl*/) { algmeta_btsolve::butsolve(A,v,d,w); } //! unit block upper triangular solve template void ubutsolve (const M& A, X& v, const Y& d, BL /*bl*/) { typename X::field_type w=1; algmeta_btsolve::butsolve(A,v,d,w); } //! relaxed unit block upper triangular solve template void ubutsolve (const M& A, X& v, const Y& d, const K& w, BL /*bl*/) { algmeta_btsolve::butsolve(A,v,d,w); } //============================================================ // generic block diagonal solves // consider block decomposition A = L + D + U // we can apply relaxation or not // we can recurse over a fixed number of levels //============================================================ // template meta program for diagonal solves template struct algmeta_bdsolve { template static void bdsolve (const M& A, X& v, const Y& d, const K& w) { // iterator types typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; // local solve at each block and immediate update rowiterator rendi=A.beforeBegin(); for (rowiterator i=A.beforeEnd(); i!=rendi; --i) { coliterator ii=(*i).find(i.index()); algmeta_bdsolve::bdsolve(*ii,v[i.index()],d[i.index()],w); } } }; // recursion end ... template<> struct algmeta_bdsolve<0,withrelax> { template static void bdsolve (const M& A, X& v, const Y& d, const K& w) { A.solve(v,d); v *= w; } }; template<> struct algmeta_bdsolve<0,norelax> { template static void bdsolve (const M& A, X& v, const Y& d, const K& /*w*/) { A.solve(v,d); } }; // user calls // default block recursion level = 1 //! block diagonal solve, no relaxation template void bdsolve (const M& A, X& v, const Y& d) { typename X::field_type w=1; algmeta_bdsolve<1,norelax>::bdsolve(A,v,d,w); } //! block diagonal solve, with relaxation template void bdsolve (const M& A, X& v, const Y& d, const K& w) { algmeta_bdsolve<1,withrelax>::bdsolve(A,v,d,w); } // general block recursion level >= 0 //! block diagonal solve, no relaxation template void bdsolve (const M& A, X& v, const Y& d, BL /*bl*/) { typename X::field_type w=1; algmeta_bdsolve::bdsolve(A,v,d,w); } //! block diagonal solve, with relaxation template void bdsolve (const M& A, X& v, const Y& d, const K& w, BL /*bl*/) { algmeta_bdsolve::bdsolve(A,v,d,w); } //============================================================ // generic steps of iteration methods // Jacobi, Gauss-Seidel, SOR, SSOR // work directly on Ax=b, ie solve M(x^{i+1}-x^i) = w (b-Ax^i) // we can recurse over a fixed number of levels //============================================================ // template meta program for iterative solver steps template struct algmeta_itsteps { template static void dbgs (const M& A, X& x, const Y& b, const K& w) { typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; bblock rhs; X xold(x); // remember old x rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { rhs = b[i.index()]; // rhs = b_i coliterator endj=(*i).end(); coliterator j=(*i).begin(); if constexpr (IsNumber()) { for (; j.index() i (*j).mmv(x[j.index()],rhs); // rhs -= sum_{j>i} a_ij * xold_j algmeta_itsteps::dbgs(*diag,x[i.index()],rhs,w); // if I==1: xnew_i = rhs/a_ii } } // next two lines: xnew_i = w / a_ii * (b_i - sum_{j=i} a_ij * xold_j) + (1-w)*xold; x *= w; x.axpy(K(1)-w,xold); } template static void bsorf (const M& A, X& x, const Y& b, const K& w) { typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; typedef typename X::block_type xblock; bblock rhs; xblock v; // Initialize nested data structure if there are entries if(A.begin()!=A.end()) v=x[0]; rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { rhs = b[i.index()]; // rhs = b_i coliterator endj=(*i).end(); // iterate over a_ij with j < i coliterator j=(*i).begin(); if constexpr (IsNumber()) { for (; j.index()=i} a_ij * xold_j) } else { for (; j.index()::bsorf(*diag,v,rhs,w); // if blocksize I==1: v = rhs/a_ii x[i.index()].axpy(w,v); // x_i = w / a_ii * (b_i - sum_{j=i} a_ij * xold_j) } } } template static void bsorb (const M& A, X& x, const Y& b, const K& w) { typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; typedef typename X::block_type xblock; bblock rhs; xblock v; // Initialize nested data structure if there are entries if(A.begin()!=A.end()) v=x[0]; rowiterator endi=A.beforeBegin(); for (rowiterator i=A.beforeEnd(); i!=endi; --i) { rhs = b[i.index()]; coliterator endj=(*i).end(); coliterator j=(*i).begin(); if constexpr (IsNumber()) { for (; j.index()mmv(x[j.index()],rhs); coliterator diag=j; for (; j!=endj; ++j) j->mmv(x[j.index()],rhs); algmeta_itsteps::bsorb(*diag,v,rhs,w); x[i.index()].axpy(w,v); } } } template static void dbjac (const M& A, X& x, const Y& b, const K& w) { typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type bblock; bblock rhs; X v(x); // allocate with same size rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { rhs = b[i.index()]; coliterator endj=(*i).end(); coliterator j=(*i).begin(); if constexpr (IsNumber()) { for (; j.index()mmv(x[j.index()],rhs); coliterator diag=j; for (; j!=endj; ++j) j->mmv(x[j.index()],rhs); algmeta_itsteps::dbjac(*diag,v[i.index()],rhs,w); } } x.axpy(w,v); } }; // end of recursion template struct algmeta_itsteps<0,M> { template static void dbgs (const M& A, X& x, const Y& b, const K& /*w*/) { A.solve(x,b); } template static void bsorf (const M& A, X& x, const Y& b, const K& /*w*/) { A.solve(x,b); } template static void bsorb (const M& A, X& x, const Y& b, const K& /*w*/) { A.solve(x,b); } template static void dbjac (const M& A, X& x, const Y& b, const K& /*w*/) { A.solve(x,b); } }; template struct algmeta_itsteps> { template< typename... MultiTypeVectorArgs, class K> static void dbgs (const MultiTypeBlockMatrix& A, MultiTypeBlockVector& x, const MultiTypeBlockVector& b, const K& w) { static const int N = MultiTypeBlockMatrix::N(); Dune::MultiTypeBlockMatrix_Solver::dbgs(A, x, b, w); } template< typename... MultiTypeVectorArgs, class K> static void bsorf (const MultiTypeBlockMatrix& A, MultiTypeBlockVector& x, const MultiTypeBlockVector& b, const K& w) { static const int N = MultiTypeBlockMatrix::N(); Dune::MultiTypeBlockMatrix_Solver::bsorf(A, x, b, w); } template< typename... MultiTypeVectorArgs, class K> static void bsorb (const MultiTypeBlockMatrix& A, MultiTypeBlockVector& x, const MultiTypeBlockVector& b, const K& w) { static const int N = MultiTypeBlockMatrix::N(); Dune::MultiTypeBlockMatrix_Solver::bsorb(A, x, b, w); } template< typename... MultiTypeVectorArgs, class K > static void dbjac (const MultiTypeBlockMatrix& A, MultiTypeBlockVector& x, const MultiTypeBlockVector& b, const K& w) { static const int N = MultiTypeBlockMatrix::N(); Dune::MultiTypeBlockMatrix_Solver::dbjac(A, x, b, w); } }; // user calls //! GS step template void dbgs (const M& A, X& x, const Y& b, const K& w) { algmeta_itsteps<1,M>::dbgs(A,x,b,w); } //! GS step template void dbgs (const M& A, X& x, const Y& b, const K& w, BL /*bl*/) { algmeta_itsteps::dbgs(A,x,b,w); } //! SOR step template void bsorf (const M& A, X& x, const Y& b, const K& w) { algmeta_itsteps<1,M>::bsorf(A,x,b,w); } //! SOR step template void bsorf (const M& A, X& x, const Y& b, const K& w, BL /*bl*/) { algmeta_itsteps::bsorf(A,x,b,w); } //! SSOR step template void bsorb (const M& A, X& x, const Y& b, const K& w) { algmeta_itsteps<1,M>::bsorb(A,x,b,w); } //! Backward SOR step template void bsorb (const M& A, X& x, const Y& b, const K& w, BL /*bl*/) { algmeta_itsteps::type>::bsorb(A,x,b,w); } //! Jacobi step template void dbjac (const M& A, X& x, const Y& b, const K& w) { algmeta_itsteps<1,M>::dbjac(A,x,b,w); } //! Jacobi step template void dbjac (const M& A, X& x, const Y& b, const K& w, BL /*bl*/) { algmeta_itsteps::dbjac(A,x,b,w); } /** @} end documentation */ } // end namespace #endif