Naslov
Improving Block-Jacobi Methods

Autori
Hari, Vjeran

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
V International Workshop on Accurate Solution of Eigenvalue Problems Hagen, Germany, June 28 - July 1, 2004

Skup
V International Workshop on Accurate Solution of Eigenvalue Problems

Mjesto i datum
Hagen, Njemačka, 28.06-01.07

Vrsta sudjelovanja
Poster

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Block-Jacobi methods; eigenvalue decompositions

Sažetak
A way how to exploit memory hierarchy to improve performance of some block methods, is explained for the case of a one-sided block-Jacobi method for computing SVD of rectangular matrices. At each step of that method, an orthogonal matrix U must be applied to two block-columns of the iterated matrix, $ [G_i, G_j]U$. Partitioning $ U$ accordingly, one can make its CS decomposition, $ U=V\Gamma W^T$, where $ V$ and $ W$ are orthogonal and block-diagonal. To reduce the flop count one observes that multiplication with $ V$ followed by $ \Gamma$ is cheaper than multiplying with the full matrix $ U$. The multiplication with the blocks of $ W^T$ can be postponed and combined with a $ V$-multiplication at a later stage. The additional cost for the book-keeping and CS decomposition is expected to be small since it involves small matrices and the computation can be done in fast memory (cache). Preliminary numerical tests show that the CPU time of one sweep of the block-Jacobi method can be, in this way, substantially ($ 20$% - $ 40$%) reduced. It is easily shown that the any block-Jacobi method is relatively accurate. As yet, the main obstacle in developing a full implementation of the new method, is the lack of a reliable an accurate code for CS decomposition of orthogonal matrices. In our tests we have computed CS decomposition via two SVDs of diagonal (or off-diagonal) blocks of $ U$, using QR with column pivoting followed by Kogbetliantz method for triangular matrices. As part of this project, sharp estimates for the relative accuracy of the Kogbetliatz method have been obtained.

Izvorni jezik
Engleski

POVEZANOST RADA