On Orthogonal Reduction to Hessenberg Form with Small Bandwidth
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F09%3A00314348" target="_blank" >RIV/67985807:_____/09:00314348 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Orthogonal Reduction to Hessenberg Form with Small Bandwidth
Original language description
Numerous algorithms in numerical linear algebra are based on the reduction of a given matrix A to a more convenient form. One of the most useful types of such reduction is the orthogonal reduction to (upper) Hessenberg form. This reduction can be computed by the Arnoldi algorithm. When A is Hermitian, the resulting upper Hessenberg matrix is tridiagonal. In this paper we study necessary and sufficient conditions on A so that the orthogonal Hessenberg reduction yields a Hessenberg matrix with small bandwidth. Our proof utilizes the idea of a "minimal counterexample", which is standard in combinatorial optimization, but rarely used in the context of linear algebra.
Czech name
O ortogonální redukci matice na pásovou Hessenbergovu matici
Czech description
Mnoho algoritmů v numerické lineární algebře je založeno na transformaci dané matice A na vhodnější tvar. Jedna z nejužitečnějších transformací je ortogonální transformace matice na (horní) Hessenbergův tvar. Tato transfomace může být realizována Arnoldiho algoritmem. Pokud je matice A hermitovská, výsledná horní Hessenbergova matice je tridiagonální. V této práci studujeme nutné a postačující podmínky, za jakých je možné ortogonálně transformovat matici A na pásovou horní Hessenbergovu matici s malou šíří pásu. Náš důkaz využívá myšlenky "minimálního protipříkladu", což je standardní nástroj v kombinatorické optimalizaci, ale zřídka používaný nástroj v lineární algebře.
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/IAA100300802" target="_blank" >IAA100300802: Theory of Krylov subspace methods and its relationship to other mathematical disciplines</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Numerical Algorithms
ISSN
1017-1398
e-ISSN
—
Volume of the periodical
51
Issue of the periodical within the volume
2
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
10
Pages from-to
—
UT code for WoS article
000265919800001
EID of the result in the Scopus database
—