Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Ridders.h
1// SPDX-FileCopyrightText: The Eigen Authors
2// SPDX-License-Identifier: MPL-2.0
3
4#ifndef EIGEN_NUMERICALDIFF_RIDDERS_H
5#define EIGEN_NUMERICALDIFF_RIDDERS_H
6
7// IWYU pragma: private
8#include "./InternalHeaderCheck.h"
9
10namespace Eigen {
11
12namespace internal {
13
14template <typename F, typename = void>
15struct ridders_solver_traits {};
16
17template <typename F>
18struct ridders_solver_traits<F, void_t<typename F::QRSolver>> {
19 using QRSolver = typename F::QRSolver;
20};
21
22} // namespace internal
23
48template <typename Functor_>
49class Ridders : public internal::ridders_solver_traits<Functor_> {
50 public:
51 EIGEN_MAKE_ALIGNED_OPERATOR_NEW
52
53 using Functor = Functor_;
54 using Scalar = typename Functor::Scalar;
55 using InputType = typename Functor::InputType;
56 using ValueType = typename Functor::ValueType;
57 using JacobianType = typename Functor::JacobianType;
58
59 static constexpr int InputsAtCompileTime = Functor::InputsAtCompileTime;
60 static constexpr int ValuesAtCompileTime = Functor::ValuesAtCompileTime;
61
63 struct Parameters {
66 Scalar initialStep = Scalar(0.01);
71 Scalar stepReduction = Scalar(2);
74 int maxSteps = 10;
75 };
76
77 Ridders() = default;
78
82 explicit Ridders(const Functor& functor, const Parameters& parameters = Parameters()) : m_functor(functor) {
84 }
85
89 eigen_assert(parameters.initialStep > Scalar(0) && (numext::isfinite)(parameters.initialStep));
90 eigen_assert(parameters.stepReduction > Scalar(1) &&
91 (numext::isfinite)(parameters.stepReduction * parameters.stepReduction));
92 eigen_assert(parameters.maxSteps >= 2);
93 eigen_assert(parameters.maxSteps <= NumTraits<Index>::highest() / 2);
94 m_parameters = parameters;
95 }
96
98 const Parameters& parameters() const { return m_parameters; }
100 Functor& functor() { return m_functor; }
102 const Functor& functor() const { return m_functor; }
103
108 int operator()(const InputType& x, ValueType& values) const { return m_functor(x, values); }
110 int inputs() const { return m_functor.inputs(); }
112 int values() const { return m_functor.values(); }
113
129 int df(const InputType& x, JacobianType& jac) const { return dfImpl(x, jac, nullptr); }
130
143 int df(const InputType& x, JacobianType& jac, InputType& error) const {
144 error.resize(x.size());
145 return dfImpl(x, jac, &error);
146 }
147
148 private:
149 Functor m_functor;
150 Parameters m_parameters;
151
152 int dfImpl(const InputType& input, JacobianType& jac, InputType* error) const {
154 NUMERICAL_DIFF_REQUIRES_A_REAL_FLOATING_POINT_SCALAR);
155 // C. J. F. Ridders, "Accurate computation of F'(x) and F'(x)F''(x)",
156 // Advances in Engineering Software 4(2), 75-76 (1982). Extrapolate central differences in h^2.
158 const Index values = m_functor.values();
159 eigen_assert(jac.rows() == values && jac.cols() == input.size());
160 if (values == 0 || input.size() == 0) {
161 if (error) error->setZero();
162 return 0;
163 }
164
165 Tableau workspace(values, 2 * Index(m_parameters.maxSteps));
166 auto first = workspace.leftCols(m_parameters.maxSteps);
167 auto second = workspace.rightCols(m_parameters.maxSteps);
168 auto current = &first;
169 auto previous = &second;
170
171 // Functors may require ValueType& outputs, which cannot bind to column views.
172 ValueType plus(values), minus(values);
173 InputType x = input;
174 const Scalar reductionSquared = m_parameters.stepReduction * m_parameters.stepReduction;
175 int evaluations = 0;
176
177 for (Index j = 0; j < input.size(); ++j) {
178 Scalar h = m_parameters.initialStep * numext::maxi(numext::abs(input[j]), Scalar(1));
179 Scalar previousPlus = input[j], previousMinus = input[j];
180 Scalar bestError = NumTraits<Scalar>::infinity();
181 jac.col(j).setConstant(NumTraits<Scalar>::quiet_NaN());
182 for (int step = 0; step < m_parameters.maxSteps; ++step) {
183 Scalar xPlus = input[j] + h;
184 Scalar xMinus = input[j] - h;
185 internal::pbarrier(xPlus);
186 internal::pbarrier(xMinus);
187 if (!(numext::isfinite)(xPlus) || !(numext::isfinite)(xMinus)) break;
188 if (step > 0 && xPlus == previousPlus && xMinus == previousMinus) break;
189
190 const Scalar separation = xPlus - xMinus;
191 if (!(separation > Scalar(0)) || !(numext::isfinite)(separation)) break;
192 previousPlus = xPlus;
193 previousMinus = xMinus;
194
195 x[j] = xPlus;
196 m_functor(x, plus);
197 x[j] = xMinus;
198 m_functor(x, minus);
199 x[j] = input[j];
200 evaluations += 2;
201
202 current->col(0) = (plus - minus) / separation;
203 if (!current->col(0).allFinite()) {
204 if (separation <= Scalar(1)) break;
205 // Divide before subtracting to avoid overflow, preserving already finite quotients.
206 auto quotient = current->col(0).array();
207 quotient = quotient.isFiniteTyped().select(quotient, plus.array() / separation - minus.array() / separation);
208 if (!current->col(0).allFinite()) break;
209 }
210 Index bestOrder = step == 0 ? 0 : -1;
211
212 Scalar factor = reductionSquared;
213 bool finite = true;
214 for (int order = 1; order <= step; ++order) {
215 // A(k,i) = (t^(2k) * A(k-1,i) - A(k-1,i-1)) / (t^(2k) - 1).
216 // Avoid forming `t^(2k) * A(k-1,i)` directly, since it can overflow.
217 current->col(order) =
218 current->col(order - 1) + (current->col(order - 1) - previous->col(order - 1)) / (factor - Scalar(1));
219 if (!current->col(order).allFinite()) {
220 finite = false;
221 break;
222 }
223
224 const Scalar estimate =
225 numext::maxi((current->col(order) - current->col(order - 1)).template lpNorm<Infinity>(),
226 (current->col(order) - previous->col(order - 1)).template lpNorm<Infinity>());
227 if ((numext::isfinite)(estimate) && estimate <= bestError) {
228 bestError = estimate;
229 bestOrder = order;
230 }
231
232 factor *= reductionSquared;
233 }
234 if (bestOrder >= 0) jac.col(j) = current->col(bestOrder);
235 if (!finite) break;
236 if (step > 0 &&
237 (current->col(step) - previous->col(step - 1)).template lpNorm<Infinity>() >= Scalar(2) * bestError)
238 break;
239
240 std::swap(current, previous);
241 h /= m_parameters.stepReduction;
242 }
243 if (error) (*error)[j] = bestError;
244 }
245 return evaluations;
246 }
247};
248
249#if EIGEN_COMP_CXXVER < 17
250template <typename Functor>
251constexpr int Ridders<Functor>::InputsAtCompileTime;
252template <typename Functor>
253constexpr int Ridders<Functor>::ValuesAtCompileTime;
254#endif
255
256} // namespace Eigen
257
258#endif // EIGEN_NUMERICALDIFF_RIDDERS_H
int df(const InputType &x, JacobianType &jac, InputType &error) const
Computes the Jacobian and an absolute error estimate per input coordinate.
Definition Ridders.h:143
int values() const
Definition Ridders.h:112
const Parameters & parameters() const
Definition Ridders.h:98
void setParameters(const Parameters &parameters)
Sets the differentiation parameters.
Definition Ridders.h:88
Ridders(const Functor &functor, const Parameters &parameters=Parameters())
Constructs from a copy of a functor and differentiation parameters.
Definition Ridders.h:82
const Functor & functor() const
Definition Ridders.h:102
int inputs() const
Definition Ridders.h:110
int operator()(const InputType &x, ValueType &values) const
Evaluates the stored functor.
Definition Ridders.h:108
Functor & functor()
Definition Ridders.h:100
int df(const InputType &x, JacobianType &jac) const
Computes the Jacobian using adaptive central differences.
Definition Ridders.h:129
Namespace containing all symbols from the Eigen library.
Parameters controlling the initial interval and the maximum refinement cost.
Definition Ridders.h:63
int maxSteps
Maximum number of central differences per input coordinate. Must be at least two and at most half the...
Definition Ridders.h:74
Scalar stepReduction
Step reduction factor applied at each refinement. The factor must be greater than one and its square ...
Definition Ridders.h:71
Scalar initialStep
Initial step scale, giving . Must be positive and finite.
Definition Ridders.h:66