A New multi-threaded and recursive direct algorithm for parallel solution of sparse linear systems

Download
2013
Bölükbaşı, Ercan Selçuk
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 linear systems effectively in parallel. In this thesis, a new direct multi-threaded and recursive algorithm based on DS factorization to solve sparse linear systems will be introduced. The algorithmic challenges of this approach will be studied on matrices from different application domains. The advantages and disadvantages of variations of the algorithm on different matrices will be discussed. Specifically, we study the effects of changing number of threads, degree of diagonal dominance, the usage of sparse right hand side solution and various methods used to find the exact solution using the reduced system. Furthermore, comparisons will be made against a well known direct parallel sparse solver.

Suggestions

Parallel solution of sparse triangular linear systems on multicore platforms
Çuğu, İlke; Manguoğlu, Murat; Department of Computer Engineering (2018)
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 ...
A New Design Approach for Rapid Evaluation of Structural Modifications Using Neural Networks
Demirkan, O.; Olceroglu, E.; BAŞDOĞAN, FATMA İPEK; Özgüven, Hasan Nevzat (2013-02-01)
Design optimization of structural systems is often iterative, time consuming and is limited by the knowledge of the designer. For that reason, a rapid design optimization scheme is desirable to avoid such problems. This paper presents and integrates two design methodologies for efficient conceptual design of structural systems involving computationally intensive analysis. The first design methodology used in this paper is structural modification technique (SMT). The SMT utilizes the frequency response funct...
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...
A Multithreaded Recursive and Nonrecursive Parallel Sparse Direct Solver
Bölükbaşı, Ercan Selçuk (2016-01-01)
Sparse linear system of equations often arises after discretization of the partial differential equations (PDEs) such as computational fluid dynamics, material science, and structural engineering. There are, however, sparse linear systems that are not governed by PDEs, some examples of such applications are circuit simulations, power network analysis, and social network analysis. For solution of sparse linear systems one can choose using either a direct or an iterative method. Direct solvers are based on so...
The Fast Multipole Method for Sparse Solution of Linear Inverse Scattering Problems
Miran, Emre Alp; Koç, Seyit Sencer (2018-11-02)
The sparse solution for the linear inverse problems provide useful results for many fundamental engineering applications such as radar imaging. The studies in the literature has shown that the computational methods for the sparse solution tend to be slow as the imaging problem gets electromagnetically large, therefore the image reconstruction gets harder for the existing computational resources. The fast multipole method (FMM) can reduce the number of operations and the memory requirement for the solution o...
Citation Formats
E. S. Bölükbaşı, “A New multi-threaded and recursive direct algorithm for parallel solution of sparse linear systems,” M.S. - Master of Science, Middle East Technical University, 2013.