Blender V5.3
ConstrainedConjugateGradient.h
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
10
11#include <Eigen/Core>
12#include <Eigen/IterativeLinearSolvers>
13#include <Eigen/Sparse>
14
15class ConstrainedConjugateGradient;
16
17namespace blender::Eigen {
18
19namespace internal {
20
33template<typename MatrixType,
34 typename Rhs,
35 typename Dest,
36 typename FilterMatrixType,
37 typename Preconditioner>
38EIGEN_DONT_INLINE void constrained_conjugate_gradient(const MatrixType &mat,
39 const Rhs &rhs,
40 Dest &x,
41 const FilterMatrixType &filter,
42 const Preconditioner &precond,
43 int &iters,
44 typename Dest::RealScalar &tol_error)
45{
46 using std::abs;
47 using std::sqrt;
48 using RealScalar = typename Dest::RealScalar;
49 using Scalar = typename Dest::Scalar;
50 using VectorType = Matrix<Scalar, Dynamic, 1>;
51
52 RealScalar tol = tol_error;
53 int maxIters = iters;
54
55 int n = mat.cols();
56
57 VectorType residual = filter * (rhs - mat * x); /* initial residual */
58
59 RealScalar rhsNorm2 = (filter * rhs).squaredNorm();
60 if (rhsNorm2 == 0) {
61 /* XXX TODO: set constrained result here. */
62 x.setZero();
63 iters = 0;
64 tol_error = 0;
65 return;
66 }
67 RealScalar threshold = tol * tol * rhsNorm2;
68 RealScalar residualNorm2 = residual.squaredNorm();
69 if (residualNorm2 < threshold) {
70 iters = 0;
71 tol_error = sqrt(residualNorm2 / rhsNorm2);
72 return;
73 }
74
75 VectorType p(n);
76 p = filter * precond.solve(residual); /* initial search direction */
77
78 VectorType z(n), tmp(n);
79 RealScalar absNew = numext::real(
80 residual.dot(p)); /* The square of the absolute value of `r` scaled by `invM`. */
81 int i = 0;
82 while (i < maxIters) {
83 tmp.noalias() = filter * (mat * p); /* The bottleneck of the algorithm. */
84
85 Scalar alpha = absNew / p.dot(tmp); /* The amount we travel on direction. */
86 x += alpha * p; /* Update solution. */
87 residual -= alpha * tmp; /* Update residue. */
88
89 residualNorm2 = residual.squaredNorm();
90 if (residualNorm2 < threshold) {
91 break;
92 }
93
94 z = precond.solve(residual); /* Approximately solve for `A z = residual`. */
95
96 RealScalar absOld = absNew;
97 absNew = numext::real(residual.dot(z)); /* Update the absolute value of `r`. */
98
99 /* Calculate the Gram-Schmidt value used to create the new search direction. */
100 RealScalar beta = absNew / absOld;
101
102 p = filter * (z + beta * p); /* Update search direction. */
103 i++;
104 }
105 tol_error = sqrt(residualNorm2 / rhsNorm2);
106 iters = i;
107}
108
109} // namespace internal
110
111#if 0 /* unused */
112template<typename MatrixType> struct MatrixFilter {
113 MatrixFilter() : m_cmat(NULL) {}
114
115 MatrixFilter(const MatrixType &cmat) : m_cmat(&cmat) {}
116
117 void setMatrix(const MatrixType &cmat)
118 {
119 m_cmat = &cmat;
120 }
121
122 template<typename VectorType> void apply(VectorType v) const
123 {
124 v = (*m_cmat) * v;
125 }
126
127 protected:
128 const MatrixType *m_cmat;
129};
130#endif
131
132template<typename _MatrixType,
133 int _UpLo = Lower,
134 typename _FilterMatrixType = _MatrixType,
135 typename _Preconditioner = DiagonalPreconditioner<typename _MatrixType::Scalar>>
136namespace internal
137{
138
139 template<typename _MatrixType, int _UpLo, typename _FilterMatrixType, typename _Preconditioner>
140 struct traits<
141 ConstrainedConjugateGradient<_MatrixType, _UpLo, _FilterMatrixType, _Preconditioner>> {
142 using MatrixType = _MatrixType;
143 using FilterMatrixType = _FilterMatrixType;
144 using Preconditioner = _Preconditioner;
145 };
146
147} // namespace internal
148
199template<typename _MatrixType, int _UpLo, typename _FilterMatrixType, typename _Preconditioner>
201 : public IterativeSolverBase<
202 ConstrainedConjugateGradient<_MatrixType, _UpLo, _FilterMatrixType, _Preconditioner>> {
203 using Base = IterativeSolverBase<ConstrainedConjugateGradient>;
204 using Base::m_error;
205 using Base::m_info;
206 using Base::m_isInitialized;
207 using Base::m_iterations;
208 using Base::mp_matrix;
209
210 public:
211 using MatrixType = _MatrixType;
212 using Scalar = typename MatrixType::Scalar;
213 using Index = typename MatrixType::Index;
214 using RealScalar = typename MatrixType::RealScalar;
215 using FilterMatrixType = _FilterMatrixType;
216 using Preconditioner = _Preconditioner;
217
218 enum { UpLo = _UpLo };
219
222
235
237
239 {
240 return m_filter;
241 }
243 {
244 return m_filter;
245 }
246
253 template<typename Rhs, typename Guess>
254 internal::solve_retval_with_guess<ConstrainedConjugateGradient, Rhs, Guess> solveWithGuess(
255 const MatrixBase<Rhs> &b, const Guess &x0) const
256 {
257 eigen_assert(m_isInitialized && "ConjugateGradient is not initialized.");
258 eigen_assert(
259 Base::rows() == b.rows() &&
260 "ConjugateGradient::solve(): invalid number of rows of the right hand side matrix b");
261 return internal::solve_retval_with_guess<ConstrainedConjugateGradient, Rhs, Guess>(
262 *this, b.derived(), x0);
263 }
264
266 template<typename Rhs, typename Dest> void _solveWithGuess(const Rhs &b, Dest &x) const
267 {
268 m_iterations = Base::maxIterations();
269 m_error = Base::m_tolerance;
270
271 for (int j = 0; j < b.cols(); j++) {
272 m_iterations = Base::maxIterations();
273 m_error = Base::m_tolerance;
274
275 typename Dest::ColXpr xj(x, j);
276 internal::constrained_conjugate_gradient(mp_matrix->template selfadjointView<UpLo>(),
277 b.col(j),
278 xj,
279 m_filter,
280 Base::m_preconditioner,
281 m_iterations,
282 m_error);
283 }
284
285 m_isInitialized = true;
286 m_info = m_error <= Base::m_tolerance ? Success : NoConvergence;
287 }
288
290 template<typename Rhs, typename Dest> void _solve(const Rhs &b, Dest &x) const
291 {
292 x.setOnes();
294 }
295
296 protected:
298};
299
300namespace internal {
301
302template<typename _MatrixType, int _UpLo, typename _Filter, typename _Preconditioner, typename Rhs>
303struct solve_retval<ConstrainedConjugateGradient<_MatrixType, _UpLo, _Filter, _Preconditioner>,
304 Rhs>
305 : solve_retval_base<ConstrainedConjugateGradient<_MatrixType, _UpLo, _Filter, _Preconditioner>,
306 Rhs> {
308 EIGEN_MAKE_SOLVE_HELPERS(Dec, Rhs)
309
310 template<typename Dest> void evalTo(Dest &dst) const
311 {
312 dec()._solve(rhs(), dst);
313 }
314};
315
316} // end namespace internal
317
318} // namespace blender::Eigen
#define A
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
A conjugate gradient solver for sparse self-adjoint problems with additional constraints.
internal::solve_retval_with_guess< ConstrainedConjugateGradient, Rhs, Guess > solveWithGuess(const MatrixBase< Rhs > &b, const Guess &x0) const
ccl_device_inline float beta(const float x, const float y)
Definition math_base.h:708
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)
void apply(bContext &C, GestureData &gesture_data, wmOperator &op)
ATTR_WARN_UNUSED_RESULT const BMVert * v
sqrt(x)+1/max(0
float Scalar
Definition eigen_utils.h:28