Product Hybrid Block GMRES For Nonsymmetrical Linear Systems With Multiple Right-hand Sides

In the field of information theory, cybernetics and econometrics, linear systems with multiple right-hand sides attract much interest. Block GMRES (BGMRES) is one of the most effective iterative algorithms for solving such problems. Unfortunately, its computational cost increases significantly per iteration as the number of steps increases, frequently rendering the method impractical. To overcome the difficulty, restarting scheme or hybrid scheme may be employed. In this paper a global property, call the complementary behavior, of the restarted BGMRES is studied. It is shown that the residual polynomials from different cycles can complement with each other in reducing the residual. Based on this property, a product hybrid block GMRES is proposed.According to the complementary behavior of restarted BGMRES, the residual vectors resulted from different cycles are partial to different eigenvectors. In consequence, the residual polynomials of successive restarting cycles differ from each other clearly. On the other hand, the product of the polynomials can make a balance in each direction of the eigenvectors. By employing the product polynomial to implement the Richardson iteration, the product hybrid BGMRES improves the convergence of the residual vector significantly. Numerical experiments also indicate that the new algorithm has better practical performance and lower memory requirements than other block methods for the solution of systems with multiple right-hand sides.