A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers

Date

2021-01-01

Author

Mehrmann, Volker
Manguoğlu, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

267
views

0
downloads

We propose a two-level iterative scheme for solving general sparse linear systems. The proposed scheme consists of a sparse preconditioner that increases the norm of the skew-symmetric part relative to the rest and makes the main diagonal of the coefficient matrix as close to the identity as possible so that the preconditioned system is as close to a shifted skew-symmetric matrix as possible. The preconditioned system is then solved via a particular Minimal Residual Method for Shifted Skew-Symmetric Systems (MRS). This leads to a two-level (inner and outer) iterative scheme where the MRS has short-term recurrences and satisfies an optimality condition. A preconditioner for the inner system is designed via a skew-symmetry-preserving deflation strategy based on the skew-Lanczos process. We demonstrate the robustness of the proposed scheme on sparse matrices from various applications.

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85106666699&origin=inward
https://hdl.handle.net/11511/91104

Journal

Electronic Transactions on Numerical Analysis

DOI

https://doi.org/10.1553/etna_vol54s370

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2018-01-01) We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation define...
A parallel multithreaded sparse triangular linear system solver Cugu, Ilke; Manguoğlu, Murat (Elsevier BV, 2020-07-15) We propose a parallel sparse triangular linear system solver based on the Spike algorithm. Sparse triangular systems are required to be solved in many applications. Often, they are a bottleneck due to their inherently sequential nature. Furthermore, typically many successive systems with the same coefficient matrix and with different right hand side vectors are required to be solved. The proposed solver decouples the problem at the cost of extra arithmetic operations as in the banded case. Compared to the b...
A ROBUST ITERATIVE SCHEME FOR SYMMETRIC INDEFINITE SYSTEMS Manguoğlu, Murat (Society for Industrial & Applied Mathematics (SIAM), 2019-01-01) We propose a two-level nested preconditioned iterative scheme for solving sparse linear systems of equations in which the coefficient matrix is symmetric and indefinite with a relatively small number of negative eigenvalues. The proposed scheme consists of an outer minimum residual (MINRES) iteration, preconditioned by an inner conjugate gradient (CG) iteration in which CG can be further preconditioned. The robustness of the proposed scheme is illustrated by solving indefinite linear systems that arise in t...
An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29) We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...
A tearing-based hybrid parallel sparse linear system solver NAUMOV, Maxim; Manguoğlu, Murat; SAMEH, Ahmed (Elsevier BV, 2010-09-15) We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size ...

Citation Formats

V. Mehrmann and M. Manguoğlu, “A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers,” Electronic Transactions on Numerical Analysis, pp. 370–391, 2021, Accessed: 00, 2021. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85106666699&origin=inward.