Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
DPR1EigenSolver.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#ifndef EIGEN_STRUCTURED_DPR1_EIGEN_SOLVER_H
11#define EIGEN_STRUCTURED_DPR1_EIGEN_SOLVER_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17
77template <typename RealScalar_>
79 public:
80 using RealScalar = RealScalar_;
81 using Scalar = RealScalar;
82 using Index = Eigen::Index;
83 using VectorType = Matrix<RealScalar, Dynamic, 1>;
84 using MatrixType = Matrix<RealScalar, Dynamic, Dynamic>;
85
86 static_assert(std::is_same<RealScalar, float>::value || std::is_same<RealScalar, double>::value ||
87 std::is_same<RealScalar, long double>::value,
88 "DPR1EigenSolver supports only float, double, and long double scalar types.");
89
91 DPR1EigenSolver() = default;
92
95 DPR1EigenSolver(const VectorType& d, RealScalar rho, const VectorType& z, int options = ComputeEigenvectors) {
96 compute(d, rho, z, options);
97 }
98
100 DPR1EigenSolver& compute(const VectorType& d, RealScalar rho, const VectorType& z, int options = ComputeEigenvectors);
101
103 const VectorType& eigenvalues() const {
104 eigen_assert(m_isInitialized && "DPR1EigenSolver is not initialized.");
105 return m_eivalues;
106 }
107
110 const MatrixType& eigenvectors() const {
111 eigen_assert(m_isInitialized && "DPR1EigenSolver is not initialized.");
112 eigen_assert(m_vectorsComputed && "eigenvectors were not computed");
113 return m_eivec;
114 }
115
121 eigen_assert(m_isInitialized && "DPR1EigenSolver is not initialized.");
122 return m_info;
123 }
124
125 private:
126 // A deflation-stage Givens rotation acting on working rows (i, j).
127 struct Rotation {
128 Index i, j;
129 RealScalar c, s;
130 };
131
135 static RealScalar secular(const VectorType& delta, const VectorType& zeta2, RealScalar rho, RealScalar tau) {
136 return RealScalar(1) + rho * (zeta2.array() / (delta.array() - tau)).sum();
137 }
138
139 VectorType m_eivalues;
140 MatrixType m_eivec;
141 bool m_isInitialized = false;
142 bool m_vectorsComputed = false;
144};
145
146template <typename RealScalar_>
148 const VectorType& z, int options) {
149 const Index n = d.size();
150 EIGEN_INTERNAL_ASSERT_SAME_SIZE_MSG(d, z, "d and z must have the same size");
151 eigen_assert((options & ~EigVecMask) == 0 && (options & EigVecMask) != EigVecMask && "invalid option parameter");
152 const bool computeVectors = (options & ComputeEigenvectors) == ComputeEigenvectors;
153 m_vectorsComputed = false;
154 m_info = Success;
155
156 m_eivalues.resize(n);
157 if (computeVectors) m_eivec.setIdentity(n, n);
158
159 // Non-finite input would break the sorting comparator (not a strict weak
160 // order under NaN) and silently deflate everything; reject it up front.
161 if (!(d.allFinite() && z.allFinite() && (numext::isfinite)(rho))) {
162 m_eivalues.setConstant(NumTraits<RealScalar>::quiet_NaN());
163 m_info = InvalidInput;
164 m_isInitialized = true;
165 return *this;
166 }
167 if (n == 0) {
168 m_vectorsComputed = computeVectors;
169 m_isInitialized = true;
170 return *this;
171 }
172
173 const bool negated = rho < RealScalar(0);
174 const VectorType dW = negated ? VectorType(-d) : d;
175
176 // pi maps each sorted working index to its input row.
177 std::vector<Index> pi;
178 pi.reserve(static_cast<std::size_t>(n));
179 for (Index i = 0; i < n; ++i) pi.push_back(i);
180 std::stable_sort(pi.begin(), pi.end(), [&dW](Index a, Index b) { return dW[a] < dW[b]; });
181 VectorType ds(n), zs(n);
182 for (Index i = 0; i < n; ++i) {
183 ds[i] = dW[pi[static_cast<std::size_t>(i)]];
184 zs[i] = z[pi[static_cast<std::size_t>(i)]];
185 }
186
187 // Normalize z and absorb ||z||^2 into rho, then scale the problem by the exact
188 // power of two s = 2^-scaleExp that brings max(||D||_inf, rho ||z||^2) into
189 // [1/2, 1): eig(sD + s rho zz^T) = s eig(D + rho zz^T).
190 const RealScalar znorm = zs.stableNorm();
191 if (znorm > RealScalar(0)) zs /= znorm;
192 RealScalar rhoW = rho == RealScalar(0) || znorm == RealScalar(0) ? RealScalar(0) : (numext::abs(rho) * znorm) * znorm;
193 if (!(numext::isfinite)(rhoW)) {
194 // An overflowing update would make the deflation tolerance infinite and
195 // silently deflate it away.
196 m_eivalues.setConstant(NumTraits<RealScalar>::quiet_NaN());
197 m_info = InvalidInput;
198 m_isInitialized = true;
199 return *this;
200 }
201 EIGEN_USING_STD(frexp)
202 EIGEN_USING_STD(ldexp)
203 RealScalar scaledNorm = numext::maxi(ds.cwiseAbs().maxCoeff(), rhoW); // in [1/2, 1) once scaled
204 int scaleExp = 0;
205 if (scaledNorm > RealScalar(0)) scaledNorm = frexp(scaledNorm, &scaleExp);
206 ds = ds.array().ldexp(-scaleExp).matrix();
207 rhoW = ldexp(rhoW, -scaleExp);
208
209 // Backward-error budget: dropping a coupling of size <= tol perturbs the
210 // matrix by O(tol), like LAPACK's xLAED2. Using max(|d|_inf, rho*||z||^2) as
211 // the scale is the unscaled-problem generalization of xLAED2's criterion: the
212 // perturbation stays O(eps * (||D|| + rho ||z||^2)), i.e. backward stable in
213 // the data.
214 const RealScalar tol = RealScalar(8) * NumTraits<RealScalar>::epsilon() * scaledNorm;
215
216 std::vector<Rotation> rotations;
217 std::vector<bool> deflated;
218
219 if (rhoW <= tol) {
220 deflated.assign(static_cast<std::size_t>(n), true);
221 } else {
222 // Negligible z_i leaves d_i as an eigenvalue.
223 deflated.reserve(static_cast<std::size_t>(n));
224 for (Index i = 0; i < n; ++i) deflated.push_back(rhoW * numext::abs(zs[i]) <= tol);
225 // The dropped off-diagonal coupling is |c*s*(ds[i]-ds[p])| <= tol.
226 Index p = -1;
227 for (Index i = 0; i < n; ++i) {
228 if (deflated[static_cast<std::size_t>(i)]) continue;
229 if (p >= 0) {
230 const RealScalar r = numext::hypot(zs[p], zs[i]);
231 const RealScalar c = zs[i] / r, s = zs[p] / r; // zeroes the earlier entry
232 const RealScalar gap = ds[i] - ds[p];
233 if (numext::abs(c * s * gap) <= tol) {
234 // Rotated diagonal (c^2 a + s^2 b, s^2 a + c^2 b), a = ds[p], b = ds[i], with c^2 + s^2 = 1
235 // applied exactly and the smaller weight w = min(c^2, s^2) <= 1/2 on the gap:
236 // |s| <= |c|: (a + s^2 gap, b - s^2 gap), otherwise (b - c^2 gap, a + c^2 gap).
237 // Equal poles (gap = 0) keep their value, which the weighted sums lose to the rounding of
238 // c^2 + s^2, and the rounding of a wide gap enters scaled by w.
239 const RealScalar left = ds[p], right = ds[i];
240 if (numext::abs(s) <= numext::abs(c)) {
241 const RealScalar shift = s * s * gap;
242 ds[p] = left + shift;
243 ds[i] = right - shift;
244 } else {
245 const RealScalar shift = c * c * gap;
246 ds[p] = right - shift;
247 ds[i] = left + shift;
248 }
249 zs[i] = r;
250 zs[p] = RealScalar(0);
251 deflated[static_cast<std::size_t>(p)] = true;
252 // Recorded for both options, keeping computeVectors out of the loops that produce the
253 // eigenvalues: GCC unswitches this loop on it, and IBM double-double operations are not
254 // commutative, so the two copies' operand orders can round differently.
255 rotations.push_back(Rotation{p, i, c, s});
256 }
257 }
258 if (!deflated[static_cast<std::size_t>(i)]) p = i;
259 }
260 }
261
262 std::vector<Index> sub; // working positions of the surviving poles
263 for (Index i = 0; i < n; ++i)
264 if (!deflated[static_cast<std::size_t>(i)]) sub.push_back(i);
265 const Index m = static_cast<Index>(sub.size());
266
267 VectorType lambdaW = ds;
268
269 MatrixType subVectors; // m x m secular eigenvectors (in subproblem coordinates)
270
271 if (m > 0) {
272 VectorType delta(m), zeta(m), zeta2(m);
273 std::vector<Index> shiftIndex(static_cast<std::size_t>(m));
274 VectorType tau(m);
275 for (Index a = 0; a < m; ++a) {
276 delta[a] = ds[sub[static_cast<std::size_t>(a)]];
277 zeta[a] = zs[sub[static_cast<std::size_t>(a)]];
278 }
279 zeta2.array() = zeta.array() * zeta.array();
280 const RealScalar zeta2sum = zeta2.sum();
281
282 // Bisection stops when the bracket has collapsed to adjacent floating-point
283 // numbers. The backstop covers exponent_range + 2*digits halvings, enough
284 // to shrink a unit-width bracket to a subnormal root offset and resolve it.
285 const int digits =
286 (std::numeric_limits<RealScalar>::digits > 0) ? static_cast<int>(std::numeric_limits<RealScalar>::digits) : 128;
287 const int expRange = (std::numeric_limits<RealScalar>::max_exponent > std::numeric_limits<RealScalar>::min_exponent)
288 ? static_cast<int>(std::numeric_limits<RealScalar>::max_exponent) -
289 static_cast<int>(std::numeric_limits<RealScalar>::min_exponent)
290 : 16 * digits;
291 const int maxBisect = expRange + 2 * digits + 32;
292 VectorType lam(m), dsh(m); // dsh is refilled from scratch each root
293 for (Index k = 0; k < m; ++k) {
294 // Choose the shift pole and the bracket, entirely in shifted coordinates.
295 RealScalar lo, hi;
296 Index shift;
297 if (k + 1 == m) {
298 // Last root: it lies in (delta_m, delta_m + rho*|zeta|^2]; never form
299 // the unshifted right end (it can round to the pole itself).
300 shift = k;
301 lo = RealScalar(0);
302 hi = rhoW * zeta2sum;
303 } else {
304 // Interior root: the secular function is increasing between the poles,
305 // so its sign at the midpoint picks the nearer pole as the shift.
306 const RealScalar left = delta[k], right = delta[k + 1];
307 const RealScalar mid = left + (right - left) / RealScalar(2);
308 if (secular(delta, zeta2, rhoW, mid) > RealScalar(0)) {
309 shift = k;
310 lo = RealScalar(0);
311 hi = mid - left;
312 } else {
313 shift = k + 1;
314 lo = mid - right; // negative
315 hi = RealScalar(0);
316 }
317 }
318 const RealScalar shiftVal = delta[shift];
319 dsh.array() = delta.array() - shiftVal;
320
321 // Bisection: g(lo) < 0 < g(hi) by the pole signs (for shift = k the
322 // function tends to -inf as tau -> 0+, for shift = k+1 to +inf as
323 // tau -> 0-). The endpoints are never evaluated.
324 RealScalar a0 = lo, b0 = hi;
325 bool converged = false;
326 for (int iter = 0; iter < maxBisect; ++iter) {
327 const RealScalar t = a0 + (b0 - a0) / RealScalar(2);
328 if (t == a0 || t == b0) {
329 converged = true; // interval fully resolved
330 break;
331 }
332 if (secular(dsh, zeta2, rhoW, t) > RealScalar(0))
333 b0 = t;
334 else
335 a0 = t;
336 }
337 if (!converged) m_info = NoConvergence;
338 const RealScalar t = a0 + (b0 - a0) / RealScalar(2);
339 shiftIndex[static_cast<std::size_t>(k)] = shift;
340 tau[k] = t;
341 lam[k] = shiftVal + t;
342 }
343
344 // ---- Gu-Eisenstat weights: the z-vector for which lam are exact roots ----
345 // zhat_i^2 = prod_j (lam_j - delta_i) / (rho * prod_{j != i} (delta_j - delta_i)),
346 // with every distance lam_j - delta_i formed as (delta_shift(j) - delta_i) + tau_j.
347 // Numerator and denominator factors are paired so the running product stays O(1).
348 VectorType zhat(m);
349 for (Index i = 0; i < m; ++i) {
350 RealScalar acc = ((delta[shiftIndex[static_cast<std::size_t>(i)]] - delta[i]) + tau[i]) / rhoW;
351 for (Index j = 0; j < m; ++j) {
352 if (j == i) continue;
353 const RealScalar num = (delta[shiftIndex[static_cast<std::size_t>(j)]] - delta[i]) + tau[j];
354 acc *= num / (delta[j] - delta[i]);
355 }
356 zhat[i] = numext::abs(acc) > RealScalar(0) ? RealScalar(numext::sqrt(numext::abs(acc))) : RealScalar(0);
357 if (zeta[i] < RealScalar(0)) zhat[i] = -zhat[i];
358 }
359
360 // ---- secular eigenvectors from the Gu-Eisenstat weights ----
361 if (computeVectors) {
362 subVectors.resize(m, m);
363 for (Index j = 0; j < m; ++j) {
364 const Index sj = shiftIndex[static_cast<std::size_t>(j)];
365 if (tau[j] == RealScalar(0)) {
366 // The root coincides with its shift pole to working precision (a
367 // fully underflowed bracket): the eigenvector is that pole's axis.
368 subVectors.col(j).setZero();
369 subVectors(sj, j) = RealScalar(1);
370 continue;
371 }
372 // Divide by the pole distances delta_i - lam_j, each formed as
373 // (delta_i - delta_sj) - tau_j.
374 subVectors.col(j).array() = zhat.array() / ((delta.array() - delta[sj]) - tau[j]);
375 subVectors.col(j).stableNormalize();
376 }
377 }
378 for (Index k = 0; k < m; ++k) lambdaW[sub[static_cast<std::size_t>(k)]] = lam[k];
379 }
380
381 std::vector<Index> order;
382 order.reserve(static_cast<std::size_t>(n));
383 for (Index i = 0; i < n; ++i) order.push_back(i);
384 std::stable_sort(order.begin(), order.end(), [&lambdaW](Index a, Index b) { return lambdaW[a] < lambdaW[b]; });
385
386 std::vector<Index> subSlot(static_cast<std::size_t>(n), -1);
387 for (Index a = 0; a < m; ++a) subSlot[static_cast<std::size_t>(sub[static_cast<std::size_t>(a)])] = a;
388
389 for (Index t = 0; t < n; ++t) {
390 const Index w = order[static_cast<std::size_t>(t)];
391 const Index outCol = negated ? n - 1 - t : t;
392 m_eivalues[outCol] = negated ? -lambdaW[w] : lambdaW[w];
393 if (!computeVectors) continue;
394
395 VectorType wvec = VectorType::Zero(n);
396 const Index slot = subSlot[static_cast<std::size_t>(w)];
397 if (slot < 0) {
398 wvec[w] = RealScalar(1);
399 } else {
400 for (Index a = 0; a < m; ++a) wvec[sub[static_cast<std::size_t>(a)]] = subVectors(a, slot);
401 }
402 // w <- G*w with G = [[c, s], [-s, c]]: for exactly equal poles this maps the
403 // deflated unit vector e_p to (c, -s) = (z_i, -z_p)/r, the exact eigenvector
404 // of the 2x2 block orthogonal to the weight vector.
405 for (auto it = rotations.rbegin(); it != rotations.rend(); ++it) {
406 const RealScalar wi = wvec[it->i], wj = wvec[it->j];
407 wvec[it->i] = it->c * wi + it->s * wj;
408 wvec[it->j] = -it->s * wi + it->c * wj;
409 }
410 for (Index i = 0; i < n; ++i) m_eivec(pi[static_cast<std::size_t>(i)], outCol) = wvec[i];
411 }
412
413 m_eivalues = m_eivalues.array().ldexp(scaleExp).matrix();
414 if (!m_eivalues.allFinite()) {
415 m_eivalues.setConstant(NumTraits<RealScalar>::quiet_NaN());
416 m_info = InvalidInput;
417 }
418
419 m_vectorsComputed = computeVectors && m_info != InvalidInput;
420 m_isInitialized = true;
421 return *this;
422}
423
424} // namespace Eigen
425
426#endif // EIGEN_STRUCTURED_DPR1_EIGEN_SOLVER_H
Direct O(n^2) eigensolver for real symmetric diagonal-plus-rank-one matrices , via the secular equati...
Definition DPR1EigenSolver.h:78
const VectorType & eigenvalues() const
Definition DPR1EigenSolver.h:103
ComputationInfo info() const
Definition DPR1EigenSolver.h:120
DPR1EigenSolver(const VectorType &d, RealScalar rho, const VectorType &z, int options=ComputeEigenvectors)
Definition DPR1EigenSolver.h:95
const MatrixType & eigenvectors() const
Definition DPR1EigenSolver.h:110
DPR1EigenSolver & compute(const VectorType &d, RealScalar rho, const VectorType &z, int options=ComputeEigenvectors)
Definition DPR1EigenSolver.h:147
Derived & setZero(Index rows, Index cols)
constexpr void resize(Index rows, Index cols)
ComputationInfo
ComputeEigenvectors
Namespace containing all symbols from the Eigen library.
const Eigen::CwiseBinaryOp< Eigen::internal::scalar_zeta_op< typename DerivedX::Scalar >, const DerivedX, const DerivedQ > zeta(const Eigen::ArrayBase< DerivedX > &x, const Eigen::ArrayBase< DerivedQ > &q)
Definition SpecialFunctionsArrayAPI.h:141