DOI: https://doi.org/10.26089/NumMet.v16r109

Parallel forming of preconditioners based on the approximation of the Sherman-Morrison inversion formula

Authors

  • I.O. Arushanyan
  • A.K. Novikov
  • S.P. Kopysov

Keywords:

linear systems
explicit preconditioning
Sherman-Morrison formula
parallel computing
graphics accelerators

Abstract

Acceleration of preconditioned bi-conjugate gradient stabilized (BiCGStab) methods with preconditioners based on the matrix approximation by the Sherman-Morrison inversion formula is studied. A new form of the parallel algorithm using matrix-vector products to generate preconditioning matrices is proposed. A parallelization efficiency of the most resource-intensive operations of such preconditioners on multi-core central and graphics processing units (CPUs and GPUs) is shown.

New computational technologies

Downloads

Published

2015-02-26

Issue

Vol. 16 (2015): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

I.O. Arushanyan

Institute of Mechanics of UB RAS (IM UB RAS)
• Junior Researcher

A.K. Novikov

Institute of Mechanics of UB RAS (IM UB RAS)
• Head of Laboratory

S.P. Kopysov

Institute of Mechanics of UB RAS (IM UB RAS)
• Senior Researcher

References

  1. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003).
  2. R. Li and Y. Saad, “GPU-Accelerated Preconditioned Iterative Linear Solvers,” J. Supercomput. 63 (2), 443-466 (2013).
  3. M. Benzi, “Preconditioning Techniques for Large Linear Systems: A Survey,” J. Comput. Phys. 182 (2), 418-477 (2002).
  4. L. Yu. Kolotilina and A. Yu. Yeremin, “Factorized Sparse Approximate Inverse Preconditionings I: Theory,” SIAM J. Matrix Anal. Appl. 14 (1), 45-58 (1993).
  5. M. J. Grote and T. Huckle, “Parallel Preconditioning with Sparse Approximate Inverses,” SIAM J. Sci. Comput. 18 (3), 838-853 (1997).
  6. R. Bru, J. Cerdán, J. Marín, and J. Mas, “Preconditioning Sparse Nonsymmetric Linear Systems with the Sherman-Morrison Formula,” SIAM J. Sci. Comput. 25 (2), 701-715 (2003).
  7. J. Sherman and W. J. Morrison, “Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix,” Ann. Math. Stat. 21 (1), 124-127 (1950).
  8. N. S. Nedozhogin, A. S. Sarmakeeva, and S. P. Kopysov, “Sherman-Morrison High-Performance Algorithm for Matrix Inversion on GPU,” Vestn. South Ural Univ., Ser.: Vychisl. Mat. Inform. 3 (2), 101-108 (2014).
  9. S. Kopysov, I. Kuzmin, N. Nedozhogin, et al., “Scalable Hybrid Implementation of the Schur Complement Method for Multi-GPU Systems,” J. Supercomput. 69 (1), 81-88 (2014).
  10. S. P. Kopysov, I. M. Kuzmin, N. S. Nedozhogin, et al., “Parallel Implementation of a Finite-Element Algorithms on a Graphics Accelerator in the Software Package FEStudio,” Komp’yut. Issled. Model. 6 (1), 79-97 (2014).