// 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_ILU_HH #define DUNE_ISTL_ILU_HH #include #include #include #include #include #include #include #include #include "istlexception.hh" /** \file * \brief The incomplete LU factorization kernels */ namespace Dune { /** @addtogroup ISTL_Kernel @{ */ namespace ILU { //! compute ILU decomposition of A. A is overwritten by its decomposition template void blockILU0Decomposition (M& A) { // iterator types typedef typename M::RowIterator rowiterator; typedef typename M::ColIterator coliterator; typedef typename M::block_type block; // implement left looking variant with stored inverse rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { // coliterator is diagonal after the following loop coliterator endij=(*i).end(); // end of row i coliterator ij; // eliminate entries left of diagonal; store L factor for (ij=(*i).begin(); ij.index() void blockILUBacksolve (const M& A, X& v, const Y& d) { // iterator types typedef typename M::ConstRowIterator rowiterator; typedef typename M::ConstColIterator coliterator; typedef typename Y::block_type dblock; typedef typename X::block_type vblock; // lower triangular solve rowiterator endi=A.end(); for (rowiterator i=A.begin(); i!=endi; ++i) { // We need to be careful here: Directly using // auto rhs = Impl::asVector(d[ i.index() ]); // is not OK in case this is a proxy. Hence // we first have to copy the value. Notice that // this is still not OK, if the vector type itself returns // proxy references. dblock rhsValue(d[i.index()]); auto&& rhs = Impl::asVector(rhsValue); for (coliterator j=(*i).begin(); j.index()i.index(); --j) Impl::asMatrix(*j).mmv(Impl::asVector(v[j.index()]),rhs); auto&& vi = Impl::asVector(v[i.index()]); Impl::asMatrix(*j).mv(rhs,vi); // diagonal stores inverse! } } // recursive function template to access first entry of a matrix template typename M::field_type& firstMatrixElement (M& A, [[maybe_unused]] typename std::enable_if_t::value>* sfinae = nullptr) { return firstMatrixElement(*(A.begin()->begin())); } template K& firstMatrixElement (K& A, [[maybe_unused]] typename std::enable_if_t::value>* sfinae = nullptr) { return A; } template K& firstMatrixElement (FieldMatrix& A) { return A[0][0]; } /*! ILU decomposition of order n Computes ILU decomposition of order n. The matrix ILU should be an empty matrix in row_wise creation mode. This allows the user to either specify the number of nonzero elements or to determine it automatically at run-time. */ template void blockILUDecomposition (const M& A, int n, M& ILU) { // iterator types typedef typename M::ColIterator coliterator; typedef typename M::ConstRowIterator crowiterator; typedef typename M::ConstColIterator ccoliterator; typedef typename M::CreateIterator createiterator; typedef typename M::field_type K; typedef std::map map; typedef typename map::iterator mapiterator; // symbolic factorization phase, store generation number in first matrix element crowiterator endi=A.end(); createiterator ci=ILU.createbegin(); for (crowiterator i=A.begin(); i!=endi; ++i) { map rowpattern; // maps column index to generation // initialize pattern with row of A for (ccoliterator j=(*i).begin(); j!=(*i).end(); ++j) rowpattern[j.index()] = 0; // eliminate entries in row which are to the left of the diagonal for (mapiterator ik=rowpattern.begin(); (*ik).first) rowpattern[ILUij.index()]; } // copy entries of A for (crowiterator i=A.begin(); i!=endi; ++i) { coliterator ILUij; coliterator endILUij = ILU[i.index()].end();; for (ILUij=ILU[i.index()].begin(); ILUij!=endILUij; ++ILUij) (*ILUij) = 0; // clear row ccoliterator Aij = (*i).begin(); ccoliterator endAij = (*i).end(); ILUij = ILU[i.index()].begin(); while (Aij!=endAij && ILUij!=endILUij) { if (Aij.index()==ILUij.index()) { *ILUij = *Aij; ++Aij; ++ILUij; } else { if (Aij.index()> struct CRS { typedef B block_type; typedef size_t size_type; CRS() : nRows_( 0 ) {} size_type rows() const { return nRows_; } size_type nonZeros() const { assert( rows_[ rows() ] != size_type(-1) ); return rows_[ rows() ]; } void resize( const size_type nRows ) { if( nRows_ != nRows ) { nRows_ = nRows ; rows_.resize( nRows_+1, size_type(-1) ); } } void reserveAdditional( const size_type nonZeros ) { const size_type needed = values_.size() + nonZeros ; if( values_.capacity() < needed ) { const size_type estimate = needed * 1.1; values_.reserve( estimate ); cols_.reserve( estimate ); } } void push_back( const block_type& value, const size_type index ) { values_.push_back( value ); cols_.push_back( index ); } std::vector< size_type > rows_; std::vector< block_type, Alloc> values_; std::vector< size_type > cols_; size_type nRows_; }; //! convert ILU decomposition into CRS format for lower and upper triangular and inverse. template void convertToCRS(const M& A, CRS& lower, CRS& upper, InvVector& inv ) { typedef typename M :: size_type size_type; lower.resize( A.N() ); upper.resize( A.N() ); inv.resize( A.N() ); // lower and upper triangular should store half of non zeros minus diagonal const size_t memEstimate = (A.nonzeroes() - A.N())/2; assert( A.nonzeroes() != 0 ); lower.reserveAdditional( memEstimate ); upper.reserveAdditional( memEstimate ); const auto endi = A.end(); size_type row = 0; size_type colcount = 0; lower.rows_[ 0 ] = colcount; for (auto i=A.begin(); i!=endi; ++i, ++row) { const size_type iIndex = i.index(); // store entries left of diagonal for (auto j=(*i).begin(); j.index() < iIndex; ++j ) { lower.push_back( (*j), j.index() ); ++colcount; } lower.rows_[ iIndex+1 ] = colcount; } const auto rendi = A.beforeBegin(); row = 0; colcount = 0; upper.rows_[ 0 ] = colcount ; // NOTE: upper and inv store entries in reverse row and col order, // reverse here relative to ILU for (auto i=A.beforeEnd(); i!=rendi; --i, ++ row ) { const auto endij=(*i).beforeBegin(); // end of row i const size_type iIndex = i.index(); // store in reverse row order for faster access during backsolve for (auto j=(*i).beforeEnd(); j != endij; --j ) { const size_type jIndex = j.index(); if( j.index() == iIndex ) { inv[ row ] = (*j); break; // assuming consecutive ordering of A } else if ( j.index() >= i.index() ) { upper.push_back( (*j), jIndex ); ++colcount ; } } upper.rows_[ row+1 ] = colcount; } } // end convertToCRS //! LU backsolve with stored inverse in CRS format for lower and upper triangular template void blockILUBacksolve (const CRS& lower, const CRS& upper, const InvVector& inv, X& v, const Y& d) { // iterator types typedef typename Y :: block_type dblock; typedef typename X :: block_type vblock; typedef typename X :: size_type size_type ; const size_type iEnd = lower.rows(); const size_type lastRow = iEnd - 1; if( iEnd != upper.rows() ) { DUNE_THROW(ISTLError,"ILU::blockILUBacksolve: lower and upper rows must be the same"); } // lower triangular solve for( size_type i=0; i