Linearizing the Method of Conjugate Gradients

Serge Gratton; David Titley-Peloquin; Philippe Toint; Jean Tshimanga Ilunga

doi:10.1137/120889848

Linearizing the Method of Conjugate Gradients

Serge Gratton, David Titley-Peloquin, Philippe Toint, Jean Tshimanga Ilunga

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

63 Téléchargements (Pure)

Résumé

The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.

langue originale	Anglais
Pages (de - à)	110-126
journal	SIAM Journal on Matrix Analysis and Applications
Volume	35
Numéro de publication	1
Date de mise en ligne précoce	14 févr. 2014
Les DOIs	https://doi.org/10.1137/120889848
Etat de la publication	Publié - 2014

Accès au document

10.1137/120889848

74875Accepted author manuscript, 345 KB

4 Citations
1 Article

Observations Thinning In Data Assimilation Computations
Gratton, S., Rincon-Camacho, M., Simon, E. & Toint, P., 2015, Dans: EURO Journal on Computational Optimization. 3, p. 31-51
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

File

1 Actif

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. & TOINT, P.
1/01/87 → …
Projet: Axe de recherche

1 Discours invité
1 Présentation orale
1 Recherche/Enseignement dans une institution externe

A primal-dual approach of weak-constrained variational data assimilation: (Iterate) History matters
Philippe Toint (Orateur)
13 oct. 2017
Activité: Discours ou présentation › Discours invité
Data Assimilation for Weather Forecasting: Reducing the Curse of Dimensionality
Philippe Toint (Orateur invité)
1 déc. 2015
Activité: Discours ou présentation › Présentation orale
University of Oxford
Philippe Toint (Chercheur visiteur)
14 nov. 2013 → 17 nov. 2013
Activité: Visite d'une organisation externe › Recherche/Enseignement dans une institution externe

Contient cette citation

@article{c047f6d1df644c8fa72502cd464fb1a9,

title = "Linearizing the Method of Conjugate Gradients",

abstract = "The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.",

keywords = "linear algebra, conjugate gradients, sesnistivity analysis",

author = "Serge Gratton and David Titley-Peloquin and Philippe Toint and {Tshimanga Ilunga}, Jean",

year = "2014",

doi = "10.1137/120889848",

language = "English",

volume = "35",

pages = "110--126",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Linearizing the Method of Conjugate Gradients

AU - Gratton, Serge

AU - Titley-Peloquin, David

AU - Toint, Philippe

AU - Tshimanga Ilunga, Jean

PY - 2014

Y1 - 2014

N2 - The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.

AB - The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.

KW - linear algebra

KW - conjugate gradients

KW - sesnistivity analysis

U2 - 10.1137/120889848

DO - 10.1137/120889848

M3 - Article

SN - 0895-4798

VL - 35

SP - 110

EP - 126

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 1

ER -

Linearizing the Method of Conjugate Gradients

Résumé

Accès au document

Empreinte digitale

Résultat de recherche

Observations Thinning In Data Assimilation Computations

Projets

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Activités

A primal-dual approach of weak-constrained variational data assimilation: (Iterate) History matters

Data Assimilation for Weather Forecasting: Reducing the Curse of Dimensionality

University of Oxford

Contient cette citation