A cooperative conjugate gradient method for linear systems permitting multithread implementation of low complexity

Amit Bhaya 1 Pierre-Alexandre Bliman 2 Guilherme Niedu 1 Fernando Pazos 1
1 UFRJ - Universidade Federal do Rio de Janeiro [Rio de Janeiro]
2 SISYPHE - SIgnals and SYstems in PHysiology & Engineering
Inria Paris-Rocquencourt
Abstract : This paper proposes a generalization of the conjugate gradient (CG) method used to solve the equation $Ax=b$ for a symmetric positive definite matrix $A$ of large size $n$. The generalization consists of permitting the scalar control parameters (= stepsizes in gradient and conjugate gradient directions) to be replaced by matrices, so that multiple descent and conjugate directions are updated simultaneously. Implementation involves the use of multiple agents or threads and is referred to as cooperative CG (cCG), in which the cooperation between agents resides in the fact that the calculation of each entry of the control parameter matrix now involves information that comes from the other agents. For a sufficiently large dimension $n$, the use of an optimal number of cores gives the result that the multithread implementation has worst case complexity $O(n^{2+1/3})$ in exact arithmetic. Numerical experiments, that illustrate the interest of theoretical results, are carried out on a multicore computer
Type de document :
Communication dans un congrès
CDC 2012 - 51st IEEE Conference on Decision and Control, Dec 2012, Maui, HI, United States. IEEE, Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, pp.638-643, 2012, 〈10.1109/CDC.2012.6426341〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00761333
Contributeur : Pierre-Alexandre Bliman <>
Soumis le : mercredi 5 décembre 2012 - 12:26:53
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

arxiv

Identifiants

Collections

INRIA | TDS-MACS

Citation

Amit Bhaya, Pierre-Alexandre Bliman, Guilherme Niedu, Fernando Pazos. A cooperative conjugate gradient method for linear systems permitting multithread implementation of low complexity. CDC 2012 - 51st IEEE Conference on Decision and Control, Dec 2012, Maui, HI, United States. IEEE, Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, pp.638-643, 2012, 〈10.1109/CDC.2012.6426341〉. 〈hal-00761333〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

127

Contact


archive-ouverte@inria.fr