Chapter

Cost of Computations Using Krylov Subspace Methods

Jörg Liesen and Zdenek Strakos

in Krylov Subspace Methods

Published in print October 2012 | ISBN: 9780199655410
Published online January 2013 | e-ISBN: 9780191744174 | DOI: http://dx.doi.org/10.1093/acprof:oso/9780199655410.003.0005

Series: Numerical Mathematics and Scientific Computation

Cost of Computations Using Krylov Subspace Methods

Show Summary Details

Preview

Using the Poisson model problem as a motivation, the chapter shows that evaluation of computational cost in computations using Krylov subspace methods depends on unresolved but important issues such as the local distribution of the algebraic error. The chapter discusses principal differences between direct and iterative computations, computational cost of individual iterations, the concept of convergence, and cost of particular computations in contrast with the concept of complexity. These issues, including effects of rounding errors, are then illustrated and developed further using the conjugate gradient method (CG) and the generalised minimal residual method (GMRES). Special attention is paid to the intriguing relationship between spectral information and convergence behaviour, including the role of clustered eigenvalues and, in the Hermitian (positive definite) case, the related sensitivity of the Gauss–Christoffel quadrature. It is further shown that the algebraic error in CG computations tends to have oscillating components. After a brief summary of main numerical stability results concerning CG and GMRES, the chapter ends by pointing out some omitted issues and an outlook to further work.

Keywords: computational cost; particular computations and complexity; CG; GMRES; convergence rate bounds; finite precision behaviour; spectral information and convergence behaviour; delay of convergence; maximal attainable accuracy; local distribution of the algebraic error; backward stability

Chapter.  61463 words.  Illustrated.

Subjects: Applied Mathematics

Full text: subscription required

How to subscribe Recommend to my Librarian

Buy this work at Oxford University Press »

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.