Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
BDCSVDImpl.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// We used the "A Divide-And-Conquer Algorithm for the Bidiagonal SVD"
5// research report written by Ming Gu and Stanley C.Eisenstat
6// The code variable names correspond to the names they used in their
7// report
8//
9// Copyright (C) 2013 Gauthier Brun <brun.gauthier@gmail.com>
10// Copyright (C) 2013 Nicolas Carre <nicolas.carre@ensimag.fr>
11// Copyright (C) 2013 Jean Ceccato <jean.ceccato@ensimag.fr>
12// Copyright (C) 2013 Pierre Zoppitelli <pierre.zoppitelli@ensimag.fr>
13// Copyright (C) 2013 Jitse Niesen <jitse@maths.leeds.ac.uk>
14// Copyright (C) 2014-2017 Gael Guennebaud <gael.guennebaud@inria.fr>
15//
16// Source Code Form is subject to the terms of the Mozilla
17// Public License v. 2.0. If a copy of the MPL was not distributed
18// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
19// SPDX-License-Identifier: MPL-2.0
20
21#ifndef EIGEN_BDCSVD_IMPL_H
22#define EIGEN_BDCSVD_IMPL_H
23
24// IWYU pragma: private
25#include "./InternalHeaderCheck.h"
26
27namespace Eigen {
28
29namespace internal {
30
39template <typename RealScalar_>
40class bdcsvd_impl {
41 public:
42 using RealScalar = RealScalar_;
43 using Literal = typename NumTraits<RealScalar>::Literal;
44 using MatrixXr = Matrix<RealScalar, Dynamic, Dynamic, ColMajor>;
45 using VectorType = Matrix<RealScalar, Dynamic, 1>;
46 using ArrayXr = Array<RealScalar, Dynamic, 1>;
47 using ArrayXi = Array<Index, 1, Dynamic>;
48 using ArrayRef = Ref<ArrayXr>;
49 using ConstArrayRef = Ref<const ArrayXr>;
50 using IndicesRef = Ref<ArrayXi>;
51
52 bdcsvd_impl() : m_algoswap(16), m_compU(false), m_compV(false), m_numIters(0), m_info(Success) {}
53
54 void allocate(Index diagSize, bool compU, bool compV);
55
57 void divide(Index firstCol, Index lastCol, Index firstRowW, Index firstColW, Index shift);
58
60 void splitNegligibleSuperdiagonal(Index n);
61
62 MatrixXr& naiveU() { return m_naiveU; }
63 const MatrixXr& naiveU() const { return m_naiveU; }
64 MatrixXr& naiveV() { return m_naiveV; }
65 const MatrixXr& naiveV() const { return m_naiveV; }
66 MatrixXr& computed() { return m_computed; }
67 const MatrixXr& computed() const { return m_computed; }
68 ComputationInfo info() const { return m_info; }
69 int numIters() const { return m_numIters; }
70 int algoSwap() const { return m_algoswap; }
71 void setAlgoSwap(int s) { m_algoswap = s; }
72
73 private:
74 void computeSVDofM(Index firstCol, Index n, MatrixXr& U, VectorType& singVals, MatrixXr& V);
75 void computeSingVals(const ArrayRef& col0, const ArrayRef& diag, const IndicesRef& perm, VectorType& singVals,
76 ArrayRef shifts, ArrayRef mus, ArrayRef workspace);
77 void perturbCol0(const ArrayRef& col0, const ArrayRef& diag, const IndicesRef& perm, const VectorType& singVals,
78 const ArrayRef& shifts, const ArrayRef& mus, ArrayRef zhat);
79 void computeSingVecs(const ArrayRef& zhat, const ArrayRef& diag, const IndicesRef& perm, const VectorType& singVals,
80 const ArrayRef& shifts, const ArrayRef& mus, MatrixXr& U, MatrixXr& V);
81 void deflation43(Index firstCol, Index shift, Index i, Index size);
82 void deflation44(Index firstColu, Index firstColm, Index firstRowW, Index firstColW, Index i, Index j, Index size);
83 void deflation(Index firstCol, Index lastCol, Index k, Index firstRowW, Index firstColW, Index shift);
84 void structured_update(Block<MatrixXr, Dynamic, Dynamic> A, const MatrixXr& B, Index n1);
85 static EIGEN_STRONG_INLINE RealScalar productOfQuotients(RealScalar firstNumerator, RealScalar firstDenominator,
86 RealScalar secondNumerator, RealScalar secondDenominator);
87 static EIGEN_STRONG_INLINE RealScalar sequentialQuotient(RealScalar numerator, RealScalar firstDenominator,
88 RealScalar secondDenominator);
89 static RealScalar secularEq(RealScalar x, const ConstArrayRef& col0, const ConstArrayRef& diag,
90 const ConstArrayRef& diagShifted, RealScalar shift);
91 template <typename SVDType>
92 void computeBaseCase(SVDType& svd, Index n, Index firstCol, Index firstRowW, Index firstColW, Index shift);
93
94 MatrixXr m_naiveU, m_naiveV;
95 MatrixXr m_computed;
96 ArrayXr m_workspace;
97 ArrayXi m_workspaceI;
98 // Reused base-case JacobiSVDs (one per option set) so that recursive divide()
99 // calls don't reallocate JacobiSVD's internal U/V/sigma buffers each time.
100 JacobiSVD<MatrixXr, ComputeFullU> m_baseSvdU;
101 JacobiSVD<MatrixXr, ComputeFullU | ComputeFullV> m_baseSvdUV;
102 int m_algoswap;
103 bool m_compU, m_compV;
104 int m_numIters;
105 ComputationInfo m_info;
106};
107
108template <typename RealScalar_>
109void bdcsvd_impl<RealScalar_>::allocate(Index diagSize, bool compU, bool compV) {
110 m_compU = compU;
111 m_compV = compV;
112 m_numIters = 0;
113 m_info = Success;
114
115 m_computed = MatrixXr::Zero(diagSize + 1, diagSize);
116
117 if (m_compU)
118 m_naiveU = MatrixXr::Zero(diagSize + 1, diagSize + 1);
119 else
120 m_naiveU = MatrixXr::Zero(2, diagSize + 1);
121
122 if (m_compV) m_naiveV = MatrixXr::Zero(diagSize, diagSize);
123
124 // Vector updates need the three matrix-sized packing buffers used by
125 // structured_update(). Values-only decompositions only need five vectors:
126 // diag, shifts, mus, zhat, and diagShifted.
127 if (m_compU || m_compV)
128 m_workspace.resize((diagSize + 1) * (diagSize + 1) * 3);
129 else
130 m_workspace.resize(5 * diagSize);
131 m_workspaceI.resize(3 * diagSize);
132}
133
134// LAPACK's xBDSDC normalizes the bidiagonal by its largest entry and splits wherever a superdiagonal entry falls
135// below eps, so a run of rounding noise never becomes a sub-problem. Eigen scales the input matrix but has no such
136// split: every threshold in deflation() is formed from the sub-problem's own maximum, so a block whose entries are
137// uniformly tiny looks well scaled from the inside and gets resolved for its own relative accuracy. Zeroing here
138// costs one pass and leaves the perturbation within the eps * ||B|| the SVD already carries.
139template <typename RealScalar_>
140void bdcsvd_impl<RealScalar_>::splitNegligibleSuperdiagonal(Index n) {
141 if (n < 2) return;
142 // xBDSDC scales d and e by DLANST('M', n, d, e), the largest entry of either, and then splits at
143 // 0.9 * DLAMCH('E'). DLAMCH('E') is the unit roundoff, i.e. half of NumTraits::epsilon(), so the
144 // same threshold unscaled is 0.45 * epsilon * ||B||_max.
145 const RealScalar norm = numext::maxi(m_computed.topRows(n).diagonal().cwiseAbs().maxCoeff(),
146 m_computed.topRows(n).template diagonal<-1>().cwiseAbs().maxCoeff());
147 const RealScalar threshold = RealScalar(0.45) * NumTraits<RealScalar>::epsilon() * norm;
148 for (Index i = 0; i + 1 < n; ++i)
149 if (numext::abs(m_computed(i + 1, i)) < threshold) m_computed(i + 1, i) = RealScalar(0);
150}
151
160template <typename RealScalar_>
161void bdcsvd_impl<RealScalar_>::structured_update(Block<MatrixXr, Dynamic, Dynamic> A, const MatrixXr& B, Index n1) {
162 Index n = A.rows();
163 if (n > 100) {
164 // If the matrices are large enough, let's exploit the sparse structure of A by
165 // splitting it in half (wrt n1), and packing the non-zero columns.
166 Index n2 = n - n1;
167 Map<MatrixXr> A1(m_workspace.data(), n1, n);
168 Map<MatrixXr> A2(m_workspace.data() + n1 * n, n2, n);
169 Map<MatrixXr> B1(m_workspace.data() + n * n, n, n);
170 Map<MatrixXr> B2(m_workspace.data() + 2 * n * n, n, n);
171 Index k1 = 0, k2 = 0;
172 for (Index j = 0; j < n; ++j) {
173 if ((A.col(j).head(n1).array() != Literal(0)).any()) {
174 A1.col(k1) = A.col(j).head(n1);
175 B1.row(k1) = B.row(j);
176 ++k1;
177 }
178 if ((A.col(j).tail(n2).array() != Literal(0)).any()) {
179 A2.col(k2) = A.col(j).tail(n2);
180 B2.row(k2) = B.row(j);
181 ++k2;
182 }
183 }
184
185 A.topRows(n1).noalias() = A1.leftCols(k1) * B1.topRows(k1);
186 A.bottomRows(n2).noalias() = A2.leftCols(k2) * B2.topRows(k2);
187 } else {
188 Map<MatrixXr, Aligned> tmp(m_workspace.data(), n, n);
189 tmp.noalias() = A * B;
190 A = tmp;
191 }
192}
193
194template <typename RealScalar_>
195template <typename SVDType>
196void bdcsvd_impl<RealScalar_>::computeBaseCase(SVDType& svd, Index n, Index firstCol, Index firstRowW, Index firstColW,
197 Index shift) {
198 svd.compute(m_computed.block(firstCol, firstCol, n + 1, n));
199 m_info = svd.info();
200 if (m_info != Success && m_info != NoConvergence) return;
201 if (m_compU)
202 m_naiveU.block(firstCol, firstCol, n + 1, n + 1) = svd.matrixU();
203 else {
204 m_naiveU.row(0).segment(firstCol, n + 1) = svd.matrixU().row(0);
205 m_naiveU.row(1).segment(firstCol, n + 1) = svd.matrixU().row(n);
206 }
207 if (m_compV) m_naiveV.block(firstRowW, firstColW, n, n) = svd.matrixV();
208 m_computed.block(firstCol + shift, firstCol + shift, n + 1, n).setZero();
209 m_computed.diagonal().segment(firstCol + shift, n) = svd.singularValues().head(n);
210}
211
212// The divide algorithm is done "in place", we are always working on subsets of the same matrix. The divide methods
213// takes as argument the place of the submatrix we are currently working on.
214
215//@param firstCol : The Index of the first column of the submatrix of m_computed and for m_naiveU;
216//@param lastCol : The Index of the last column of the submatrix of m_computed and for m_naiveU;
217// lastCol + 1 - firstCol is the size of the submatrix.
218//@param firstRowW : The Index of the first row of the matrix W that we are to change. (see the reference paper section
219// 1 for more information on W)
220//@param firstColW : Same as firstRowW with the column.
221//@param shift : Each time one takes the left submatrix, one must add 1 to the shift. Why? Because! We actually want the
222// last column of the U submatrix
223// to become the first column (*coeff) and to shift all the other columns to the right. There are more details on the
224// reference paper.
225template <typename RealScalar_>
226void bdcsvd_impl<RealScalar_>::divide(Index firstCol, Index lastCol, Index firstRowW, Index firstColW, Index shift) {
227 // requires rows = cols + 1;
228 const Index n = lastCol - firstCol + 1;
229 const Index k = n / 2;
230 const RealScalar considerZero = (std::numeric_limits<RealScalar>::min)();
231 RealScalar alphaK;
232 RealScalar betaK;
233 RealScalar r0;
234 RealScalar lambda, phi, c0, s0;
235 // We use the other algorithm which is more efficient for small
236 // matrices.
237 if (n < m_algoswap) {
238 if (m_compV) {
239 computeBaseCase(m_baseSvdUV, n, firstCol, firstRowW, firstColW, shift);
240 } else {
241 computeBaseCase(m_baseSvdU, n, firstCol, firstRowW, firstColW, shift);
242 }
243 return;
244 }
245 // We use the divide and conquer algorithm
246 alphaK = m_computed(firstCol + k, firstCol + k);
247 betaK = m_computed(firstCol + k + 1, firstCol + k);
248 // The divide must be done in that order in order to have good results. Divide change the data inside the submatrices
249 // and the divide of the right submatrice reads one column of the left submatrice. That's why we need to treat the
250 // right submatrix before the left one.
251 divide(k + 1 + firstCol, lastCol, k + 1 + firstRowW, k + 1 + firstColW, shift);
252 if (m_info != Success && m_info != NoConvergence) return;
253 divide(firstCol, k - 1 + firstCol, firstRowW, firstColW + 1, shift + 1);
254 if (m_info != Success && m_info != NoConvergence) return;
255
256 if (m_compU) {
257 lambda = m_naiveU(firstCol + k, firstCol + k);
258 phi = m_naiveU(firstCol + k + 1, lastCol + 1);
259 } else {
260 lambda = m_naiveU(1, firstCol + k);
261 phi = m_naiveU(0, lastCol + 1);
262 }
263 // LAPACK's xLASD2 likewise uses xLAPY2 for this merge coupling. The
264 // scaled hypotenuse avoids destructive underflow when both products are
265 // below sqrt(min()).
266 r0 = numext::hypot(alphaK * lambda, betaK * phi);
267 if (m_compV) m_naiveV(firstRowW + k, firstColW) = Literal(1);
268 if (r0 < considerZero) {
269 c0 = Literal(1);
270 s0 = Literal(0);
271 } else {
272 c0 = alphaK * lambda / r0;
273 s0 = betaK * phi / r0;
274 }
275
276 m_computed(firstCol + shift, firstCol + shift) = r0;
277 if (m_compU) {
278 m_computed.col(firstCol + shift).segment(firstCol + shift + 1, k) =
279 alphaK * m_naiveU.row(firstCol + k).segment(firstCol, k).transpose();
280 m_computed.col(firstCol + shift).segment(firstCol + shift + k + 1, n - k - 1) =
281 betaK * m_naiveU.row(firstCol + k + 1).segment(firstCol + k + 1, n - k - 1).transpose();
282 } else {
283 m_computed.col(firstCol + shift).segment(firstCol + shift + 1, k) =
284 alphaK * m_naiveU.row(1).segment(firstCol, k).transpose();
285 m_computed.col(firstCol + shift).segment(firstCol + shift + k + 1, n - k - 1) =
286 betaK * m_naiveU.row(0).segment(firstCol + k + 1, n - k - 1).transpose();
287 }
288
289 if (m_compU) {
290 Map<VectorType, Aligned> q1(m_workspace.data(), k + 1);
291 q1 = m_naiveU.col(firstCol + k).segment(firstCol, k + 1);
292 // we shift Q1 to the right
293 for (Index i = firstCol + k - 1; i >= firstCol; i--)
294 m_naiveU.col(i + 1).segment(firstCol, k + 1) = m_naiveU.col(i).segment(firstCol, k + 1);
295 // we shift q1 at the left with a factor c0
296 m_naiveU.col(firstCol).segment(firstCol, k + 1) = (q1 * c0);
297 // last column = q1 * - s0
298 m_naiveU.col(lastCol + 1).segment(firstCol, k + 1) = (q1 * (-s0));
299 // first column = q2 * s0
300 m_naiveU.col(firstCol).segment(firstCol + k + 1, n - k) =
301 m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) * s0;
302 // q2 *= c0
303 m_naiveU.col(lastCol + 1).segment(firstCol + k + 1, n - k) *= c0;
304 } else {
305 RealScalar q1 = m_naiveU(0, firstCol + k);
306 // we shift Q1 to the right
307 for (Index i = firstCol + k - 1; i >= firstCol; i--) m_naiveU(0, i + 1) = m_naiveU(0, i);
308 // we shift q1 at the left with a factor c0
309 m_naiveU(0, firstCol) = (q1 * c0);
310 // last column = q1 * - s0
311 m_naiveU(0, lastCol + 1) = (q1 * (-s0));
312 // first column = q2 * s0
313 m_naiveU(1, firstCol) = m_naiveU(1, lastCol + 1) * s0;
314 // q2 *= c0
315 m_naiveU(1, lastCol + 1) *= c0;
316 m_naiveU.row(1).segment(firstCol + 1, k).setZero();
317 m_naiveU.row(0).segment(firstCol + k + 1, n - k - 1).setZero();
318 }
319
320 // Second part: try to deflate singular values in combined matrix
321 deflation(firstCol, lastCol, k, firstRowW, firstColW, shift);
322
323 // Third part: compute SVD of combined matrix
324 MatrixXr UofSVD, VofSVD;
325 VectorType singVals;
326 computeSVDofM(firstCol + shift, n, UofSVD, singVals, VofSVD);
327
328 if (m_compU)
329 structured_update(m_naiveU.block(firstCol, firstCol, n + 1, n + 1), UofSVD, (n + 2) / 2);
330 else {
331 Map<Matrix<RealScalar, 2, Dynamic>, Aligned> tmp(m_workspace.data(), 2, n + 1);
332 tmp.noalias() = m_naiveU.middleCols(firstCol, n + 1) * UofSVD;
333 m_naiveU.middleCols(firstCol, n + 1) = tmp;
334 }
335
336 if (m_compV) structured_update(m_naiveV.block(firstRowW, firstColW, n, n), VofSVD, (n + 1) / 2);
337
338 // Recursive children leave this block diagonal; this merge only adds its
339 // first column. Clear that column instead of rewriting the full n-by-n block.
340 m_computed.col(firstCol + shift).segment(firstCol + shift, n).setZero();
341 m_computed.diagonal().segment(firstCol + shift, n) = singVals;
342} // end divide
343
344// Compute SVD of m_computed.block(firstCol, firstCol, n + 1, n); this block only has non-zeros in
345// the first column and on the diagonal and has undergone deflation, so diagonal is in increasing
346// order except for possibly the (0,0) entry. The computed SVD is stored U, singVals and V, except
347// that if m_compV is false, then V is not computed. Singular values are sorted in decreasing order.
348template <typename RealScalar_>
349void bdcsvd_impl<RealScalar_>::computeSVDofM(Index firstCol, Index n, MatrixXr& U, VectorType& singVals, MatrixXr& V) {
350 const RealScalar considerZero = (std::numeric_limits<RealScalar>::min)();
351 ArrayRef col0 = m_computed.col(firstCol).segment(firstCol, n);
352 m_workspace.head(n) = m_computed.block(firstCol, firstCol, n, n).diagonal();
353 ArrayRef diag = m_workspace.head(n);
354 diag(0) = Literal(0);
355
356 // Allocate space for singular values and vectors
357 singVals.resize(n);
358 U.resize(n + 1, n + 1);
359 if (m_compV) V.resize(n, n);
360
361 // Many singular values might have been deflated, the zero ones have been moved to the end,
362 // but others are interleaved and we must ignore them at this stage.
363 // To this end, let's compute a permutation skipping them:
364 Index actual_n = n;
365 while (actual_n > 1 && numext::is_exactly_zero(diag(actual_n - 1))) {
366 --actual_n;
367 eigen_internal_assert(numext::is_exactly_zero(col0(actual_n)));
368 }
369 Index m = 0; // size of the deflated problem
370 for (Index k = 0; k < actual_n; ++k)
371 if (numext::abs(col0(k)) > considerZero) m_workspaceI(m++) = k;
372 Map<ArrayXi> perm(m_workspaceI.data(), m);
373
374 Map<ArrayXr> shifts(m_workspace.data() + 1 * n, n);
375 Map<ArrayXr> mus(m_workspace.data() + 2 * n, n);
376 Map<ArrayXr> zhat(m_workspace.data() + 3 * n, n);
377
378 // Compute singVals, shifts, and mus
379 // U is filled by computeSingVecs below; reuse its storage to pack the active secular terms.
380 Map<ArrayXr> secularWorkspace(U.data(), 2 * n);
381 computeSingVals(col0, diag, perm, singVals, shifts, mus, secularWorkspace);
382
383 // Compute zhat
384 perturbCol0(col0, diag, perm, singVals, shifts, mus, zhat);
385
386 computeSingVecs(zhat, diag, perm, singVals, shifts, mus, U, V);
387
388 // Because of deflation, the singular values might not be completely sorted.
389 // Fortunately, reordering them is a O(n) problem
390 for (Index i = 0; i < actual_n - 1; ++i) {
391 if (singVals(i) > singVals(i + 1)) {
392 using std::swap;
393 swap(singVals(i), singVals(i + 1));
394 U.col(i).swap(U.col(i + 1));
395 if (m_compV) V.col(i).swap(V.col(i + 1));
396 }
397 }
398
399 // Reverse order so that singular values in increased order
400 // Because of deflation, the zeros singular-values are already at the end
401 singVals.head(actual_n).reverseInPlace();
402 U.leftCols(actual_n).rowwise().reverseInPlace();
403 if (m_compV) V.leftCols(actual_n).rowwise().reverseInPlace();
404}
405
406template <typename RealScalar_>
407EIGEN_STRONG_INLINE typename bdcsvd_impl<RealScalar_>::RealScalar bdcsvd_impl<RealScalar_>::productOfQuotients(
408 RealScalar firstNumerator, RealScalar firstDenominator, RealScalar secondNumerator, RealScalar secondDenominator) {
409 // Keep the divisions separate: combining their denominators can underflow even when the final product is finite.
410 RealScalar firstQuotient = firstNumerator / firstDenominator;
411 RealScalar secondQuotient = secondNumerator / secondDenominator;
412#if defined(__FAST_MATH__) || EIGEN_COMP_NVHPC
413 // NVHPC does not expose a preprocessor macro for -fast, so retain the barriers in all NVHPC builds.
414 pbarrier(firstQuotient);
415 pbarrier(secondQuotient);
416#endif
417 return firstQuotient * secondQuotient;
418}
419
420template <typename RealScalar_>
421EIGEN_STRONG_INLINE typename bdcsvd_impl<RealScalar_>::RealScalar bdcsvd_impl<RealScalar_>::sequentialQuotient(
422 RealScalar numerator, RealScalar firstDenominator, RealScalar secondDenominator) {
423 RealScalar firstQuotient = numerator / firstDenominator;
424#if defined(__FAST_MATH__) || EIGEN_COMP_NVHPC
425 pbarrier(firstQuotient);
426#endif
427 return firstQuotient / secondDenominator;
428}
429
430template <typename RealScalar_>
431typename bdcsvd_impl<RealScalar_>::RealScalar bdcsvd_impl<RealScalar_>::secularEq(RealScalar mu,
432 const ConstArrayRef& col0,
433 const ConstArrayRef& diag,
434 const ConstArrayRef& diagShifted,
435 RealScalar shift) {
436 RealScalar res = Literal(1);
437 for (Index i = 0; i < col0.size(); ++i) {
438 res += productOfQuotients(col0(i), diagShifted(i) - mu, col0(i), diag(i) + shift + mu);
439 }
440 return res;
441}
442
443template <typename RealScalar_>
444void bdcsvd_impl<RealScalar_>::computeSingVals(const ArrayRef& col0, const ArrayRef& diag, const IndicesRef& perm,
445 VectorType& singVals, ArrayRef shifts, ArrayRef mus,
446 ArrayRef workspace) {
447 // See Ren-Cang Li, "Solving Secular Equations Stably and Efficiently",
448 // LAPACK Working Note 89 (1994), and LAPACK's xLASD4/xLASD5 for the
449 // stability rationale behind pole-relative shifts and safeguarded steps.
450 using std::swap;
451
452 Index n = col0.size();
453 const Index m = perm.size();
454 // perm is strictly increasing, so its last entry identifies a contiguous prefix.
455 const bool contiguous = m == 0 || perm(m - 1) == m - 1;
456 if (!contiguous) {
457 for (Index i = 0; i < m; ++i) {
458 workspace(i) = col0(perm(i));
459 workspace(m + i) = diag(perm(i));
460 }
461 }
462 // Bind the views once for the repeated secularEq evaluations.
463 const ConstArrayRef activeCol0 = Map<const ArrayXr>(contiguous ? col0.data() : workspace.data(), m);
464 const ConstArrayRef activeDiag = Map<const ArrayXr>(contiguous ? diag.data() : workspace.data() + m, m);
465 Index actual_n = n;
466 // Note that here actual_n is computed based on col0(i)==0 instead of diag(i)==0 as above
467 // because 1) we have diag(i)==0 => col0(i)==0 and 2) if col0(i)==0, then diag(i) is already a singular value.
468 while (actual_n > 1 && numext::is_exactly_zero(col0(actual_n - 1))) --actual_n;
469
470 for (Index k = 0; k < n; ++k) {
471 if (numext::is_exactly_zero(col0(k)) || actual_n == 1) {
472 // if col0(k) == 0, then entry is deflated, so singular value is on diagonal
473 // if actual_n==1, then the deflated problem is already diagonalized
474 singVals(k) = k == 0 ? col0(0) : diag(k);
475 mus(k) = Literal(0);
476 shifts(k) = k == 0 ? col0(0) : diag(k);
477 continue;
478 }
479
480 // otherwise, use secular equation to find singular value
481 RealScalar left = diag(k);
482 RealScalar right; // was: = (k != actual_n-1) ? diag(k+1) : (diag(actual_n-1) + col0.matrix().norm());
483 if (k == actual_n - 1)
484 right = (diag(actual_n - 1) + col0.matrix().stableNorm());
485 else {
486 // Skip deflated singular values,
487 // recall that at this stage we assume that z[j]!=0 and all entries for which z[j]==0 have been put aside.
488 // This should be equivalent to using perm[]
489 Index l = k + 1;
490 while (numext::is_exactly_zero(col0(l))) {
491 ++l;
492 eigen_internal_assert(l < actual_n);
493 }
494 right = diag(l);
495 }
496
497 // first decide whether it's closer to the left end or the right end
498 RealScalar mid = left + (right - left) / Literal(2);
499 RealScalar fMid = secularEq(mid, activeCol0, activeDiag, activeDiag, Literal(0));
500 RealScalar shift = (k == actual_n - 1 || fMid > Literal(0)) ? left : right;
501
502 // measure everything relative to shift
503 Map<ArrayXr> diagShifted(m_workspace.data() + 4 * n, m);
504 const ConstArrayRef shiftedRef(diagShifted);
505 diagShifted = activeDiag - shift;
506
507 if (k != actual_n - 1) {
508 // mid rounds to working precision, but midShifted is exact relative to the pole. With close poles, fMid can
509 // therefore misplace the root, and the bisection below only reaches 0.51 * (right - left) from the shift.
510 RealScalar midShifted = (right - left) / RealScalar(2);
511 // we can test exact equality here, because shift comes from `... ? left : right`
512 if (numext::equal_strict(shift, right)) midShifted = -midShifted;
513 RealScalar fMidShifted = secularEq(midShifted, activeCol0, activeDiag, shiftedRef, shift);
514 const RealScalar rootSideShift = fMidShifted > Literal(0) ? left : right;
515 if (!numext::equal_strict(shift, rootSideShift)) {
516 shift = rootSideShift;
517 diagShifted = activeDiag - shift;
518 }
519 }
520
521 // initial guess
522 RealScalar muPrev, muCur;
523 // we can test exact equality here, because shift comes from `... ? left : right`
524 if (numext::equal_strict(shift, left)) {
525 muPrev = (right - left) * RealScalar(0.1);
526 if (k == actual_n - 1)
527 muCur = right - left;
528 else
529 muCur = (right - left) * RealScalar(0.5);
530 } else {
531 muPrev = -(right - left) * RealScalar(0.1);
532 muCur = -(right - left) * RealScalar(0.5);
533 }
534
535 RealScalar fPrev = secularEq(muPrev, activeCol0, activeDiag, shiftedRef, shift);
536 RealScalar fCur = secularEq(muCur, activeCol0, activeDiag, shiftedRef, shift);
537 if (numext::abs(fPrev) < numext::abs(fCur)) {
538 swap(fPrev, fCur);
539 swap(muPrev, muCur);
540 }
541
542 // Fit a / mu + b through the two previous iterates. Equal signs permit extrapolation; flat fits and
543 // samples whose reciprocals may overflow stay on bisection. The interval and residual checks below
544 // safeguard each interpolation step.
545 const RealScalar minNormal = (std::numeric_limits<RealScalar>::min)();
546 bool useBisection =
547 fPrev * fCur > Literal(0) && !(numext::abs(fCur - fPrev) > NumTraits<RealScalar>::epsilon() &&
548 numext::abs(fPrev) <= (std::numeric_limits<RealScalar>::max)() &&
549 numext::abs(muPrev) >= minNormal && numext::abs(muCur) >= minNormal);
550 while (!numext::is_exactly_zero(fCur) &&
551 numext::abs(muCur - muPrev) > Literal(8) * NumTraits<RealScalar>::epsilon() *
552 numext::maxi<RealScalar>(numext::abs(muCur), numext::abs(muPrev)) &&
553 numext::abs(fCur - fPrev) > NumTraits<RealScalar>::epsilon() && !useBisection) {
554 ++m_numIters;
555
556 // Find a and b such that the function f(mu) = a / mu + b matches the current and previous samples.
557 RealScalar a = (fCur - fPrev) / (Literal(1) / muCur - Literal(1) / muPrev);
558 RealScalar b = fCur - a / muCur;
559 // And find mu such that f(mu)==0:
560 RealScalar muZero = -a / b;
561 RealScalar fZero = secularEq(muZero, activeCol0, activeDiag, shiftedRef, shift);
562
563 muPrev = muCur;
564 fPrev = fCur;
565 muCur = muZero;
566 fCur = fZero;
567
568 // we can test exact equality here, because shift comes from `... ? left : right`
569 if (numext::equal_strict(shift, left) && (muCur < Literal(0) || muCur > right - left)) useBisection = true;
570 if (numext::equal_strict(shift, right) && (muCur < -(right - left) || muCur > Literal(0))) useBisection = true;
571 if (numext::abs(fCur) > numext::abs(fPrev)) useBisection = true;
572 }
573
574 // fall back on bisection method if rational interpolation did not work
575 if (useBisection) {
576 RealScalar leftShifted, rightShifted;
577 // we can test exact equality here, because shift comes from `... ? left : right`
578 if (numext::equal_strict(shift, left)) {
579 // to avoid overflow, we must have mu > max(real_min, |z(k)|/sqrt(real_max)),
580 // the factor 2 is to be more conservative
581 leftShifted = numext::maxi<RealScalar>(
582 (std::numeric_limits<RealScalar>::min)(),
583 Literal(2) * numext::abs(col0(k)) / numext::sqrt((std::numeric_limits<RealScalar>::max)()));
584
585 // check that we did it right:
586 eigen_internal_assert(
587 (numext::isfinite)(productOfQuotients(col0(k), leftShifted, col0(k), diag(k) + shift + leftShifted)));
588 rightShifted = (k == actual_n - 1)
589 ? right
590 : ((right - left) * RealScalar(0.51)); // theoretically we can take 0.5, but let's be safe
591 } else {
592 leftShifted = -(right - left) * RealScalar(0.51);
593 if (k + 1 < n)
594 rightShifted = -numext::maxi<RealScalar>(
595 (std::numeric_limits<RealScalar>::min)(),
596 numext::abs(col0(k + 1)) / numext::sqrt((std::numeric_limits<RealScalar>::max)()));
597 else
598 rightShifted = -(std::numeric_limits<RealScalar>::min)();
599 }
600 RealScalar fLeft = secularEq(leftShifted, activeCol0, activeDiag, shiftedRef, shift);
601 eigen_internal_assert(fLeft < Literal(0));
602
603 if (fLeft < Literal(0)) {
604 while (rightShifted - leftShifted >
605 Literal(2) * NumTraits<RealScalar>::epsilon() *
606 numext::maxi<RealScalar>(numext::abs(leftShifted), numext::abs(rightShifted))) {
607 RealScalar midShifted = (leftShifted + rightShifted) / Literal(2);
608 fMid = secularEq(midShifted, activeCol0, activeDiag, shiftedRef, shift);
609 eigen_internal_assert((numext::isfinite)(fMid));
610
611 // An exact root must end the search: with fLeft = 0, every later sign test would fail and drive the search to
612 // rightShifted.
613 if (numext::is_exactly_zero(fMid)) {
614 leftShifted = rightShifted = midShifted;
615 break;
616 }
617
618 if (fLeft * fMid < Literal(0)) {
619 rightShifted = midShifted;
620 } else {
621 leftShifted = midShifted;
622 fLeft = fMid;
623 }
624 }
625 muCur = (leftShifted + rightShifted) / Literal(2);
626 } else {
627 // We have a problem as shifting on the left or right give either a positive or negative value
628 // at the middle of [left,right]...
629 // Instead of aborting or entering an infinite loop,
630 // let's just use the middle as the estimated zero-crossing:
631 muCur = (right - left) * RealScalar(0.5);
632 // we can test exact equality here, because shift comes from `... ? left : right`
633 if (numext::equal_strict(shift, right)) muCur = -muCur;
634 }
635 }
636
637 singVals[k] = shift + muCur;
638 shifts[k] = shift;
639 mus[k] = muCur;
640 }
641}
642
643// zhat is perturbation of col0 for which singular vectors can be computed stably (see Section 3.1)
644template <typename RealScalar_>
645void bdcsvd_impl<RealScalar_>::perturbCol0(const ArrayRef& col0, const ArrayRef& diag, const IndicesRef& perm,
646 const VectorType& singVals, const ArrayRef& shifts, const ArrayRef& mus,
647 ArrayRef zhat) {
648 Index n = col0.size();
649 Index m = perm.size();
650 if (m == 0) {
651 zhat.setZero();
652 return;
653 }
654 Index lastIdx = perm(m - 1);
655 // The offset permits to skip deflated entries while computing zhat
656 for (Index k = 0; k < n; ++k) {
657 if (numext::is_exactly_zero(col0(k))) // deflated
658 zhat(k) = Literal(0);
659 else {
660 // see equation (3.6)
661 RealScalar dk = diag(k);
662 // Materialize the close subtraction before adding the small correction.
663 // Unsafe FP reassociation may otherwise turn `mus + (shift - dk)` into
664 // `(mus + shift) - dk`, losing `mus` when `shift` and `dk` cancel.
665 RealScalar diff = shifts(lastIdx) - dk;
666 pbarrier(diff);
667 RealScalar prod = (singVals(lastIdx) + dk) * (mus(lastIdx) + diff);
668
669 for (Index l = 0; l < m; ++l) {
670 Index i = perm(l);
671 if (i != k) {
672 // There is no valid predecessor when the first active index is already on the
673 // right of k. Treat this as a numerical issue and zero the product.
674 if (i >= k && l == 0) {
675 m_info = NumericalIssue;
676 prod = Literal(0);
677 break;
678 }
679 Index j = i < k ? i : perm(l - 1);
680 diff = shifts(j) - dk;
681 pbarrier(diff);
682 prod *= productOfQuotients(singVals(j) + dk, diag(i) + dk, mus(j) + diff, diag(i) - dk);
683 }
684 }
685 // This product is non-negative in exact arithmetic. As in LAPACK's
686 // xLASD8, take abs before sqrt to tolerate a negative rounding residue.
687 RealScalar tmp = numext::sqrt(numext::abs(prod));
688 zhat(k) = col0(k) > Literal(0) ? RealScalar(tmp) : RealScalar(-tmp);
689 }
690 }
691}
692
693// compute singular vectors
694template <typename RealScalar_>
695void bdcsvd_impl<RealScalar_>::computeSingVecs(const ArrayRef& zhat, const ArrayRef& diag, const IndicesRef& perm,
696 const VectorType& singVals, const ArrayRef& shifts, const ArrayRef& mus,
697 MatrixXr& U, MatrixXr& V) {
698 Index n = zhat.size();
699 Index m = perm.size();
700
701 for (Index k = 0; k < n; ++k) {
702 if (numext::is_exactly_zero(zhat(k))) {
703 U.col(k) = VectorType::Unit(n + 1, k);
704 if (m_compV) V.col(k) = VectorType::Unit(n, k);
705 } else {
706 U.col(k).setZero();
707 if (m_compV) V.col(k).setZero();
708 const RealScalar shift = shifts(k);
709 const RealScalar mu = mus(k);
710 const RealScalar singularValue = singVals(k);
711 for (Index l = 0; l < m; ++l) {
712 Index i = perm(l);
713 const RealScalar diagonal = diag(i);
714 const RealScalar z = zhat(i);
715 RealScalar diff = diagonal - shift;
716 pbarrier(diff);
717 diff -= mu;
718 pbarrier(diff);
719 const RealScalar sum = diagonal + singularValue;
720 U(i, k) = sequentialQuotient(z, diff, sum);
721 if (m_compV && l > 0) V(i, k) = sequentialQuotient(diagonal * z, diff, sum);
722 }
723 U(n, k) = Literal(0);
724 // LAPACK's xLASD3 normalizes these vectors with xNRM2. Use the scaled
725 // normalization unconditionally: under -ffast-math, compilers may
726 // assume that the overflowing result of norm() is finite and discard
727 // an isfinite-based fallback.
728 U.col(k).stableNormalize();
729
730 if (m_compV) {
731 V(0, k) = Literal(-1);
732 V.col(k).stableNormalize();
733 }
734 }
735 }
736 U.col(n) = VectorType::Unit(n + 1, n);
737}
738
739// page 12_13
740// i >= 1, di almost null and zi non null.
741// We use a rotation to zero out zi applied to the left of M, and set di = 0.
742template <typename RealScalar_>
743void bdcsvd_impl<RealScalar_>::deflation43(Index firstCol, Index shift, Index i, Index size) {
744 Index start = firstCol + shift;
745 RealScalar c = m_computed(start, start);
746 RealScalar s = m_computed(start + i, start);
747 RealScalar r = numext::hypot(c, s);
748 if (numext::is_exactly_zero(r)) {
749 m_computed(start + i, start + i) = Literal(0);
750 return;
751 }
752 m_computed(start, start) = r;
753 m_computed(start + i, start) = Literal(0);
754 m_computed(start + i, start + i) = Literal(0);
755
756 JacobiRotation<RealScalar> J(c / r, -s / r);
757 if (m_compU)
758 m_naiveU.middleRows(firstCol, size + 1).applyOnTheRight(firstCol, firstCol + i, J);
759 else
760 m_naiveU.applyOnTheRight(firstCol, firstCol + i, J);
761} // end deflation 43
762
763// page 13
764// i,j >= 1, i > j, and |di - dj| < epsilon * norm2(M)
765// We apply two rotations to have zi = 0, and dj = di.
766template <typename RealScalar_>
767void bdcsvd_impl<RealScalar_>::deflation44(Index firstColu, Index firstColm, Index firstRowW, Index firstColW, Index i,
768 Index j, Index size) {
769 RealScalar s = m_computed(firstColm + i, firstColm);
770 RealScalar c = m_computed(firstColm + j, firstColm);
771 RealScalar r = numext::hypot(c, s);
772 if (numext::is_exactly_zero(r)) {
773 m_computed(firstColm + j, firstColm + j) = m_computed(firstColm + i, firstColm + i);
774 return;
775 }
776 c /= r;
777 s /= r;
778 m_computed(firstColm + j, firstColm) = r;
779 m_computed(firstColm + j, firstColm + j) = m_computed(firstColm + i, firstColm + i);
780 m_computed(firstColm + i, firstColm) = Literal(0);
781
782 JacobiRotation<RealScalar> J(c, -s);
783 if (m_compU)
784 m_naiveU.middleRows(firstColu, size + 1).applyOnTheRight(firstColu + j, firstColu + i, J);
785 else
786 m_naiveU.applyOnTheRight(firstColu + j, firstColu + i, J);
787 if (m_compV) m_naiveV.middleRows(firstRowW, size).applyOnTheRight(firstColW + j, firstColW + i, J);
788} // end deflation 44
789
790// acts on block from (firstCol+shift, firstCol+shift) to (lastCol+shift, lastCol+shift) [inclusive]
791template <typename RealScalar_>
792void bdcsvd_impl<RealScalar_>::deflation(Index firstCol, Index lastCol, Index k, Index firstRowW, Index firstColW,
793 Index shift) {
794 const Index length = lastCol + 1 - firstCol;
795
796 Block<MatrixXr, Dynamic, 1> col0(m_computed, firstCol + shift, firstCol + shift, length, 1);
797 Diagonal<MatrixXr> fulldiag(m_computed);
798 VectorBlock<Diagonal<MatrixXr>, Dynamic> diag(fulldiag, firstCol + shift, length);
799
800 const RealScalar considerZero = (std::numeric_limits<RealScalar>::min)();
801 RealScalar maxDiag = diag.tail((std::max)(Index(1), length - 1)).cwiseAbs().maxCoeff();
802 RealScalar epsilon_strict = numext::maxi<RealScalar>(considerZero, NumTraits<RealScalar>::epsilon() * maxDiag);
803 RealScalar epsilon_coarse =
804 Literal(8) * NumTraits<RealScalar>::epsilon() * numext::maxi<RealScalar>(col0.cwiseAbs().maxCoeff(), maxDiag);
805
806 // condition 4.1
807 if (diag(0) < epsilon_coarse) {
808 diag(0) = epsilon_coarse;
809 }
810
811 // condition 4.2
812 for (Index i = 1; i < length; ++i)
813 if (numext::abs(col0(i)) < epsilon_strict) {
814 col0(i) = Literal(0);
815 }
816
817 // condition 4.3
818 for (Index i = 1; i < length; i++)
819 if (diag(i) < epsilon_coarse) {
820 deflation43(firstCol, shift, i, length);
821 }
822
823 {
824 // Check for total deflation:
825 // If we have a total deflation, then we have to consider col0(0)==diag(0) as a singular value during sorting.
826 const bool total_deflation = (col0.tail(length - 1).array().abs() < considerZero).all();
827
828 // Sort the diagonal entries, since diag(1:k-1) and diag(k:length) are already sorted, let's do a sorted merge.
829 // First, compute the respective permutation.
830 Index* permutation = m_workspaceI.data();
831 {
832 permutation[0] = 0;
833 Index p = 1;
834
835 // Move deflated diagonal entries at the end.
836 for (Index i = 1; i < length; ++i)
837 if (diag(i) < considerZero) permutation[p++] = i;
838
839 Index i = 1, j = k + 1;
840 for (; p < length; ++p) {
841 if (i > k)
842 permutation[p] = j++;
843 else if (j >= length)
844 permutation[p] = i++;
845 else if (diag(i) < diag(j))
846 permutation[p] = j++;
847 else
848 permutation[p] = i++;
849 }
850 }
851
852 // If we have a total deflation, then we have to insert diag(0) at the right place
853 if (total_deflation) {
854 for (Index i = 1; i < length; ++i) {
855 Index pi = permutation[i];
856 if (diag(pi) < considerZero || diag(0) < diag(pi))
857 permutation[i - 1] = permutation[i];
858 else {
859 permutation[i - 1] = 0;
860 break;
861 }
862 }
863 }
864
865 // Current index of each col, and current column of each index
866 Index* realInd = m_workspaceI.data() + length;
867 Index* realCol = m_workspaceI.data() + 2 * length;
868
869 for (int pos = 0; pos < length; pos++) {
870 realCol[pos] = pos;
871 realInd[pos] = pos;
872 }
873
874 for (Index i = total_deflation ? 0 : 1; i < length; i++) {
875 const Index pi = permutation[length - (total_deflation ? i + 1 : i)];
876 const Index J = realCol[pi];
877
878 using std::swap;
879 // swap diagonal and first column entries:
880 swap(diag(i), diag(J));
881 if (i != 0 && J != 0) swap(col0(i), col0(J));
882
883 // change columns
884 if (m_compU)
885 m_naiveU.col(firstCol + i)
886 .segment(firstCol, length + 1)
887 .swap(m_naiveU.col(firstCol + J).segment(firstCol, length + 1));
888 else
889 m_naiveU.col(firstCol + i).segment(0, 2).swap(m_naiveU.col(firstCol + J).segment(0, 2));
890 if (m_compV)
891 m_naiveV.col(firstColW + i)
892 .segment(firstRowW, length)
893 .swap(m_naiveV.col(firstColW + J).segment(firstRowW, length));
894
895 // update real pos
896 const Index realI = realInd[i];
897 realCol[realI] = J;
898 realCol[pi] = i;
899 realInd[J] = realI;
900 realInd[i] = pi;
901 }
902 }
903
904 // condition 4.4
905 {
906 Index i = length - 1;
907 // Find last non-deflated entry.
908 while (i > 0 && (diag(i) < considerZero || numext::abs(col0(i)) < considerZero)) --i;
909
910 for (; i > 1; --i)
911 if ((diag(i) - diag(i - 1)) < epsilon_coarse) {
912 deflation44(firstCol, firstCol + shift, firstRowW, firstColW, i, i - 1, length);
913 }
914 }
915
916} // end deflation
917
918} // end namespace internal
919
920} // end namespace Eigen
921
922#endif // EIGEN_BDCSVD_IMPL_H
ComputationInfo
Definition Constants.h:455
@ Aligned
Definition Constants.h:243
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461