On Orthogonal Reduction to Hessenberg Form with Small Bandwidth

0314348 - ÚI 2009 RIV NL eng J - Článek v odborném periodiku
Faber, V. - Liesen, J. - Tichý, Petr
On Orthogonal Reduction to Hessenberg Form with Small Bandwidth.
[O ortogonální redukci matice na pásovou Hessenbergovu matici.]
Numerical Algorithms. Roč. 51, č. 2 (2009), s. 133-142. ISSN 1017-1398. E-ISSN 1572-9265
Grant CEP: GA AV ČR IAA100300802
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: reduction to Hessenberg form * Krylov subspace methods * Arnoldi method * Lanczos method
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.716, rok: 2009

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.

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.
Trvalý link: http://hdl.handle.net/11104/0164882