engleski

Adapting the Kogbetliantz Method to Shared Memory Machines

Typical fast SVD solvers for general matrices, like Divide and Conquer, Differential QED and the QR method, first reduce the initial matrix to bidiagonal form. It is known that this initial reduction can deteriorate the relative accuracy of the smallest singular values even if the initial matrix is well-behaved for accurate SVD computation. For such matrices, the one-sided Jacobi methods have proved to be very accurate and the latest research indicates that they can be made fast. Since they possess intrinsic parallelism, they are fast and accurate on standard and parallel computers. In this report, we pay attention to the less known two-sided Jacobi-type method, the Kogbetliantz method. Recent research of Matejaš and Hari, and Londre and Rhee prove that this method is relatively accurate. When compared with the one-sided methods, the Kogbetliantz method has certain advantages (almost diagonal matrix is further diagonalized, it uses sound stopping criterion \ldots ) and disadvantages (left transformations are slow, it requires more memory space \ldots ). The Kogbetliantz method is the most efficient and accurate for nearly diagonal triangular matrices. Here, we present an adaptation of the Kogbetliantz method for work with shared memory machines. It essentially preserves the (initially created) zero elements, which has beneficial impact to its simplicity and to the quadratic asymptotic convergence. The method can be further modified to work with blocks, which leads to the better usage of contemporary processor capabilities like the cache memory. In addition, the slowdown coming from the left transformations can be essentially reduced.

Kogbetliantz method; parallel computing

nije evidentirano