Počet záznamů: 1

On Orthogonal Reduction to Hessenberg Form with Small Bandwidth

  1. 1.
    0314348 - UIVT-O 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
    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
    Název souboruStaženoVelikostKomentářVerzePřístup
    0314348.pdf0192.3 KBAutorský preprintpovolen