A cooperative conjugate gradient method for linear systems permitting efficient multi-thread implementation

Abstract : This paper revisits, in a multi-thread context, the so-called mul-tiparameter or block conjugate gradient (BCG) methods, first proposed as sequential algorithms by O'Leary and Brezinski, for the solution of the linear system Ax = b, for an n-dimensional symmetric positive definite matrix A. Instead of the scalar parameters of the classical CG algorithm, which minimizes a scalar functional at each iteration, multiple descent and conjugate directions are updated simultaneously. Implementation involves the use of multiple threads and the algorithm is referred to as cooperative CG (CCG) in order to emphasize that each thread now uses information that comes from the other threads. It is shown that for a sufficiently large matrix dimension n, the use of an optimal number of threads results in a worst case flop count of O(n 7/3) in exact arithmetic. Numerical experiments on a multicore, multi-thread computer , for synthetic and real matrices, illustrate the theoretical results.
Type de document :
Article dans une revue
Computational and Applied Mathematics, Springer Verlag, 2017, pp.1-28. 〈10.1007/s40314-016-0416-7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01558765
Contributeur : Pierre-Alexandre Bliman <>
Soumis le : lundi 10 juillet 2017 - 01:57:57
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Fichier

bbnp16b.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Amit Bhaya, Pierre-Alexandre Bliman, Guilherme Niedu, Fernando Pazos. A cooperative conjugate gradient method for linear systems permitting efficient multi-thread implementation. Computational and Applied Mathematics, Springer Verlag, 2017, pp.1-28. 〈10.1007/s40314-016-0416-7〉. 〈hal-01558765〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

48