Eric de SturlerSwiss Center for Scientific Computing (SCSC-ETHZ) Swiss Federal Institute of Technology Zurich ETH Zentrum, RZ F-11 CH-8092 Zurich, Switzerland In optimal methods based on the Arnoldi iteration, if a large number of iterations is necessary, the storage requirements become excessive and the iterations too expensive. Therefore, in practice one restarts after a given number of iterations, m, (like GMRES(m)), or one truncates the set of Arnoldi vectors, typically by keeping only the last m vectors (like GCR(m)). However, this often leads to a loss of superlinear convergence or even to stagnation of the convergence. Nested iterative methods [1] and/or more general truncation schemes offer the possibility of near optimal convergence with reasonable memory requirements and low iteration cost, if the right vectors to keep for orthogonalization in future iterations can be selected. Recently proposed strategies seem to focus on removing certain parts of the spectrum. However, these strategies generally assume that the spectrum is in the positive real half plane, and are therefore not generally applicable. Moreover, recent papers by Z. Strakos and A. Greembaum show that even for a favourable spectrum the convergence of full GMRES (which is optimal) can still be arbitrarily bad (stagnating) depending on the eigenvectors of the matrix; i.e. the non-normality plays a large role as well. Therefore, we propose a different strategy. We compute the singular value decomposition of a small matrix (Z) constructed from the iteration parameters, that is, from the Hessenberg matrix in GMRES(m) or from the product of the matrices that describe the projections in the nested method. This singular value decomposition reveals exactly what role the orthogonalization on each arbitrary subspace of the space spanned by the Arnoldi vectors has played in the convergence so far. Where we use the term Arnoldi vectors to indicate both the search vectors generated by GMRES or GCR and the search vectors in the outer iteration if we use a nested method. To be more precise, if we consider one or more vectors defined as the products of the matrix with the Arnoldi vectors as its columns and the left singular vectors of Z, then a function of the corresponding singular values determines how much worse the convergence would have been had this vector or the space spanned by these vectors not been projected out in the previous iterations. This can be generalized to arbitrary subspaces. So this function of the singular values defines the deterioration from the optimal convergence. This information can be used to select the dimension and the basis of the space to be projected out (orthogonalized upon) in future iterations. Preliminary numerical tests indicate that this approach leads to a very effective truncation strategy. [1] E. de Sturler, "Nested Krylov methods based on GCR", Technical Report 93-50, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands, 1993. (accepted Journal of Comp. and Appl. Mathematics, North -Holland)