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

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...
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...
LCD codes from tridiagonal Toeplitz matrices
Shi, Minjia; Özbudak, Ferruh; Xu, Li; Solé, Patrick (2021-10-01)
Double Toeplitz (DT) codes are codes with a generator matrix of the form (I,T) with T a Toeplitz matrix, that is to say constant on the diagonals parallel to the main. When T is tridiagonal and symmetric we determine its spectrum explicitly by using Dickson polynomials, and deduce from there conditions for the code to be LCD. Using a special concatenation process, we construct optimal or quasi-optimal examples of binary and ternary LCD codes from DT codes over extension fields.
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.