On Worst-Case GMRES, ideal GMRES, and the Polynomial Numerical Hull of a Jordan block

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F07%3A00092720" target="_blank" >RIV/67985807:_____/07:00092720 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On Worst-Case GMRES, ideal GMRES, and the Polynomial Numerical Hull of a Jordan block

Original language description

When solving a linear algebraic system Ax = b with GMRES, the relative residual norm at each step is bounded from above by the so-called ideal GMRES approximation. This worst-case bound is sharp (i.e. it is attainable by the relative GMRES residual norm)in case of a normal matrix A , but it need not characterize the worst-case GMRES behavior if A is nonnormal. Characterizing the tightness of this bound for nonnormal matrices A represents an important and largely open problem in the convergence analysisof Krylov subspace methods. In this paper we address this problem in case A is a single Jordan block. We study the relation between ideal and worst-case GMRES as well as the problem of estimating the ideal GMRES approximation. Furthermore, we prove newresults about the radii of the polynomial numerical hulls of Jordan blocks. Using these, we discuss the closeness of the lower bound on the ideal GMRES approximation that is derived from the radius of the polynomial numerical hull.

Czech name

O worst-case GMRES, ideální GMRES a o polynomiálním numerickém obalu Jordanova bloku

Czech description

Řešíme-li soustavu lineárních algebraických rovnic $Ax=b$ metodou GMRES, lze relativní normu residua omezit shora pomocí tzv. ideální GMRES. Pro normální matice charakterizuje ideální GMRES nejhorší možné chování metody GMRES (worst-case GMRES). Ideálnía worst-case GMRES se však mohou lišit pro matice, které nejsou normální. Charakterizace vztahu mezi ideální a worst-case GMRES pro nenormální matice představuje důležitý otevřený problém v oblasti konvergenční analýzy krylovovských metod. V práci se zabýváme tímto problémem pro případ, kdy $A$ je Jordanův blok. Studujeme vztah mezi ideální a worst-case GMRES jakož i odhad hodnoty ideální GMRES v závislosti na iteračním kroku a na vlastním čísle Jordanova bloku. Prezentujeme nové výsledky týkající se určování velikostí poloměrů polynomiálních numerických obalů Jordanova bloku. Na základě těchto výsledků diskutujeme kvalitu známého odhadu hodnoty ideální GMRES, založeného na poloměru polynomiálního numerického obalu.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/1ET400300415" target="_blank" >1ET400300415: Modelling and simulation of complex technical problems:effective numerical algorithms and parallel implementation using new information technologie</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Electronic Transactions on Numerical Analysis

ISSN

1068-9613

e-ISSN

—

Volume of the periodical

26

Issue of the periodical within the volume

-

Country of publishing house

US - UNITED STATES

Number of pages

21

Pages from-to

453-473

UT code for WoS article

—

EID of the result in the Scopus database

—