MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc's eigensolvers

Abstract We consider the computation of a few eigenpairs of a generalized eigenvalue problem A x = λ B x with block-tridiagonal matrices, not necessarily symmetric, in the context of Krylov methods. In this kind of computation, it is often necessary to solve a linear system of equations in each iteration of the eigensolver, for instance when B is not the identity matrix or when computing interior eigenvalues with the shift-and-invert spectral transformation. In this work, we aim to compare different direct linear solvers that can exploit the block-tridiagonal structure. Block cyclic reduction and the Spike algorithm are considered. A parallel implementation based on MPI is developed in the context of the SLEPc library. The use of GPU devices to accelerate local computations shows to be competitive for large block sizes.

• Publication year

  2017

• Venue

  Parallel Computing

• Publication date

  2017-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.parco.2017.11.006
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• PETSc Users Manual: Revision 3.11

  2019influential reference
• On the performance and energy efficiency of sparse linear algebra on GPUs

  2017cited by this paper
• A fast band-Krylov eigensolver for macromolecular functional motion simulation on multicore architectures and graphics processors

  2016cited by this paper
• Manycore Algorithms for Batch Scalar and Block Tridiagonal Solvers

  2016cited by this paper
• Optimized analysis of isotropic high-nuclearity spin clusters with GPU acceleration

  2016cited by this paper
• Parallelism in Matrix Computations

  2016cited by this paper
• A discontinuous Galerkin method with block cyclic reduction solver for simulating compressible flows on GPUs

  2015cited by this paper
• A GPU‐based preconditioned Newton‐Krylov solver for flexible multibody dynamics

  2015cited by this paper
• A general tridiagonal solver for coprocessors: Adapting g-Spike for the Intel Xeon Phi

  2015cited by this paper
• GPU Implementation of Krylov Solvers for Block-Tridiagonal Eigenvalue Problems

  2015cited by this paper
• A direct tridiagonal solver based on Givens rotations for GPU architectures

  2015cited by this paper
• Pipelined Iterative Solvers with Kernel Fusion for Graphics Processing Units

  2014cited by this paper
• Preliminary Implementation of PETSc Using GPUs

  2013cited by this paper
• Revisiting parallel cyclic reduction and parallel prefix-based algorithms for block tridiagonal systems of equations

  2013cited by this paper
• Efficient heterogeneous execution on large multicore and accelerator platforms: Case study using a block tridiagonal solver

  2013cited by this paper
• A scalable, numerically stable, high-performance tridiagonal solver using GPUs

  2012cited by this paper
• Divide and Conquer on Hybrid GPU-Accelerated Multicore Systems

  2012cited by this paper
• Toward a High Performance Tile Divide and Conquer Algorithm for the Dense Symmetric Eigenvalue Problem

  2012cited by this paper
• A threaded SPIKE algorithm for solving general banded systems

  2011cited by this paper
• Condensed forms for the symmetric eigenvalue problem on multi‐threaded architectures

  2011cited by this paper
• BCYCLIC: A parallel block tridiagonal matrix cyclic solver

  2010influential reference
• Fast tridiagonal solvers on the GPU

  2010cited by this paper
• Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing

  2010cited by this paper
• Towards dense linear algebra for hybrid GPU accelerated manycore systems

  2009influential reference
• Analysis of the Truncated SPIKE Algorithm

  2008influential reference
• Comparison of parallel eigensolvers for a discretized radiative transfer problem

  2007cited by this paper
• A parallel hybrid banded system solver: the SPIKE algorithm

  2006cited by this paper
• SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems

  2005cited by this paper
• An L 1 refined projection approximate solution of the radiation transfer equation in stellar atmospheres

  2002cited by this paper
• A Krylov-Schur Algorithm for Large Eigenproblems

  2001cited by this paper
• Templates for the Solution of Algebraic Eigenvalue Problems

  2000cited by this paper
• Cyclic Reduction - History and Applications

  1997cited by this paper
• Stability of the block cyclic reduction

  1996cited by this paper
• Some Aspects of the Cyclic Reduction Algorithm for Block Tridiagonal Linear Systems

  1976cited by this paper
• The Solution of Tridiagonal Linear Systems on the CDC STAR 100 Computer

  1975cited by this paper
• On direct methods for solving Poisson's equation

  1970cited by this paper

• Coupled Incomplete Cholesky and Jacobi Preconditioned Conjugate Gradient on the New Generation of Sunway Many-Core Architecture

  2023cites this paper
• MPCGPU: Real-Time Nonlinear Model Predictive Control through Preconditioned Conjugate Gradient on the GPU

  2023cites this paper
• Curriculum Vitae

  2020cites this paper
• A parallel hybrid implementation of the 2D acoustic wave equation

  2020cites this paper
• Modified method of parallel matrix sweep

  2020cites this paper
• Dense and sparse parallel linear algebra algorithms on graphics processing units

  2018cites this paper
• Probabilistic modeling of renewable energy source based on Spark platform with large-scale sample data

  2018cites this paper