diff options
author | Christoph Hertzberg <chtz@informatik.uni-bremen.de> | 2015-07-26 20:30:30 +0200 |
---|---|---|
committer | Christoph Hertzberg <chtz@informatik.uni-bremen.de> | 2015-07-26 20:30:30 +0200 |
commit | a44d022cafce5b1f8e452a22d43bd23265438ca6 (patch) | |
tree | 7ebe6a90bdf3e4aa70554e8c8beccc3443e1fbb7 | |
parent | 4b3052c54d14f486c2665530f06cdeff636169e4 (diff) |
bug #792: SparseLU::factorize failed for structurally rank deficient matrices
-rw-r--r-- | Eigen/src/SparseLU/SparseLU_pivotL.h | 11 | ||||
-rw-r--r-- | test/sparse_solver.h | 20 | ||||
-rw-r--r-- | test/sparselu.cpp | 4 |
3 files changed, 27 insertions, 8 deletions
diff --git a/Eigen/src/SparseLU/SparseLU_pivotL.h b/Eigen/src/SparseLU/SparseLU_pivotL.h index 562128b69..a86dac93f 100644 --- a/Eigen/src/SparseLU/SparseLU_pivotL.h +++ b/Eigen/src/SparseLU/SparseLU_pivotL.h @@ -71,7 +71,7 @@ Index SparseLUImpl<Scalar,StorageIndex>::pivotL(const Index jcol, const RealScal // Determine the largest abs numerical value for partial pivoting Index diagind = iperm_c(jcol); // diagonal index - RealScalar pivmax = 0.0; + RealScalar pivmax(-1.0); Index pivptr = nsupc; Index diag = emptyIdxLU; RealScalar rtemp; @@ -87,8 +87,9 @@ Index SparseLUImpl<Scalar,StorageIndex>::pivotL(const Index jcol, const RealScal } // Test for singularity - if ( pivmax == 0.0 ) { - pivrow = lsub_ptr[pivptr]; + if ( pivmax <= RealScalar(0.0) ) { + // if pivmax == -1, the column is structurally empty, otherwise it is only numerically zero + pivrow = pivmax < RealScalar(0.0) ? diagind : lsub_ptr[pivptr]; perm_r(pivrow) = StorageIndex(jcol); return (jcol+1); } @@ -104,13 +105,13 @@ Index SparseLUImpl<Scalar,StorageIndex>::pivotL(const Index jcol, const RealScal // Diagonal element exists using std::abs; rtemp = abs(lu_col_ptr[diag]); - if (rtemp != 0.0 && rtemp >= thresh) pivptr = diag; + if (rtemp != RealScalar(0.0) && rtemp >= thresh) pivptr = diag; } pivrow = lsub_ptr[pivptr]; } // Record pivot row - perm_r(pivrow) = StorageIndex(jcol); + perm_r(pivrow) = StorageIndex(jcol); // Interchange row subscripts if (pivptr != nsupc ) { diff --git a/test/sparse_solver.h b/test/sparse_solver.h index 64f6ac4fe..90362ca0f 100644 --- a/test/sparse_solver.h +++ b/test/sparse_solver.h @@ -332,7 +332,18 @@ Index generate_sparse_square_problem(Solver&, typename Solver::MatrixType& A, De return size; } -template<typename Solver> void check_sparse_square_solving(Solver& solver, int maxSize = 300, int maxRealWorldSize = 100000) + +struct prune_column { + Index m_col; + prune_column(Index col) : m_col(col) {} + template<class Scalar> + bool operator()(Index, Index col, const Scalar&) const { + return col != m_col; + } +}; + + +template<typename Solver> void check_sparse_square_solving(Solver& solver, int maxSize = 300, int maxRealWorldSize = 100000, bool checkDeficient = false) { typedef typename Solver::MatrixType Mat; typedef typename Mat::Scalar Scalar; @@ -364,6 +375,13 @@ template<typename Solver> void check_sparse_square_solving(Solver& solver, int m b = DenseVector::Zero(size); check_sparse_solving(solver, A, b, dA, b); } + // regression test for Bug 792 (structurally rank deficient matrices): + if(checkDeficient && size>1) { + Index col = internal::random<int>(0,size-1); + A.prune(prune_column(col)); + solver.compute(A); + VERIFY_IS_EQUAL(solver.info(), NumericalIssue); + } } // First, get the folder diff --git a/test/sparselu.cpp b/test/sparselu.cpp index 231c857ad..c725847d8 100644 --- a/test/sparselu.cpp +++ b/test/sparselu.cpp @@ -42,8 +42,8 @@ template<typename T> void test_sparselu_T() SparseLU<SparseMatrix<T, ColMajor, long int>, NaturalOrdering<long int> > sparselu_natural; check_sparse_square_solving(sparselu_colamd); - check_sparse_square_solving(sparselu_amd, 300, 2000); - check_sparse_square_solving(sparselu_natural, 300, 2000); + check_sparse_square_solving(sparselu_amd, 300, 2000, !true); // FIXME AMD ordering fails for structurally deficient matrices! + check_sparse_square_solving(sparselu_natural, 300, 2000, true); check_sparse_square_abs_determinant(sparselu_colamd); check_sparse_square_abs_determinant(sparselu_amd); |