A tearing-based hybrid parallel sparse linear system solver

Date

2010-09-15

Author

NAUMOV, Maxim
Manguoğlu, Murat
SAMEH, Ahmed

Metadata

Show full item record

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

Item Usage Stats

157
views

0
downloads

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.

Subject Keywords

Applied Mathematics, Computational Mathematics

URI

https://hdl.handle.net/11511/40196

Journal

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

DOI

https://doi.org/10.1016/j.cam.2010.04.016

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A nested iterative scheme for computation of incompressible flows in long domains Manguoğlu, Murat; Tezduyar, Tayfun E.; Sathe, Sunil (Springer Science and Business Media LLC, 2008-12-01) We present an effective preconditioning technique for solving the nonsymmetric linear systems encountered in computation of incompressible flows in long domains. The application category we focus on is arterial fluid mechanics. These linear systems are solved using a nested iterative scheme with an outer Richardson scheme and an inner iteration that is handled via a Krylov subspace method. Test computations that demonstrate the robustness of our nested scheme are presented.
A parallel multithreaded sparse triangular linear system solver Cugu, Ilke; Manguoğlu, Murat (Elsevier BV, 2020-07-15) We propose a parallel sparse triangular linear system solver based on the Spike algorithm. Sparse triangular systems are required to be solved in many applications. Often, they are a bottleneck due to their inherently sequential nature. Furthermore, typically many successive systems with the same coefficient matrix and with different right hand side vectors are required to be solved. The proposed solver decouples the problem at the cost of extra arithmetic operations as in the banded case. Compared to the b...
A second order decoupled penalty projection method based on deferred correction for MHD in Elsässer variable Erkmen, Dilek; Kaya Merdan, Songül; Cibik, Aytekin (Elsevier BV, 2020-06-01) © 2019 Elsevier B.V.We study the deferred correction method for the magnetohydrodynamics (MHD) system written in Elsässer variables. The proposed algorithm is based on the penalty projection with grad-div stabilized Taylor Hood solutions of the Elsässer formulation. In this way, second order accuracy of the method in time is obtained through the deferred correction method with excellent mass conservation properties. For the proposed method, stability is rigorously proven and numerical experiments are presen...
A ROBUST ITERATIVE SCHEME FOR SYMMETRIC INDEFINITE SYSTEMS Manguoğlu, Murat (Society for Industrial & Applied Mathematics (SIAM), 2019-01-01) We propose a two-level nested preconditioned iterative scheme for solving sparse linear systems of equations in which the coefficient matrix is symmetric and indefinite with a relatively small number of negative eigenvalues. The proposed scheme consists of an outer minimum residual (MINRES) iteration, preconditioned by an inner conjugate gradient (CG) iteration in which CG can be further preconditioned. The robustness of the proposed scheme is illustrated by solving indefinite linear systems that arise in t...
A finite element variational multiscale method for the Navier-Stokes equations Volker, John; Kaya Merdan, Songül (Society for Industrial & Applied Mathematics (SIAM), 2005-01-01) This paper presents a variational multiscale method (VMS) for the incompressible Navier-Stokes equations which is defined by a large scale space L-H for the velocity deformation tensor and a turbulent viscosity nu(T). The connection of this method to the standard formulation of a VMS is explained. The conditions on L-H under which the VMS can be implemented easily and efficiently into an existing finite element code for solving the Navier - Stokes equations are studied. Numerical tests with the Smagorinsky ...

Citation Formats

M. NAUMOV, M. Manguoğlu, and A. SAMEH, “A tearing-based hybrid parallel sparse linear system solver,” JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, pp. 3025–3038, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/40196.