25#include "./InternalHeaderCheck.h"
28#include "BDCSVDImpl.h"
32template <
typename MatrixType_,
int Options>
37template <
typename MatrixType_,
int Options>
38struct traits<BDCSVD<MatrixType_, Options> > : svd_traits<MatrixType_, Options> {
39 using MatrixType = MatrixType_;
75template <
typename MatrixType_,
int Options_>
86 using MatrixType = MatrixType_;
87 using Scalar =
typename Base::Scalar;
88 using RealScalar =
typename Base::RealScalar;
89 using Literal =
typename NumTraits<RealScalar>::Literal;
93 QRDecomposition = internal::get_qr_preconditioner(Options),
94 ComputationOptions = internal::get_computation_options(Options),
95 RowsAtCompileTime = Base::RowsAtCompileTime,
96 ColsAtCompileTime = Base::ColsAtCompileTime,
97 DiagSizeAtCompileTime = Base::DiagSizeAtCompileTime,
98 MaxRowsAtCompileTime = Base::MaxRowsAtCompileTime,
99 MaxColsAtCompileTime = Base::MaxColsAtCompileTime,
100 MaxDiagSizeAtCompileTime = Base::MaxDiagSizeAtCompileTime,
101 MatrixOptions = Base::MatrixOptions
104 using MatrixUType =
typename Base::MatrixUType;
105 using MatrixVType =
typename Base::MatrixVType;
106 using SingularValuesType =
typename Base::SingularValuesType;
129 BDCSVD(Index rows, Index cols) : m_numIters(0) { allocate(rows, cols, internal::get_computation_options(Options)); }
147 EIGEN_DEPRECATED_WITH_REASON(
"Options should be specified using the class template parameter.")
148 BDCSVD(Index rows, Index cols,
unsigned int computationOptions) : m_numIters(0) {
149 internal::check_svd_options_assertions<MatrixType, Options>(computationOptions, rows, cols);
150 allocate(rows, cols, computationOptions);
158 template <
typename Derived>
160 compute_impl(matrix, internal::get_computation_options(Options));
172 template <
typename DerivedD,
typename DerivedE>
174 compute_bidiagonal_impl(diagonal, superdiagonal, internal::get_computation_options(Options));
189 template <
typename Derived>
190 EIGEN_DEPRECATED_WITH_REASON(
"Options should be specified using the class template parameter.")
191 BDCSVD(const
MatrixBase<Derived>& matrix,
unsigned int computationOptions) : m_numIters(0) {
192 internal::check_svd_options_assertions<MatrixType, Options>(computationOptions, matrix.rows(), matrix.cols());
193 compute_impl(matrix, computationOptions);
201 template <
typename Derived>
203 return compute_impl(matrix, m_computationOptions);
215 template <
typename Derived>
216 EIGEN_DEPRECATED_WITH_REASON(
"Options should be specified using the class template parameter.")
218 internal::check_svd_options_assertions<MatrixType, Options>(computationOptions, matrix.rows(), matrix.cols());
219 return compute_impl(matrix, computationOptions);
231 template <
typename DerivedD,
typename DerivedE>
233 return compute_bidiagonal_impl(diagonal, superdiagonal, m_computationOptions);
236 void setSwitchSize(
int s) {
237 eigen_assert(s >= 3 &&
"BDCSVD the size of the algo switch has to be at least 3.");
238 if (s == m_impl.algoSwap())
return;
239 m_impl.setAlgoSwap(s);
241 m_isAllocated =
false;
245 template <
typename Derived>
246 BDCSVD& compute_impl(
const MatrixBase<Derived>& matrix,
unsigned int computationOptions);
247 template <
typename Derived>
248 BDCSVD& compute_impl(
const MatrixBase<Derived>& matrix,
unsigned int computationOptions, internal::true_type);
249 template <
typename Derived>
250 BDCSVD& compute_impl(
const MatrixBase<Derived>& matrix,
unsigned int computationOptions, internal::false_type);
251 template <
typename DerivedD,
typename DerivedE>
252 BDCSVD& compute_bidiagonal_impl(
const MatrixBase<DerivedD>& diagonal,
const MatrixBase<DerivedE>& superdiagonal,
253 unsigned int computationOptions);
254 template <
typename HouseholderU,
typename HouseholderV,
typename NaiveU,
typename NaiveV>
255 void copyUV(
const HouseholderU& householderU,
const HouseholderV& householderV,
const NaiveU& naiveU,
256 const NaiveV& naivev);
259 void allocate(Index rows, Index cols,
unsigned int computationOptions);
260 void allocate_small(Index rows, Index cols,
unsigned int computationOptions);
261 internal::bdcsvd_impl<RealScalar> m_impl;
262 bool m_isTranspose =
false;
263 bool m_useQrDecomp =
false;
267 HouseholderQR<MatrixX> qrDecomp;
268 internal::UpperBidiagonalization<MatrixX> bid;
269 MatrixX copyWorkspace;
270 MatrixX reducedTriangle;
273 Matrix<Scalar, 1, Dynamic, RowMajor> m_householderWorkspace;
275 using Base::m_computationOptions;
276 using Base::m_computeThinU;
277 using Base::m_computeThinV;
279 using Base::m_isAllocated;
280 using Base::m_isInitialized;
281 using Base::m_matrixU;
282 using Base::m_matrixV;
283 using Base::m_nonzeroSingularValues;
284 using Base::m_singularValues;
291template <
typename MatrixType,
int Options>
292void BDCSVD<MatrixType, Options>::allocate(Index rows, Index cols,
unsigned int computationOptions) {
293 if (Base::allocate(rows, cols, computationOptions))
return;
295 if (cols < m_impl.algoSwap())
296 smallSvd.allocate(rows, cols, internal::get_computation_options(Options | computationOptions));
298 m_isTranspose = (cols > rows);
300 bool compU = computeV();
301 bool compV = computeU();
302 if (m_isTranspose) std::swap(compU, compV);
304 m_impl.allocate(diagSize(), compU, compV);
310 constexpr Index kMinAspectRatio = 4;
311 constexpr bool disableQrDecomp =
static_cast<int>(QRDecomposition) ==
static_cast<int>(
DisableQRDecomposition);
312 m_useQrDecomp = !disableQrDecomp && ((rows / kMinAspectRatio >= cols) || (cols / kMinAspectRatio >= rows));
315 reducedTriangle =
MatrixX(diagSize(), diagSize());
318 copyWorkspace =
MatrixX(m_isTranspose ? cols : rows, m_isTranspose ? rows : cols);
319 bid = internal::UpperBidiagonalization<MatrixX>(m_useQrDecomp ? diagSize() : copyWorkspace.rows(),
320 m_useQrDecomp ? diagSize() : copyWorkspace.cols());
323template <
typename MatrixType,
int Options>
324void BDCSVD<MatrixType, Options>::allocate_small(Index rows, Index cols,
unsigned int computationOptions) {
325 if (Base::allocate(rows, cols, computationOptions))
return;
327 smallSvd.allocate(rows, cols, internal::get_computation_options(Options | computationOptions));
328 m_isTranspose = (cols > rows);
331template <
typename MatrixType,
int Options>
332template <
typename Derived>
334 unsigned int computationOptions) {
335 EIGEN_STATIC_ASSERT_SAME_MATRIX_SIZE(Derived, MatrixType);
336 EIGEN_STATIC_ASSERT((std::is_same<typename Derived::Scalar, typename MatrixType::Scalar>::value),
337 Input matrix must have the same Scalar type as the
BDCSVD object.);
340 using AlwaysUseSmallSvd = internal::bool_constant<(MaxColsAtCompileTime != Dynamic && MaxColsAtCompileTime < 3)>;
341 return compute_impl(matrix, computationOptions, AlwaysUseSmallSvd());
344template <
typename MatrixType,
int Options>
345template <
typename Derived>
348 allocate_small(matrix.rows(), matrix.cols(), computationOptions);
350 smallSvd.compute(matrix);
351 m_isInitialized =
true;
352 m_info = smallSvd.info();
354 if (computeU()) m_matrixU = smallSvd.matrixU();
355 if (computeV()) m_matrixV = smallSvd.matrixV();
356 m_singularValues = smallSvd.singularValues();
357 m_nonzeroSingularValues = smallSvd.nonzeroSingularValues();
362template <
typename MatrixType,
int Options>
363template <
typename Derived>
365 const MatrixBase<Derived>& matrix,
unsigned int computationOptions, internal::false_type) {
366 allocate(matrix.rows(), matrix.cols(), computationOptions);
368 const RealScalar considerZero = (std::numeric_limits<RealScalar>::min)();
371 if (matrix.cols() < m_impl.algoSwap()) {
372 smallSvd.compute(matrix);
373 m_isInitialized =
true;
374 m_info = smallSvd.info();
376 if (computeU()) m_matrixU = smallSvd.matrixU();
377 if (computeV()) m_matrixV = smallSvd.matrixV();
378 m_singularValues = smallSvd.singularValues();
379 m_nonzeroSingularValues = smallSvd.nonzeroSingularValues();
387 const RealScalar maxCoeff = internal::safe_scaling<RealScalar>::max_abs_component(matrix.derived());
388 if (!(numext::isfinite)(maxCoeff)) {
389 m_isInitialized =
true;
394 const auto factors = m_isTranspose
395 ? internal::safe_scaling<RealScalar>::scale_to(copyWorkspace, matrix.adjoint(), maxCoeff)
396 : internal::safe_scaling<RealScalar>::scale_to(copyWorkspace, matrix, maxCoeff);
403 qrDecomp.compute(copyWorkspace);
404 reducedTriangle = qrDecomp.matrixQR().topRows(diagSize());
405 reducedTriangle.template triangularView<StrictlyLower>().setZero();
406 bid.compute(reducedTriangle);
408 bid.compute(copyWorkspace);
412 m_impl.naiveU().setZero();
413 m_impl.naiveV().setZero();
419 m_impl.computed().setZero();
420 m_impl.computed().topRows(diagSize()).diagonal() = bid.bidiagonal().diagonal();
421 m_impl.computed().topRows(diagSize()).
template diagonal<-1>() = bid.bidiagonal().diagonal(1);
422 m_impl.splitNegligibleSuperdiagonal(diagSize());
423 m_impl.divide(0, diagSize() - 1, 0, 0, 0);
424 m_info = m_impl.info();
425 m_numIters = m_impl.numIters();
427 m_isInitialized =
true;
432 for (
int i = 0; i < diagSize(); i++) {
433 RealScalar a = numext::abs(m_impl.computed().coeff(i, i));
434 m_singularValues.coeffRef(i) = a;
435 if (a < considerZero) {
436 m_nonzeroSingularValues = i;
437 m_singularValues.tail(diagSize() - i - 1).setZero();
439 }
else if (i == diagSize() - 1) {
440 m_nonzeroSingularValues = i + 1;
445 internal::safe_scaling<RealScalar>::unscale_in_place(m_singularValues, maxCoeff, factors);
449 copyUV(bid.householderV(), bid.householderU(), m_impl.naiveV(), m_impl.naiveU());
451 copyUV(bid.householderU(), bid.householderV(), m_impl.naiveU(), m_impl.naiveV());
454 if (m_isTranspose && computeV())
455 m_matrixV.applyOnTheLeft(qrDecomp.householderQ());
456 else if (!m_isTranspose && computeU())
457 m_matrixU.applyOnTheLeft(qrDecomp.householderQ());
460 m_isInitialized =
true;
464template <
typename MatrixType,
int Options>
465template <
typename HouseholderU,
typename HouseholderV,
typename NaiveU,
typename NaiveV>
466EIGEN_DONT_INLINE
void BDCSVD<MatrixType, Options>::copyUV(
const HouseholderU& householderU,
467 const HouseholderV& householderV,
const NaiveU& naiveU,
468 const NaiveV& naiveV) {
474 Index Ucols = m_computeThinU ? diagSize() : rows();
475 m_matrixU = MatrixX::Identity(rows(), Ucols);
476 m_matrixU.topLeftCorner(diagSize(), diagSize()) =
477 naiveV.topLeftCorner(diagSize(), diagSize()).template cast<Scalar>();
479 auto sub = m_matrixU.topLeftCorner(householderU.cols(), diagSize());
480 householderU.applyThisOnTheLeft(sub, m_householderWorkspace);
482 householderU.applyThisOnTheLeft(m_matrixU, m_householderWorkspace);
486 Index Vcols = m_computeThinV ? diagSize() : cols();
487 m_matrixV = MatrixX::Identity(cols(), Vcols);
488 m_matrixV.topLeftCorner(diagSize(), diagSize()) =
489 naiveU.topLeftCorner(diagSize(), diagSize()).template cast<Scalar>();
491 auto sub = m_matrixV.topLeftCorner(householderV.cols(), diagSize());
492 householderV.applyThisOnTheLeft(sub, m_householderWorkspace);
494 householderV.applyThisOnTheLeft(m_matrixV, m_householderWorkspace);
499template <
typename MatrixType,
int Options>
500template <
typename DerivedD,
typename DerivedE>
503 EIGEN_STATIC_ASSERT(DerivedD::IsVectorAtCompileTime, THIS_METHOD_IS_ONLY_FOR_VECTORS);
504 EIGEN_STATIC_ASSERT(DerivedE::IsVectorAtCompileTime, THIS_METHOD_IS_ONLY_FOR_VECTORS);
505 EIGEN_STATIC_ASSERT((NumTraits<typename DerivedD::Scalar>::IsComplex == 0),
506 THIS_FUNCTION_IS_NOT_FOR_COMPLEX_VALUED_MATRICES);
507 EIGEN_STATIC_ASSERT((NumTraits<typename DerivedE::Scalar>::IsComplex == 0),
508 THIS_FUNCTION_IS_NOT_FOR_COMPLEX_VALUED_MATRICES);
510 const Index n = diagonal.size();
511 eigen_assert((n == 0 || superdiagonal.size() == n - 1) &&
"superdiagonal must have size diagonal.size() - 1");
514 allocate(n, n, computationOptions);
517 m_isInitialized =
true;
519 m_nonzeroSingularValues = 0;
524 const RealScalar diagScale = internal::safe_scaling<RealScalar>::recover_flushed_max_coeff(
525 diagonal.derived(), diagonal.cwiseAbs().template maxCoeff<PropagateNaN>());
526 const RealScalar superdiagScale =
527 n > 1 ? internal::safe_scaling<RealScalar>::recover_flushed_max_coeff(
528 superdiagonal.derived(), superdiagonal.cwiseAbs().template maxCoeff<PropagateNaN>())
530 const RealScalar maxCoeff = internal::max_preserving_subnormals(diagScale, superdiagScale);
531 if (!(numext::isfinite)(maxCoeff)) {
532 m_isInitialized =
true;
537 const RealScalar considerZero = (std::numeric_limits<RealScalar>::min)();
539 if (n < m_impl.algoSwap()) {
541 MatrixX B = MatrixX::Zero(n, n);
542 auto diagonalDest = B.diagonal();
544 internal::safe_scaling<RealScalar>::scale_to(diagonalDest, diagonal.template cast<Scalar>(), maxCoeff);
546 auto superdiagonalDest = B.diagonal(1);
547 internal::safe_scaling<RealScalar>::scale_to(superdiagonalDest, superdiagonal.template cast<Scalar>(), maxCoeff,
551 m_isInitialized =
true;
552 m_info = smallSvd.info();
554 internal::safe_scaling<RealScalar>::unscale_to(m_singularValues, smallSvd.singularValues(), maxCoeff, factors);
555 m_nonzeroSingularValues = smallSvd.nonzeroSingularValues();
556 if (computeU()) m_matrixU = smallSvd.matrixU();
557 if (computeV()) m_matrixV = smallSvd.matrixV();
564 m_impl.naiveU().setZero();
565 m_impl.naiveV().setZero();
566 m_impl.computed().setZero();
567 auto diagonalDest = m_impl.computed().diagonal();
569 internal::safe_scaling<RealScalar>::scale_to(diagonalDest, diagonal.template cast<RealScalar>(), maxCoeff);
571 auto superdiagonalDest = m_impl.computed().template diagonal<-1>().head(n - 1);
572 internal::safe_scaling<RealScalar>::scale_to(superdiagonalDest, superdiagonal.template cast<RealScalar>(), maxCoeff,
576 m_isTranspose =
false;
579 m_impl.splitNegligibleSuperdiagonal(n);
580 m_impl.divide(0, n - 1, 0, 0, 0);
581 m_info = m_impl.info();
582 m_numIters = m_impl.numIters();
584 m_isInitialized =
true;
589 for (
int i = 0; i < diagSize(); i++) {
590 RealScalar a = numext::abs(m_impl.computed().coeff(i, i));
591 m_singularValues.coeffRef(i) = a;
592 if (a < considerZero) {
593 m_nonzeroSingularValues = i;
594 m_singularValues.tail(diagSize() - i - 1).setZero();
596 }
else if (i == diagSize() - 1) {
597 m_nonzeroSingularValues = i + 1;
602 internal::safe_scaling<RealScalar>::unscale_in_place(m_singularValues, maxCoeff, factors);
608 Index Ucols = m_computeThinU ? diagSize() : rows();
609 m_matrixU = MatrixX::Identity(rows(), Ucols);
610 m_matrixU.topLeftCorner(diagSize(), diagSize()) =
611 m_impl.naiveV().template cast<Scalar>().topLeftCorner(diagSize(), diagSize());
614 Index Vcols = m_computeThinV ? diagSize() : cols();
615 m_matrixV = MatrixX::Identity(cols(), Vcols);
616 m_matrixV.topLeftCorner(diagSize(), diagSize()) =
617 m_impl.naiveU().template cast<Scalar>().topLeftCorner(diagSize(), diagSize());
620 m_isInitialized =
true;
630template <
typename Derived>
631template <
int Options>
642template <
typename Derived>
643template <
int Options>
645 unsigned int computationOptions)
const {
General-purpose arrays with easy API for coefficient-wise operations.
Definition Array.h:55
class Bidiagonal Divide and Conquer SVD
Definition BDCSVD.h:76
BDCSVD(const MatrixBase< DerivedD > &diagonal, const MatrixBase< DerivedE > &superdiagonal)
Constructor performing the SVD of an upper bidiagonal matrix given its diagonal and superdiagonal.
Definition BDCSVD.h:173
BDCSVD()
Default Constructor.
Definition BDCSVD.h:121
BDCSVD(const MatrixBase< Derived > &matrix)
Constructor performing the decomposition of given matrix, using the custom options specified with the...
Definition BDCSVD.h:159
BDCSVD & compute(const MatrixBase< Derived > &matrix)
Method performing the decomposition of given matrix. Computes Thin/Full unitaries U/V if specified us...
Definition BDCSVD.h:202
BDCSVD & compute(const MatrixBase< DerivedD > &diagonal, const MatrixBase< DerivedE > &superdiagonal)
Compute the SVD of an upper bidiagonal matrix given its diagonal and superdiagonal.
Definition BDCSVD.h:232
BDCSVD(Index rows, Index cols)
Default Constructor with memory preallocation.
Definition BDCSVD.h:129
Householder QR decomposition of a matrix.
Definition HouseholderQR.h:77
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
A matrix or vector expression mapping an existing expression.
Definition Ref.h:261
bool computeV() const
Definition SVDBase.h:277
bool computeU() const
Definition SVDBase.h:275
SVDBase()
Definition SVDBase.h:350
@ DisableQRDecomposition
Definition Constants.h:434
@ PreconditionSquareMatrix
Definition Constants.h:437
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Matrix< Type, Dynamic, Dynamic > MatrixX
Dynamic×Dynamic matrix of type Type.
Definition Matrix.h:524
Eigen::Index Index
The interface type of indices.
Definition EigenBase.h:44