ON THE ITERATIVE SOLUTION OF SYSTEMS OF THE FORM A T Ax = A T b + c

Henri Calandra (1) , Serge Gratton (2, 3) , Elisa Riccietti (4) , Xavier Vasseur (5)

1 Total E&P
2 IRIT-APO - Algorithmes Parallèles et Optimisation
3 Toulouse INP - Institut National Polytechnique (Toulouse)
4 ENS de Lyon - École normale supérieure de Lyon
5 ISAE-SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace

Given a full column rank matrix A ∈ R m×n (m ≥ n), we consider a special class of linear systems of the form A ⊤ Ax = A ⊤ b + c with x, c ∈ R n and b ∈ R m. The occurrence of c in the right-hand side of the equation prevents the direct application of standard methods for least squares problems. Hence, we investigate alternative solution methods that, as in the case of normal equations, take advantage of the peculiar structure of the system to avoid unstable computations, such as forming A ⊤ A explicitly. We propose two iterative methods that are based on specific reformulations of the problem and we provide explicit closed formulas for the structured condition number related to each problem. These formula allow us to compute a more accurate estimate of the forward error than the standard one used for generic linear systems, that does not take into account the structure of the perturbations. The relevance of our estimates is shown on a set of synthetic test problems. Numerical experiments highlight both the increased robustness and accuracy of the proposed methods compared to the standard conjugate gradient method. It is also found that the new methods can compare to standard direct methods in terms of solution accuracy.

Mots clés: Linear systems; Conjugate Gradient Method; Forward Error; Least Squares Problems

Domaines: Mathématiques [math]; Informatique [cs]

Henri Calandra, Serge Gratton, Elisa Riccietti, Xavier Vasseur. ON THE ITERATIVE SOLUTION OF SYSTEMS OF THE FORM A T Ax = A T b + c. SIAM Journal on Matrix Analysis and Applications, 2020, pp.1-25. ⟨hal-02943217⟩