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

DOI10.1137/17M1144465zbMATH Open1395.65006arXiv1708.06290OpenAlexW2964105082MaRDI QIDQ4580279FDOQ4580279

Authors: Nela Bosner, Zvonimir Bujanović, Zlatko Drmač 

Publication date: 14 August 2018

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

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.

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

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

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)

Cites Work

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

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

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)