Differentiating the Method of Conjugate Gradients

Serge Gratton (1, 2, 3) , David Titley-Peloquin (1, 4) , Philippe Toint (5) , Jean Tshimanga Ilunga (1, 2)

1 IRIT-APO - Algorithmes Parallèles et Optimisation
2 CERFACS - Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique
3 Toulouse INP - Institut National Polytechnique (Toulouse)
4 McGill University = Université McGill [Montréal, Canada]
5 NaXys - Namur Center for Complex Systems [Namur]

The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations $Ax=b$, where $A\in\Re^{n\times n}$ is symmetric positive definite. Let $x_k$ denote the $k$th iterate of CG. This is a nonlinear differentiable function of $b$. In this paper we obtain expressions for $J_k$, the Jacobian matrix of $x_k$ with respect to $b$. We use these expressions to obtain bounds on $\|J_k\|_2$, the spectral norm condition number of $x_k$, and discuss algorithms to compute or estimate $J_kv$ and $J_k^Tv$ for a given vector $v$.

Mots clés: conjugate gradients algorithm; Lanczos algorithm; perturbation analysis; lineariza-tion; automatic differentiation

Domaines: Informatique [cs]

Serge Gratton, David Titley-Peloquin, Philippe Toint, Jean Tshimanga Ilunga. Differentiating the Method of Conjugate Gradients. SIAM Journal on Matrix Analysis and Applications, 2014, 35 (1), pp.110--126. ⟨10.1137/120889848⟩. ⟨hal-03224134⟩