Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Cauchy.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9//
10// References:
11// [1] J. J. Dongarra, J. R. Bunch, C. B. Moler and G. W. Stewart, "LINPACK
12// Users' Guide", SIAM, 1979. determinant()'s balanced accumulation follows
13// the convention of its xGEDI routines, which return determinants as a
14// (fraction, exponent) pair to avoid spurious overflow/underflow.
15// [2] P. H. Sterbenz, "Floating-Point Computation", Prentice-Hall, 1974.
16// Scaling by a power of two is exact, the property the balanced
17// accumulation relies on.
18
19#ifndef EIGEN_STRUCTURED_CAUCHY_H
20#define EIGEN_STRUCTURED_CAUCHY_H
21
22// IWYU pragma: private
23#include "./InternalHeaderCheck.h"
24
25namespace Eigen {
26
27template <typename Scalar_, int Rows_ = Dynamic, int Cols_ = Dynamic>
28class Cauchy;
29
30template <typename Scalar_>
31class CauchyLU;
32
33namespace internal {
34
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_;
45 // Deliberately no NestByRefBit: transpose(), conjugate() and adjoint() return
46 // owning temporaries, so Product must nest the operator by value for a
47 // delayed-evaluated product expression to keep its left factor alive. The copy
48 // is O(m+n), negligible against the O(mn) product evaluation.
49 static constexpr unsigned int Flags = 0;
50};
51
52template <typename Scalar_, int Rows_, int Cols_>
53struct evaluator_traits<Cauchy<Scalar_, Rows_, Cols_>> {
54 using Kind = IndexBased;
55 using Shape = StructuredShape;
56};
57
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;
66};
67
68} // namespace internal
69
113template <typename Scalar_, int Rows_, int Cols_>
114class Cauchy : public EigenBase<Cauchy<Scalar_, Rows_, Cols_>> {
115 public:
116 using Scalar = Scalar_;
117 using RealScalar = typename NumTraits<Scalar>::Real;
118 using StorageIndex = int;
119 using RowNodeVector = Matrix<Scalar, Rows_, 1>;
120 using ColNodeVector = Matrix<Scalar, Cols_, 1>;
121
122 EIGEN_MAKE_ALIGNED_OPERATOR_NEW_IF(bool(RowNodeVector::NeedsToAlign || ColNodeVector::NeedsToAlign))
123
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;
131 // Deliberately no IsVectorAtCompileTime: Ref<const Cauchy>'s default StrideType
132 // argument reads it, so its absence makes internal::is_ref_compatible SFINAE to
133 // false and keeps the iterative solvers on their matrix-free path.
134
137 template <typename XDerived, typename YDerived>
138 Cauchy(const MatrixBase<XDerived>& x, const MatrixBase<YDerived>& y) : m_x(x), m_y(y) {
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");
143 }
144
145 EIGEN_DEVICE_FUNC Index rows() const { return m_x.size(); }
146 EIGEN_DEVICE_FUNC Index cols() const { return m_y.size(); }
147
149 const RowNodeVector& rowNodes() const { return m_x; }
151 const ColNodeVector& colNodes() const { return m_y; }
152
154 Scalar coeff(Index row, Index col) const { return Scalar(1) / (m_x.coeff(row) - m_y.coeff(col)); }
155
159
162 Cauchy conjugate() const { return Cauchy(m_x.conjugate(), m_y.conjugate()); }
163
167 return Cauchy<Scalar, Cols_, Rows_>(-m_y.conjugate(), -m_x.conjugate());
168 }
169
182 Scalar determinant() const {
183 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(*this, "Cauchy::determinant requires a square matrix");
184 const Index n = rows();
185 Scalar det(1);
186 Index exponent = 0;
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);
193 }
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);
200 }
201 return internal::apply_exponent(det, exponent);
202 }
203
206 template <typename Dest>
207 void evalTo(Dest& dst) const {
208 applyAssignment(dst, internal::assign_op<typename Dest::Scalar, Scalar>());
209 }
210
212 template <typename Dest>
213 void addTo(Dest& dst) const {
214 applyAssignment(dst, internal::add_assign_op<typename Dest::Scalar, Scalar>());
215 }
216
218 template <typename Dest>
219 void subTo(Dest& dst) const {
220 applyAssignment(dst, internal::sub_assign_op<typename Dest::Scalar, Scalar>());
221 }
222
228 template <typename Rhs>
230 return Product<Cauchy, Rhs>(*this, v.derived());
231 }
232
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");
243 // A unit alpha must not multiply: even the identity complex scalar (1,0)
244 // pollutes an (Inf,0) value with NaN through the 0*Inf cross term.
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));
248 };
249 // Reuse saves (r-1)/r of the divisions. A real operator applied to a complex
250 // right-hand side gains nothing: the complex updates dominate its real divisions.
251 if (rhs.cols() > 1 && std::is_same<ProductScalar, Scalar>::value) {
252 // Row blocks keep the r destination columns of a block in cache across all
253 // n reciprocal columns; the floor keeps the per-column updates long.
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);
264 }
265 }
266 return;
267 }
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();
270 }
271
272 private:
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);
278 }
279 }
280
281 RowNodeVector m_x;
282 ColNodeVector m_y;
283};
284
288template <typename XDerived, typename YDerived>
293
332template <typename Scalar_>
333class CauchyLU : public SolverBase<CauchyLU<Scalar_>> {
334 public:
335 using Base = SolverBase<CauchyLU>;
336 friend class SolverBase<CauchyLU>;
337 EIGEN_GENERIC_PUBLIC_INTERFACE(CauchyLU)
338 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
339 using DenseVector = Matrix<Scalar, Dynamic, 1>;
340
342 CauchyLU() : m_isInitialized(false), m_info(InvalidInput) {}
343
345 template <int Rows_, int Cols_>
346 explicit CauchyLU(const Cauchy<Scalar, Rows_, Cols_>& C) : m_isInitialized(false), m_info(InvalidInput) {
347 compute(C);
348 }
349
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();
361 DenseVector x = C.rowNodes();
362 const DenseVector y = C.colNodes();
363 DenseVector a = DenseVector::Ones(n);
364 DenseVector b = DenseVector::Ones(n);
365 m_lu.resize(n, n);
366 m_perm.resize(static_cast<std::size_t>(n));
367 m_info = Success;
368
369 for (Index k = 0; k < n; ++k) {
370 Index piv = k;
371 RealScalar best(-1);
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) {
376 best = mag;
377 piv = i;
378 }
379 }
380 if (piv != k) {
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]);
384 }
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)) {
388 m_info = NumericalIssue;
389 m_lu.row(k).tail(n - k - 1).setZero();
390 m_lu.col(k).tail(n - k - 1).setZero();
391 continue;
392 }
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]);
396 if (!(numext::isfinite)(m_lu(k, j))) m_info = NumericalIssue;
397 }
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]);
400 }
401 m_isInitialized = true;
402 return *this;
403 }
404
405 Index rows() const noexcept { return m_lu.rows(); }
406 Index cols() const noexcept { return m_lu.cols(); }
407
411 eigen_assert(m_isInitialized && "CauchyLU is not initialized.");
412 return m_info;
413 }
414
415#ifdef EIGEN_PARSED_BY_DOXYGEN
420 template <typename Rhs>
421 inline const Solve<CauchyLU, Rhs> solve(const MatrixBase<Rhs>& b) const;
422#endif
423
424#ifndef EIGEN_PARSED_BY_DOXYGEN
426 template <typename RhsType, typename DstType>
427 void _solve_impl(const RhsType& rhs, DstType& dst) const {
428 dst = rhs;
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));
432 }
433 m_lu.template triangularView<UnitLower>().solveInPlace(dst);
434 m_lu.template triangularView<Upper>().solveInPlace(dst);
435 }
436
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));
448 }
449 if (Conjugate) dst = dst.conjugate().eval();
450 }
451#endif
452
453 private:
454 DenseMatrix m_lu;
455 std::vector<Index> m_perm; // transposition applied at each elimination step
456 bool m_isInitialized;
457 ComputationInfo m_info;
458};
459
460namespace internal {
461
462// Single product specialization covering every product tag; see the note in
463// Circulant.h.
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> {};
467
468} // namespace internal
469
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;
485#endif
486
487} // namespace Eigen
488
489#endif // EIGEN_STRUCTURED_CAUCHY_H
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
ComputationInfo
NumericalIssue
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.