Report 2009-40

A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms

P. Benner, P. Ezzatti, D. Kressner, E.S. Quintana-Ortí and A. Remón

Abstract: We describe a hybrid Lyapunov solver based on the matrix sign function that accelerates the intensive parts of the computation using a graphics processor (GPU) while executing the remaining operations in a general-purpose multicore processor. The initial stage of the iterative solver operates in singleprecision arithmetic, to exploit the many-core parallelism of current GPUs, returning a full-rank factor to the solution of the equation. To improve this approximate solution, the second stage consists of an efficient iterative refinement procedure that allows to cheaply recover full double-precision accuracy. The combination of these two stages results in a mixed-precision algorithm, that exploits the capabilities of both general-purpose multi-core processors and many-core GPUs, overlapping critical computations. Experiments using a platform equipped with two Intel Xeon QuadCore processors and an Nvidia Tesla C1060 show the efficiency of this approach to solve Lyapunov equations arising in practical model reduction applications: compared with a classical implementation that exploits the parallelism of a general-purpose processor using a multi-threaded implementation of BLAS and operates in double-precision, our hybrid algorithm delivers 4.24–6.46 speed-ups while attaining the same accuracy in the solution.

Keywords: Lyapunov equations, matrix sign function, graphics processors, multi-core processors, control theory

Paper: Available as PDF (286KB) or as hardcopy to order reports@sam.math.ethz.ch.