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

MPI+OpenMP implementation of the BiCGStab method with explicit preconditioning for the numerical solution of sparse linear systems

Authors

  • I.E. Kaporin
  • O.Yu. Milyukova

Keywords:

iterative solution of linear systems
sparse matrices
incomplete inverse triangular factorization
parallel preconditioning
BiCGStab method

Abstract

A preconditioner for a large sparse nonsymmetric positive definite matrix is considered on the basis of its approximate inverse in the form of product of a lower triangular sparse matrix by an upper triangular matrix. For the class of matrices being considered, a new preconditioning based on the approximate block Jacobi with incomplete inverse LU-factorization preconditioning is proposed. For a parallel implementation of the corresponding preconditioned BiCGStab algorithm, the MPI+OpenMP techniques are used. The timing results obtained for the MPI+OpenMP and MPI implementations of the proposed preconditioning and for the Jacobi preconditioning used with the BiCGStab are compared using several test problems from the SuiteSparse collection (formerly known as the University of Florida sparse matrix collection).

New computational technologies

Downloads

Published

2020-01-11

Issue

Vol. 20 (2019): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biographies

I.E. Kaporin

Dorodnicyn Computing Centre of RAS
• Chief Researcher

O.Yu. Milyukova

Keldysh Institute of Applied Mathematics of RAS
• Leading Researcher

References

  1. I. E. Kaporin, “A Preconditioned Conjugate-Gradient Method for Solving Discrete Analogs of Differential Problems,” Differ. Uravn. 26 (7), 1225-1236 (1990) [Differ. Equ. 26 (12), 897-906 (1990)].
  2. I. E. Kaporin, “New Convergence Results and Preconditioning Strategies for the Conjugate Gradient Method,” Numer. Linear Algebra Appl. 1 (2), 179-210 (1994).
  3. I. E. Kaporin and O. Yu. Milyukova, Incomplete Inverse Triangular Factorization in Parallel Algorithms of Preconditioned Conjugate Gradient Methods , Preprint No. 037 (Keldysh Institute of Applied Mathematics, Moscow, 2017).
  4. I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Explicitly Preconditioned Conjugate Gradient Method , Preprint No. 008 (Keldysh Institute of Applied Mathematics, Moscow, 2018).
  5. I. E. Kaporin and O. Yu. Milyukova, “MPI+OpenMP Parallel Implementation of the Conjugate Gradient Method with Factorized Explicit Preconditioners,” Voprosy Atomn. Nauki Tekhniki, Ser.: Mat. Mod. Fiz. Proc., No. 4, 57-69 (2018).
  6. T. A. Davis and Y. Hu, “The University of Florida Sparse Matrix Collection,” ACM Trans. Math. Softw. 38 (2011).
    doi 10.1145/2049662.2049663
  7. I. E. Kaporin and O. Yu. Milyukova, “Massively Parallel Preconditioned Conjugate Gradient Algorithm for the Numerical Solution of Linear Algebraic Equations,” in Optimization and Applications (Comput. Center Ross. Akad. Nauk, Moscow, 2011), Issue 2, pp. 132-157.
  8. P. A. Knight, “The Sinkhorn-Knopp Algorithm: Convergence and Applications,” SIAM J. Matrix Anal. Appl. 30 (1), 261-275 (2008).
  9. I. E. Kaporin, “Iterative Solution of Linear Systems Using the Incomplete Inverse Triangular Decomposition,” in Direct and Inverse Problems of Mathematical Physics (Mosk. Gos. Univ., Moscow, 1991), pp. 71-77.
  10. D. S. Kershaw, “The Incomplete Cholesky-Conjugate Gradient Method for the Iterative Solution of Systems of Linear Equations,” J. Comput. Phys. 26 (1), 43-65 (1978).
  11. H. Anzt, T. K. Huckle, J. Br854ckle, and J. Dongarra, “Incomplete Sparse Approximate Inverses for Parallel Preconditioning,” Parallel Comput. 71, 1-22 (2018).
  12. H. A. van der Vorst, “Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comput. 13 (2), 631-644 (1992).
  13. T. F. Chan and T. Szeto, “Composite Step Product Methods for Solving Nonsymmetric Linear Systems,” SIAM J. Sci. Comput. 17 (6), 1491-1508 (1996).
  14. Y. Saad and M. H. Schultz, “GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comput. 7 (3), 856-869 (1986).
  15. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, 1981).
  16. I. E. Kaporin, “Localization of the Eigenvalues of a Pencil of Positive Definite Matrices,” Zh. Vychisl. Mat. Mat. Fiz. 48 (11), 1923-1931 (2008) [Comput. Math. Math. Phys. 48 (11), 1917-1926 (2008)].
  17. I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Implementation of BiCGStab Method with Factorized Explicit Preconditioner , Preprint No. 047 (Keldysh Institute of Applied Mathematics, Moscow, 2019).