Partitioning and Reordering for Spike-Based Distributed-Memory Parallel Gauss--Seidel

Date

2022-04-01

Author

Torun, Tugba
Torun, F. Sukru
Manguoğlu, Murat
Aykanat, Cevdet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

135
views

0
downloads

Gauss--Seidel (GS) is a widely used iterative method for solving sparse linear sys-tems of equations and also known to be effective as a smoother in algebraic multigrid methods.Parallelization of GS is a challenging task since solving the sparse lower triangular system in GSconstitutes a sequential bottleneck at each iteration. We propose a distributed-memory parallel GS(dmpGS) by implementing a parallel sparse triangular solver (stSpike) based on the Spike algorithm.stSpike decouples the global triangular system into smaller systems that can be solved concurrentlyand requires the solution of a much smaller reduced sparse lower triangular system which constitutesa sequential bottleneck. In order to alleviate this bottleneck and to reduce the communication over-head of dmpGS, we propose a partitioning and reordering model consisting of two phases. The firstphase is a novel hypergraph partitioning model whose partitioning objective simultaneously encodesminimizing the reduced system size and the communication volume. The second phase is an in-blockrow reordering method for decreasing the nonzero count of the reduced system. Extensive experi-ments on a dataset consisting of 359 sparse linear systems verify the effectiveness of the proposedpartitioning and reordering model in terms of reducing the communication and the sequential com-putational overheads. Parallel experiments on 12 large systems using up to 320 cores demonstratethat the proposed model significantly improves the scalability of dmpGS

Subject Keywords

parallel Gauss--Seidel, distributed-memory, Spike algorithm, parallel sparse trian-gular solve, hypergraph partitioning, sparse matrix reordering

URI

https://epubs.siam.org/doi/epdf/10.1137/21M1411603
https://hdl.handle.net/11511/96890

Journal

SIAM JOURNAL OF SCIENTIFIC COMPUTING

DOI

https://doi.org/10.1137/21m1411603

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Parallel computation of the diagonal of the inverse of a sparse matrix Fasllija, Edona; Manguoğlu, Murat; Department of Computer Engineering (2017) We consider the parallel computation of the diagonal of the inverse of a large sparse matrix. This problem is critical in many applications such as quantum mechanics and uncertainty quantification, where a subset of the entries of the inverse matrix, usually the diagonal, is required. A straightforward approach involves inverting the matrix explicitly and extracting the diagonal of the computed inverse. This approach, however, almost always is too costly for large sparse matrices since the inverse is often ...
A parallel sparse algorithm targeting arterial fluid mechanics computations Manguoğlu, Murat; Sameh, Ahmed H.; Tezduyar, Tayfun E. (2011-09-01) Iterative solution of large sparse nonsymmetric linear equation systems is one of the numerical challenges in arterial fluid-structure interaction computations. This is because the fluid mechanics parts of the fluid + structure block of the equation system that needs to be solved at every nonlinear iteration of each time step corresponds to incompressible flow, the computational domains include slender parts, and accurate wall shear stress calculations require boundary layer mesh refinement near the arteria...
Modified iterative methods for linear systems of equations Karasözen, Bülent (1998-01-01) An extension of the modified Jacobi and Gauss-Seidel methods for systems of linear equations has been introduced. The convergence properties of the proposed methods have been analyzed and compared with the classical and modified methods. The numerical results obtained for some linear systems show that the extended modified methods are superior to other modified iterative methods.
Improved parallel preconditioners for multidisciplinary topology optimisations AKAY, HASAN UMUR; Oktay, E.; Manguoğlu, Murat; Sivas, A. A. (2016-01-01) Two commonly used preconditioners were evaluated for parallel solution of linear systems of equations with high condition numbers. The test cases were derived from topology optimisation applications in multiple disciplines, where the material distribution finite element methods were used. Because in this optimisation method, the equations rapidly become ill-conditioned due to disappearance of large number of elements from the design space as the optimisations progresses, it is shown that the choice for a su...
Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2017-03-01) Underdetermined systems of equations in which the minimum norm solution needs to be computed arise in many applications, such as geophysics, signal processing, and biomedical engineering. In this article, we introduce a new parallel algorithm for obtaining the minimum 2-norm solution of an underdetermined system of equations. The proposed algorithm is based on the Balance scheme, which was originally developed for the parallel solution of banded linear systems. The proposed scheme assumes a generalized band...

Citation Formats

T. Torun, F. S. Torun, M. Manguoğlu, and C. Aykanat, “Partitioning and Reordering for Spike-Based Distributed-Memory Parallel Gauss--Seidel,” SIAM JOURNAL OF SCIENTIFIC COMPUTING, vol. 44, pp. 99–123, 2022, Accessed: 00, 2022. [Online]. Available: https://epubs.siam.org/doi/epdf/10.1137/21M1411603.