A parallel multithreaded sparse triangular linear system solver

Cugu I., MANGUOĞLU M.

COMPUTERS & MATHEMATICS WITH APPLICATIONS, cilt.80, sa.2, ss.371-385, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 80 Sayı: 2
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1016/j.camwa.2019.09.012
  • Dergi Adı: COMPUTERS & MATHEMATICS WITH APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, Metadex, MLA - Modern Language Association Database, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.371-385
  • Anahtar Kelimeler: Sparse triangular linear systems, Direct methods, Parallel computing, ALGORITHM, PERFORMANCE, SPIKE, LIBRARY
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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. (C) 2019 Elsevier Ltd. All rights reserved.