How Fast are Nonsymmetric Matrix Iterations?

Three leading iterative methods for the solution of nonsymmetric systems of linear equations are CGN (the conjugate gradient iteration applied to the normal equations), GMRES (residual minimization in a Krylov space), and CGS (a biorthogonalization algorithm adapted from the biconjugate gradient iteration). Do these methods differ fundamentally in capabilities? If so, which is best under which circumstances? The existing literature, in relying mainly on empirical studies, has failed to confront these questions systematically. In this paper it is shown that the convergence of CGN is governed by singular values and that of GMRES and CGS by eigenvalues or pseudo-eigenvalues. The three methods are found to be fundamentally different, and to substantiate this conclusion, examples of matrices are presented for which each iteration outperforms the others by a factor of size $O(\sqrt N )$ or $O(N)$ where N is the matrix dimension. Finally, it is shown that the performance of iterative methods for a particular mat...