11#ifndef EIGEN_POLYNOMIAL_SOLVER_H
12#define EIGEN_POLYNOMIAL_SOLVER_H
15#include "./InternalHeaderCheck.h"
32template <
typename Scalar_,
int Deg_>
33class PolynomialSolverBase {
35 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(Scalar_, Deg_ == Dynamic ? Dynamic : Deg_)
37 using Scalar = Scalar_;
39 using RootType = internal::make_complex_t<Scalar>;
42 using Index = DenseIndex;
45 template <
typename OtherPolynomial>
46 inline void setPolynomial(
const OtherPolynomial& poly) {
47 m_roots.
resize(poly.size() - 1);
51 template <
typename OtherPolynomial>
52 inline PolynomialSolverBase(
const OtherPolynomial& poly) {
53 setPolynomial(poly());
56 inline PolynomialSolverBase() {}
60 inline const RootsType&
roots()
const {
return m_roots; }
73 template <
typename Stl_back_insertion_sequence>
74 inline void realRoots(Stl_back_insertion_sequence& bi_seq,
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());
86 template <
typename Predicate>
87 inline const RootType& selectComplexRoot_withRespectToNorm(Predicate& pred)
const {
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)) {
105 std::greater<RealScalar> greater;
106 return selectComplexRoot_withRespectToNorm(greater);
113 std::less<RealScalar> less;
114 return selectComplexRoot_withRespectToNorm(less);
118 template <
typename Predicate>
119 inline const RealScalar& selectRealRoot_withRespectToAbsRealPart(
120 Predicate& pred,
bool& hasArealRoot,
123 hasArealRoot =
false;
127 for (Index i = 0; i < m_roots.size(); ++i) {
128 if (abs(m_roots[i].imag()) <= absImaginaryThreshold) {
132 val = abs(m_roots[i].real());
134 const RealScalar curr = abs(m_roots[i].real());
135 if (pred(curr, val)) {
140 }
else if (!hasArealRoot) {
141 if (abs(m_roots[i].imag()) < abs(m_roots[res].imag())) {
146 return numext::real_ref(m_roots[res]);
149 template <
typename Predicate>
150 inline const RealScalar& selectRealRoot_withRespectToRealPart(
151 Predicate& pred,
bool& hasArealRoot,
152 const RealScalar& absImaginaryThreshold = NumTraits<Scalar>::dummy_precision())
const {
154 hasArealRoot =
false;
158 for (Index i = 0; i < m_roots.size(); ++i) {
159 if (abs(m_roots[i].imag()) <= absImaginaryThreshold) {
163 val = m_roots[i].real();
165 const RealScalar curr = m_roots[i].real();
166 if (pred(curr, val)) {
172 if (abs(m_roots[i].imag()) < abs(m_roots[res].imag())) {
177 return numext::real_ref(m_roots[res]);
197 std::greater<RealScalar> greater;
198 return selectRealRoot_withRespectToAbsRealPart(greater, hasArealRoot, absImaginaryThreshold);
217 std::less<RealScalar> less;
218 return selectRealRoot_withRespectToAbsRealPart(less, hasArealRoot, absImaginaryThreshold);
237 std::greater<RealScalar> greater;
238 return selectRealRoot_withRespectToRealPart(greater, hasArealRoot, absImaginaryThreshold);
257 std::less<RealScalar> less;
258 return selectRealRoot_withRespectToRealPart(less, hasArealRoot, absImaginaryThreshold);
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;
299template <
typename Scalar_,
int Deg_>
300class PolynomialSolver :
public PolynomialSolverBase<Scalar_, Deg_> {
302 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF_VECTORIZABLE_FIXED_SIZE(Scalar_, Deg_ == Dynamic ? Dynamic : Deg_)
304 using PS_Base = PolynomialSolverBase<Scalar_, Deg_>;
305 EIGEN_POLYNOMIAL_SOLVER_BASE_INHERITED_TYPES(PS_Base)
310 using ComplexScalar = internal::make_complex_t<Scalar_>;
314 template <
typename OtherPolynomial>
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);
321 m_eigenSolver.compute(companion.denseMatrix());
323 m_roots = m_eigenSolver.eigenvalues();
325 const RealScalar scale = poly.realView().cwiseAbs().maxCoeff();
326 const auto scaledPoly = (poly / scale).eval();
329 }
else if (poly.size() == 2) {
331 m_roots[0] = -poly[0] / poly[1];
336 template <
typename OtherPolynomial>
341 inline PolynomialSolver() {}
348 template <
typename OtherPolynomial>
349 static RealScalar evaluate(
const OtherPolynomial& poly,
const RootType& z, RootType& value, RootType& derivative,
351 const Index degree = poly.size() - 1;
352 value = RootType(poly[degree]);
353 derivative = RootType(0);
355 for (Index k = degree - 1; k >= 0; --k) {
356 derivative = derivative * z + value;
357 value = value * z + RootType(poly[k]);
359 return RealScalar(0);
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);
368 const RealScalar errorScale = numext::sqrt(RealScalar(2)) * NumTraits<RealScalar>::epsilon();
369 return (RealScalar(2) * errorScale) * mu - errorScale * numext::abs(value);
380 template <
typename OtherPolynomial>
382 const Index n = m_roots.size();
387 for (Index i = 0; i < n; ++i) {
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);
396 RootType value, derivative;
397 for (
int sweep = 0; sweep < maxSweeps; ++sweep) {
399 for (Index i = 0; i < n; ++i) {
400 if (!active[i])
continue;
401 const RootType z = m_roots[i];
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)) {
411 const RootType newton = value / derivative;
412 if (!(numext::abs(newton) > eps * numext::abs(z))) {
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;
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;
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];
446 template <
typename OtherPolynomial>
448 const Index n = m_roots.size();
451 EIGEN_IF_CONSTEXPR (realPolynomial) {
452 for (Index i = 0; i < n; ++i) {
453 if (!(numext::imag(m_roots[i]) > RealScalar(0)))
continue;
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]));
465 paired[i] = paired[partner] =
true;
466 const RootType mean = (m_roots[i] + numext::conj(m_roots[partner])) / RealScalar(2);
468 m_roots[partner] = numext::conj(mean);
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;
481 if (!(numext::abs(numext::imag(m_roots[i])) <=
484 const RealScalar bound = evaluate(poly, realPart, value, derivative,
true);
485 if ((numext::isfinite)(bound) && numext::abs(value) <= bound) m_roots[i] = realPart;
489 using PS_Base::m_roots;
490 EigenSolverType m_eigenSolver;
493template <
typename Scalar_>
494class PolynomialSolver<Scalar_, 1> :
public PolynomialSolverBase<Scalar_, 1> {
496 using PS_Base = PolynomialSolverBase<Scalar_, 1>;
497 EIGEN_POLYNOMIAL_SOLVER_BASE_INHERITED_TYPES(PS_Base)
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];
509 template <
typename OtherPolynomial>
510 inline PolynomialSolver(
const OtherPolynomial& poly) {
514 inline PolynomialSolver() {}
517 using PS_Base::m_roots;
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.