ROL
ROL_Lanczos.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Rapid Optimization Library (ROL) Package
4 //
5 // Copyright 2014 NTESS and the ROL contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef ROL_LANCZOS_H
11 #define ROL_LANCZOS_H
12 
13 #include "ROL_Krylov.hpp"
14 #include "ROL_LinearOperator.hpp"
15 #include "ROL_Vector.hpp"
16 #include "ROL_Types.hpp"
17 #include "ROL_LAPACK.hpp"
18 
19 namespace ROL {
20 
29 template<class Real>
30 class Lanczos {
31 
32  template <typename T> using ROL::Ptr = ROL::Ptr<T>;
33  template <typename T> using vector = std::vector<T>;
34 
35  template typename vector<Real> size_type uint;
36 
37  typedef Vector<Real> V;
39 
40  typedef ROL::ParameterList PL;
41 
42 private:
43 
44  ROL::LAPACK<int,Real> lapack_;
45 
46  vector<ROL::Ptr<V> > Q_; // Orthogonal basis
47  vector<Real> alpha_; // Diagonal recursion coefficients
48  vector<Real> beta_; // Sub/super-diagonal recursion coefficients
49 
50  // Temporary vectors for factorizations, linear solves, and eigenvalue calculations
55  vector<Real> y_; // Arnoldi expansion coefficients
56 
57  vector<Real> work_; // Scratch space for eigenvalue decomposition
58  vector<int> ipiv_; // Pivots for LU
59 
60  ROL::Ptr<V> u_; // An auxilliary vector
61 
62  Real max_beta_; // maximum beta encountered
63  Real tol_beta_; // relative smallest beta allowed
64 
65  Real tol_ortho_; // Maximum orthogonality loss tolerance
66 
67  int maxit_; // Maximum number of vectors to store
68 
69  int k_; // current iterate number
70 
71 
72  // Allocte memory for Arnoldi vectors and recurions coefficients
73  void allocate( void ) {
74 
75  u_ = b.clone();
76 
77  alpha_.reserve(maxit_);
78  beta_.reserve(maxit_);
79 
80  dl_.reserve(maxit_);
81  d_.reserve(maxit_);
82  du_.reserve(maxit_);
83  du2_.reserve(maxit_);
84 
85  work_.reserve(4*maxit_);
86 
87  ipiv_.reserve(maxit_);
88 
89  y_.reserve(maxit_);
90 
91  alpha_.reserve(maxit_);
92  beta_.reserve(maxit_);
93 
94  for( uint j=0; j<maxit_; ++j ) {
95  Q_.push_back(b.clone());
96  }
97  }
98 
99 public:
100 
101  enum class FLAG_ITERATE : unsigned {
102  ITERATE_SUCCESS = 0,
103  ITERATE_SMALL_BETA, // Beta too small to continue
104  ITERATE_MAX_REACHED, // Reached maximum number of iterations
105  ITERATE_ORTHO_TOL, // Reached maximim orthogonality loss
107  };
108 
109  enum class FLAG_SOLVE : unsigned {
110  SOLVE_SUCCESS = 0,
113  SOLVE_LAST
114  };
115 
116 
117  Lanczos( ROL::ParameterList &PL ) {
118  PL &krylovList = parlist.sublist("General").sublist("Krylov");
119  PL &lanczosList = krylovList.sublist("Lanczos");
120 
121  Real tol_default = std::sqrt(ROL_EPSILON<Real>());
122 
123  maxit_ = krylovList_.get("Iteration Limit",10);
124  tol_beta_ = lanczosList.get("Beta Relative Tolerance", tol_default);
125  tol_ortho_ = lanczosList.get("Orthogonality Tolerance", tol_default);
126 
127  }
128 
129  void initialize( const V& b ) {
130  allocate();
131  reset(b);
132 
133  }
134 
135  void initialize( const V &x0, const V &b, const LO &A, Real &tol ) {
136  allocate();
137  reset(x0,b,A,tol);
138 
139  }
140 
141 
142  void reset( const V &b ) {
143  k_ = 0;
144  max_beta_ = 0;
145  Q_[0]->set(b);
146  beta_[0] = Q_[0]->norm();
147  max_beta_ = std::max(max_beta_,beta_[0]);
148  Q_[0]->scale(1.0/beta_[0]);
149  }
150 
151  void reset( const V &x0, const V &b, const LO &A, Real &tol ) {
152  k_ = 0;
153  max_beta_ = 0;
154  Q_[0]->set(b);
155  A.apply(*u_,x0,tol);
156  Q_[0]->axpy(-1.0,*u_);
157  beta_[0] = Q_[0]->norm();
158  max_beta_ = std::max(max_beta_,beta_[0]);
159  Q_[0]->scale(1.0/beta_[0]);
160  }
161 
162  FLAG_ITERATE iterate( const OP &A, Real &tol ) {
163 
164  if( k_ == maxit_ ) {
165  return ITERATE_MAX_REACHED;
166  }
167 
168  A.apply(*u_,*(Q_[k]),tol);
169  Real delta;
170 
171  if( k_>0 ) {
172  u_->axpy(-beta_[k],V_[k_-1]);
173  }
174  alpha_[k] = u_->dot(*(V_[k]));
175  u_->axpy(alpha_[k],V_[k_]);
176 
177  if( k_>0 ) {
178  delta = u_->dot(*(V_[k-1]));
179  u_->axpy(-delta,*(V_[k-1]));
180  }
181  delta = u_->dot(*(V_[k]));
182  alpha_[k] += delta;
183 
184  if( k_ < maxit_-1 ) {
185  u_->axpy(-delta,*(V_[k_]));
186  beta_[k+1] = u_->norm();
187  max_beta_ = std::max(max_beta_,beta_[k+1]);
188  if(beta_[k+1] < tol_beta_*max_beta_) {
189  return ITERATE_SMALL_BETA;
190  }
191 
192  V_[k+1]->set(*u_);
193  V_[k+1]->scale(1.0/beta_[k+1]);
194 
195  // Check orthogonality
196  Real dotprod = V_[k+1]->dot(*(V_[0]));
197 
198  if( std::sqrt(dotprod) > tol_ortho_ ) {
199  return ITERATE_ORTHO_TOL;
200  }
201  }
202 
203  ++k_;
204  return ITERATE_SUCCESS;
205  }
206 
207  // Compute the eigenvalues of the tridiagonal matrix T
208  void eigenvalues( std::vector<Real> &E ) {
209 
210  std::vector<Real> Z(1,0); // Don't compute eigenvectors
211 
212  int INFO;
213  int LDZ = 0;
214  const char COMPZ = 'N':
215  d_ = alpha_;
216  du_ = beta_;
217 
218  lapack_->STEQR(COMPZ,k_,&d_[0],&du_[0],&Z[0],LDZ,&work_[0],&INFO);
219 
220  if( INFO < 0 ) {
221  return SOLVE_ILLEGAL_VALUE;
222  }
223  else if( INFO > 0 ) {
224  return SOLVE_SINGULAR_U;
225  }
226 
227  }
228 
229  FLAG_SOLVE solve( V &x, Real tau=0 ) {
230 
231  const char TRANS = 'N';
232  const int NRHS = 1;
233  int INFO;
234 
235  // Fill arrays
236  for(uint j=0;j<k_;++j) {
237  d_[j] = alpha_[j]+tau;
238  }
239 
240  dl_ = beta_;
241  du_ = beta_;
242  du2_.assign(maxit_,0);
243 
244  // Do Tridiagonal LU factorization
245  lapack_->GTTRF(k_,&dl_[0],&d_[0],&du_[0],&du2_[0],&ipiv_[0],&INFO);
246 
247  // Solve the factorized system for Arnoldi expansion coefficients
248  lapack_->GTTRS(TRANS,k_,1,&dl[0],&d_[0],&du_[0],&du2_[0],&ipiv_[0],&y_[0],k_,&INFO);
249 
250  }
251 
252 
253 
254 }; // class LanczosFactorization
255 } // namespace ROL
256 
257 #endif // ROL_LANCZOS_H
void reset(const V &x0, const V &b, const LO &A, Real &tol)
vector< Real > y_
Definition: ROL_Lanczos.hpp:55
typename PV< Real >::size_type size_type
FLAG_SOLVE solve(V &x, Real tau=0)
std::vector< T > vector
Definition: ROL_Lanczos.hpp:33
vector< Real > work_
Definition: ROL_Lanczos.hpp:57
vector< Real > alpha_
Definition: ROL_Lanczos.hpp:47
ROL::LAPACK< int, Real > lapack_
Definition: ROL_Lanczos.hpp:44
Contains definitions of custom data types in ROL.
vector< int > ipiv_
Definition: ROL_Lanczos.hpp:58
LinearOperator< Real > OP
Definition: ROL_Lanczos.hpp:38
virtual void apply(Vector< Real > &Hv, const Vector< Real > &v, Real &tol) const =0
Apply linear operator.
Defines the linear algebra or vector space interface.
Definition: ROL_Vector.hpp:46
ROL::ParameterList PL
Definition: ROL_Lanczos.hpp:40
ROL::Ptr< V > u_
Definition: ROL_Lanczos.hpp:60
FLAG_ITERATE iterate(const OP &A, Real &tol)
Interface for computing the Lanczos vectors and approximate solutions to symmetric indefinite linear ...
Definition: ROL_Lanczos.hpp:30
vector< Real > du_
Definition: ROL_Lanczos.hpp:53
Lanczos(ROL::ParameterList &PL)
Provides the interface to apply a linear operator.
vector< ROL::Ptr< V > > Q_
Definition: ROL_Lanczos.hpp:46
Vector< Real > V
Definition: ROL_Lanczos.hpp:37
void initialize(const V &b)
vector< Real > dl_
Definition: ROL_Lanczos.hpp:51
vector< Real > d_
Definition: ROL_Lanczos.hpp:52
template vector< Real > size_type uint
Definition: ROL_Lanczos.hpp:35
void allocate(void)
Definition: ROL_Lanczos.hpp:73
void initialize(const V &x0, const V &b, const LO &A, Real &tol)
vector< Real > du2_
Definition: ROL_Lanczos.hpp:54
vector< Real > beta_
Definition: ROL_Lanczos.hpp:48
void reset(const V &b)
void eigenvalues(std::vector< Real > &E)