Parallel solver for shifted systems in a hybrid CPU-GPU framework

DOI10.1137/17M1144465MaRDI QIDQ4580279zbMATHOpenAlexFDO

Authors Nela Bosner, Zvonimir Bujanović, Zlatko Drmač

Publication date 14 August 2018

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.06290

zbMATH Keywords

transfer functionHessenberg matrixGPUpseudospectruminterpolatory model reductionparallel solvershifted linear systems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Large-scale systems (93A15) Linear systems in control theory (93C05) Frequency-response methods in control theory (93C80)

Abstract: This paper proposes a combination of a hybrid CPU--GPU and a pure GPU software implementation of a direct algorithm for solving shifted linear systems $(A-sigmaI)X=B$ with large number of complex shifts $sigma$ and multiple right-hand sides. Such problems often appear e.g. in control theory when evaluating the transfer function, or as a part of an algorithm performing interpolatory model reduction, as well as when computing pseudospectra and structured pseudospectra, or solving large linear systems of ordinary differential equations. The proposed algorithm first jointly reduces the general full $nimesn$ matrix $A$ and the $nimesm$ full right-hand side matrix $B$ to the controller Hessenberg canonical form that facilitates efficient solution: $A$ is transformed to a so-called $m$-Hessenberg form and $B$ is made upper-triangular. This is implemented as blocked highly parallel CPU--GPU hybrid algorithm; individual blocks are reduced by the CPU, and the necessary updates of the rest of the matrix are split among the cores of the CPU and the GPU. To enhance parallelization, the reduction and the updates are overlapped. In the next phase, the reduced $m$-Hessenberg--triangular systems are solved entirely on the GPU, with shifts divided into batches. The benefits of such load distribution are demonstrated by numerical experiments. In particular, we show that our proposed implementation provides an excellent basis for efficient implementations of computational methods in systems and control theory, from evaluation of transfer function to the interpolatory model reduction.

Recommendations

• A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms
• Efficient generalized Hessenberg form and applications
• Efficient algorithm for simultaneous reduction to the \(m\)-Hessenberg-triangular-triangular form
• Performance models and workload distribution algorithms for optimizing a hybrid CPU-GPU multifrontal solver
• Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing

Cites work

• scientific article; zbMATH DE number 3841228 (Why is no real title available?)
• $\mathcal{H}_2$ Model Reduction for Large-Scale Linear Dynamical Systems
• A note on shifted Hessenberg systems and frequency response computation
• A survey of projection-based model reduction methods for parametric dynamical systems
• Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing
• An alternative Givens ordering
• BiCGStab(\(\ell\)) for families of shifted linear systems
• Calculation of Pseudospectra by the Arnoldi Iteration
• Computation of Pseudospectra by Continuation
• Computing $A^\alpha, \log(A)$, and Related Matrix Functions by Contour Integrals
• Computing the field of values and pseudospectra using the Lanczos method with continuation
• Efficient generalized Hessenberg form and applications
• Hessenberg and Hessenberg/triangular forms in linear system thcory†
• Interpolatory model reduction of large-scale dynamical systems
• Interpolatory projection methods for parameterized model reduction
• LAPACK Users' Guide
• Large-scale computation of pseudospectra using ARPACK and eigs
• Preconditioned multishift BiCG for \(\mathcal{H}_2\)-optimal model reduction
• Recycling BICG with an application to model reduction
• Recycling BiCGSTAB with an application to parametric model order reduction
• Recycling Krylov Subspaces for Sequences of Linear Systems
• Restarted GMRES for Shifted Linear Systems
• Restarted full orthogonalization method for shifted linear systems
• Spectral value sets: A graphical tool for robustness analysis
• Transfer functions and resolvent norm approximation of large matrices
• \(h_{2}\)-norm optimal model reduction for large scale discrete dynamical MIMO systems

Cited in

(3)

• A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms
• An Algorithm for the Complete Solution of the Quartic Eigenvalue Problem
• Scalability pipelined algorithm of the conjugate gradient method on heterogeneous platforms

Describes a project that uses

Uses Software

• LAPACK
• eigs
• ARPACK
• CUBLAS
• Eigtool

This page was built for publication: Parallel solver for shifted systems in a hybrid CPU-GPU framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580279)