ConstrainedConjugateGradient.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) Blender Foundation
 * All rights reserved.
 */
 
#pragma once
 
#include <Eigen/Core>
 
namespace Eigen {
 
namespace internal {
 
template<typename MatrixType,
         typename Rhs,
         typename Dest,
         typename FilterMatrixType,
         typename Preconditioner>
EIGEN_DONT_INLINE void constrained_conjugate_gradient(const MatrixType &mat,
                                                      const Rhs &rhs,
                                                      Dest &x,
                                                      const FilterMatrixType &filter,
                                                      const Preconditioner &precond,
                                                      int &iters,
                                                      typename Dest::RealScalar &tol_error)
{
  using std::abs;
  using std::sqrt;
  typedef typename Dest::RealScalar RealScalar;
  typedef typename Dest::Scalar Scalar;
  typedef Matrix<Scalar, Dynamic, 1> VectorType;
 
  RealScalar tol = tol_error;
  int maxIters = iters;
 
  int n = mat.cols();
 
  VectorType residual = filter * (rhs - mat * x); /* initial residual */
 
  RealScalar rhsNorm2 = (filter * rhs).squaredNorm();
  if (rhsNorm2 == 0) {
    /* XXX TODO set constrained result here */
    x.setZero();
    iters = 0;
    tol_error = 0;
    return;
  }
  RealScalar threshold = tol * tol * rhsNorm2;
  RealScalar residualNorm2 = residual.squaredNorm();
  if (residualNorm2 < threshold) {
    iters = 0;
    tol_error = sqrt(residualNorm2 / rhsNorm2);
    return;
  }
 
  VectorType p(n);
  p = filter * precond.solve(residual); /* initial search direction */
 
  VectorType z(n), tmp(n);
  RealScalar absNew = numext::real(
      residual.dot(p)); /* the square of the absolute value of r scaled by invM */
  int i = 0;
  while (i < maxIters) {
    tmp.noalias() = filter * (mat * p); /* the bottleneck of the algorithm */
 
    Scalar alpha = absNew / p.dot(tmp); /* the amount we travel on dir */
    x += alpha * p;                     /* update solution */
    residual -= alpha * tmp;            /* update residue */
 
    residualNorm2 = residual.squaredNorm();
    if (residualNorm2 < threshold) {
      break;
    }
 
    z = precond.solve(residual); /* approximately solve for "A z = residual" */
 
    RealScalar absOld = absNew;
    absNew = numext::real(residual.dot(z)); /* update the absolute value of r */
    RealScalar beta =
        absNew /
        absOld; /* calculate the Gram-Schmidt value used to create the new search direction */
    p = filter * (z + beta * p); /* update search direction */
    i++;
  }
  tol_error = sqrt(residualNorm2 / rhsNorm2);
  iters = i;
}
 
}  // namespace internal
 
#if 0 /* unused */
template<typename MatrixType> struct MatrixFilter {
  MatrixFilter() : m_cmat(NULL)
  {
  }
 
  MatrixFilter(const MatrixType &cmat) : m_cmat(&cmat)
  {
  }
 
  void setMatrix(const MatrixType &cmat)
  {
    m_cmat = &cmat;
  }
 
  template<typename VectorType> void apply(VectorType v) const
  {
    v = (*m_cmat) * v;
  }
 
 protected:
  const MatrixType *m_cmat;
};
#endif
 
template<typename _MatrixType,
         int _UpLo = Lower,
         typename _FilterMatrixType = _MatrixType,
         typename _Preconditioner = DiagonalPreconditioner<typename _MatrixType::Scalar>>
class ConstrainedConjugateGradient;
 
namespace internal {
 
template<typename _MatrixType, int _UpLo, typename _FilterMatrixType, typename _Preconditioner>
struct traits<
    ConstrainedConjugateGradient<_MatrixType, _UpLo, _FilterMatrixType, _Preconditioner>> {
  typedef _MatrixType MatrixType;
  typedef _FilterMatrixType FilterMatrixType;
  typedef _Preconditioner Preconditioner;
};
 
}  // namespace internal
 
template<typename _MatrixType, int _UpLo, typename _FilterMatrixType, typename _Preconditioner>
class ConstrainedConjugateGradient
    : public IterativeSolverBase<
          ConstrainedConjugateGradient<_MatrixType, _UpLo, _FilterMatrixType, _Preconditioner>> {
  typedef IterativeSolverBase<ConstrainedConjugateGradient> Base;
  using Base::m_error;
  using Base::m_info;
  using Base::m_isInitialized;
  using Base::m_iterations;
  using Base::mp_matrix;
 
 public:
  typedef _MatrixType MatrixType;
  typedef typename MatrixType::Scalar Scalar;
  typedef typename MatrixType::Index Index;
  typedef typename MatrixType::RealScalar RealScalar;
  typedef _FilterMatrixType FilterMatrixType;
  typedef _Preconditioner Preconditioner;
 
  enum { UpLo = _UpLo };
 
 public:
  ConstrainedConjugateGradient() : Base()
  {
  }
 
  ConstrainedConjugateGradient(const MatrixType &A) : Base(A)
  {
  }
 
  ~ConstrainedConjugateGradient()
  {
  }
 
  FilterMatrixType &filter()
  {
    return m_filter;
  }
  const FilterMatrixType &filter() const
  {
    return m_filter;
  }
 
  template<typename Rhs, typename Guess>
  inline const internal::solve_retval_with_guess<ConstrainedConjugateGradient, Rhs, Guess>
  solveWithGuess(const MatrixBase<Rhs> &b, const Guess &x0) const
  {
    eigen_assert(m_isInitialized && "ConjugateGradient is not initialized.");
    eigen_assert(
        Base::rows() == b.rows() &&
        "ConjugateGradient::solve(): invalid number of rows of the right hand side matrix b");
    return internal::solve_retval_with_guess<ConstrainedConjugateGradient, Rhs, Guess>(
        *this, b.derived(), x0);
  }
 
  template<typename Rhs, typename Dest> void _solveWithGuess(const Rhs &b, Dest &x) const
  {
    m_iterations = Base::maxIterations();
    m_error = Base::m_tolerance;
 
    for (int j = 0; j < b.cols(); j++) {
      m_iterations = Base::maxIterations();
      m_error = Base::m_tolerance;
 
      typename Dest::ColXpr xj(x, j);
      internal::constrained_conjugate_gradient(mp_matrix->template selfadjointView<UpLo>(),
                                               b.col(j),
                                               xj,
                                               m_filter,
                                               Base::m_preconditioner,
                                               m_iterations,
                                               m_error);
    }
 
    m_isInitialized = true;
    m_info = m_error <= Base::m_tolerance ? Success : NoConvergence;
  }
 
  template<typename Rhs, typename Dest> void _solve(const Rhs &b, Dest &x) const
  {
    x.setOnes();
    _solveWithGuess(b, x);
  }
 
 protected:
  FilterMatrixType m_filter;
};
 
namespace internal {
 
template<typename _MatrixType, int _UpLo, typename _Filter, typename _Preconditioner, typename Rhs>
struct solve_retval<ConstrainedConjugateGradient<_MatrixType, _UpLo, _Filter, _Preconditioner>,
                    Rhs>
    : solve_retval_base<ConstrainedConjugateGradient<_MatrixType, _UpLo, _Filter, _Preconditioner>,
                        Rhs> {
  typedef ConstrainedConjugateGradient<_MatrixType, _UpLo, _Filter, _Preconditioner> Dec;
  EIGEN_MAKE_SOLVE_HELPERS(Dec, Rhs)
 
  template<typename Dest> void evalTo(Dest &dst) const
  {
    dec()._solve(rhs(), dst);
  }
};
 
}  // end namespace internal
 
}  // end namespace Eigen