19#ifndef EIGEN_STRUCTURED_CAUCHY_H
20#define EIGEN_STRUCTURED_CAUCHY_H
23#include "./InternalHeaderCheck.h"
27template <
typename Scalar_,
int Rows_ = Dynamic,
int Cols_ = Dynamic>
30template <
typename Scalar_>
35template <
typename Scalar_,
int Rows_,
int Cols_>
36struct traits<Cauchy<Scalar_, Rows_, Cols_>> {
37 using Scalar = Scalar_;
38 using StorageKind = Dense;
39 using XprKind = MatrixXpr;
40 using StorageIndex = int;
41 static constexpr int RowsAtCompileTime = Rows_;
42 static constexpr int ColsAtCompileTime = Cols_;
43 static constexpr int MaxRowsAtCompileTime = Rows_;
44 static constexpr int MaxColsAtCompileTime = Cols_;
49 static constexpr unsigned int Flags = 0;
52template <
typename Scalar_,
int Rows_,
int Cols_>
53struct evaluator_traits<Cauchy<Scalar_, Rows_, Cols_>> {
54 using Kind = IndexBased;
55 using Shape = StructuredShape;
58template <
typename Scalar_>
59struct traits<CauchyLU<Scalar_>> : traits<Matrix<Scalar_, Dynamic, Dynamic>> {
60 using XprKind = MatrixXpr;
61 using StorageKind = SolverStorage;
62 using StorageIndex = int;
63 using BaseTraits = traits<Matrix<Scalar_, Dynamic, Dynamic>>;
64 static constexpr unsigned int Flags = BaseTraits::Flags &
RowMajorBit;
65 static constexpr int CoeffReadCost = Dynamic;
113template <
typename Scalar_,
int Rows_,
int Cols_>
116 using Scalar = Scalar_;
118 using StorageIndex = int;
122 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(
bool(RowNodeVector::NeedsToAlign || ColNodeVector::NeedsToAlign))
124 static constexpr int RowsAtCompileTime = Rows_;
125 static constexpr int ColsAtCompileTime = Cols_;
126 static constexpr int MaxRowsAtCompileTime = Rows_;
127 static constexpr int MaxColsAtCompileTime = Cols_;
128 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Rows_, Cols_);
129 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
130 static constexpr bool IsRowMajor =
false;
137 template <
typename XDerived,
typename YDerived>
139 EIGEN_STATIC_ASSERT_VECTOR_ONLY(XDerived)
140 EIGEN_STATIC_ASSERT_VECTOR_ONLY(YDerived)
141 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_x,
"Cauchy node vectors must be non-empty");
142 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_y,
"Cauchy node vectors must be non-empty");
145 EIGEN_DEVICE_FUNC Index rows()
const {
return m_x.size(); }
146 EIGEN_DEVICE_FUNC Index cols()
const {
return m_y.size(); }
149 const RowNodeVector&
rowNodes()
const {
return m_x; }
151 const ColNodeVector&
colNodes()
const {
return m_y; }
154 Scalar
coeff(
Index row,
Index col)
const {
return Scalar(1) / (m_x.coeff(row) - m_y.coeff(col)); }
183 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(*
this,
"Cauchy::determinant requires a square matrix");
184 const Index n = rows();
187 for (
Index j = 1; j < n; ++j)
188 for (
Index i = 0; i < j; ++i) {
189 const Scalar xDiff = internal::balance_exponent(Scalar(m_x.coeff(j) - m_x.coeff(i)), exponent);
190 det = internal::balance_exponent(Scalar(det * xDiff), exponent);
191 const Scalar yDiff = internal::balance_exponent(Scalar(m_y.coeff(i) - m_y.coeff(j)), exponent);
192 det = internal::balance_exponent(Scalar(det * yDiff), exponent);
194 for (
Index j = 0; j < n; ++j)
195 for (
Index i = 0; i < n; ++i) {
196 Index denomExponent = 0;
197 const Scalar d = internal::balance_exponent(Scalar(m_x.coeff(i) - m_y.coeff(j)), denomExponent);
198 exponent -= denomExponent;
199 det = internal::balance_exponent(Scalar(det / d), exponent);
201 return internal::apply_exponent(det, exponent);
206 template <
typename Dest>
207 void evalTo(Dest& dst)
const {
208 applyAssignment(dst, internal::assign_op<typename Dest::Scalar, Scalar>());
212 template <
typename Dest>
213 void addTo(Dest& dst)
const {
214 applyAssignment(dst, internal::add_assign_op<typename Dest::Scalar, Scalar>());
218 template <
typename Dest>
219 void subTo(Dest& dst)
const {
220 applyAssignment(dst, internal::sub_assign_op<typename Dest::Scalar, Scalar>());
228 template <
typename Rhs>
239 template <
typename Dest,
typename Rhs,
typename ProductScalar>
240 void addProduct(Dest& dst,
const Rhs& rhs,
const ProductScalar& alpha)
const {
241 const Index n = cols();
242 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*
this, rhs,
"invalid product: dimensions do not match");
245 const bool unitAlpha = alpha == ProductScalar(1);
246 const auto weight = [&](Index j, Index k) {
247 return unitAlpha ? ProductScalar(rhs.coeff(j, k)) : ProductScalar(alpha * rhs.
coeff(j, k));
251 if (rhs.cols() > 1 && std::is_same<ProductScalar, Scalar>::value) {
254 constexpr Index kBlockBytes =
Index(1) << 19;
255 constexpr Index kMinBlockRows = 1024;
256 const Index m = rows(), r = rhs.cols();
257 const Index blockRows = numext::mini(m, numext::maxi(kMinBlockRows, kBlockBytes / (r *
Index(
sizeof(Scalar)))));
258 Matrix<Scalar, Dynamic, 1, ColMajor, Rows_> reciprocals(blockRows);
259 for (Index i = 0; i < m; i += blockRows) {
260 const Index b = numext::mini(blockRows, m - i);
261 for (Index j = 0; j < n; ++j) {
262 reciprocals.head(b) = (m_x.segment(i, b).array() - m_y.
coeff(j)).inverse();
263 for (Index k = 0; k < r; ++k) dst.col(k).segment(i, b) += weight(j, k) * reciprocals.head(b);
268 for (
Index k = 0; k < rhs.cols(); ++k)
269 for (
Index j = 0; j < n; ++j) dst.col(k) += weight(j, k) * (m_x.array() - m_y.coeff(j)).inverse().matrix();
273 template <
typename Dest,
typename Assignment>
274 void applyAssignment(Dest& dst,
const Assignment& assignment)
const {
275 for (
Index j = 0; j < cols(); ++j) {
276 auto dstColumn = dst.col(j);
277 internal::call_assignment_no_alias(dstColumn, (m_x.array() - m_y.coeff(j)).inverse().matrix(), assignment);
288template <
typename XDerived,
typename YDerived>
332template <
typename Scalar_>
337 EIGEN_GENERIC_PUBLIC_INTERFACE(
CauchyLU)
345 template <
int Rows_,
int Cols_>
357 template <
int Rows_,
int Cols_>
359 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(C,
"CauchyLU requires a square Cauchy matrix");
360 const Index n = C.rows();
363 DenseVector a = DenseVector::Ones(n);
364 DenseVector b = DenseVector::Ones(n);
366 m_perm.resize(
static_cast<std::size_t
>(n));
369 for (
Index k = 0; k < n; ++k) {
372 for (
Index i = k; i < n; ++i) {
373 m_lu(i, k) = a[i] * b[k] / (x[i] - y[k]);
374 const RealScalar mag = numext::abs(m_lu(i, k));
375 if ((numext::isnan)(mag) || mag > best) {
381 m_lu.row(piv).head(k + 1).swap(m_lu.row(k).head(k + 1));
382 std::swap(x[piv], x[k]);
383 std::swap(a[piv], a[k]);
385 m_perm[
static_cast<std::size_t
>(k)] = piv;
386 const Scalar pivot = m_lu(k, k);
387 if (pivot == Scalar(0) || !(numext::isfinite)(pivot)) {
389 m_lu.row(k).tail(n - k - 1).setZero();
390 m_lu.col(k).tail(n - k - 1).setZero();
393 m_lu.col(k).tail(n - k - 1) /= pivot;
394 for (
Index j = k + 1; j < n; ++j) {
395 m_lu(k, j) = a[k] * b[j] / (x[k] - y[j]);
398 for (
Index i = k + 1; i < n; ++i) a[i] *= (x[i] - x[k]) / (x[i] - y[k]);
399 for (
Index j = k + 1; j < n; ++j) b[j] *= (y[j] - y[k]) / (y[j] - x[k]);
401 m_isInitialized =
true;
405 Index rows() const noexcept {
return m_lu.rows(); }
406 Index cols() const noexcept {
return m_lu.cols(); }
411 eigen_assert(m_isInitialized &&
"CauchyLU is not initialized.");
415#ifdef EIGEN_PARSED_BY_DOXYGEN
420 template <
typename Rhs>
424#ifndef EIGEN_PARSED_BY_DOXYGEN
426 template <
typename RhsType,
typename DstType>
427 void _solve_impl(
const RhsType& rhs, DstType& dst)
const {
429 for (
Index k = 0; k < rows(); ++k) {
430 const Index piv = m_perm[
static_cast<std::size_t
>(k)];
431 if (piv != k) dst.row(k).swap(dst.row(piv));
433 m_lu.template triangularView<UnitLower>().solveInPlace(dst);
434 m_lu.template triangularView<Upper>().solveInPlace(dst);
440 template <
bool Conjugate,
typename RhsType,
typename DstType>
441 void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const {
442 dst = rhs.template conjugateIf<Conjugate>();
443 m_lu.template triangularView<Upper>().transpose().solveInPlace(dst);
444 m_lu.template triangularView<UnitLower>().transpose().solveInPlace(dst);
445 for (Index k = rows() - 1; k >= 0; --k) {
446 const Index piv = m_perm[
static_cast<std::size_t
>(k)];
447 if (piv != k) dst.row(k).swap(dst.row(piv));
449 if (Conjugate) dst = dst.conjugate().eval();
455 std::vector<Index> m_perm;
456 bool m_isInitialized;
464template <
typename Scalar_,
int Rows_,
int Cols_,
typename Rhs,
int ProductTag>
465struct generic_product_impl<Cauchy<Scalar_, Rows_, Cols_>, Rhs, StructuredShape, DenseShape, ProductTag>
466 : structured_product_impl<Cauchy<Scalar_, Rows_, Cols_>, Rhs> {};
470#if EIGEN_COMP_CXXVER < 17
471template <
typename Scalar_,
int Rows_,
int Cols_>
472constexpr int Cauchy<Scalar_, Rows_, Cols_>::RowsAtCompileTime;
473template <
typename Scalar_,
int Rows_,
int Cols_>
474constexpr int Cauchy<Scalar_, Rows_, Cols_>::ColsAtCompileTime;
475template <
typename Scalar_,
int Rows_,
int Cols_>
476constexpr int Cauchy<Scalar_, Rows_, Cols_>::MaxRowsAtCompileTime;
477template <
typename Scalar_,
int Rows_,
int Cols_>
478constexpr int Cauchy<Scalar_, Rows_, Cols_>::MaxColsAtCompileTime;
479template <
typename Scalar_,
int Rows_,
int Cols_>
480constexpr int Cauchy<Scalar_, Rows_, Cols_>::SizeAtCompileTime;
481template <
typename Scalar_,
int Rows_,
int Cols_>
482constexpr int Cauchy<Scalar_, Rows_, Cols_>::MaxSizeAtCompileTime;
483template <
typename Scalar_,
int Rows_,
int Cols_>
484constexpr bool Cauchy<Scalar_, Rows_, Cols_>::IsRowMajor;
Partially pivoted O(n^2) LU solver for square Cauchy systems (Gohberg-Kailath-Olshevsky).
Definition Cauchy.h:333
CauchyLU()
Definition Cauchy.h:342
const Solve< CauchyLU, Rhs > solve(const MatrixBase< Rhs > &b) const
ComputationInfo info() const
Definition Cauchy.h:410
CauchyLU(const Cauchy< Scalar, Rows_, Cols_ > &C)
Definition Cauchy.h:346
CauchyLU & compute(const Cauchy< Scalar, Rows_, Cols_ > &C)
Definition Cauchy.h:358
An m x n Cauchy matrix represented by its two node vectors.
Definition Cauchy.h:114
Scalar determinant() const
Definition Cauchy.h:182
Product< Cauchy, Rhs > operator*(const MatrixBase< Rhs > &v) const
Definition Cauchy.h:229
const ColNodeVector & colNodes() const
Definition Cauchy.h:151
Scalar coeff(Index row, Index col) const
Definition Cauchy.h:154
Cauchy< Scalar, Cols_, Rows_ > transpose() const
Definition Cauchy.h:158
Cauchy< Scalar, Cols_, Rows_ > adjoint() const
Definition Cauchy.h:166
Cauchy conjugate() const
Definition Cauchy.h:162
const RowNodeVector & rowNodes() const
Definition Cauchy.h:149
Cauchy(const MatrixBase< XDerived > &x, const MatrixBase< YDerived > &y)
Definition Cauchy.h:138
constexpr const Scalar & coeff(Index index) const
Cauchy< typename XDerived::Scalar, XDerived::SizeAtCompileTime, YDerived::SizeAtCompileTime > makeCauchy(const MatrixBase< XDerived > &x, const MatrixBase< YDerived > &y)
Definition Cauchy.h:289
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.