Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
DiagonalPlusLowRank.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] M. A. Woodbury, "Inverting Modified Matrices", Memorandum Report 42,
12// Statistical Research Group, Princeton University, 1950. The Woodbury
13// identity behind solve() and inverse().
14// [2] W. W. Hager, "Updating the Inverse of a Matrix", SIAM Review, 31(2),
15// pp. 221-239, 1989. Review of the Woodbury identity and of the matrix
16// determinant lemma used by determinant().
17// [3] J. J. Dongarra, J. R. Bunch, C. B. Moler and G. W. Stewart, "LINPACK
18// Users' Guide", SIAM, 1979. determinant()'s balanced accumulation follows
19// the convention of its xGEDI routines, which return determinants as a
20// (fraction, exponent) pair to avoid spurious overflow/underflow.
21// [4] P. H. Sterbenz, "Floating-Point Computation", Prentice-Hall, 1974.
22// Scaling by a power of two is exact, the property the balanced
23// accumulation relies on.
24// [5] E. L. Yip, "A Note on the Stability of Solving a Rank-p Modification of
25// a Linear System by the Sherman-Morrison-Woodbury Formula", SIAM Journal
26// on Scientific and Statistical Computing, 7(2), pp. 507-513, 1986. The
27// accuracy limitation of the Woodbury solve noted on solve().
28
29#ifndef EIGEN_STRUCTURED_DIAGONAL_PLUS_LOW_RANK_H
30#define EIGEN_STRUCTURED_DIAGONAL_PLUS_LOW_RANK_H
31
32// IWYU pragma: private
33#include "./InternalHeaderCheck.h"
34
35namespace Eigen {
36
37template <typename Scalar_, int Size_ = Dynamic, int Rank_ = Dynamic>
39
40namespace internal {
41
42template <typename Scalar_, int Size_, int Rank_>
43struct traits<DiagonalPlusLowRank<Scalar_, Size_, Rank_>> {
44 using Scalar = Scalar_;
45 using StorageKind = Dense;
46 using XprKind = MatrixXpr;
47 using StorageIndex = int;
48 static constexpr int RowsAtCompileTime = Size_;
49 static constexpr int ColsAtCompileTime = Size_;
50 static constexpr int MaxRowsAtCompileTime = Size_;
51 static constexpr int MaxColsAtCompileTime = Size_;
52 // Deliberately no NestByRefBit: transpose(), conjugate(), adjoint(), inverse()
53 // and makeDiagonalPlusLowRank() return owning temporaries, so Product must nest
54 // the operator by value for a delayed-evaluated product expression to keep its
55 // left factor alive. The copy is O(nk), on par with a single product evaluation.
56 static constexpr unsigned int Flags = 0;
57};
58
59template <typename Scalar_, int Size_, int Rank_>
60struct evaluator_traits<DiagonalPlusLowRank<Scalar_, Size_, Rank_>> {
61 using Kind = IndexBased;
62 using Shape = StructuredShape;
63};
64
65// Compile-time dispatch keeps fixed rank zero from instantiating a 0 x 0 LU;
66// C++14 cannot express this branch with if constexpr.
67template <int Rank_>
68struct dplr_capacitance_impl {
71 template <typename Op, typename Dinv, typename Workspace>
72 static void subtractSolveCorrection(const Op& op, const Dinv& dinv, Workspace& x) {
73 if (op.correctionRank() == 0 || x.size() == 0) return;
74 PartialPivLU<typename Op::CapacitanceType> cap(op.capacitance());
75 x.noalias() -= dinv.asDiagonal() * (op.factorU() * cap.solve(op.factorV().adjoint() * x));
76 }
78 template <typename Op, typename Dinv, typename Factor>
79 static void inverseFactor(const Op& op, const Dinv& dinv, Factor& Up) {
80 if (op.correctionRank() == 0) return;
81 PartialPivLU<typename Op::CapacitanceType> cap(op.capacitance());
82 const typename Op::CapacitanceType K = cap.inverse();
83 Up.noalias() = -(dinv.asDiagonal() * op.factorU() * K);
84 }
89 template <typename Op>
90 static typename Op::Scalar balancedCapacitanceDeterminant(const Op& op, Index& exponent) {
91 using Scalar = typename Op::Scalar;
92 if (op.correctionRank() == 0) return Scalar(1);
93 const PartialPivLU<typename Op::CapacitanceType> lu(op.capacitance());
94 Scalar det(static_cast<typename Op::RealScalar>(lu.permutationP().determinant()));
95 for (Index i = 0; i < lu.matrixLU().rows(); ++i)
96 det = balance_exponent(det * balance_exponent(lu.matrixLU().coeff(i, i), exponent), exponent);
97 return det;
98 }
99};
100
101template <>
102struct dplr_capacitance_impl<0> {
103 template <typename Op, typename Dinv, typename Workspace>
104 static void subtractSolveCorrection(const Op&, const Dinv&, Workspace&) {}
105 template <typename Op, typename Dinv, typename Factor>
106 static void inverseFactor(const Op&, const Dinv&, Factor&) {}
107 template <typename Op>
108 static typename Op::Scalar balancedCapacitanceDeterminant(const Op&, Index&) {
109 return typename Op::Scalar(1);
110 }
111};
112
113} // namespace internal
114
152template <typename Scalar_, int Size_, int Rank_>
153class DiagonalPlusLowRank : public EigenBase<DiagonalPlusLowRank<Scalar_, Size_, Rank_>> {
154 public:
155 using Scalar = Scalar_;
156 using RealScalar = typename NumTraits<Scalar>::Real;
157 using StorageIndex = int;
158 using DiagonalVector = Matrix<Scalar, Size_, 1>;
159 using FactorType = Matrix<Scalar, Size_, Rank_>;
160 using CapacitanceType = Matrix<Scalar, Rank_, Rank_>;
161
162 static constexpr int RowsAtCompileTime = Size_;
163 static constexpr int ColsAtCompileTime = Size_;
164 static constexpr int MaxRowsAtCompileTime = Size_;
165 static constexpr int MaxColsAtCompileTime = Size_;
166 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(Size_, Size_);
167 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
168 static constexpr bool IsRowMajor = false;
169 // Deliberately no IsVectorAtCompileTime: Ref<const DiagonalPlusLowRank>'s default
170 // StrideType argument reads it, so its absence makes internal::is_ref_compatible
171 // SFINAE to false and keeps the iterative solvers on their matrix-free path.
172
176 template <typename DDerived, typename UDerived, typename VDerived>
178 : m_d(d), m_U(U), m_V(V) {
179 EIGEN_STATIC_ASSERT_VECTOR_ONLY(DDerived)
180 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_d, "DiagonalPlusLowRank must be non-empty");
181 EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_ROWS_MSG(m_d, m_U, "factor dimensions do not match");
182 EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_ROWS_MSG(m_d, m_V, "factor dimensions do not match");
183 EIGEN_INTERNAL_ASSERT_SAME_COLS_MSG(m_U, m_V, "factor dimensions do not match");
184 }
185
186 EIGEN_DEVICE_FUNC Index rows() const { return m_d.size(); }
187 EIGEN_DEVICE_FUNC Index cols() const { return m_d.size(); }
189 Index correctionRank() const { return m_U.cols(); }
190
192 const DiagonalVector& diagonal() const { return m_d; }
194 const FactorType& factorU() const { return m_U; }
196 const FactorType& factorV() const { return m_V; }
197
199 Scalar coeff(Index row, Index col) const {
200 Scalar r = m_V.row(col).dot(m_U.row(row)); // dot() conjugates its first argument
201 if (row == col) r += m_d.coeff(row);
202 return r;
203 }
204
207 DiagonalPlusLowRank transpose() const { return DiagonalPlusLowRank(m_d, m_V.conjugate(), m_U.conjugate()); }
208
212 return DiagonalPlusLowRank(m_d.conjugate(), m_U.conjugate(), m_V.conjugate());
213 }
214
217 DiagonalPlusLowRank adjoint() const { return DiagonalPlusLowRank(m_d.conjugate(), m_V, m_U); }
218
225 CapacitanceType capacitance() const {
226 const Index k = correctionRank();
227 CapacitanceType c = CapacitanceType::Identity(k, k);
228 if (k == 0) return c;
229 const DiagonalVector dinv = m_d.cwiseInverse();
230 c.noalias() += m_V.adjoint() * dinv.asDiagonal() * m_U;
231 return c;
232 }
233
244 template <typename Rhs>
246 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, b, false, "right-hand side has the wrong number of rows");
247 const DiagonalVector dinv = m_d.cwiseInverse();
248 Matrix<Scalar, Size_, Rhs::ColsAtCompileTime> x = dinv.asDiagonal() * b;
249 internal::dplr_capacitance_impl<Rank_>::subtractSolveCorrection(*this, dinv, x);
250 return x;
251 }
252
258 const DiagonalVector dinv = m_d.cwiseInverse();
259 FactorType Up(rows(), correctionRank());
260 internal::dplr_capacitance_impl<Rank_>::inverseFactor(*this, dinv, Up);
261 FactorType Vp = dinv.conjugate().asDiagonal() * m_V;
262 return DiagonalPlusLowRank(dinv, Up, Vp);
263 }
264
284 Scalar determinant() const {
285 Scalar det(1);
286 Index exponent = 0;
287 for (Index i = 0; i < rows(); ++i)
288 det = internal::balance_exponent(det * internal::balance_exponent(m_d.coeff(i), exponent), exponent);
289 const Scalar capDet = internal::dplr_capacitance_impl<Rank_>::balancedCapacitanceDeterminant(*this, exponent);
290 det = internal::balance_exponent(det * capDet, exponent);
291 return internal::apply_exponent(det, exponent);
292 }
293
296 template <typename Dest>
297 void evalTo(Dest& dst) const {
298 dst.noalias() = m_U * m_V.adjoint();
299 dst.diagonal() += m_d;
300 }
301
303 template <typename Dest>
304 void addTo(Dest& dst) const {
305 dst.noalias() += m_U * m_V.adjoint();
306 dst.diagonal() += m_d;
307 }
308
310 template <typename Dest>
311 void subTo(Dest& dst) const {
312 dst.noalias() -= m_U * m_V.adjoint();
313 dst.diagonal() -= m_d;
314 }
315
321 template <typename Rhs>
325
330 template <typename Dest, typename Rhs, typename ProductScalar>
331 void addProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
332 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*this, rhs, "invalid product: dimensions do not match");
334 dst += alpha * (m_d.asDiagonal() * r);
335 if (correctionRank() > 0) {
337 dst.noalias() += alpha * (m_U * t);
338 }
339 }
340
341 private:
342 DiagonalVector m_d;
343 FactorType m_U;
344 FactorType m_V;
345};
346
350template <typename DDerived, typename UDerived, typename VDerived>
356
357namespace internal {
358
359// Single product specialization covering every product tag; see the note in
360// Circulant.h.
361template <typename Scalar_, int Size_, int Rank_, typename Rhs, int ProductTag>
362struct generic_product_impl<DiagonalPlusLowRank<Scalar_, Size_, Rank_>, Rhs, StructuredShape, DenseShape, ProductTag>
363 : structured_product_impl<DiagonalPlusLowRank<Scalar_, Size_, Rank_>, Rhs> {};
364
365} // namespace internal
366
367#if EIGEN_COMP_CXXVER < 17
368template <typename Scalar_, int Size_, int Rank_>
369constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::RowsAtCompileTime;
370template <typename Scalar_, int Size_, int Rank_>
371constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::ColsAtCompileTime;
372template <typename Scalar_, int Size_, int Rank_>
373constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::MaxRowsAtCompileTime;
374template <typename Scalar_, int Size_, int Rank_>
375constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::MaxColsAtCompileTime;
376template <typename Scalar_, int Size_, int Rank_>
377constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::SizeAtCompileTime;
378template <typename Scalar_, int Size_, int Rank_>
379constexpr int DiagonalPlusLowRank<Scalar_, Size_, Rank_>::MaxSizeAtCompileTime;
380template <typename Scalar_, int Size_, int Rank_>
381constexpr bool DiagonalPlusLowRank<Scalar_, Size_, Rank_>::IsRowMajor;
382#endif
383
384} // namespace Eigen
385
386#endif // EIGEN_STRUCTURED_DIAGONAL_PLUS_LOW_RANK_H
An n x n operator : a diagonal matrix plus a rank-k correction, stored as its diagonal and the two n ...
Definition DiagonalPlusLowRank.h:153
const FactorType & factorV() const
Definition DiagonalPlusLowRank.h:196
Scalar coeff(Index row, Index col) const
Definition DiagonalPlusLowRank.h:199
Matrix< Scalar, Size_, Rhs::ColsAtCompileTime > solve(const MatrixBase< Rhs > &b) const
Definition DiagonalPlusLowRank.h:245
DiagonalPlusLowRank conjugate() const
Definition DiagonalPlusLowRank.h:211
DiagonalPlusLowRank adjoint() const
Definition DiagonalPlusLowRank.h:217
const FactorType & factorU() const
Definition DiagonalPlusLowRank.h:194
Product< DiagonalPlusLowRank, Rhs > operator*(const MatrixBase< Rhs > &v) const
Definition DiagonalPlusLowRank.h:322
DiagonalPlusLowRank inverse() const
Definition DiagonalPlusLowRank.h:257
const DiagonalVector & diagonal() const
Definition DiagonalPlusLowRank.h:192
DiagonalPlusLowRank(const MatrixBase< DDerived > &d, const MatrixBase< UDerived > &U, const MatrixBase< VDerived > &V)
Definition DiagonalPlusLowRank.h:177
CapacitanceType capacitance() const
Definition DiagonalPlusLowRank.h:225
DiagonalPlusLowRank transpose() const
Definition DiagonalPlusLowRank.h:207
Index correctionRank() const
Definition DiagonalPlusLowRank.h:189
Scalar determinant() const
Definition DiagonalPlusLowRank.h:284
DiagonalPlusLowRank< typename DDerived::Scalar, DDerived::SizeAtCompileTime, UDerived::ColsAtCompileTime > makeDiagonalPlusLowRank(const MatrixBase< DDerived > &d, const MatrixBase< UDerived > &U, const MatrixBase< VDerived > &V)
Definition DiagonalPlusLowRank.h:352
Namespace containing all symbols from the Eigen library.