Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
PolynomialSolver.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2010 Manuel Yguel <manuel.yguel@gmail.com>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_POLYNOMIAL_SOLVER_H
12#define EIGEN_POLYNOMIAL_SOLVER_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
32template <typename Scalar_, int Deg_>
33class PolynomialSolverBase {
34 public:
35 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(Scalar_, Deg_ == Dynamic ? Dynamic : Deg_)
36
37 using Scalar = Scalar_;
38 using RealScalar = typename NumTraits<Scalar>::Real;
39 using RootType = internal::make_complex_t<Scalar>;
40 using RootsType = Matrix<RootType, Deg_, 1>;
41
42 using Index = DenseIndex;
43
44 protected:
45 template <typename OtherPolynomial>
46 inline void setPolynomial(const OtherPolynomial& poly) {
47 m_roots.resize(poly.size() - 1);
48 }
49
50 public:
51 template <typename OtherPolynomial>
52 inline PolynomialSolverBase(const OtherPolynomial& poly) {
53 setPolynomial(poly());
54 }
55
56 inline PolynomialSolverBase() {}
57
58 public:
60 inline const RootsType& roots() const { return m_roots; }
61
62 public:
73 template <typename Stl_back_insertion_sequence>
74 inline void realRoots(Stl_back_insertion_sequence& bi_seq,
75 const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
76 using std::abs;
77 bi_seq.clear();
78 for (Index i = 0; i < m_roots.size(); ++i) {
79 if (abs(m_roots[i].imag()) < absImaginaryThreshold) {
80 bi_seq.push_back(m_roots[i].real());
81 }
82 }
83 }
84
85 protected:
86 template <typename Predicate>
87 inline const RootType& selectComplexRoot_withRespectToNorm(Predicate& pred) const {
88 Index res = 0;
89 RealScalar norm2 = numext::abs2(m_roots[0]);
90 for (Index i = 1; i < m_roots.size(); ++i) {
91 const RealScalar currNorm2 = numext::abs2(m_roots[i]);
92 if (pred(currNorm2, norm2)) {
93 res = i;
94 norm2 = currNorm2;
95 }
96 }
97 return m_roots[res];
98 }
99
100 public:
104 inline const RootType& greatestRoot() const {
105 std::greater<RealScalar> greater;
106 return selectComplexRoot_withRespectToNorm(greater);
107 }
108
112 inline const RootType& smallestRoot() const {
113 std::less<RealScalar> less;
114 return selectComplexRoot_withRespectToNorm(less);
115 }
116
117 protected:
118 template <typename Predicate>
119 inline const RealScalar& selectRealRoot_withRespectToAbsRealPart(
120 Predicate& pred, bool& hasArealRoot,
121 const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
122 using std::abs;
123 hasArealRoot = false;
124 Index res = 0;
125 RealScalar val(0);
126
127 for (Index i = 0; i < m_roots.size(); ++i) {
128 if (abs(m_roots[i].imag()) <= absImaginaryThreshold) {
129 if (!hasArealRoot) {
130 hasArealRoot = true;
131 res = i;
132 val = abs(m_roots[i].real());
133 } else {
134 const RealScalar curr = abs(m_roots[i].real());
135 if (pred(curr, val)) {
136 val = curr;
137 res = i;
138 }
139 }
140 } else if (!hasArealRoot) {
141 if (abs(m_roots[i].imag()) < abs(m_roots[res].imag())) {
142 res = i;
143 }
144 }
145 }
146 return numext::real_ref(m_roots[res]);
147 }
148
149 template <typename Predicate>
150 inline const RealScalar& selectRealRoot_withRespectToRealPart(
151 Predicate& pred, bool& hasArealRoot,
152 const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
153 using std::abs;
154 hasArealRoot = false;
155 Index res = 0;
156 RealScalar val(0);
157
158 for (Index i = 0; i < m_roots.size(); ++i) {
159 if (abs(m_roots[i].imag()) <= absImaginaryThreshold) {
160 if (!hasArealRoot) {
161 hasArealRoot = true;
162 res = i;
163 val = m_roots[i].real();
164 } else {
165 const RealScalar curr = m_roots[i].real();
166 if (pred(curr, val)) {
167 val = curr;
168 res = i;
169 }
170 }
171 } else {
172 if (abs(m_roots[i].imag()) < abs(m_roots[res].imag())) {
173 res = i;
174 }
175 }
176 }
177 return numext::real_ref(m_roots[res]);
178 }
179
180 public:
195 inline const RealScalar& absGreatestRealRoot(
196 bool& hasArealRoot, const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
197 std::greater<RealScalar> greater;
198 return selectRealRoot_withRespectToAbsRealPart(greater, hasArealRoot, absImaginaryThreshold);
199 }
200
215 inline const RealScalar& absSmallestRealRoot(
216 bool& hasArealRoot, const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
217 std::less<RealScalar> less;
218 return selectRealRoot_withRespectToAbsRealPart(less, hasArealRoot, absImaginaryThreshold);
219 }
220
235 inline const RealScalar& greatestRealRoot(
236 bool& hasArealRoot, const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
237 std::greater<RealScalar> greater;
238 return selectRealRoot_withRespectToRealPart(greater, hasArealRoot, absImaginaryThreshold);
239 }
240
255 inline const RealScalar& smallestRealRoot(
256 bool& hasArealRoot, const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision()) const {
257 std::less<RealScalar> less;
258 return selectRealRoot_withRespectToRealPart(less, hasArealRoot, absImaginaryThreshold);
259 }
260
261 protected:
262 RootsType m_roots;
263};
264
265#define EIGEN_POLYNOMIAL_SOLVER_BASE_INHERITED_TYPES(BASE) \
266 using Scalar = typename BASE::Scalar; \
267 using RealScalar = typename BASE::RealScalar; \
268 using RootType = typename BASE::RootType; \
269 using RootsType = typename BASE::RootsType;
270
299template <typename Scalar_, int Deg_>
300class PolynomialSolver : public PolynomialSolverBase<Scalar_, Deg_> {
301 public:
302 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(Scalar_, Deg_ == Dynamic ? Dynamic : Deg_)
303
304 using PS_Base = PolynomialSolverBase<Scalar_, Deg_>;
305 EIGEN_POLYNOMIAL_SOLVER_BASE_INHERITED_TYPES(PS_Base)
306
307 using CompanionMatrixType = Matrix<Scalar, Deg_, Deg_>;
308 using EigenSolverType = std::conditional_t<NumTraits<Scalar>::IsComplex, ComplexEigenSolver<CompanionMatrixType>,
310 using ComplexScalar = internal::make_complex_t<Scalar_>;
311
312 public:
314 template <typename OtherPolynomial>
315 void compute(const OtherPolynomial& poly) {
316 eigen_assert(Scalar(0) != poly[poly.size() - 1]);
317 eigen_assert(poly.size() > 1);
318 if (poly.size() > 2) {
319 internal::companion<Scalar, Deg_> companion(poly);
320 companion.balance();
321 m_eigenSolver.compute(companion.denseMatrix());
322 eigen_assert(m_eigenSolver.info() == Eigen::Success);
323 m_roots = m_eigenSolver.eigenvalues();
324 // Uniform coefficient scaling must not overflow or underflow the refinement's Horner recurrences.
325 const RealScalar scale = poly.realView().cwiseAbs().maxCoeff();
326 const auto scaledPoly = (poly / scale).eval();
327 refineRoots(scaledPoly);
328 cleanUpRoots(scaledPoly);
329 } else if (poly.size() == 2) {
330 m_roots.resize(1);
331 m_roots[0] = -poly[0] / poly[1];
332 }
333 }
334
335 public:
336 template <typename OtherPolynomial>
337 inline PolynomialSolver(const OtherPolynomial& poly) {
338 compute(poly);
339 }
340
341 inline PolynomialSolver() {}
342
343 protected:
344 // Evaluates p(z) and p'(z) by Horner's rule. With withBound, returns Higham's running bound on the rounding error
345 // of the value (Higham 2002, Algorithm 5.1), otherwise zero: the moduli it needs cost more than the recurrence.
346 // The real bound is u (2 mu - |p(z)|), u = eps / 2; a complex product rounds by at most 2 sqrt(2) u |z| |y| and a
347 // complex sum by u |y|, so the complex bound is sqrt(2) eps (2 mu - |p(z)|).
348 template <typename OtherPolynomial>
349 static RealScalar evaluate(const OtherPolynomial& poly, const RootType& z, RootType& value, RootType& derivative,
350 bool withBound) {
351 const Index degree = poly.size() - 1;
352 value = RootType(poly[degree]);
353 derivative = RootType(0);
354 if (!withBound) {
355 for (Index k = degree - 1; k >= 0; --k) {
356 derivative = derivative * z + value;
357 value = value * z + RootType(poly[k]);
358 }
359 return RealScalar(0);
360 }
361 const RealScalar absz = numext::abs(z);
362 RealScalar mu = numext::abs(value) / RealScalar(2);
363 for (Index k = degree - 1; k >= 0; --k) {
364 derivative = derivative * z + value;
365 value = value * z + RootType(poly[k]);
366 mu = mu * absz + numext::abs(value);
367 }
368 const RealScalar errorScale = numext::sqrt(RealScalar(2)) * NumTraits<RealScalar>::epsilon();
369 return (RealScalar(2) * errorScale) * mu - errorScale * numext::abs(value);
370 }
371
380 template <typename OtherPolynomial>
381 void refineRoots(const OtherPolynomial& poly) {
382 const Index n = m_roots.size();
383 const RealScalar eps = NumTraits<RealScalar>::epsilon();
384 // Convergence is not guaranteed for clustered roots; retain the eigenvalue estimates as a fallback.
385 const int maxSweeps = NumTraits<RealScalar>::digits();
386 EIGEN_IF_CONSTEXPR (!NumTraits<Scalar>::IsComplex) {
387 for (Index i = 0; i < n; ++i) {
388 // Real iterates cannot reach a nonreal root; perturb by +/- i eps |z|.
389 if (numext::imag(m_roots[i]) == RealScalar(0)) {
390 const RealScalar perturbation = eps * numext::abs(m_roots[i]);
391 m_roots[i] += RootType(0, i % 2 == 0 ? perturbation : -perturbation);
392 }
393 }
394 }
396 RootType value, derivative;
397 for (int sweep = 0; sweep < maxSweeps; ++sweep) {
398 bool moving = false;
399 for (Index i = 0; i < n; ++i) {
400 if (!active[i]) continue;
401 const RootType z = m_roots[i];
402 // The eigenvalues can pass the rounding test with a backward error of ~10 eps, while one step from them
403 // lands near eps, so the test applies from the second sweep on.
404 const bool testResidual = sweep > 0;
405 const RealScalar bound = evaluate(poly, z, value, derivative, testResidual);
406 if ((testResidual && !(numext::abs(value) > bound)) || !(numext::isfinite)(bound) ||
407 derivative == RootType(0)) {
408 active[i] = false;
409 continue;
410 }
411 const RootType newton = value / derivative;
412 if (!(numext::abs(newton) > eps * numext::abs(z))) {
413 active[i] = false;
414 continue;
415 }
416 RootType repulsion(0);
417 for (Index j = 0; j < n; ++j) {
418 const RootType gap = z - m_roots[j];
419 if (j != i && gap != RootType(0)) repulsion += RootType(1) / gap;
420 }
421 const RootType denominator = RootType(1) - newton * repulsion;
422 const RootType refined = z - (denominator == RootType(0) ? newton : RootType(newton / denominator));
423 if ((numext::isfinite)(numext::abs(refined))) {
424 m_roots[i] = refined;
425 moving = true;
426 } else {
427 active[i] = false;
428 }
429 }
430 if (!moving) return;
431 }
432 // Keep improvements to slowly converging multiple roots, but reject a larger residual at the sweep cap.
433 for (Index i = 0; i < n; ++i) {
434 if (!active[i]) continue;
435 RootType initialValue;
436 evaluate(poly, m_roots[i], value, derivative, false);
437 evaluate(poly, m_eigenSolver.eigenvalues()[i], initialValue, derivative, false);
438 if (!(numext::abs(value) <= numext::abs(initialValue))) m_roots[i] = m_eigenSolver.eigenvalues()[i];
439 }
440 }
441
446 template <typename OtherPolynomial>
447 void cleanUpRoots(const OtherPolynomial& poly) {
448 const Index n = m_roots.size();
449 constexpr bool realPolynomial = !NumTraits<Scalar>::IsComplex;
451 EIGEN_IF_CONSTEXPR (realPolynomial) {
452 for (Index i = 0; i < n; ++i) {
453 if (!(numext::imag(m_roots[i]) > RealScalar(0))) continue;
454 Index partner = n;
455 RealScalar distance = numext::imag(m_roots[i]);
456 for (Index j = 0; j < n; ++j) {
457 if (paired[j] || !(numext::imag(m_roots[j]) < RealScalar(0))) continue;
458 const RealScalar d = numext::abs(m_roots[j] - numext::conj(m_roots[i]));
459 if (d < distance) {
460 distance = d;
461 partner = j;
462 }
463 }
464 if (partner < n) {
465 paired[i] = paired[partner] = true;
466 const RootType mean = (m_roots[i] + numext::conj(m_roots[partner])) / RealScalar(2);
467 m_roots[i] = mean;
468 m_roots[partner] = numext::conj(mean);
469 }
470 }
471 }
472 RootType value, derivative;
473 for (Index i = 0; i < n; ++i) {
474 if (numext::imag(m_roots[i]) == RealScalar(0)) continue;
475 const RootType realPart(numext::real(m_roots[i]));
476 if (realPolynomial && !paired[i]) {
477 m_roots[i] = realPart;
478 continue;
479 }
480 // A small residual at realPart can belong to a different root.
481 if (!(numext::abs(numext::imag(m_roots[i])) <=
482 numext::sqrt(NumTraits<RealScalar>::epsilon()) * numext::abs(realPart)))
483 continue;
484 const RealScalar bound = evaluate(poly, realPart, value, derivative, true);
485 if ((numext::isfinite)(bound) && numext::abs(value) <= bound) m_roots[i] = realPart;
486 }
487 }
488
489 using PS_Base::m_roots;
490 EigenSolverType m_eigenSolver;
491};
492
493template <typename Scalar_>
494class PolynomialSolver<Scalar_, 1> : public PolynomialSolverBase<Scalar_, 1> {
495 public:
496 using PS_Base = PolynomialSolverBase<Scalar_, 1>;
497 EIGEN_POLYNOMIAL_SOLVER_BASE_INHERITED_TYPES(PS_Base)
498
499 public:
501 template <typename OtherPolynomial>
502 void compute(const OtherPolynomial& poly) {
503 eigen_assert(poly.size() == 2);
504 eigen_assert(Scalar(0) != poly[1]);
505 m_roots[0] = -poly[0] / poly[1];
506 }
507
508 public:
509 template <typename OtherPolynomial>
510 inline PolynomialSolver(const OtherPolynomial& poly) {
511 compute(poly);
512 }
513
514 inline PolynomialSolver() {}
515
516 protected:
517 using PS_Base::m_roots;
518};
519
520} // end namespace Eigen
521
522#endif // EIGEN_POLYNOMIAL_SOLVER_H
constexpr void resize(Index rows, Index cols)
const RealScalar & smallestRealRoot(bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Definition PolynomialSolver.h:255
const RealScalar & absGreatestRealRoot(bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Definition PolynomialSolver.h:195
const RealScalar & absSmallestRealRoot(bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Definition PolynomialSolver.h:215
void realRoots(Stl_back_insertion_sequence &bi_seq, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Definition PolynomialSolver.h:74
const RootType & greatestRoot() const
Definition PolynomialSolver.h:104
const RealScalar & greatestRealRoot(bool &hasArealRoot, const RealScalar &absImaginaryThreshold=NumTraits< Scalar >::dummy_precision()) const
Definition PolynomialSolver.h:235
const RootType & smallestRoot() const
Definition PolynomialSolver.h:112
const RootsType & roots() const
Definition PolynomialSolver.h:60
A polynomial solver.
Definition PolynomialSolver.h:300
void refineRoots(const OtherPolynomial &poly)
Definition PolynomialSolver.h:381
void compute(const OtherPolynomial &poly)
Definition PolynomialSolver.h:315
void cleanUpRoots(const OtherPolynomial &poly)
Definition PolynomialSolver.h:447
Namespace containing all symbols from the Eigen library.