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

Research output: Contribution to journal › Article › peer-review

63 Downloads (Pure)

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.

Original language	English
Pages (from-to)	110-126
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	35
Issue number	1
Early online date	14 Feb 2014
DOIs	https://doi.org/10.1137/120889848
Publication status	Published - 2014

Keywords

linear algebra
conjugate gradients
sesnistivity analysis

Access to 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, In: EURO Journal on Computational Optimization. 3, p. 31-51
Research output: Contribution to journal › Article › peer-review

File

1 Active

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization
Sartenaer, A. & TOINT, P.
1/01/87 → …
Project: Research Axis

1 Invited talk
1 Oral presentation
1 Research/Teaching in a external institution

A primal-dual approach of weak-constrained variational data assimilation: (Iterate) History matters
Philippe Toint (Speaker)
13 Oct 2017
Activity: Talk or presentation types › Invited talk
Data Assimilation for Weather Forecasting: Reducing the Curse of Dimensionality
Philippe Toint (Invited speaker)
1 Dec 2015
Activity: Talk or presentation types › Oral presentation
University of Oxford
Philippe Toint (Visiting researcher)
14 Nov 2013 → 17 Nov 2013
Activity: Visiting an external institution types › Research/Teaching in a external institution

Cite this

@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

Abstract

Keywords

Access to Document

Fingerprint

Research output

Observations Thinning In Data Assimilation Computations

Projects

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Activities

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

Cite this