A parallel multithreaded sparse triangular linear system solver

2020-07-15
Cugu, Ilke
Manguoğlu, Murat
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 banded case, there are extra savings due to the sparsity of the triangular coefficient matrix. We show the parallel performance of the proposed solver against the stateof-the-art parallel sparse triangular solver in Intel's Math Kernel Library (MKL) on a multicore architecture. We also show the effect of various sparse matrix reordering schemes. Numerical results show that the proposed solver outperforms MKL's solver in similar to 80% of cases by a factor of 2.47, on average.
COMPUTERS & MATHEMATICS WITH APPLICATIONS

Suggestions

A tearing-based hybrid parallel sparse linear system solver
NAUMOV, Maxim; Manguoğlu, Murat; SAMEH, Ahmed (Elsevier BV, 2010-09-15)
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 ...
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 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.
On disconjugacy and stability criteria for discrete Hamiltonian systems
Mert, R.; Zafer, Ağacık (Elsevier BV, 2011-10-01)
By making use of new Lyapunov type inequalities, we establish disconjugacy and stability criteria for discrete Hamiltonian systems. The stability criteria are given when the system is periodic.
Oscillation of solutions of second order mixed nonlinear differential equations under impulsive perturbations
ÖZBEKLER, ABDULLAH; Zafer, Ağacık (Elsevier BV, 2011-02-01)
New oscillation criteria are obtained for second order forced mixed nonlinear impulsive differential equations of the form
Citation Formats
I. Cugu and M. Manguoğlu, “A parallel multithreaded sparse triangular linear system solver,” COMPUTERS & MATHEMATICS WITH APPLICATIONS, pp. 371–385, 2020, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41833.