Parallelizable restarted iterative methods for nonsymmetric linear systems. Part 1: Theory

Large sparse nonsymmetric problems of the form Au = b are frequently solved using restarted conjugate gradient-type algorithms such as the popular GCR and GMRES algorithms. In this study the authors define a new class of algorithms which generate the same iterates as the standard GMRES algorithm but require as little as half of the computational expense. This performance improvement is obtained by using short economical three-term recurrences to replace the long recurrence used by GMRES. The new algorithms are shown to have good numerical properties in typical cases, and the new algorithms may be easily modified to be as numerically safe as standard GMRES. Numerical experiments with these algorithms are given in Part 2, in which they demonstrate the improved performance of the new schemes on different computer architectures