BelosCGSingleRedIter.hpp

Go to the documentation of this file.

// @HEADER
// *****************************************************************************
//                 Belos: Block Linear Solvers Package
//
// Copyright 2004-2016 NTESS and the Belos contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER
 
#ifndef BELOS_CG_SINGLE_RED_ITER_HPP
#define BELOS_CG_SINGLE_RED_ITER_HPP

 
#include "BelosConfigDefs.hpp"
#include "BelosTypes.hpp"
#include "BelosCGIteration.hpp"
 
#include "BelosLinearProblem.hpp"
#include "BelosOutputManager.hpp"
#include "BelosStatusTest.hpp"
#include "BelosStatusTestGenResNorm.hpp"
#include "BelosOperatorTraits.hpp"
#include "BelosMultiVecTraits.hpp"
#include "BelosDenseMatTraits.hpp"
 
#include "Teuchos_ScalarTraits.hpp"
#include "Teuchos_ParameterList.hpp"
#include "Teuchos_TimeMonitor.hpp"

 
namespace Belos {



  template <class ScalarType, class MV, class DM = DefaultDenseMatrix<int,ScalarType>>
  class CGSingleRedIterationState : public CGIterationStateBase<ScalarType, MV, DM> {
 
  public:
    CGSingleRedIterationState() = default;
 
    CGSingleRedIterationState(Teuchos::RCP<const MV> tmp) {
      initialize(tmp);
    }
 
    virtual ~CGSingleRedIterationState() = default;
 
    void initialize(Teuchos::RCP<const MV> tmp, int _numVectors) {
      using MVT = MultiVecTraits<ScalarType, MV, DM>;
 
      TEUCHOS_ASSERT(_numVectors == 1);
 
      // W = (AZ, R, Z)
      W = MVT::Clone( *tmp, 3 );
      std::vector<int> index2(2,0);
      std::vector<int> index(1,0);
 
      // S = (AZ, R)
      index2[0] = 0;
      index2[1] = 1;
      S = MVT::CloneViewNonConst( *W, index2 );
 
      // U = (AZ, Z)
      index2[0] = 0;
      index2[1] = 2;
      U = MVT::CloneViewNonConst( *W, index2 );
 
      index[0] = 1;
      this->R = MVT::CloneViewNonConst( *W, index );
      index[0] = 0;
      AZ = MVT::CloneViewNonConst( *W, index );
      index[0] = 2;
      this->Z = MVT::CloneViewNonConst( *W, index );
 
      // T = (R, Z)
      index2[0] = 1;
      index2[1] = 2;
      T = MVT::CloneViewNonConst( *W, index2 );
 
      // V = (AP, P)
      V = MVT::Clone( *tmp, 2 );
      index[0] = 0;
      this->AP = MVT::CloneViewNonConst( *V, index );
      index[0] = 1;
      this->P = MVT::CloneViewNonConst( *V, index );
 
      CGIterationStateBase<ScalarType, MV, DM>::initialize(tmp, _numVectors);
    }
 
    bool matches(Teuchos::RCP<const MV> tmp, int _numVectors=1) const {
      return (CGIterationStateBase<ScalarType, MV, DM>::matches(tmp, _numVectors) &&
              !W.is_null() &&
              !V.is_null() &&
              !U.is_null() &&
              !S.is_null() &&
              !T.is_null() &&
              !AZ.is_null());
    }
 
    Teuchos::RCP<MV> W;
    Teuchos::RCP<MV> V;
    Teuchos::RCP<MV> U;
    Teuchos::RCP<MV> S;
    Teuchos::RCP<MV> T;
    Teuchos::RCP<MV> AZ;
 
  };
 
template<class ScalarType, class MV, class OP, class DM = DefaultDenseMatrix<int,ScalarType>>
class CGSingleRedIter : virtual public CGIteration<ScalarType,MV,OP,DM> {
 
  public:
 
  //
  // Convenience typedefs
  //
  using MVT = MultiVecTraits<ScalarType, MV, DM>;
  using OPT = OperatorTraits<ScalarType, MV, OP>;
  using DMT = DenseMatTraits<ScalarType, DM>;
  using SCT = Teuchos::ScalarTraits<ScalarType>;
  using MagnitudeType = typename SCT::magnitudeType;



  CGSingleRedIter( const Teuchos::RCP<LinearProblem<ScalarType,MV,OP,DM> > &problem,
                   const Teuchos::RCP<OutputManager<ScalarType> > &printer,
                   const Teuchos::RCP<StatusTest<ScalarType,MV,OP,DM> > &tester,
                   const Teuchos::RCP<StatusTestGenResNorm<ScalarType,MV,OP,DM> > &convTester,
                   Teuchos::ParameterList &params );

  virtual ~CGSingleRedIter() = default;
 



  void iterate();

  void initializeCG(Teuchos::RCP<CGIterationStateBase<ScalarType,MV,DM> > newstate, Teuchos::RCP<MV> R_0);

  void initialize()
  {
    initializeCG(Teuchos::null, Teuchos::null);
  }

  Teuchos::RCP<CGIterationStateBase<ScalarType,MV,DM> > getState() const {
    auto state = Teuchos::rcp(new CGSingleRedIterationState<ScalarType,MV,DM>());
    state->W = W_;
    state->V = V_;
    state->U = U_;
    state->S = S_;
    state->T = T_;
    state->R = R_;
    state->Z = Z_;
    state->P = P_;
    state->AP = AP_;
    state->AZ = AZ_;
    return state;
  }
 
  void setState(Teuchos::RCP<CGIterationStateBase<ScalarType,MV,DM> >  state) {
    auto s = Teuchos::rcp_dynamic_cast<CGSingleRedIterationState<ScalarType,MV,DM> >(state, true);
    W_ = s->W;
    V_ = s->V;
    U_ = s->U;
    S_ = s->S;
    T_ = s->T;
    R_ = s->R;
    Z_ = s->Z;
    P_ = s->P;
    AP_ = s->AP;
    AZ_ = s->AZ;
  }

 



  int getNumIters() const { return iter_; }

  void resetNumIters( int iter = 0 ) { iter_ = iter; }

  Teuchos::RCP<const MV> getNativeResiduals( std::vector<MagnitudeType> *norms ) const;


  Teuchos::RCP<MV> getCurrentUpdate() const { return Teuchos::null; }




  const LinearProblem<ScalarType,MV,OP,DM>& getProblem() const { return *lp_; }

  int getBlockSize() const { return 1; }

  void setBlockSize(int blockSize) {
    TEUCHOS_TEST_FOR_EXCEPTION(blockSize!=1,std::invalid_argument,
           "Belos::CGSingleRedIter::setBlockSize(): Cannot use a block size that is not one.");
  }

  bool isInitialized() { return initialized_; }

  void setDoCondEst(bool /* val */){/*ignored*/}

  Teuchos::ArrayView<MagnitudeType> getDiag() {
    Teuchos::ArrayView<MagnitudeType> temp;
    return temp;
  }

  Teuchos::ArrayView<MagnitudeType> getOffDiag() {
    Teuchos::ArrayView<MagnitudeType> temp;
    return temp;
  }

 
  private:
 
  //
  // Internal methods
  //
 
  // Classes inputed through constructor that define the linear problem to be solved.
  //
  const Teuchos::RCP<LinearProblem<ScalarType,MV,OP,DM> >    lp_;
  const Teuchos::RCP<OutputManager<ScalarType> >          om_;
  const Teuchos::RCP<StatusTest<ScalarType,MV,OP,DM> >       stest_;
  const Teuchos::RCP<StatusTestGenResNorm<ScalarType,MV,OP,DM> >       convTest_;
 
  //
  // Current solver state
  //
  // initialized_ specifies that the basis vectors have been initialized and the iterate() routine
  // is capable of running; _initialize is controlled  by the initialize() member method
  // For the implications of the state of initialized_, please see documentation for initialize()
  bool initialized_;
 
  // Current number of iterations performed.
  int iter_;
 
  // Should the allreduce for convergence detection be merged with the inner products?
  bool foldConvergenceDetectionIntoAllreduce_;
 
  // <r,z>
  ScalarType rHz_;
  // <r,r>
  ScalarType rHr_;
 
  //
  // State Storage
  //
  // Residual
  Teuchos::RCP<MV> R_;
  // Preconditioned residual
  Teuchos::RCP<MV> Z_;
  // Operator applied to preconditioned residual
  Teuchos::RCP<MV> AZ_;
  // Direction vector
  Teuchos::RCP<MV> P_;
  // Operator applied to direction vector
  Teuchos::RCP<MV> AP_;
  //
  // W_ = (R_, AZ_, Z_)
  Teuchos::RCP<MV> W_;
  // S_ = (R_, AZ_)
  Teuchos::RCP<MV> S_;
  // T_ = (Z_, R_)
  Teuchos::RCP<MV> T_;
  // U_ = (AZ_, Z_)
  Teuchos::RCP<MV> U_;
  // V_ = (AP_, P_)
  Teuchos::RCP<MV> V_;
 
};

  // Constructor.
  template<class ScalarType, class MV, class OP, class DM>
  CGSingleRedIter<ScalarType,MV,OP,DM>::CGSingleRedIter(const Teuchos::RCP<LinearProblem<ScalarType,MV,OP,DM> > &problem,
                 const Teuchos::RCP<OutputManager<ScalarType> > &printer,
                 const Teuchos::RCP<StatusTest<ScalarType,MV,OP,DM> > &tester,
                                                     const Teuchos::RCP<StatusTestGenResNorm<ScalarType,MV,OP,DM> > &convTester,
                 Teuchos::ParameterList &params ):
    lp_(problem),
    om_(printer),
    stest_(tester),
    convTest_(convTester),
    initialized_(false),
    iter_(0)
  {
    foldConvergenceDetectionIntoAllreduce_ = params.get<bool>("Fold Convergence Detection Into Allreduce",false);
  }

  // Setup the state storage.
  template<class ScalarType, class MV, class OP, class DM>
  void CGSingleRedIter<ScalarType,MV,OP,DM>::initializeCG(Teuchos::RCP<CGIterationStateBase<ScalarType,MV,DM> > newstate, Teuchos::RCP<MV> R_0)
  {
    // Initialize the state storage if it isn't already.
    Teuchos::RCP<const MV> lhsMV = lp_->getLHS();
    Teuchos::RCP<const MV> rhsMV = lp_->getRHS();
    Teuchos::RCP<const MV> tmp = ( (rhsMV!=Teuchos::null)? rhsMV: lhsMV );
    TEUCHOS_ASSERT(!newstate.is_null());
    if (!Teuchos::rcp_dynamic_cast<CGSingleRedIterationState<ScalarType,MV,DM> >(newstate, true)->matches(tmp, 1))
      newstate->initialize(tmp, 1);
    setState(newstate);
 
    std::string errstr("Belos::CGSingleRedIter::initialize(): Specified multivectors must have a consistent length and width.");
 
    {
 
      TEUCHOS_TEST_FOR_EXCEPTION( MVT::GetGlobalLength(*newstate->R) != MVT::GetGlobalLength(*R_),
                          std::invalid_argument, errstr );
      TEUCHOS_TEST_FOR_EXCEPTION( MVT::GetNumberVecs(*newstate->R) != 1,
                          std::invalid_argument, errstr );
 
      // Copy basis vectors from newstate into V
      if (R_0 != R_) {
        // copy over the initial residual (unpreconditioned).
  MVT::Assign( *R_0, *R_ );
      }
 
      // Compute initial direction vectors
      // Initially, they are set to the preconditioned residuals
      //
      if ( lp_->getLeftPrec() != Teuchos::null ) {
        lp_->applyLeftPrec( *R_, *Z_ );
        if ( lp_->getRightPrec() != Teuchos::null ) {
          Teuchos::RCP<MV> tmp2 = MVT::Clone( *Z_, 1 );
          lp_->applyRightPrec( *Z_, *tmp2 );
          MVT::Assign( *tmp2, *Z_ );
        }
      }
      else if ( lp_->getRightPrec() != Teuchos::null ) {
        lp_->applyRightPrec( *R_, *Z_ );
      }
      else {
        MVT::Assign( *R_, *Z_ );
      }
 
      // Multiply the current preconditioned residual vector by A and store in AZ_
      lp_->applyOp( *Z_, *AZ_ );
 
      // P_ := Z_
      // Logically, AP_ := AZ_
      MVT::Assign( *U_, *V_);
    }
 
    // The solver is initialized
    initialized_ = true;
  }
 

  // Get the norms of the residuals native to the solver.
  template<class ScalarType, class MV, class OP, class DM>
  Teuchos::RCP<const MV>
  CGSingleRedIter<ScalarType,MV,OP,DM>::getNativeResiduals( std::vector<MagnitudeType> *norms ) const {
    if (convTest_->getResNormType() == Belos::PreconditionerNorm) {
      (*norms)[0] = std::sqrt(Teuchos::ScalarTraits<ScalarType>::magnitude(rHz_));
      return Teuchos::null;
    } else if (foldConvergenceDetectionIntoAllreduce_ && convTest_->getResNormType() == Belos::TwoNorm) {
      (*norms)[0] = std::sqrt(Teuchos::ScalarTraits<ScalarType>::magnitude(rHr_));
      return Teuchos::null;
    } else
      return R_;
  }
 

  // Iterate until the status test informs us we should stop.
  template<class ScalarType, class MV, class OP, class DM>
  void CGSingleRedIter<ScalarType,MV,OP,DM>::iterate()
  {
    //
    // Allocate/initialize data structures
    //
    if (!initialized_) {
      initialize();
    }
 
    // Allocate memory for scalars.
    Teuchos::RCP<DM> sHz = DMT::Create( 2, 1 );
    Teuchos::RCP<DM> sHt = DMT::Create( 2, 2 );
    ScalarType rHz_old, alpha, beta, delta;
 
    // Create convenience variables for zero and one.
    const ScalarType one = Teuchos::ScalarTraits<ScalarType>::one();
    const MagnitudeType zero = Teuchos::ScalarTraits<MagnitudeType>::zero();
 
    // Get the current solution vector.
    Teuchos::RCP<MV> cur_soln_vec = lp_->getCurrLHSVec();
 
    // Check that the current solution vector only has one column.
    TEUCHOS_TEST_FOR_EXCEPTION( MVT::GetNumberVecs(*cur_soln_vec) != 1, CGIterateFailure,
                        "Belos::CGSingleRedIter::iterate(): current linear system has more than one vector!" );
 
    if (foldConvergenceDetectionIntoAllreduce_ && convTest_->getResNormType() == Belos::TwoNorm) {
      // Compute first <S_,T_> a.k.a. <R_,Z_>, <AZ_,Z_> and <R_,R_> combined (also computes unneeded <AZ_,R_>)
      MVT::MvTransMv( one, *S_, *T_, *sHt );
      DMT::SyncDeviceToHost( *sHt );
      rHz_ = DMT::ValueConst(*sHt,1,1);
      delta = DMT::ValueConst(*sHt,0,1);
      rHr_ = DMT::ValueConst(*sHt,1,0);
    } else {
      // Compute first <s,z> a.k.a. <r,z> and <Az,z> combined
      MVT::MvTransMv( one, *S_, *Z_, *sHz );
      DMT::SyncDeviceToHost( *sHz );
      rHz_ = DMT::ValueConst(*sHz,1,0);
      delta = DMT::ValueConst(*sHz,0,0);
    }
    if ((Teuchos::ScalarTraits<ScalarType>::magnitude(delta) < Teuchos::ScalarTraits<ScalarType>::eps()) &&
        (stest_->checkStatus(this) == Passed))
      return;
    alpha = rHz_ / delta;
 
    // Check that alpha is a positive number!
    TEUCHOS_TEST_FOR_EXCEPTION( SCT::real(alpha) <= zero, CGPositiveDefiniteFailure,
      "Belos::CGSingleRedIter::iterate(): non-positive value for p^H*A*p encountered!" );

    // Iterate until the status test tells us to stop.
    //
    if (foldConvergenceDetectionIntoAllreduce_ && convTest_->getResNormType() == Belos::TwoNorm) {
      // Iterate until the status test tells us to stop.
      //
      while (true) {
 
        // Update the solution vector x := x + alpha * P_
        //
        MVT::MvAddMv( one, *cur_soln_vec, alpha, *P_, *cur_soln_vec );
        //
        // Compute the new residual R_ := R_ - alpha * AP_
        //
        MVT::MvAddMv( one, *R_, -alpha, *AP_, *R_ );
        //
        // Apply preconditioner to new residual to update Z_
        //
        if ( lp_->getLeftPrec() != Teuchos::null ) {
          lp_->applyLeftPrec( *R_, *Z_ );
          if ( lp_->getRightPrec() != Teuchos::null ) {
            Teuchos::RCP<MV> tmp = MVT::CloneCopy( *Z_ );
            lp_->applyRightPrec( *tmp, *Z_ );
          }
        }
        else if ( lp_->getRightPrec() != Teuchos::null ) {
          lp_->applyRightPrec( *R_, *Z_ );
        }
        else {
          MVT::Assign( *R_, *Z_ );
        }
        //
        // Multiply the current preconditioned residual vector by A and store in AZ_
        lp_->applyOp( *Z_, *AZ_ );
        //
        // Compute <S_,T_> a.k.a. <R_,Z_>, <AZ_,Z_> and <R_,R_> combined (also computes unneeded <AZ_,R_>)
        MVT::MvTransMv( one, *S_, *T_, *sHt );
        DMT::SyncDeviceToHost( *sHt ); 
        //
        // Update scalars.
        rHz_old = rHz_;
        rHz_ = DMT::ValueConst(*sHt,1,1);
        delta = DMT::ValueConst(*sHt,0,1);
        rHr_ = DMT::ValueConst(*sHt,1,0);
 
        // Increment the iteration
        iter_++;
        //
        // Check the status test, now that the solution and residual have been updated
        //
        if (stest_->checkStatus(this) == Passed) {
          break;
        }
        //
        beta = rHz_ / rHz_old;
        alpha = rHz_ / (delta - (beta*rHz_ / alpha));
        //
        // Check that alpha is a positive number!
        TEUCHOS_TEST_FOR_EXCEPTION( SCT::real(alpha) <= zero, CGPositiveDefiniteFailure,
                                    "Belos::CGSingleRedIter::iterate(): non-positive value for p^H*A*p encountered!" );
 
        //
        // Update the direction vector P_ := Z_ + beta * P_
        // Update AP_ through recurrence relation AP_ := AZ_ + beta * AP_
        // Hence: V_ = (AP_, P_) := (AZ_, Z_) + beta (AP_, P_) = U_ + beta * V_
        //
        MVT::MvAddMv( one, *U_, beta, *V_, *V_ );
 
      } // end while (1)
    } else {
      // Iterate until the status test tells us to stop.
      //
      while (true) {
 
        // Update the solution vector x := x + alpha * P_
        //
        MVT::MvAddMv( one, *cur_soln_vec, alpha, *P_, *cur_soln_vec );
        //
        // Compute the new residual R_ := R_ - alpha * AP_
        //
        MVT::MvAddMv( one, *R_, -alpha, *AP_, *R_ );
 
        // Increment the iteration
        iter_++;
        //
        // Check the status test, now that the solution and residual have been updated
        //
        if (stest_->checkStatus(this) == Passed) {
          break;
        }
        //
        // Apply preconditioner to new residual to update Z_
        //
        if ( lp_->getLeftPrec() != Teuchos::null ) {
          lp_->applyLeftPrec( *R_, *Z_ );
          if ( lp_->getRightPrec() != Teuchos::null ) {
            Teuchos::RCP<MV> tmp = MVT::CloneCopy( *Z_ );
            lp_->applyRightPrec( *tmp, *Z_ );
          }
        }
        else if ( lp_->getRightPrec() != Teuchos::null ) {
          lp_->applyRightPrec( *R_, *Z_ );
        }
        else {
          MVT::Assign( *R_, *Z_ );
        }
        //
        // Multiply the current preconditioned residual vector by A and store in AZ_
        lp_->applyOp( *Z_, *AZ_ );
        //
        // Compute <S_,Z_> a.k.a. <R_,Z_> and <AZ_,Z_> combined
        MVT::MvTransMv( one, *S_, *Z_, *sHz );
        DMT::SyncDeviceToHost( *sHz );
        //
        // Update scalars.
        rHz_old = rHz_;
        rHz_ = DMT::ValueConst(*sHz,1,0);
        delta = DMT::ValueConst(*sHz,0,0);
        //
        beta = rHz_ / rHz_old;
        alpha = rHz_ / (delta - (beta*rHz_ / alpha));
        //
        // Check that alpha is a positive number!
        TEUCHOS_TEST_FOR_EXCEPTION( SCT::real(alpha) <= zero, CGPositiveDefiniteFailure,
                                    "Belos::CGSingleRedIter::iterate(): non-positive value for p^H*A*p encountered!" );
 
        //
        // Update the direction vector P_ := Z_ + beta * P_
        // Update AP_ through recurrence relation AP_ := AZ_ + beta * AP_
        // Hence: V_ = (AP_, P_) := (AZ_, Z_) + beta (AP_, P_) = U_ + beta * V_
        //
        MVT::MvAddMv( one, *U_, beta, *V_, *V_ );
 
      } // end while (1)
    }
  }
 
} // end Belos namespace
 
#endif /* BELOS_CG_SINGLE_RED_ITER_HPP */