Naslov
GPU algorithms for solving shifted systems with multiple right–hand sides

Autori
Bosner, Nela ; Bujanović, Zvonimir ; Drmač, Zlatko

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

Skup
5th Croatian Mathematical Congress

Mjesto i datum
Rijeka, Hrvatska, 18.06.2012. - 21.06.2012

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
GPU algorithms ; shifted systems ; m-Hessenberg reductions

Sažetak
We propose hybrid CPU-GPU and pure GPU algorithms for solving shifted systems with multiple right sides, and for large number of shifts. This prob- lems appears in control theory when frequency response matrix of a system is required, or when numerical solution of large linear system of ODE’s is sought. The algorithm is based on two steps. The first step reduces matrix and right– hand side of the system to a suitable form, and this is done only once. This suitable form enables us to solve the system simply and quickly. The second step repeatedly solves the systems for different shifts. We distinguish two cases of the shifted systems with m right–hand sides. (a) (A − σI)X = B where I is the identity matrix. In this case A is reduced to m-Hessenberg form and B is reduced to triangular form, and these reductions are done simultaneously in the first step. (b) (A − σE)X = B where E is a general matrix. In this case A is reduced to m-Hessenberg form and B and E are reduced to triangular form. All these reductions are done simultaneously in the first step, too. In both cases we will obtain a linear system with the m-Hessenberg system matrix and the triangular right–hand side, which is easily solved by annihilating m subdiagonals of the system matrix. We will introduce a highly parallel CPU- GPU hybrid algorithm for the reduction in the first step in case [(a)], and a GPU algorithm for the reduction in case [(b)] which is quite a challenge for parallelization. The most efficient algorithm is a GPU implementation of the solver which simultaneous solves a large number of shifted systems in the m- Hessenberg–triangular form.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA