This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 926 - Patch: Improved GMRES Implementation
Summary: Patch: Improved GMRES Implementation
Status: NEW
Alias: None
Product: Eigen
Classification: Unclassified
Component: Unsupported modules (show other bugs)
Version: 3.2
Hardware: All All
: Normal Unknown
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-01-03 16:56 UTC by ettersi
Modified: 2019-12-04 14:02 UTC (History)
3 users (show)



Attachments
Improved GMRES Implementation (25.68 KB, patch)
2015-01-03 16:56 UTC, ettersi
no flags Details | Diff

Description ettersi 2015-01-03 16:56:27 UTC
Created attachment 513 [details]
Improved GMRES Implementation

Improvements include:
 - Termination based on relative error quantity (like e.g. ConjugateGradient)
 - Document termination criterion
 - Properly set info() and error() fields after call to solve()
 - Rename set_restart() -> setRestart() and get_restart() -> restart() to follow the Eigen naming convention
 - More verbous in-code documentation
 - Use x = 0 as default initial guess as documented
 - Avoid excessive memory use if user specifies large restart parameter
Comment 1 Gael Guennebaud 2015-01-15 22:52:37 UTC
Thank you for the patch.

However, it is based on eigen3.2, while several fixes have already been made in the devel branch. In particular, the following changeset should be considered and merged:

https://bitbucket.org/eigen/eigen/commits/47eb59a2ea6ea

Moreover, the calls to std::min should be protected with parenthesis: (std::min)(...)
Comment 2 ettersi 2015-01-16 10:18:14 UTC
The differences between 3.2 and the default branches are:
 - Some changes to gmres() (i.e., the actual algorithm) by Kolja Brix: 
    - Convergence check based on residual
    - Bug fixes
 - Some changes to how this algorithm is called by Gael Guennebaud

(You're invited to verify the above, I am not yet much experienced with version control.) 

Also my implementation uses a residual-based convergence check, and the bug fixes should be obsolete because I largely reimplemented the gmres() function. The changes by Kolja are thus covered. 

Merging your changes should be fairly easy. I can do it sometime if there is hope that these changes will make it into the library.
Comment 3 Gael Guennebaud 2015-01-17 22:27:13 UTC
Alright, so it seems that one of the main difference is that one version use the following threshold:

tol_error * precond.solve(rhs - mat*x).norm()

while yours is:

tol_error * precond.solve(rhs).norm()

To find which is one is correct, could you elaborate on what "w(k)" is supposed to represent when being compared to the threshold for convergence? Is it supposed to be equal to preconditioned residual precond.solve(rhs - mat*x).norm() where x is the current solution?
Comment 4 ettersi 2015-01-18 08:45:24 UTC
Exactly. A detailed explanation is given in Saad's "Iterative Methods for Sparse Linear Systems", Section 6.5.3, and the claim is explicitly formulated in Proposition 6.9 (3.). The w in the code equals g in the notation of Saad.
Comment 5 Nobody 2019-12-04 14:02:04 UTC
-- 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/926.

Note You need to log in before you can comment on or make changes to this bug.