Parallel computation of the diagonal of the inverse of a sparse matrix

Download

index.pdf

Date

2017

Author

Fasllija, Edona

Metadata

Show full item record

Item Usage Stats

251
views

119
downloads

We consider the parallel computation of the diagonal of the inverse of a large sparse matrix. This problem is critical in many applications such as quantum mechanics and uncertainty quantification, where a subset of the entries of the inverse matrix, usually the diagonal, is required. A straightforward approach involves inverting the matrix explicitly and extracting the diagonal of the computed inverse. This approach, however, almost always is too costly for large sparse matrices since the inverse is often dense. In this thesis, we develop a novel parallel algorithm for computing the diagonal of the inverse based on the parallel DS factorization and approximate inverse techniques combined with a special structural dropping strategy step that exploits the peculiar sparsity pattern of the S matrix. We analyze the parallel scalability and performance of the proposed algorithm using sparse matrices from various applications.

Subject Keywords

Sparse matrices, Parallel programming (Computer science).

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Parallel processing of two-dimensional euler equations for compressible flows Doǧru, K.; Aksel, M.h.; Tuncer, İsmail Hakkı (2008-12-01) A parallel implementation of a previously developed finite volume algorithm for the solution of two-dimensional, unsteady, compressible Euler equations is given. The conservative form of the Euler equations is discretized with a second order accurate, one-step Lax-Wendroff scheme. Local time stepping is utilized in order to accelerate the convergence. For the parallel implementation of the method, the solution domain is partitioned into a number of subdomains to be distributed to separate processors for par...
Partitioning and Reordering for Spike-Based Distributed-Memory Parallel Gauss--Seidel Torun, Tugba; Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2022-04-01) Gauss--Seidel (GS) is a widely used iterative method for solving sparse linear sys-tems of equations and also known to be effective as a smoother in algebraic multigrid methods.Parallelization of GS is a challenging task since solving the sparse lower triangular system in GSconstitutes a sequential bottleneck at each iteration. We propose a distributed-memory parallel GS(dmpGS) by implementing a parallel sparse triangular solver (stSpike) based on the Spike algorithm.stSpike d...
Transformation-based metamaterials to eliminate the staircasing error in the finite difference time domain method Ozgun, Ozlem; Kuzuoğlu, Mustafa (Wiley, 2012-07-01) A coordinate transformation technique is introduced for the finite difference time domain method to alleviate the effects of errors introduced by the staircasing approximation of curved geometries that do not conform to a Cartesian grid. An anisotropic metamaterial region, which is adapted to the Cartesian grid and designed by the coordinate transformation technique, is constructed around the curved boundary of the object, and the region occupied between the curved boundary and the inner boundary of the ani...
Bounded operators and complemented subspaces of Cartesian products DJAKOV, PLAMEN; TERZİOĞLU, AHMET TOSUN; Yurdakul, Murat Hayrettin; Zahariuta, V. (2011-02-01) We study the structure of complemented subspaces in Cartesian products X x Y of Kothe spaces X and Y under the assumption that every linear continuous operator from X to Y is bounded. In particular, it is proved that each non-Montel complemented subspace with absolute basis E subset of X x Y is isomorphic to a space of the form E(1) x E(2), where E(1) is a complemented subspace of X and E(2) is a complemented subspace of Y. (C) 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Improved parallel preconditioners for multidisciplinary topology optimisations AKAY, HASAN UMUR; Oktay, E.; Manguoğlu, Murat; Sivas, A. A. (2016-01-01) Two commonly used preconditioners were evaluated for parallel solution of linear systems of equations with high condition numbers. The test cases were derived from topology optimisation applications in multiple disciplines, where the material distribution finite element methods were used. Because in this optimisation method, the equations rapidly become ill-conditioned due to disappearance of large number of elements from the design space as the optimisations progresses, it is shown that the choice for a su...

Citation Formats

E. Fasllija, “Parallel computation of the diagonal of the inverse of a sparse matrix,” M.S. - Master of Science, Middle East Technical University, 2017.