The worst-case GMRES for normal matrices
dc.contributor.author | Liesen, Jörg | |
dc.contributor.author | Tichý, Petr | |
dc.date.accessioned | 2021-12-17T10:05:31Z | |
dc.date.available | 2021-12-17T10:05:31Z | |
dc.date.issued | 2003-09-15 | |
dc.description.abstract | We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. We completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow to study the worst-case GMRES residual norm in dependence of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a constant factor of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an ``average'' residual norm, our results are of relevance beyond the worst case. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15491 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14264 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | GMRES | en |
dc.subject.other | evaluation of convergence | en |
dc.subject.other | ideal GMRES | en |
dc.subject.other | normal matrices | en |
dc.subject.other | min-max problem | en |
dc.title | The worst-case GMRES for normal matrices | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 2003, 27 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 65F10 Iterative methods for linear systems | en |
tub.subject.msc2000 | 65F15 Eigenvalues, eigenvectors | en |
tub.subject.msc2000 | 65F20 Overdetermined systems, pseudoinverses | en |
tub.subject.msc2000 | 15A06 Linear equations | en |
tub.subject.msc2000 | 15A09 Matrix inversion, generalized inverses | en |
tub.subject.msc2000 | 15A18 Eigenvalues, singular values, and eigenvectors | en |