Search

In this paper we introduce a variant of the Newton iteration for the matrix sign function that results in an efficient numerical solver for a certain class of algebraic Riccati equations (AREs). In particular, when the Hamiltonian matrix associated with the ARE can be composed as $\left [\begin {array}{llll}{A}&{BB^{T}}\\{C^{T}C}&{-A^{T}}\end {array}\right ]$, with B and $C^{T}$ having a much larger number of rows than columns, the new algorithm exploits the special structure of the off-diagonal blocks to yield an alternative factored Newton iteration which reduces the cost per iteration by a factor of up to 8 (16 in case A is symmetric negative definite) w.r.t. the conventional iterative scheme. Experiments with a large collection of benchmark examples show that the factored iteration attains numerical accuracy similar to that of the conventional Newton iteration as well as the structure-preserving doubling algorithm. High-performance implementations of these methods, making heavy use of LAPACK linked to a multi-threaded implementation of BLAS, demonstrate the clear advantage of the new iteration on a 48-core AMD-based platform. [ABSTRACT FROM AUTHOR]

We address the numerical solution of Lyapunov, algebraic and differential Riccati equations, via the matrix sign function, on platforms equipped with general-purpose multicore processors and, optionally, one or more graphics processing units (GPUs). In particular, we review the solvers for these equations, as well as the underlying methods, analyze their concurrency and scalability and provide details on their parallel implementation. Our experimental results show that this class of hardware provides sufficient computational power to tackle large-scale problems, which only a few years ago would have required a cluster of computers. [ABSTRACT FROM AUTHOR]

Lyapack is a package for the solution of large-scale sparse problems arising in control theory. The package has a modular design, and is implemented as a Matlab toolbox, which renders it easy to utilize, modify and extend with new functionality. However, in general, the use of Matlab in combination with a general-purpose multi-core architecture (CPU) offers limited performance when tackling the sparse linear algebra operations underlying the numerical methods involved in control theory. In this paper we extend Lyapack to leverage the computational power of graphics processors (GPUs). The experimental evaluation of a new CUDA-enabled solver for the Lyapunov equation, a crucial operation appearing in control theory problems, shows a significant runtime reduction when compared with the original CPU version of Lyapack, while retaining the usability of a Matlab-based implementation. [ABSTRACT FROM AUTHOR]

Abstract: We describe a hybrid Lyapunov solver based on the matrix sign function, where the intensive parts of the computation are accelerated using a graphics processor (GPU) while executing the remaining operations on a general-purpose multi-core processor (CPU). The initial stage of the iteration operates in single-precision arithmetic, returning a low-rank factor of an approximate solution. As the main computation in this stage consists of explicit matrix inversions, we propose a hybrid implementation of Gauß–Jordan elimination using look-ahead to overlap computations on GPU and CPU. To improve the approximate solution, we introduce an iterative refinement procedure that allows to cheaply recover full double-precision accuracy. In contrast to earlier approaches to iterative refinement for Lyapunov equations, this approach retains the low-rank factorization structure of the approximate solution. The combination of the two stages results in a mixed-precision algorithm, that exploits the capabilities of both general-purpose CPUs and many-core GPUs and overlaps critical computations. Numerical experiments using real-world data and a platform equipped with two Intel Xeon QuadCore processors and an Nvidia Tesla C1060 show a significant efficiency gain of the hybrid method compared to a classical CPU implementation. [Copyright &y& Elsevier]