The most effective iterative methods for solving nonsymmetric linear systems appear to be ones that are based on the two-sided Lanczos algorithm; e.g., QMR and BiCGSTAB. Unfortunately, however, our theoretical understanding of these methods is lacking. Most current analysis makes no assumption about the left starting vector, but it is demonstrated that some such assumption is crucial. Without it, any 3-term recurrence run for no more than (n+2)/2 steps, where n is the size of the matrix, is the two-sided Lanczos algorithm for some left starting vector.
Despite the lack of theory, numerical examples demonstrate that the performance of these methods is not very sensitive to the choice of the left starting vector, if that vector is chosen randomly. We give some ideas as to why, but a full theoretical explanation has yet to be developed.