CARP-CG

CARP-CG is a conjugate gradient (CG) acceleration of CARP, which was introduced by the authors as a robust block-parallel scheme for sparse linear systems. CARP performs Kaczmarz (KACZ) row projections within the blocks, and the results from the separate blocks are merged by averaging, for each component, its updated values from the different blocks. The averaging operations are equivalent to a sequence of certain KACZ row projections in some superspace (the “averaging projections”), and so CARP is equivalent to KACZ with cyclic relaxation parameters in that superspace. The CG-acceleration of CARP is based on a generalization of the (sequential) CGMN algorithm of {\itA. Björck} and {\itT. Elfving} [BIT, Nord. Tidskr. Inf.-behandl. 19, 145-1-63 (1979; Zbl 0409.65022)], which accelerates KACZ by running it in a double sweep on the equations of a linear system, using a fixed relaxation parameter. CGMN is generalized to allow cyclic relaxation parameters, so the resulting method, called CGMNC, can be applied in the superspace. The averaging projections in the superspace can be done in any order, so CGMNC in the superspace can be implemented in the regular space by using CARP in a double sweep. The resulting algorithm, CARP-CG, is as robust as CARP but converges significantly faster. CARP-CG is compared with restarted GMRES, Bi-CGSTAB and CGS, with and without various preconditioners, on some stiff linear systems derived from convection dominated elliptic partial differential equations. The results indicate that CARP-CG is very robust and its runtime is very competitive with the other methods. A scaled version of CGNR was also tested, and it was as robust as CARP-CG, but slower.


References in zbMATH (referenced in 10 articles , 1 standard article )

Showing results 1 to 10 of 10.
Sorted by year (citations)

  1. Dastour, Hatef; Liao, Wenyuan: An optimal 13-point finite difference scheme for a 2D Helmholtz equation with a perfectly matched layer boundary condition (2021)
  2. Gordon, Dan; Gordon, Rachel: CADD: a seamless solution to the domain decomposition problem of subdomain boundaries and cross-points (2020)
  3. Gordon, Dan: A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates (2018)
  4. Li, Y.; Han, Bo; Métivier, L.; Brossier, R.: Optimal fourth-order staggered-grid finite-difference scheme for 3D frequency-domain viscoelastic wave modeling (2016)
  5. Gordon, Dan; Gordon, Rachel; Turkel, Eli: Compact high order schemes with gradient-direction derivatives for absorbing boundary conditions (2015)
  6. Turkel, Eli; Gordon, Dan; Gordon, Rachel; Tsynkov, Semyon: Compact 2D and 3D sixth order schemes for the Helmholtz equation with variable wave number (2013)
  7. Gordon, Dan; Gordon, Rachel: Parallel solution of high frequency Helmholtz equations using high order finite difference schemes (2012)
  8. Elble, Joseph M.; Sahinidis, Nikolaos V.; Vouzis, Panagiotis: GPU computing with Kaczmarz’s and other iterative algorithms for linear systems (2010)
  9. Gordon, Dan; Gordon, Rachel: CARP-CG: A robust and efficient parallel solver for linear systems, applied to strongly convection dominated PDEs (2010)
  10. Gordon, Dan; Gordon, Rachel: Row scaling as a preconditioner for some nonsymmetric linear systems with discontinuous coefficients (2010)