A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM

Download

index.pdf

Date

2018-01-01

Author

Torun, F. Sukru
Manguoğlu, Murat
Aykanat, Cevdet

Metadata

Show full item record

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

Item Usage Stats

224
views

97
downloads

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 defined on this graph model, the partitioning objective of minimizing the cutsize directly corresponds to minimizing the sum of interblock inner products between block rows thus leading to an improvement in the eigenvalue spectrum of the iteration matrix. This in turn leads to a significant reduction in the number of iterations required for convergence. Extensive experiments conducted on a large set of matrices confirm the validity of the proposed method against a state-of-the-art method.

Subject Keywords

Row projection methods, Block Cimmino algorithm, Krylov subspace methods, Row inner-product graph, Graph partitioning

URI

https://hdl.handle.net/11511/38983

Journal

SIAM JOURNAL ON SCIENTIFIC COMPUTING

DOI

https://doi.org/10.1137/18m1166407

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A quadtree-based adaptively-refined cartesian-grid algorithm for solution of the euler equations Bulkök, Murat; Aksel, Mehmet Haluk; Department of Mechanical Engineering (2005) A Cartesian method for solution of the steady two-dimensional Euler equations is produced. Dynamic data structures are used and both geometric and solution-based adaptations are applied. Solution adaptation is achieved through solution-based gradient information. The finite volume method is used with cell-centered approach. The solution is converged to a steady state by means of an approximate Riemann solver. Local time step is used for convergence acceleration. A multistage time stepping scheme is used to ...
A parallel sparse algorithm targeting arterial fluid mechanics computations Manguoğlu, Murat; Sameh, Ahmed H.; Tezduyar, Tayfun E. (2011-09-01) Iterative solution of large sparse nonsymmetric linear equation systems is one of the numerical challenges in arterial fluid-structure interaction computations. This is because the fluid mechanics parts of the fluid + structure block of the equation system that needs to be solved at every nonlinear iteration of each time step corresponds to incompressible flow, the computational domains include slender parts, and accurate wall shear stress calculations require boundary layer mesh refinement near the arteria...
A Rayleigh–Ritz Method for Numerical Solutions of Linear Fredholm Integral Equations of the Second Kind Kaya, Ruşen; Taşeli, Hasan (2022-01-01) A Rayleigh–Ritz Method is suggested for solving linear Fredholm integral equations of the second kind numerically in a desired accuracy. To test the performance of the present approach, the classical one-dimensional Schrödinger equation -y″(x)+v(x)y(x)=λy(x),x∈(-∞,∞) has been converted into an integral equation. For a regular problem, the unbounded interval is truncated to x∈ [ - ℓ, ℓ] , where ℓ is regarded as a boundary parameter. Then, the resulting integral equation has been solved and the results are co...
A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers Mehrmann, Volker; Manguoğlu, Murat (2021-01-01) 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...
An algorithm for estimating Box–Cox transformation parameter in ANOVA Dag, Osman; İlk Dağ, Özlem (Informa UK Limited, 2016-8-5) In this study, we construct a feasible region, in which we maximize the likelihood function, by using Shapiro-Wilk and Bartlett's test statistics to obtain Box-Cox power transformation parameter for solving the issues of non-normality and/or heterogeneity of variances in analysis of variance (ANOVA). Simulation studies illustrate that the proposed approach is more successful in attaining normality and variance stabilization, and is at least as good as the usual maximum likelihood estimation (MLE) in estimat...

Citation Formats

F. S. Torun, M. Manguoğlu, and C. Aykanat, “A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM,” SIAM JOURNAL ON SCIENTIFIC COMPUTING, pp. 0–0, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38983.