gtsam 4.1.1 gtsam
PowerMethod.h
Go to the documentation of this file.
1/* ----------------------------------------------------------------------------
2
3 * GTSAM Copyright 2010-2019, Georgia Tech Research Corporation,
4 * Atlanta, Georgia 30332-0415
6 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7
9
10 * -------------------------------------------------------------------------- */
11
20#pragma once
21
22#include <gtsam/base/Matrix.h>
23#include <gtsam/base/Vector.h>
24
25#include <Eigen/Core>
26#include <Eigen/Sparse>
27#include <random>
28#include <vector>
29
30namespace gtsam {
31
32using Sparse = Eigen::SparseMatrix<double>;
33
56template <class Operator>
58 protected:
63 const Operator &A_;
64
65 const int dim_; // dimension of Matrix A
66
67 size_t nrIterations_; // number of iterations
68
69 double ritzValue_; // Ritz eigenvalue
70 Vector ritzVector_; // Ritz eigenvector
71
72 public:
75
77 explicit PowerMethod(const Operator &A,
78 const boost::optional<Vector> initial = boost::none)
79 : A_(A), dim_(A.rows()), nrIterations_(0) {
80 Vector x0;
81 x0 = initial ? initial.get() : Vector::Random(dim_);
82 x0.normalize();
83
84 // initialize Ritz eigen value
85 ritzValue_ = 0.0;
86
87 // initialize Ritz eigen vector
88 ritzVector_ = powerIteration(x0);
89 }
90
95 Vector powerIteration(const Vector &x) const {
96 Vector y = A_ * x;
97 y.normalize();
98 return y;
99 }
100
105 Vector powerIteration() const { return powerIteration(ritzVector_); }
106
112 bool converged(double tol) const {
113 const Vector x = ritzVector_;
114 // store the Ritz eigen value
115 const double ritzValue = x.dot(A_ * x);
116 const double error = (A_ * x - ritzValue * x).norm();
117 return error < tol;
118 }
119
121 size_t nrIterations() const { return nrIterations_; }
122
129 bool compute(size_t maxIterations, double tol) {
130 // Starting
131 bool isConverged = false;
132
133 for (size_t i = 0; i < maxIterations && !isConverged; i++) {
134 ++nrIterations_;
135 // update the ritzVector after power iteration
136 ritzVector_ = powerIteration();
137 // update the ritzValue
138 ritzValue_ = ritzVector_.dot(A_ * ritzVector_);
139 isConverged = converged(tol);
140 }
141
142 return isConverged;
143 }
144
146 double eigenvalue() const { return ritzValue_; }
147
149 Vector eigenvector() const { return ritzVector_; }
150};
151
152} // namespace gtsam
typedef and functions to augment Eigen's MatrixXd
typedef and functions to augment Eigen's VectorXd
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
Compute maximum Eigenpair with power method.
Definition: PowerMethod.h:57
Vector powerIteration(const Vector &x) const
Run power iteration to get ritzVector with previous ritzVector x, and return A * x / || A * x ||.
Definition: PowerMethod.h:95
Vector eigenvector() const
Return the eigenvector.
Definition: PowerMethod.h:149
const Operator & A_
Const reference to an externally-held matrix whose minimum-eigenvalue we want to compute.
Definition: PowerMethod.h:63
double eigenvalue() const
Return the eigenvalue.
Definition: PowerMethod.h:146
PowerMethod(const Operator &A, const boost::optional< Vector > initial=boost::none)
Construct from the aim matrix and intial ritz vector.
Definition: PowerMethod.h:77
Vector powerIteration() const
Run power iteration to get ritzVector with previous ritzVector x, and return A * x / || A * x ||.
Definition: PowerMethod.h:105
bool converged(double tol) const
After Perform power iteration on a single Ritz value, check if the Ritz residual for the current Ritz...
Definition: PowerMethod.h:112
bool compute(size_t maxIterations, double tol)
Start the power/accelerated iteration, after performing the power/accelerated iteration,...
Definition: PowerMethod.h:129
size_t nrIterations() const
Return the number of iterations.
Definition: PowerMethod.h:121