A scalable iterative dense linear system solver for multiple right-hand sides in data analytics

Vassilis Kalantzis; A. Cristiano I. Malossi; Costas Bekas; Alessandro Curioni; Efstratios Gallopoulos; Yousef Saad

doi:10.1016/j.parco.2017.12.005

A scalable iterative dense linear system solver for multiple right-hand sides in data analytics

Vassilis Kalantzis, A. Cristiano I. Malossi, Costas Bekas, Alessandro Curioni, Efstratios Gallopoulos, Yousef Saad

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We describe Parallel-Projection Block Conjugate Gradient (PP-BCG), a distributed iterative solver for the solution of dense and symmetric positive definite linear systems with multiple right-hand sides. In particular, we focus on linear systems appearing in the context of stochastic estimation of the diagonal of the matrix inverse in Uncertainty Quantification. PP-BCG is based on the block Conjugate Gradient algorithm combined with Galerkin projections to accelerate the convergence rate of the solution process of the linear systems. Numerical experiments on massively parallel architectures illustrate the performance of the proposed scheme in terms of efficiency and convergence rate, as well as its effectiveness relative to the (block) Conjugate Gradient and the Cholesky-based ScaLAPACK solver. In particular, on a 4 rack BG/Q with up to 65,536 processor cores using dense matrices of order as high as 524,288 and 800 right-hand sides, PP-BCG can be 2x-3x faster than the aforementioned techniques.

Original language	English (US)
Pages (from-to)	136-153
Number of pages	18
Journal	Parallel Computing
Volume	74
DOIs	https://doi.org/10.1016/j.parco.2017.12.005
State	Published - May 2018

Bibliographical note

Funding Information:
Vassilis Kalantzis was partially supported by a Gerondelis Foundation Fellowship. This work was completed while E. Gallopoulos was on sabbatical leave at the Dept. CSE, University of Minnesota. We thank the University of Minnesota Supercomputing Institute for providing the computational resources needed in the initial stage of this work. We also thank the anonymous referees for their comments which greatly improved the clarity and presentation of this paper.

Publisher Copyright:
© 2018 Elsevier B.V.

Keywords

(Block) Conjugate Gradient
Deflation
Galerkin projections
Massively parallel architectures
Multiple right-hand sides

Access

10.1016/j.parco.2017.12.005

Cite this

@article{19a48e667c044f32a641b76bb8d58179,

title = "A scalable iterative dense linear system solver for multiple right-hand sides in data analytics",

abstract = "We describe Parallel-Projection Block Conjugate Gradient (PP-BCG), a distributed iterative solver for the solution of dense and symmetric positive definite linear systems with multiple right-hand sides. In particular, we focus on linear systems appearing in the context of stochastic estimation of the diagonal of the matrix inverse in Uncertainty Quantification. PP-BCG is based on the block Conjugate Gradient algorithm combined with Galerkin projections to accelerate the convergence rate of the solution process of the linear systems. Numerical experiments on massively parallel architectures illustrate the performance of the proposed scheme in terms of efficiency and convergence rate, as well as its effectiveness relative to the (block) Conjugate Gradient and the Cholesky-based ScaLAPACK solver. In particular, on a 4 rack BG/Q with up to 65,536 processor cores using dense matrices of order as high as 524,288 and 800 right-hand sides, PP-BCG can be 2x-3x faster than the aforementioned techniques.",

keywords = "(Block) Conjugate Gradient, Deflation, Galerkin projections, Massively parallel architectures, Multiple right-hand sides",

author = "Vassilis Kalantzis and Malossi, {A. Cristiano I.} and Costas Bekas and Alessandro Curioni and Efstratios Gallopoulos and Yousef Saad",

note = "Funding Information: Vassilis Kalantzis was partially supported by a Gerondelis Foundation Fellowship. This work was completed while E. Gallopoulos was on sabbatical leave at the Dept. CSE, University of Minnesota. We thank the University of Minnesota Supercomputing Institute for providing the computational resources needed in the initial stage of this work. We also thank the anonymous referees for their comments which greatly improved the clarity and presentation of this paper. Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = may,

doi = "10.1016/j.parco.2017.12.005",

language = "English (US)",

volume = "74",

pages = "136--153",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

}

TY - JOUR

T1 - A scalable iterative dense linear system solver for multiple right-hand sides in data analytics

AU - Kalantzis, Vassilis

AU - Malossi, A. Cristiano I.

AU - Bekas, Costas

AU - Curioni, Alessandro

AU - Gallopoulos, Efstratios

AU - Saad, Yousef

N1 - Funding Information: Vassilis Kalantzis was partially supported by a Gerondelis Foundation Fellowship. This work was completed while E. Gallopoulos was on sabbatical leave at the Dept. CSE, University of Minnesota. We thank the University of Minnesota Supercomputing Institute for providing the computational resources needed in the initial stage of this work. We also thank the anonymous referees for their comments which greatly improved the clarity and presentation of this paper. Publisher Copyright: © 2018 Elsevier B.V.

PY - 2018/5

Y1 - 2018/5

N2 - We describe Parallel-Projection Block Conjugate Gradient (PP-BCG), a distributed iterative solver for the solution of dense and symmetric positive definite linear systems with multiple right-hand sides. In particular, we focus on linear systems appearing in the context of stochastic estimation of the diagonal of the matrix inverse in Uncertainty Quantification. PP-BCG is based on the block Conjugate Gradient algorithm combined with Galerkin projections to accelerate the convergence rate of the solution process of the linear systems. Numerical experiments on massively parallel architectures illustrate the performance of the proposed scheme in terms of efficiency and convergence rate, as well as its effectiveness relative to the (block) Conjugate Gradient and the Cholesky-based ScaLAPACK solver. In particular, on a 4 rack BG/Q with up to 65,536 processor cores using dense matrices of order as high as 524,288 and 800 right-hand sides, PP-BCG can be 2x-3x faster than the aforementioned techniques.

AB - We describe Parallel-Projection Block Conjugate Gradient (PP-BCG), a distributed iterative solver for the solution of dense and symmetric positive definite linear systems with multiple right-hand sides. In particular, we focus on linear systems appearing in the context of stochastic estimation of the diagonal of the matrix inverse in Uncertainty Quantification. PP-BCG is based on the block Conjugate Gradient algorithm combined with Galerkin projections to accelerate the convergence rate of the solution process of the linear systems. Numerical experiments on massively parallel architectures illustrate the performance of the proposed scheme in terms of efficiency and convergence rate, as well as its effectiveness relative to the (block) Conjugate Gradient and the Cholesky-based ScaLAPACK solver. In particular, on a 4 rack BG/Q with up to 65,536 processor cores using dense matrices of order as high as 524,288 and 800 right-hand sides, PP-BCG can be 2x-3x faster than the aforementioned techniques.

KW - (Block) Conjugate Gradient

KW - Deflation

KW - Galerkin projections

KW - Massively parallel architectures

KW - Multiple right-hand sides

UR - http://www.scopus.com/inward/record.url?scp=85041039382&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041039382&partnerID=8YFLogxK

U2 - 10.1016/j.parco.2017.12.005

DO - 10.1016/j.parco.2017.12.005

M3 - Article

AN - SCOPUS:85041039382

VL - 74

SP - 136

EP - 153

JO - Parallel Computing

JF - Parallel Computing

SN - 0167-8191

ER -

A scalable iterative dense linear system solver for multiple right-hand sides in data analytics

Abstract

Bibliographical note

Keywords

Access

Other files and links

Fingerprint

Cite this