Parallel sparse and banded matrix – multiple vectors multiplication

Download

index.pdf

Date

2014

Author

Cincioğlu, Meftun

Metadata

Show full item record

Item Usage Stats

147
views

54
downloads

In this thesis, performance of two important primitives, namely sparse and banded matrix – multiple vectors multiplication are studied. Sparse matrix – multiple vectors multiplication (SpMM) is one of the basic and most time consuming operations in many problems in science and engineering. Hence, any improvement in the performance of SpMM operations has a great impact on the wide spectrum of problems. One of the objectives of this thesis is to improve the performance of parallel SpMM operation by reducing indirect memory access, improving communication pattern, and load balancing. For this purpose, partitioning tools and permutation algorithms are used. Banded matrix – multiple vectors multiplication is used as a primitive operation in iterative solution of banded linear systems or in other applications. An improved method is presented that has an advantage especially for banded matrices having small bandwidth and multiplied by large number of vectors. All these numerical experiments are performed in two different computing platforms.

Subject Keywords

Matrices., Sparse matrices., Banded matrices., Vector processing (Computer science).

URI

http://etd.lib.metu.edu.tr/upload/12617651/index.pdf
https://hdl.handle.net/11511/23981

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Parallel bio-inspired single source shortest path algorithms Arslan, Hilal; Manguoğlu, Murat; Department of Computer Engineering (2017) Real-world shortest path problems that usually dynamically change are challeng- ing and computationally expensive, and earlier studies in the literature require pro- hibitively long time to obtain the solution. To cope with such problems, we introduce novel bio-inspired parallel algorithms based on Physarum Solver. The first proposed algorithm is a fast and efficient parallel Physarum Solver with the objective to find the shortest path for static graphs with positive edge weights. Next, we propose a novel f...
Large sparse matrix-vector multiplication over finite fields Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat; Department of Cryptography (2019) Cryptographic computations such as factoring integers and computing discrete logarithms require solving a large sparse system of linear equations over finite fields. When dealing with such systems iterative solvers such as Wiedemann or Lanczos algorithms are used. The computational cost of both methods is often dominated by successive matrix-vector products. In this thesis, we introduce a new algorithm for computing a large sparse matrix-vector multiplication over finite fields. The proposed algorithm is im...
A two dimensional euler flow solver on adaptive cartesian grids Siyahhan, Bercan; Aksel, Mehmet Haluk; Department of Mechanical Engineering (2008) In the thesis work, a code to solve the two dimensional compressible Euler equations for external flows around arbitrary geometries have been developed. A Cartesianmesh generator is incorporated to the solver. Hence the pre-processing can be performed together with the solution within a single code. The code is written in the C++ programming language and its object oriented capabilities have been exploited to save memory in the data structure developed. The Cartesian mesh is formed by dividing squares succe...
A modular regularized variational multiscale proper orthogonal decomposition for incompressible flows Eroglu, Fatma G.; Kaya Merdan, Songül; Rebholz, Leo G. (Elsevier BV, 2017-10-01) In this paper, we propose, analyze and test a post-processing implementation of a projection-based variational multiscale (VMS) method with proper orthogonal decomposition (POD) for the incompressible Navier-Stokes equations. The projection-based VMS stabilization is added as a separate post-processing step to the standard POD approximation, and since the stabilization step is completely decoupled, the method can easily be incorporated into existing codes, and stabilization parameters can be tuned independe...
Identification of structural non-linearities using describing functions and the Sherman-Morrison method Ozer, Mehmet Bulent; Özgüven, Hasan Nevzat; Royston, Thomas J. (Elsevier BV, 2009-01-01) In this study, a new method for type and parametric identification of a non-linear element in an otherwise linear structure is introduced. This work is an extension of a previous study in which a method was developed to localize non-linearity in multi-degree of freedom systems and to identify type and parameters of the non-linear element when it is located at a ground connection of the system. The method uses a describing function approach for representing the non-linearity in the structure. The describing ...

Citation Formats

M. Cincioğlu, “Parallel sparse and banded matrix – multiple vectors multiplication,” M.S. - Master of Science, Middle East Technical University, 2014.