Naslov
Speeding-up simultaneous reductions of several matrices to a condensed form

Autori
Bosner, Nela

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

Izvornik
ApplMath 18 / - , 2018, 17-17

Skup
Ninth Conference on Applied Mathematics and Scientific Computing (ApplMath18)

Mjesto i datum
Šibenik, Hrvatska, 17.09.2018. - 20.09.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
Hessenberg-triangular-triangular-triangular form ; generalized singular value and eigenvalue problem ; Givens rotations ; block and parallel implementations

Sažetak
We are concerned with the simultaneous orthogonal reductions of several matrices to a condensed form, based on the Givens rotations. The basic task of these algorithms is to reduce one matrix to Hessenberg or $m$-Hessenberg form, and the others to triangular form. Such condensed forms are suitable for solving multiple shifted systems $(\sigma E-A)X=B$, and for solving the generalized singular value problem $A^{; ; T}; ; Ax=\mu^{; ; 2}; ; B^{; ; T}; ; Bx$. At the beginning of the reduction algorithm, all matrices except one are reduced to the triangular form by QR factorization, and then the remaining matrix is reduced to the Hessenberg form while simultaneously preserving triangular form of the other matrices. The later reduction is performed by Givens rotations, which renders the whole algorithm very inefficient. We proposed several techniques for speeding-up applications of the rotations. One approach is based on blocking strategies on at least two levels, and the other approach exploits multithreading ability of modern CPUs, as well as parallel computing on GPU. Both approaches offer respectable speed-up factors. The optimal efficiency is obtained by combining the blocking strategy with parallel updates, and by overlapping the reduction step on the CPU with the compute-intensive updates based on matrix--matrix multiplications performed on the GPU.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA