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

Download
2017
Fasllija, Edona
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. 

Suggestions

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...
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
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.