Row Projection Methods for Large Nonsymmetric Linear Systems

Publisher Website
Google Scholar
Abstract
Three conjugate gradient accelerated row projection (RP) methods for nonsymmetric linear systems are presented and their properties described. One method is based on Kaczmarz’s method and has an iteration matrix that is the product of orthogonal projectors; another is based on Cimmino’s method and has an iteration matrix that is the sum of orthogonal projectors. A new RP method, which requires fewer matrix-vector operations, explicitly reduces the problem size, is error reducing in the two-norm, and consistently produces better solutions than other RP algorithms, is also introduced. Using comparisons with the method of conjugate gradient applied to the normal equations, the properties of RP methods are explained. A row partitioning approach is described that yields parallel implementations suitable for a wide range of computer architectures, requires only a few vectors of extra storage, and allows computing the necessary projections with small errors. Numerical testing verifies the robustness of this approach and shows that the resulting algorithms are competitive with other nonsymmetric solvers in speed and efficiency.