479
2012-06-22 09:56:30 +0000
Adjust the max iteration count wrt arithmetic precision
2019-12-04 11:44:19 +0000
1
1
1
Unclassified
Eigen
Eigenvalues
unspecified
All
All
RESOLVED
FIXED
Normal
Unknown
---
387
1
gael.guennebaud
eigen.nobody
desire.nuentsa_wakam
gael.guennebaud
jacob.benoit.1
jitseniesen
oldest_to_newest
1934
0
gael.guennebaud
2012-06-22 09:56:30 +0000
Currently, the maximal number of iterations allowed in the Schur decomposition is fixed to 40. While this is good for double, this is clearly not enough for floating point numbers with much higher precision. The same situation probably arises in other iterative algorithms.
I see several options:
1 - find a way to automatically compute a max number of iterations based on NumTraits<Scalar>::epsilon()
2 - let the user adjust the max number of iterations
3 - find another way to detect no convergence
1962
1
desire.nuentsa_wakam
2012-07-09 11:15:27 +0000
This parameter is really problem-dependent. The user should have the possibility to adjust it. For the default value, we can follow the approach in LAPACK and EISPACK where the maximum number of iterations is 30 * size_of_the_matrix;
For the point 3, iterative methods for linear systems stops when itmax is reached or when the norm of the current residual is greater than the norm of the right-hand side multiplied by some predefined constant dtol.
1977
2
desire.nuentsa_wakam
2012-07-16 13:09:17 +0000
https://bitbucket.org/eigen/eigen/changeset/0b631af56bad/
changeset: 0b631af56bad
branch: 3.1
user: dnuentsa
date: 2012-07-16 11:31:59
summary: bug 479 : Adjust max iterations count wrt matrix size
1978
3
jitseniesen
2012-07-16 17:10:36 +0000
I thought that Eispack has a maximum of 30 iterations for reducing one sub-diagonal element to zero, and that is also what Eigen used. However, I had another look at the old Fortran code and I see now that it has a maximum of 30 * (number of rows) iterations for the whole reduction to triangular form. Currently, after the change, Eigen allows for 30 * (number of rows) iterations for reducing one sub-diagonal element. If that is indeed the intention - and I don't see a problem with it - then the documentation for m_maxIterations should probably be updated.
1979
4
desire.nuentsa_wakam
2012-07-16 18:21:44 +0000
Oooh No. I didn't see that iter is set to zero at the convergence of one eigenvalue. I think 30 * (number of rows) is very large for one single sub-diagonal. Can we keep 30 iterations to remove one sub-diagonal as it was done before and 30 * (number of rows) iterations for the whole reduction ?
1981
5
gael.guennebaud
2012-07-17 12:55:54 +0000
I think we should do as Lapack, and not limit a single sub-diagonal removal to 30 iterations because 1- the complexity is clearly not constant for all sub-diagonals, and 2- this strategy has been proved to fail on some examples.
1996
6
jitseniesen
2012-07-23 15:32:01 +0000
Yesterday I changed the max number of iterations used to the same strategy as Lapack/Eispack; see changeset 24a5443ecde9 for the dev branch and changeset 23f17dd6901e for the 3.1 branch.
I think we still need to give the user the opportunity to change this, for instance when using very high precision numbers.
2003
7
jitseniesen
2012-07-24 16:24:08 +0000
Changeset 58c321490416 (only in the dev branch) allows the user to specify the maximum number of iterations using an extra argument of the compute() function: eigensolver.compute(A, true, 100) computes the eigenvalues and eigenvectors of A using at most 100 iterations.
In hindsight, I'm wondering whether I should have implemented a different API, like: eigensolver.setMaxIterations(100).compute(A) . This makes the user code perhaps less cryptic. A disadvantage would be that the EigenSolver object gets an additional member variable, to store the maximum number of iterations, making the object occupy slightly more memory.
2004
8
gael.guennebaud
2012-07-24 18:36:49 +0000
I prefer the setMaxIterations() API. It is consistent with the sparse solvers, and permits to configure a solver and then pass it to a generic algorithm.
8923
9
eigen.nobody
2019-12-04 11:44:19 +0000
-- GitLab Migration Automatic Message --
This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.
You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/479.