diff options
author | Benoit Steiner <benoit.steiner.goog@gmail.com> | 2016-04-11 17:20:17 -0700 |
---|---|---|
committer | Benoit Steiner <benoit.steiner.goog@gmail.com> | 2016-04-11 17:20:17 -0700 |
commit | d6e596174d09446236b3f398d8ec39148c638ed9 (patch) | |
tree | ccb4116b05dc11d7931bac0129fd1394abe1e0b0 /Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h | |
parent | 3ca1ae2bb761d7738bcdad885639f422a6b7c914 (diff) | |
parent | 833efb39bfe4957934982112fe435ab30a0c3b4f (diff) |
Pull latest updates from upstream
Diffstat (limited to 'Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h')
-rw-r--r-- | Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h | 186 |
1 files changed, 109 insertions, 77 deletions
diff --git a/Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h b/Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h index 284e37f13..e45c272b4 100644 --- a/Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h +++ b/Eigen/src/IterativeLinearSolvers/IncompleteCholesky.h @@ -21,7 +21,7 @@ namespace Eigen { * References : C-J. Lin and J. J. Moré, Incomplete Cholesky Factorizations with * Limited memory, SIAM J. Sci. Comput. 21(1), pp. 24-45, 1999 * - * \tparam _MatrixType The type of the sparse matrix. It is advised to give a row-oriented sparse matrix + * \tparam Scalar the scalar type of the input matrices * \tparam _UpLo The triangular part that will be used for the computations. It can be Lower * or Upper. Default is Lower. * \tparam _OrderingType The ordering method to use, either AMDOrdering<> or NaturalOrdering<>. Default is AMDOrdering<int>, @@ -37,6 +37,8 @@ namespace Eigen { * and \f$ \beta \f$ be the minimum value of the diagonal. If \f$ \beta > 0 \f$ then, the factorization is directly performed * on the matrix B. Otherwise, the factorization is performed on the shifted matrix \f$ B + (\sigma+|\beta| I \f$ where * \f$ \sigma \f$ is the initial shift value as returned and set by setInitialShift() method. The default value is \f$ \sigma = 10^{-3} \f$. + * If the factorization fails, then the shift in doubled until it succeed or a maximum of ten attempts. If it still fails, as returned by + * the info() method, then you can either increase the initial shift, or better use another preconditioning technique. * */ template <typename Scalar, int _UpLo = Lower, typename _OrderingType = @@ -185,6 +187,10 @@ class IncompleteCholesky : public SparseSolverBase<IncompleteCholesky<Scalar,_Up inline void updateList(Ref<const VectorIx> colPtr, Ref<VectorIx> rowIdx, Ref<VectorSx> vals, const Index& col, const Index& jk, VectorIx& firstElt, VectorList& listCol); }; +// Based on the following paper: +// C-J. Lin and J. J. Moré, Incomplete Cholesky Factorizations with +// Limited memory, SIAM J. Sci. Comput. 21(1), pp. 24-45, 1999 +// http://ftp.mcs.anl.gov/pub/tech_reports/reports/P682.pdf template<typename Scalar, int _UpLo, typename OrderingType> template<typename _MatrixType> void IncompleteCholesky<Scalar,_UpLo, OrderingType>::factorize(const _MatrixType& mat) @@ -240,7 +246,7 @@ void IncompleteCholesky<Scalar,_UpLo, OrderingType>::factorize(const _MatrixType else m_scale(j) = 1; - // FIXME disable scaling if not needed, i.e., if it is roughly uniform? (this will make solve() faster) + // TODO disable scaling if not needed, i.e., if it is roughly uniform? (this will make solve() faster) // Scale and compute the shift for the matrix RealScalar mindiag = NumTraits<RealScalar>::highest(); @@ -251,96 +257,122 @@ void IncompleteCholesky<Scalar,_UpLo, OrderingType>::factorize(const _MatrixType eigen_internal_assert(rowIdx[colPtr[j]]==j && "IncompleteCholesky: only the lower triangular part must be stored"); mindiag = numext::mini(numext::real(vals[colPtr[j]]), mindiag); } + + FactorType L_save = m_L; RealScalar shift = 0; if(mindiag <= RealScalar(0.)) shift = m_initialShift - mindiag; - // Apply the shift to the diagonal elements of the matrix - for (Index j = 0; j < n; j++) - vals[colPtr[j]] += shift; - - // jki version of the Cholesky factorization - for (Index j=0; j < n; ++j) - { - // Left-looking factorization of the j-th column - // First, load the j-th column into col_vals - Scalar diag = vals[colPtr[j]]; // It is assumed that only the lower part is stored - col_nnz = 0; - for (Index i = colPtr[j] + 1; i < colPtr[j+1]; i++) - { - StorageIndex l = rowIdx[i]; - col_vals(col_nnz) = vals[i]; - col_irow(col_nnz) = l; - col_pattern(l) = col_nnz; - col_nnz++; - } + m_info = NumericalIssue; + + // Try to perform the incomplete factorization using the current shift + int iter = 0; + do + { + // Apply the shift to the diagonal elements of the matrix + for (Index j = 0; j < n; j++) + vals[colPtr[j]] += shift; + + // jki version of the Cholesky factorization + Index j=0; + for (; j < n; ++j) { - typename std::list<StorageIndex>::iterator k; - // Browse all previous columns that will update column j - for(k = listCol[j].begin(); k != listCol[j].end(); k++) + // Left-looking factorization of the j-th column + // First, load the j-th column into col_vals + Scalar diag = vals[colPtr[j]]; // It is assumed that only the lower part is stored + col_nnz = 0; + for (Index i = colPtr[j] + 1; i < colPtr[j+1]; i++) { - Index jk = firstElt(*k); // First element to use in the column - eigen_internal_assert(rowIdx[jk]==j); - Scalar v_j_jk = numext::conj(vals[jk]); - - jk += 1; - for (Index i = jk; i < colPtr[*k+1]; i++) + StorageIndex l = rowIdx[i]; + col_vals(col_nnz) = vals[i]; + col_irow(col_nnz) = l; + col_pattern(l) = col_nnz; + col_nnz++; + } + { + typename std::list<StorageIndex>::iterator k; + // Browse all previous columns that will update column j + for(k = listCol[j].begin(); k != listCol[j].end(); k++) { - StorageIndex l = rowIdx[i]; - if(col_pattern[l]<0) + Index jk = firstElt(*k); // First element to use in the column + eigen_internal_assert(rowIdx[jk]==j); + Scalar v_j_jk = numext::conj(vals[jk]); + + jk += 1; + for (Index i = jk; i < colPtr[*k+1]; i++) { - col_vals(col_nnz) = vals[i] * v_j_jk; - col_irow[col_nnz] = l; - col_pattern(l) = col_nnz; - col_nnz++; + StorageIndex l = rowIdx[i]; + if(col_pattern[l]<0) + { + col_vals(col_nnz) = vals[i] * v_j_jk; + col_irow[col_nnz] = l; + col_pattern(l) = col_nnz; + col_nnz++; + } + else + col_vals(col_pattern[l]) -= vals[i] * v_j_jk; } - else - col_vals(col_pattern[l]) -= vals[i] * v_j_jk; + updateList(colPtr,rowIdx,vals, *k, jk, firstElt, listCol); } - updateList(colPtr,rowIdx,vals, *k, jk, firstElt, listCol); } + + // Scale the current column + if(numext::real(diag) <= 0) + { + if(++iter>=10) + return; + + // increase shift + shift = numext::maxi(m_initialShift,RealScalar(2)*shift); + // restore m_L, col_pattern, and listCol + vals = Map<const VectorSx>(L_save.valuePtr(), nnz); + rowIdx = Map<const VectorIx>(L_save.innerIndexPtr(), nnz); + colPtr = Map<const VectorIx>(L_save.outerIndexPtr(), n+1); + col_pattern.fill(-1); + for(Index i=0; i<n; ++i) + listCol[i].clear(); + + break; + } + + RealScalar rdiag = sqrt(numext::real(diag)); + vals[colPtr[j]] = rdiag; + for (Index k = 0; k<col_nnz; ++k) + { + Index i = col_irow[k]; + //Scale + col_vals(k) /= rdiag; + //Update the remaining diagonals with col_vals + vals[colPtr[i]] -= numext::abs2(col_vals(k)); + } + // Select the largest p elements + // p is the original number of elements in the column (without the diagonal) + Index p = colPtr[j+1] - colPtr[j] - 1 ; + Ref<VectorSx> cvals = col_vals.head(col_nnz); + Ref<VectorIx> cirow = col_irow.head(col_nnz); + internal::QuickSplit(cvals,cirow, p); + // Insert the largest p elements in the matrix + Index cpt = 0; + for (Index i = colPtr[j]+1; i < colPtr[j+1]; i++) + { + vals[i] = col_vals(cpt); + rowIdx[i] = col_irow(cpt); + // restore col_pattern: + col_pattern(col_irow(cpt)) = -1; + cpt++; + } + // Get the first smallest row index and put it after the diagonal element + Index jk = colPtr(j)+1; + updateList(colPtr,rowIdx,vals,j,jk,firstElt,listCol); } - - // Scale the current column - if(numext::real(diag) <= 0) - { - m_info = NumericalIssue; - return; - } - - RealScalar rdiag = sqrt(numext::real(diag)); - vals[colPtr[j]] = rdiag; - for (Index k = 0; k<col_nnz; ++k) - { - Index i = col_irow[k]; - //Scale - col_vals(k) /= rdiag; - //Update the remaining diagonals with col_vals - vals[colPtr[i]] -= numext::abs2(col_vals(k)); - } - // Select the largest p elements - // p is the original number of elements in the column (without the diagonal) - Index p = colPtr[j+1] - colPtr[j] - 1 ; - Ref<VectorSx> cvals = col_vals.head(col_nnz); - Ref<VectorIx> cirow = col_irow.head(col_nnz); - internal::QuickSplit(cvals,cirow, p); - // Insert the largest p elements in the matrix - Index cpt = 0; - for (Index i = colPtr[j]+1; i < colPtr[j+1]; i++) + + if(j==n) { - vals[i] = col_vals(cpt); - rowIdx[i] = col_irow(cpt); - // restore col_pattern: - col_pattern(col_irow(cpt)) = -1; - cpt++; + m_factorizationIsOk = true; + m_info = Success; } - // Get the first smallest row index and put it after the diagonal element - Index jk = colPtr(j)+1; - updateList(colPtr,rowIdx,vals,j,jk,firstElt,listCol); - } - m_factorizationIsOk = true; - m_info = Success; + } while(m_info!=Success); } template<typename Scalar, int _UpLo, typename OrderingType> |