Author(s) :
Ute Kandler
,
Christian Schröder
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 10-2013
MSC 2000
- 65F15 Eigenvalues, eigenvectors
-
65F25 Orthogonalization
Abstract :
In numerous recent applications including tensor computations, compressed sensing and mixed precision arithmetics vector operations like summing, scaling, or matrix-vector multiplication are subject to inaccuracies whereas inner products are exact.
We investigate the behavior of Arnoldi's method for Hermitian matrices under these circumstances.
We introduce a special purpose variant of Gram Schmidt orthogonalization and prove bounds on the distance to orthogonality of the now-not-anymore orthogonal Krylov subspace basis.
This Gram Schmidt variant additionally implicitly provides an exactly orthogonal basis.
In the second part we perform a backward error analysis and show that
this exactly orthogonal basis satisfies a Krylov relation for a perturbed system matrix -- even in the Hermitian case. We prove bounds for the norm of the backward error which is shown to be on the level of the accuracy of the vector operations. Care is taken to avoid problems in case of near breakdowns.
Finally, numerical experiments confirm the applicability of the method and of the proven bounds.
Keywords :
inexact matrix-vector operations, Gram Schmidt orthogonalization, loss of orthogonality, Arnoldi's method, Krylov relation, backward error bounds