TfQmr.cxx

// Copyright (C) 2003-2009 Marc Duruflé
// Copyright (C) 2001-2009 Vivien Mallet
//
// This file is part of the linear-algebra library Seldon,
// http://seldon.sourceforge.net/.
//
// Seldon is free software; you can redistribute it and/or modify it under the
// terms of the GNU Lesser General Public License as published by the Free
// Software Foundation; either version 2.1 of the License, or (at your option)
// any later version.
//
// Seldon is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
// more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with Seldon. If not, see http://www.gnu.org/licenses/.
 
 
#ifndef SELDON_FILE_ITERATIVE_TFQMR_CXX
 
namespace Seldon
{
 
 
#ifdef SELDON_WITH_VIRTUAL
  template<class T, class Vector1>
  int TfQmr(const VirtualMatrix<T>& A, Vector1& x, const Vector1& b,
            Preconditioner_Base<T>& M,
            Iteration<typename ClassComplexType<T>::Treal>& iter)
#else
  template <class Titer, class Matrix1, class Vector1, class Preconditioner>
  int TfQmr(const Matrix1& A, Vector1& x, const Vector1& b,
            Preconditioner& M, Iteration<Titer> & iter)
#endif
  {
    const int N = A.GetM();
    if (N <= 0)
      return 0;
 
    Vector1 tmp(b), r0(b), v(b), h(b), w(b),
      y1(b), g(b), y0(b), rtilde(b), d(b);
 
    typedef typename Vector1::value_type Complexe;
    Complexe sigma, alpha, beta, eta, rho, rho0;
    typedef typename ClassComplexType<Complexe>::Treal Treal;
    Treal c, kappa, tau, theta;
    Complexe zero, one;
    SetComplexZero(zero);
    SetComplexOne(one);
 
    tmp.Fill(zero);
    // x is initial value
    // 1. r0 = M^{-1} (b - A x)
    Copy(b, tmp);
    if (!iter.IsInitGuess_Null())
      iter.MltAdd(-one, A, x, one, tmp);
    else
      x.Fill(zero);
 
    M.Solve(A, tmp, r0);
 
    // we initialize iter
    int success_init = iter.Init(r0);
    if (success_init != 0)
      return iter.ErrorCode();
 
    // 2. w=y=r
    Copy(r0, w);
    Copy(r0, y1);
 
    // 3. g=v=M^{-1}Ay
    Copy(y1, v);
    iter.Mlt(A, v, tmp);
    M.Solve(A, tmp, v);
    ++iter;
 
    Copy(v, g);
 
    // 4. d=0
    d.Fill(zero);
 
    // 5. tau = ||r||
    tau = Norm2(r0);
 
    // 6. theta = eta = 0
    theta = Treal(0);
    eta = zero;
 
    // 7. rtilde = r
    Copy(r0, rtilde);
 
    // 8. rho=dot(rtilde, r)
    rho = DotProd(rtilde, r0);
    rho0 = rho;
 
    iter.SetNumberIteration(0);
    // Loop until the stopping criteria are reached
    for (;;)
      {
        // 9. 10. 11.
        // sigma=dot(rtilde,v)
        // alpha=rho/sigma
        // y2k=y(2k-1)-alpha*v
        sigma = DotProd(rtilde, v);
 
        if (sigma == zero)
          {
            iter.Fail(1, "Tfqmr breakdown: sigma=0");
            break;
          }
        alpha = rho / sigma;
 
        //y0 = y1 - alpha * v;
        Copy(y1, y0);
        Add(-alpha, v, y0);
 
        // 12. h=M^{-1}*A*y
        Copy(y0, h);
        iter.Mlt(A, h, tmp);
        M.Solve(A, tmp, h);
        //split the loop of "for m = 2k-1, 2k"
 
        //The first one
        // 13. w = w-alpha*M^{-1} A y0
        //w = w - alpha * g;
        Add(-alpha, g, w);
        // 18. d=y0+((theta0^2)*eta0/alpha)*d         //need check breakdown
        if (alpha == zero)
          {
            iter.Fail(2, "Tfqmr breakdown: alpha=0");
            break;
          }
        //d = y1 + ( theta * theta * eta / alpha ) * d;
        Mlt(theta * theta * eta / alpha, d);
        Add(one, y1, d);
 
        // 14. theta=||w||_2/tau0       //need check breakdown
        if (tau == Treal(0))
          {
            iter.Fail(3, "Tfqmr breakdown: tau=0");
            break;
          }
        theta  = Norm2(w) / tau;
 
        // 15. c = 1/sqrt(1+theta^2)
        c = Treal(1) / sqrt(Treal(1) + theta * theta);
 
        // 16. tau = tau0*theta*c
        tau = tau * c * theta;
 
        // 17.  eta = (c^2)*alpha
        eta = c * c * alpha;
 
        // 19. x = x+eta*d
        Add(eta, d, x);
        // 20. kappa = tau*sqrt(m+1)
        kappa = tau * sqrt( Treal(2)* (iter.GetNumberIteration()+1) );
 
        // 21. check stopping criterion
        if ( iter.Finished(kappa) )
          {
            break;
          }
        ++iter;
        // g = h;
        Copy(h, g);
        //The second one
 
        // 13. w = w-alpha*M^{-1} A y0
        // w = w - alpha * g;
        Add(-alpha, g, w);
        // 18. d = y0+((theta0^2)*eta0/alpha)*d
        Mlt(theta * theta * eta / alpha,d);
        Add(one, y0, d);
        // 14. theta=||w||_2/tau0
        if (tau == Treal(0))
          {
            iter.Fail(4, "Tfqmr breakdown: tau=0");
            break;
          }
        theta = Norm2(w) / tau;
 
        // 15. c = 1/sqrt(1+theta^2)
        c = Treal(1) / sqrt(Treal(1) + theta * theta);
 
        // 16. tau = tau0*theta*c
        tau = tau * c * theta;
 
        // 17.  eta = (c^2)*alpha
        eta = c * c * alpha;
 
        // 19. x = x+eta*d
        Add(eta, d, x);
 
        // 20. kappa = tau*sqrt(m+1)
        kappa = tau * sqrt(Treal(2)* (iter.GetNumberIteration()+1)  + Treal(1));
 
        // 21. check stopping criterion
        if ( iter.Finished(kappa) )
          {
            break;
          }
 
        // 22. rho = dot(rtilde,w)
        // 23. beta = rho/rho0                     //need check breakdown
 
        rho0 = rho;
        rho = DotProd(rtilde, w);
        if (rho0 == zero)
          {
            iter.Fail(5, "tfqmr breakdown: beta=0");
            break;
          }
        beta = rho/rho0;
 
        // 24. y = w+beta*y0
        Copy(w, y1);
        Add(beta, y0, y1);
 
        // 25. g=M^{-1} A y
        Copy(y1, g);
        iter.Mlt(A, g, tmp);
        M.Solve(A, tmp, g);
 
        // 26. v = M^{-1}A y + beta*( M^{-1} A y0 + beta*v)
 
        Mlt(beta*beta, v);
        Add(beta, h, v);
        Add(one, g, v);
 
        ++iter;
      }
    
    return iter.ErrorCode();
  }
 
} // end namespace
 
#define SELDON_FILE_ITERATIVE_TFQMR_CXX
#endif