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

2022-04-01
Torun, Tugba
Torun, F. Sukru
Manguoğlu, Murat
Aykanat, Cevdet
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
SIAM JOURNAL OF SCIENTIFIC COMPUTING

Suggestions

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.
Large sparse matrix-vector multiplication over finite fields
Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat; Department of Cryptography (2019)
Cryptographic computations such as factoring integers and computing discrete logarithms require solving a large sparse system of linear equations over finite fields. When dealing with such systems iterative solvers such as Wiedemann or Lanczos algorithms are used. The computational cost of both methods is often dominated by successive matrix-vector products. In this thesis, we introduce a new algorithm for computing a large sparse matrix-vector multiplication over finite fields. The proposed algorithm is im...
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...
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.