26#ifndef EIGEN_STRUCTURED_VANDERMONDE_H
27#define EIGEN_STRUCTURED_VANDERMONDE_H
30#include "./InternalHeaderCheck.h"
34template <
typename Scalar_,
int Rows_ = Dynamic,
int Cols_ = Dynamic>
37template <
typename Scalar_>
42template <
typename Scalar_,
int Rows_,
int Cols_>
43struct traits<Vandermonde<Scalar_, Rows_, Cols_>> {
44 using Scalar = Scalar_;
45 using StorageKind = Dense;
46 using XprKind = MatrixXpr;
47 using StorageIndex = int;
48 static constexpr int RowsAtCompileTime = Rows_;
49 static constexpr int ColsAtCompileTime = Cols_;
50 static constexpr int MaxRowsAtCompileTime = Rows_;
51 static constexpr int MaxColsAtCompileTime = Cols_;
57 static constexpr int Flags = Rows_ == 1 && Cols_ != 1 ?
RowMajorBit : 0;
60template <
typename Scalar_,
int Rows_,
int Cols_>
61struct evaluator_traits<Vandermonde<Scalar_, Rows_, Cols_>> {
62 using Kind = IndexBased;
63 using Shape = StructuredShape;
69template <
typename Scalar_,
int Rows_,
int Cols_>
70struct evaluator<Vandermonde<Scalar_, Rows_, Cols_>> : evaluator_base<Vandermonde<Scalar_, Rows_, Cols_>> {
71 using XprType = Vandermonde<Scalar_, Rows_, Cols_>;
72 using Scalar = Scalar_;
73 static constexpr int CoeffReadCost = HugeCost;
74 static constexpr int Flags = traits<XprType>::Flags;
75 static constexpr int Alignment = 0;
77 EIGEN_DEVICE_FUNC
constexpr EIGEN_STRONG_INLINE
explicit evaluator(
const XprType& xpr) : m_xpr(xpr) {}
79 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar coeff(Index row, Index col)
const {
return m_xpr.coeff(row, col); }
85template <
typename Scalar_,
int Rows_,
int Cols_>
86struct blas_traits<Vandermonde<Scalar_, Rows_, Cols_>> {
87 using XprType = Vandermonde<Scalar_, Rows_, Cols_>;
88 using Scalar = Scalar_;
89 using ExtractType =
const XprType&;
90 using ExtractType_ = XprType;
91 using DirectLinearAccessType = XprType;
92 static constexpr bool IsComplex = NumTraits<Scalar>::IsComplex;
93 static constexpr bool IsTransposed =
false;
94 static constexpr bool NeedToConjugate =
false;
95 static constexpr bool HasUsableDirectAccess =
false;
96 static constexpr bool HasScalarFactor =
false;
97 static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE ExtractType extract(
const XprType& x) {
return x; }
98 static EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE Scalar extractScalarFactor(
const XprType&) {
return Scalar(1); }
101template <
typename Scalar_>
102struct traits<BjorckPereyra<Scalar_>> : traits<Matrix<Scalar_, Dynamic, Dynamic>> {
103 using XprKind = MatrixXpr;
104 using StorageKind = SolverStorage;
105 using StorageIndex = int;
106 using BaseTraits = traits<Matrix<Scalar_, Dynamic, Dynamic>>;
107 static constexpr int Flags = BaseTraits::Flags &
RowMajorBit;
108 static constexpr int CoeffReadCost = Dynamic;
163template <
typename Scalar_,
int Rows_,
int Cols_>
168 using Scalar = Scalar_;
170 using StorageIndex = int;
175 static constexpr int RowsAtCompileTime = Rows_;
176 static constexpr int ColsAtCompileTime = Cols_;
177 static constexpr int MaxRowsAtCompileTime = Rows_;
178 static constexpr int MaxColsAtCompileTime = Cols_;
179 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Rows_, Cols_);
180 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
181 static constexpr int Flags = internal::traits<Vandermonde>::Flags;
182 static constexpr bool IsRowMajor = (Flags &
RowMajorBit) != 0;
187 EIGEN_STATIC_ASSERT_NON_INTEGER(RealScalar)
188 EIGEN_MAKE_SCALAR_BINARY_OP_ONTHELEFT(
operator*, internal::scalar_product_op)
191 template <
typename Derived>
193 EIGEN_STATIC_ASSERT_VECTOR_ONLY(Derived)
194 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(*
this,
"Vandermonde must be non-empty");
195 eigen_assert((Cols_ == Dynamic || Cols_ == cols) &&
"cols does not match the compile-time column count");
199 template <
typename Derived>
201 EIGEN_STATIC_ASSERT(Rows_ == Dynamic || Cols_ == Dynamic || Rows_ == Cols_, YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES)
203 Cols_ == Dynamic || Derived::SizeAtCompileTime == Dynamic || Cols_ == Derived::SizeAtCompileTime,
204 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES)
207 EIGEN_DEVICE_FUNC Index rows()
const {
return m_x.size(); }
208 EIGEN_DEVICE_FUNC Index cols()
const {
return m_cols; }
211 const NodeVector&
nodes()
const {
return m_x; }
216 const Scalar xi = m_x.coeff(row);
217 for (
Index t = 0; t < col; ++t) p *= xi;
233 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(*
this,
"Vandermonde::determinant requires a square matrix");
234 const Index n = rows();
236 internal::structured_exponent_type exponent = 0;
237 for (
Index j = 1; j < n; ++j)
238 for (
Index i = 0; i < j; ++i)
239 det = internal::balance_exponent(
240 det * internal::balance_exponent(Scalar(m_x.coeff(j) - m_x.coeff(i)), exponent), exponent);
241 return internal::apply_exponent(det, exponent);
247 template <
typename Dest>
248 void evalTo(Dest& dst)
const {
249 dst.col(0).setOnes();
250 for (Index j = 1; j < m_cols; ++j) dst.col(j) = dst.col(j - 1).cwiseProduct(m_x);
254 template <
typename Dest>
255 void addTo(Dest& dst)
const {
256 NodeVector p = NodeVector::Ones(rows());
258 for (Index j = 1; j < m_cols; ++j) {
259 p = p.cwiseProduct(m_x);
265 template <
typename Dest>
266 void subTo(Dest& dst)
const {
267 NodeVector p = NodeVector::Ones(rows());
269 for (
Index j = 1; j < m_cols; ++j) {
270 p = p.cwiseProduct(m_x);
281 template <
typename Rhs>
293 template <
typename Dest,
typename Rhs,
typename ProductScalar>
294 void addProduct(Dest& dst,
const Rhs& rhs,
const ProductScalar& alpha)
const {
295 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*
this, rhs,
"invalid product: dimensions do not match");
298 const bool unitAlpha = alpha == ProductScalar(1);
299 using SplitComponents =
303 for (Index k = 0; k < rhs.cols(); ++k) {
304 horner(acc, rhs, k, SplitComponents());
306 dst.col(k) += acc.matrix();
308 dst.col(k) += alpha * acc.matrix();
313 template <
typename ProductScalar,
typename Rhs>
314 void horner(Array<ProductScalar, Rows_, 1>& acc,
const Rhs& rhs,
Index k, std::false_type)
const {
315 const Index n = m_cols;
316 acc.setConstant(ProductScalar(rhs.coeff(n - 1, k)));
317 for (
Index j = n - 2; j >= 0; --j)
318 acc = acc * m_x.array().template cast<ProductScalar>() + ProductScalar(rhs.coeff(j, k));
324 template <
typename ProductScalar,
typename Rhs>
325 void horner(Array<ProductScalar, Rows_, 1>& acc,
const Rhs& rhs,
Index k, std::true_type)
const {
326 using NodeArray = Array<Scalar, Rows_, 1>;
327 const Index n = m_cols;
328 const ProductScalar top(rhs.coeff(n - 1, k));
329 NodeArray re = NodeArray::Constant(rows(), numext::real(top));
330 NodeArray im = NodeArray::Constant(rows(), numext::imag(top));
331 for (
Index j = n - 2; j >= 0; --j) {
332 const ProductScalar c(rhs.coeff(j, k));
333 re = re * m_x.array() + numext::real(c);
334 im = im * m_x.array() + numext::imag(c);
336 acc = re.binaryExpr(im, [](
const Scalar& a,
const Scalar& b) {
return ProductScalar(a, b); });
346template <
typename Derived>
354template <
typename Derived>
400template <
typename Scalar_>
406 EIGEN_STATIC_ASSERT_NON_INTEGER(RealScalar)
413 template <
int Rows_,
int Cols_>
421 template <
int Rows_,
int Cols_>
423 EIGEN_INTERNAL_CHECK_SHAPE(V.rows() == V.cols() &&
"BjorckPereyra requires a square Vandermonde matrix",
424 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES,
429 const Index n = m_x.size();
432 for (
Index i = 0; i < j; ++i) {
433 if (m_x[i] == m_x[j]) {
439 m_isInitialized =
true;
443 Index rows() const noexcept {
return m_x.size(); }
444 Index cols() const noexcept {
return m_x.size(); }
450 eigen_assert(m_isInitialized &&
"BjorckPereyra is not initialized.");
454#ifdef EIGEN_PARSED_BY_DOXYGEN
459 template <
typename Rhs>
463#ifndef EIGEN_PARSED_BY_DOXYGEN
466 template <
typename RhsType,
typename DstType>
467 void _solve_impl(
const RhsType& rhs, DstType& dst)
const {
468 using RhsScalar =
typename RhsType::Scalar;
469 using WorkScalar =
typename DstType::Scalar;
470 using ProductOp EIGEN_UNUSED = internal::scalar_product_op<Scalar, RhsScalar>;
471 EIGEN_CHECK_BINARY_COMPATIBILITY(ProductOp, Scalar, RhsScalar)
473 const Index n = m_x.size();
476 if (!m_order.empty()) permuted.
resize(n);
477 for (
Index k = 0; k < rhs.cols(); ++k) {
479 if (!m_order.empty()) {
480 for (
Index i = 0; i < n; ++i) permuted[i] = a[m_order[static_cast<std::size_t>(i)]];
483 for (Index j = 0; j < n - 1; ++j)
484 for (Index i = n - 1; i > j; --i) a[i] = (a[i] - a[i - 1]) / (m_x[i] - m_x[i - j - 1]);
485 for (Index j = n - 2; j >= 0; --j)
486 for (Index i = j; i < n - 1; ++i) a[i] -= m_x[j] * a[i + 1];
493 template <
bool Conjugate,
typename RhsType,
typename DstType>
494 void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const {
495 using RhsScalar =
typename RhsType::Scalar;
496 using WorkScalar =
typename DstType::Scalar;
497 using ProductOp EIGEN_UNUSED = internal::scalar_product_op<Scalar, RhsScalar>;
498 EIGEN_CHECK_BINARY_COMPATIBILITY(ProductOp, Scalar, RhsScalar)
500 const Index n = m_x.size();
501 dst = rhs.template conjugateIf<Conjugate>();
502 Matrix<WorkScalar, Dynamic, 1> permuted;
503 if (!m_order.empty()) permuted.
resize(n);
504 for (
Index k = 0; k < rhs.cols(); ++k) {
506 for (
Index j = 0; j < n - 1; ++j)
507 for (
Index i = n - 1; i > j; --i) w[i] -= m_x[j] * w[i - 1];
508 for (
Index j = n - 2; j >= 0; --j) {
509 w.tail(n - j - 1).array() /= (m_x.tail(n - j - 1) - m_x.head(n - j - 1)).array();
510 for (
Index i = j; i < n - 1; ++i) w[i] -= w[i + 1];
513 if (!m_order.empty()) {
515 for (
Index i = 0; i < n; ++i) w[m_order[static_cast<std::size_t>(i)]] = permuted[i];
518 if (Conjugate) dst = dst.conjugate().eval();
523 static RealScalar lejaLogAbs(
const Scalar& z) {
return numext::log(numext::abs(z)); }
525 void initializeNodeOrder(
const NodeVector&, std::false_type) {}
527 void initializeNodeOrder(
const NodeVector& nodes, std::true_type) {
528 using Real =
typename NumTraits<Scalar>::Real;
529 const Index n = nodes.size();
530 bool genuinelyComplex =
false;
531 for (
Index i = 0; i < n; ++i) genuinelyComplex = genuinelyComplex || numext::imag(nodes[i]) != Real(0);
532 if (!genuinelyComplex || n < 2)
return;
534 const NodeVector original = nodes;
536 m_order.resize(
static_cast<std::size_t
>(n));
537 std::vector<char> selected(
static_cast<std::size_t
>(n), 0);
538 std::vector<RealScalar> scores(
static_cast<std::size_t
>(n), RealScalar(0));
540 original.unaryExpr(&lejaLogAbs).maxCoeff(&next);
542 for (
Index position = 0; position < n; ++position) {
543 m_order[
static_cast<std::size_t
>(position)] = next;
544 selected[
static_cast<std::size_t
>(next)] = 1;
545 if (position + 1 == n)
break;
547 Index candidate = -1;
548 RealScalar candidateScore = -NumTraits<RealScalar>::infinity();
549 for (
Index i = 0; i < n; ++i) {
550 if (selected[
static_cast<std::size_t
>(i)])
continue;
551 scores[
static_cast<std::size_t
>(i)] += lejaLogAbs(original[i] - original[next]);
552 if (candidate < 0 || scores[
static_cast<std::size_t
>(i)] > candidateScore) {
554 candidateScore = scores[
static_cast<std::size_t
>(i)];
560 for (
Index i = 0; i < n; ++i) m_x[i] = original[m_order[static_cast<std::size_t>(i)]];
564 std::vector<Index> m_order;
565 bool m_isInitialized;
574template <
typename SolverScalar,
typename RhsScalar,
575 bool Compatible = has_ReturnType<ScalarBinaryOpTraits<SolverScalar, RhsScalar>>::value>
576struct bjorck_pereyra_result_scalar {
577 using type = SolverScalar;
580template <
typename SolverScalar,
typename RhsScalar>
581struct bjorck_pereyra_result_scalar<SolverScalar, RhsScalar, true> {
582 using type =
typename ScalarBinaryOpTraits<SolverScalar, RhsScalar>::ReturnType;
585template <
typename SolverScalar,
typename RhsType>
586struct bjorck_pereyra_solve_traits {
587 using ResultScalar =
typename bjorck_pereyra_result_scalar<SolverScalar, typename RhsType::Scalar>::type;
589 typename make_proper_matrix_type<ResultScalar, Dynamic, RhsType::ColsAtCompileTime, RhsType::PlainObject::Options,
590 Dynamic, RhsType::MaxColsAtCompileTime>::type;
593template <
typename Scalar_,
typename RhsType>
594struct solve_traits<BjorckPereyra<Scalar_>, RhsType, Dense> : bjorck_pereyra_solve_traits<Scalar_, RhsType> {};
596template <
typename Scalar_,
typename RhsType>
597struct solve_traits<Transpose<const BjorckPereyra<Scalar_>>, RhsType, Dense>
598 : bjorck_pereyra_solve_traits<Scalar_, RhsType> {};
600template <
typename Scalar_,
typename RhsType>
601struct solve_traits<CwiseUnaryOp<scalar_conjugate_op<Scalar_>, const Transpose<const BjorckPereyra<Scalar_>>>, RhsType,
602 Dense> : bjorck_pereyra_solve_traits<Scalar_, RhsType> {};
604template <
typename Factor,
typename Scalar_,
int Rows_,
int Cols_,
typename Plain,
typename Rhs>
605struct scaled_vandermonde_product_impl
606 : generic_product_impl_base<
607 CwiseBinaryOp<scalar_product_op<Factor, Scalar_>, const CwiseNullaryOp<scalar_constant_op<Factor>, Plain>,
608 const Vandermonde<Scalar_, Rows_, Cols_>>,
609 Rhs, scaled_vandermonde_product_impl<Factor, Scalar_, Rows_, Cols_, Plain, Rhs>> {
610 using Op = Vandermonde<Scalar_, Rows_, Cols_>;
611 using ScaledOp = CwiseBinaryOp<scalar_product_op<Factor, Scalar_>,
612 const CwiseNullaryOp<scalar_constant_op<Factor>, Plain>,
const Op>;
613 using Scalar =
typename Product<ScaledOp, Rhs>::Scalar;
615 template <
typename Dest>
616 static void scaleAndAddTo(Dest& dst,
const ScaledOp& lhs,
const Rhs& rhs,
const Scalar& alpha) {
617 using RhsNested =
typename nested_eval<Rhs, Rows_>::type;
618 RhsNested actualRhs(rhs);
619 lhs.rhs().addProduct(dst, actualRhs, Scalar(alpha * lhs.lhs().functor().m_other));
625#define EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(ProductTag) \
626 template <typename Factor, typename Scalar_, int Rows_, int Cols_, typename Plain, typename Rhs> \
627 struct generic_product_impl< \
628 CwiseBinaryOp<scalar_product_op<Factor, Scalar_>, const CwiseNullaryOp<scalar_constant_op<Factor>, Plain>, \
629 const Vandermonde<Scalar_, Rows_, Cols_>>, \
630 Rhs, DenseShape, DenseShape, ProductTag> \
631 : scaled_vandermonde_product_impl<Factor, Scalar_, Rows_, Cols_, Plain, Rhs> {};
633EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(CoeffBasedProductMode)
634EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(LazyCoeffBasedProductMode)
635EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(OuterProduct)
636EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(InnerProduct)
637EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(GemvProduct)
638EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL(GemmProduct)
640#undef EIGEN_SCALED_VANDERMONDE_PRODUCT_IMPL
642template <
typename Scalar_,
int Rows_,
int Cols_,
typename Rhs,
int ProductTag>
643struct generic_product_impl<Vandermonde<Scalar_, Rows_, Cols_>, Rhs, StructuredShape, DenseShape, ProductTag>
644 : structured_product_impl<Vandermonde<Scalar_, Rows_, Cols_>, Rhs> {};
648#if EIGEN_COMP_CXXVER < 17
649template <
typename Scalar_,
int Rows_,
int Cols_>
650constexpr int Vandermonde<Scalar_, Rows_, Cols_>::RowsAtCompileTime;
651template <
typename Scalar_,
int Rows_,
int Cols_>
652constexpr int Vandermonde<Scalar_, Rows_, Cols_>::ColsAtCompileTime;
653template <
typename Scalar_,
int Rows_,
int Cols_>
654constexpr int Vandermonde<Scalar_, Rows_, Cols_>::MaxRowsAtCompileTime;
655template <
typename Scalar_,
int Rows_,
int Cols_>
656constexpr int Vandermonde<Scalar_, Rows_, Cols_>::MaxColsAtCompileTime;
657template <
typename Scalar_,
int Rows_,
int Cols_>
658constexpr int Vandermonde<Scalar_, Rows_, Cols_>::SizeAtCompileTime;
659template <
typename Scalar_,
int Rows_,
int Cols_>
660constexpr int Vandermonde<Scalar_, Rows_, Cols_>::MaxSizeAtCompileTime;
661template <
typename Scalar_,
int Rows_,
int Cols_>
662constexpr bool Vandermonde<Scalar_, Rows_, Cols_>::IsRowMajor;
663template <
typename Scalar_,
int Rows_,
int Cols_>
664constexpr int Vandermonde<Scalar_, Rows_, Cols_>::NodeOptions;
665template <
typename Scalar_,
int Rows_,
int Cols_>
666constexpr int Vandermonde<Scalar_, Rows_, Cols_>::Flags;
Björck-Pereyra O(n^2) solver for square Vandermonde systems.
Definition Vandermonde.h:401
ComputationInfo info() const
Definition Vandermonde.h:449
BjorckPereyra(const Vandermonde< Scalar, Rows_, Cols_ > &V)
Definition Vandermonde.h:414
BjorckPereyra()
Definition Vandermonde.h:410
BjorckPereyra & compute(const Vandermonde< Scalar, Rows_, Cols_ > &V)
Definition Vandermonde.h:422
const Solve< BjorckPereyra, Rhs > solve(const MatrixBase< Rhs > &f) const
constexpr void resize(Index rows, Index cols)
An m x n Vandermonde matrix represented by its node vector.
Definition Vandermonde.h:164
Vandermonde(const MatrixBase< Derived > &nodes, Index cols)
Definition Vandermonde.h:192
Scalar determinant() const
Definition Vandermonde.h:232
const NodeVector & nodes() const
Definition Vandermonde.h:211
Vandermonde(const MatrixBase< Derived > &nodes)
Definition Vandermonde.h:200
Scalar coeff(Index row, Index col) const
Definition Vandermonde.h:214
Product< Vandermonde, Rhs > operator*(const MatrixBase< Rhs > &a) const
Definition Vandermonde.h:282
Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Dynamic > makeVandermonde(const MatrixBase< Derived > &nodes, Index cols)
Definition Vandermonde.h:347
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.
constexpr Index size() const noexcept