STK++ 0.9.13
Public Types | Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | Private Attributes | List of all members
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor > Class Template Reference
Algebra

In most cases, preconditioning is necessary to ensure fast convergence of the conjugate gradient method. More...

#include <STK_CG.h>

Public Types

typedef ColVector::Type Type
 

Public Member Functions

 r_ ()
 
 iter_ (0)
 
 eps_ (eps)
 
p_mult_ p_cond_ p_init_ (p_init)
 
 PCG (PCG const &pcg)
 Copy constructor.
 
 ~PCG ()
 destructor
 
PCG * clone () const
 clone pattern
 
ColVector const & x () const
 
Real const & x (int const &i) const
 
ColVector const & r () const
 
void setEps (Type const &eps)
 Set the tolerance.
 
void setB (ColVector const &b)
 Set the constant vector.
 
void setInitFunctor (InitFunctor const &init)
 Set functor computing x at initialization.
 
void setMultFunctor (MultFunctor const &mult)
 Set functor computing Ax.
 
void setCondFunctor (CondFunctor const &cond)
 Set functor computing the value $ \mathbf{M}^{-1} \mathbf{r}$.
 
int run ()
 run the conjugate gradient
 
String const & error () const
 get the last error message.
 

Public Attributes

 : x_()
 Constructor.
 
p_mult_ mult
 
p_mult_ p_cond_ cond
 
p_mult_ p_cond_ p_b_ b {}
 

Protected Member Functions

int pcg ()
 preconditioned Gradient implementation
 

Protected Attributes

String msg_error_
 String with the last error message.
 

Private Attributes

ColVector x_
 solution of the system
 
ColVector r_
 residuals of the system
 
int iter_
 number of iterations
 
Type eps_
 tolerance
 
MultFunctor const * p_mult_
 pointer on the functor performing Ax
 
CondFunctor const * p_cond_
 pointer on the functor performing $ \mathbf{M}^{-1} \mathbf{r}$
 
InitFunctor const * p_init_
 pointer on the functor initializing x
 
ColVector const * p_b_
 constant pointer on the second member of the system
 

Detailed Description

template<class MultFunctor, class CondFunctor, class ColVector, class InitFunctor = DefaultFunctor<ColVector>>
class STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >

In most cases, preconditioning is necessary to ensure fast convergence of the conjugate gradient method.

The preconditioned conjugate gradient method takes the following form:

\[ \begin{array}{l} \mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_0 \\ \mathbf{z}_0 := \mathbf{M}^{-1} \mathbf{r}_0\\ \mathbf{p}_0 := \mathbf{z}_0 \\ k := 0 \\ \hbox{repeat} \\ \qquad \alpha_k := \frac{\mathbf{r}_k^\mathrm{T} \mathbf{z}_k}{\mathbf{p}_k^\mathrm{T} \mathbf{A p}_k} \\ \qquad \mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k \\ \qquad \mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k \\ \qquad \hbox{if } r_{k+1} \hbox{ is sufficiently small then exit loop} \\ \qquad \mathbf{z}_{k+1} := \mathbf{M}^{-1} \mathbf{r}_{k+1} \\ \qquad \beta_k := \frac{\mathbf{z}_{k+1}^\mathrm{T} \mathbf{r}_{k+1}}{\mathbf{r}_k^\mathrm{T} \mathbf{r}_k} \\ \qquad \mathbf{p}_{k+1} := \mathbf{z}_{k+1} + \beta_k \mathbf{p}_k \\ \qquad k := k + 1 \\ \hbox{end repeat} \end{array} \]

The result is $ x_{k+1}$

The above formulation is equivalent to applying the conjugate gradient method without preconditioning to the system $\mathbf{E}^{-1}\mathbf{A}(\mathbf{E}^{-1})^\mathrm{T}\mathbf{\hat{x}}=\mathbf{E}^{-1}\mathbf{b}$ where $\mathbf{EE}^\mathrm{T}=\mathbf{M}$ and $\mathbf{\hat{x}}=\mathbf{E}^\mathrm{T}\mathbf{x}$.

The preconditioner matrix M has to be symmetric positive-definite and fixed, i.e., cannot change from iteration to iteration. If any of these assumptions on the preconditioner is violated, the behavior of the preconditioned conjugate gradient method may become unpredictable.

Template Parameters
MultFunctorA functor computing the result of Ax.
CondFunctorA functor computing the value $ \mathbf{M}^{-1} \mathbf{r}$.
InitFunctorA functor computing the initial value x.
ColVectorThe type of the containers for the vectors.

Definition at line 264 of file STK_CG.h.

Member Typedef Documentation

◆ Type

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
typedef ColVector::Type STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::Type

Definition at line 267 of file STK_CG.h.

Constructor & Destructor Documentation

◆ PCG()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::PCG ( PCG< MultFunctor, CondFunctor, ColVector, InitFunctor > const &  pcg)
inline

Copy constructor.

The constructor to copy.

Parameters
pcgthe preconditioned conjugate gradient to copy

Definition at line 285 of file STK_CG.h.

286 : x_(pcg.x_), r_(pcg.r_)
287 , eps_(pcg.eps_), iter_(0)
288 , p_mult_(pcg.p_mult_)
289 , p_cond_(pcg.p_cond_)
290 , p_init_(pcg.p_init_)
291 , p_b_(pcg.p_b_)
292 {};
STK::PCG::eps_
Type eps_
tolerance
Definition STK_CG.h:382
STK::PCG::p_cond_
CondFunctor const * p_cond_
pointer on the functor performing
Definition STK_CG.h:386
STK::PCG::x_
ColVector x_
solution of the system
Definition STK_CG.h:376
STK::PCG::p_init_
InitFunctor const * p_init_
pointer on the functor initializing x
Definition STK_CG.h:388
STK::PCG::iter_
int iter_
number of iterations
Definition STK_CG.h:380
STK::PCG::pcg
int pcg()
preconditioned Gradient implementation
Definition STK_CG.h:325
STK::PCG::p_b_
ColVector const * p_b_
constant pointer on the second member of the system
Definition STK_CG.h:390
STK::PCG::r_
ColVector r_
residuals of the system
Definition STK_CG.h:378
STK::PCG::p_mult_
MultFunctor const * p_mult_
pointer on the functor performing Ax
Definition STK_CG.h:384

◆ ~PCG()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::~PCG ( )
inline

destructor

Definition at line 294 of file STK_CG.h.

294{};

Member Function Documentation

◆ clone()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
PCG * STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::clone ( ) const
inline

clone pattern

Definition at line 296 of file STK_CG.h.

296{ return new PCG(*this);}
STK::PCG::PCG
PCG(PCG const &pcg)
Copy constructor.
Definition STK_CG.h:285

◆ eps_()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::eps_ ( eps  )

◆ error()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
String const & STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::error ( ) const
inline

get the last error message.

Returns
the last error message

Definition at line 319 of file STK_CG.h.

319{ return msg_error_;}
STK::PCG::msg_error_
String msg_error_
String with the last error message.
Definition STK_CG.h:323

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::msg_error_.

◆ iter_()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::iter_ ( 0  )

◆ p_init_()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
p_mult_ p_cond_ STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_init_ ( p_init  )

◆ pcg()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
int STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg ( )
inlineprotected

preconditioned Gradient implementation

Definition at line 325 of file STK_CG.h.

326 {
327 int nbStart = 0;
328 ColVector xOld, y, z, p;
329
330 Real bnorm2 = p_b_->norm2(), alpha, beta; //
331 iter_= 0;
332 // initialization
333 if(!p_init_) {x_ = *p_b_;}
334 else { x_ = (*p_init_)();}
335 // first loop -> allow to restart algorithm in case of divergence.
336 while(nbStart<2)
337 {
338 if (bnorm2 == 0.) bnorm2 = 1.;
339 //compute the residuals
340 r_ = *p_b_ - (*p_mult_)(x_);
341 if (r_.norm2()/bnorm2 <eps_) { break;}
342 //initialization of the conjugate direction
343 y = (*p_cond_)(r_);
344 p = y;
345 Real rty=r_.dot(y);
346 while(1)
347 {
348 Real rnorm2 = r_.norm2();
349 //compute z=A p
350 z.move((*p_mult_)(p));
351 //compute alpha
352 alpha = rty/p.dot(z);
353 //update x_
354 xOld.exchange(x_);
355 x_ = xOld + alpha * p;
356 iter_++;
357 //update residuals
358 r_ = r_ - (alpha * z);
359 //update y
360 y = (*p_cond_)(r_);
361 //compute beta
362 beta = 1/rty;
363 if ((rnorm2=r_.norm2())/bnorm2 <eps_) { nbStart = 2; break;}
364 rty = r_.dot(y);
365 beta *= rty;
366 //update p_
367 p = (p * beta) + y;
368 }
369 nbStart++;
370 }
371 return iter_;
372 }
STK::Real
double Real
STK fundamental type of Real values.
Definition STK_Typedefs.h:118

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::eps_, STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::iter_, STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_b_, STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_init_, STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_mult_, STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r_, and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x_.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::run().

◆ r()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
ColVector const & STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r ( ) const
inline
Returns
the residuals b-A*x

Definition at line 303 of file STK_CG.h.

303{ return r_;}

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r_.

◆ r_()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r_ ( )

◆ run()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
int STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::run ( )
inline

run the conjugate gradient

Definition at line 315 of file STK_CG.h.

315{ return pcg();}

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg().

◆ setB()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
void STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setB ( ColVector const &  b)
inline

Set the constant vector.

Definition at line 307 of file STK_CG.h.

307{ p_b_=&b;}
STK::PCG::b
p_mult_ p_cond_ p_b_ b
Definition STK_CG.h:281

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::b, and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_b_.

◆ setCondFunctor()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
void STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setCondFunctor ( CondFunctor const &  cond)
inline

Set functor computing the value $ \mathbf{M}^{-1} \mathbf{r}$.

Definition at line 313 of file STK_CG.h.

313{ p_cond_= &cond; }
STK::PCG::cond
p_mult_ p_cond_ cond
Definition STK_CG.h:278

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::cond, and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_cond_.

◆ setEps()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
void STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setEps ( Type const &  eps)
inline

Set the tolerance.

Definition at line 305 of file STK_CG.h.

305{eps_ = eps;}

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::eps_.

◆ setInitFunctor()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
void STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setInitFunctor ( InitFunctor const &  init)
inline

Set functor computing x at initialization.

Definition at line 309 of file STK_CG.h.

309{ p_init_= &init; }

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_init_.

◆ setMultFunctor()

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
void STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setMultFunctor ( MultFunctor const &  mult)
inline

Set functor computing Ax.

Definition at line 311 of file STK_CG.h.

311{ p_mult_= &mult; }
STK::PCG::mult
p_mult_ mult
Definition STK_CG.h:277

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::mult, and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_mult_.

◆ x() [1/2]

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
ColVector const & STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x ( ) const
inline
Returns
the solution of the linear system Ax=b

Definition at line 299 of file STK_CG.h.

299{ return x_;}

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x_.

◆ x() [2/2]

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
Real const & STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x ( int const &  i) const
inline
Returns
the ith coordinate of the solution of the linear system Ax=b

Definition at line 301 of file STK_CG.h.

301{ return x_[i];}

References STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x_.

Member Data Documentation

◆ __pad0__

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::__pad0__

Constructor.

Parameters
p_multfunctor which compute Ax with A a matrix and x a vector
bfrom Ax=b
p_initfunctor which initialize x a vector
epstolerance

Definition at line 267 of file STK_CG.h.

◆ b

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
p_mult_ p_cond_ p_b_ STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::b {}

Definition at line 280 of file STK_CG.h.

281{};

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setB().

◆ cond

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
p_mult_ p_cond_ STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::cond

Definition at line 278 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setCondFunctor().

◆ eps_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
Type STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::eps_
private

tolerance

Definition at line 382 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setEps().

◆ iter_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
int STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::iter_
private

number of iterations

Definition at line 380 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg().

◆ msg_error_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
String STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::msg_error_
protected

String with the last error message.

Definition at line 323 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::error().

◆ mult

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
p_mult_ STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::mult

Definition at line 277 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setMultFunctor().

◆ p_b_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
ColVector const* STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_b_
private

constant pointer on the second member of the system

Definition at line 390 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setB().

◆ p_cond_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
CondFunctor const* STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_cond_
private

pointer on the functor performing $ \mathbf{M}^{-1} \mathbf{r}$

Definition at line 386 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setCondFunctor().

◆ p_init_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
InitFunctor const* STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_init_
private

pointer on the functor initializing x

Definition at line 388 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setInitFunctor().

◆ p_mult_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
MultFunctor const* STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::p_mult_
private

pointer on the functor performing Ax

Definition at line 384 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::setMultFunctor().

◆ r_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
ColVector STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r_
private

residuals of the system

Definition at line 378 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::r().

◆ x_

template<class MultFunctor , class CondFunctor , class ColVector , class InitFunctor = DefaultFunctor<ColVector>>
ColVector STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x_
private

solution of the system

Definition at line 376 of file STK_CG.h.

Referenced by STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::pcg(), STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x(), and STK::PCG< MultFunctor, CondFunctor, ColVector, InitFunctor >::x().

The documentation for this class was generated from the following file: