Parallel solution of sparse triangular linear systems on multicore platforms

Download
2018
Çuğu, İlke
Many large-scale applications in science and engineering require the solution of sparse linear systems. One well-known approach is to solve these systems by factorizing the coefficient matrix into nonsingular sparse triangular matrices and solving the resulting sparse triangular systems via backward and forward sweep (substitution) operations. This can be considered as a direct solver or it is part of the preconditioning operation in an iterative scheme if incomplete factorization is computed. Often, these sparse triangular systems are the main performance bottleneck due to their inherently sequential nature. With the emergence of multi-core platforms, the interest in solving sparse triangular linear systems effectively in parallel has grown. In this thesis, a parallel sparse triangular linear system solver based on the generalization of Spike algorithm is proposed. The performance constraints of the proposed algorithm and their impacts on the performance are evaluated on matrices from different application domains. Furthermore, performance comparisons are made against the state-of-the-art parallel sparse triangular solver of Intel's Math Kernel Library.

Suggestions

A New multi-threaded and recursive direct algorithm for parallel solution of sparse linear systems
Bölükbaşı, Ercan Selçuk; Manguoğlu, Murat; Department of Computer Engineering (2013)
Many of the science and engineering applications need to solve linear systems to model a real problem. Usually these linear systems have sparse coefficient matrices and thus require an effective solution of sparse linear systems which is usually the most time consuming operation. Circuit simulation, material science, power network analysis and computational fluid dynamics can be given as examples of these problems. With the introduction of multi-core processors, it became more important to solve sparse line...
Learning the Domain of Sparse Matrices
Salm, Suleyman; Manguoğlu, Murat; Aktulga, Hasan Metin (2016-12-20)
Large sparse linear system of equations arise in many areas of science and engineering. Although, there are several black-box general sparse solvers, usually they are not as effective as domain specific solvers. In addition, most solvers contain multiple choices during the solution process which can be tailored to a specific domain. A natural first step towards a black-box solver that is as effective as domain specific solvers is to come up with a technique to identify the application domain of the problem....
Structured neural networks for modeling and identification of nonlinear mechanical systems
Kılıç, Ergin; Dölen, Melik; Koku, Ahmet Buğra; Department of Mechanical Engineering (2012)
Most engineering systems are highly nonlinear in nature and thus one could not develop efficient mathematical models for these systems. Artificial neural networks, which are used in estimation, filtering, identification and control in technical literature, are considered as universal modeling and functional approximation tools. Unfortunately, developing a well trained monolithic type neural network (with many free parameters/weights) is known to be a daunting task since the process of loading a specific pat...
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...
Sparse linear sensor arrays: analysis of recent coarray based arrays and array design for nonlinear processing
Epçaçan, Erdal; Çiloğlu, Tolga; Department of Electrical and Electronics Engineering (2021-9-09)
In this thesis, sparse linear sensor arrays have been studied. The study of sparse arrays in this work can be considered under two main headings: Analysis and comparison of recently proposed coarray based arrays, and the adaptation of the nonlinear apodization method for linear arrays and its use in sparse linear array design. Recently proposed coarray-based sparse arrays are designed with closed form structures without the need for any optimization and have much higher degrees of freedom (DOF) than a unif...
Citation Formats
İ. Çuğu, “Parallel solution of sparse triangular linear systems on multicore platforms,” M.S. - Master of Science, Middle East Technical University, 2018.