Algorithmic bombardment for the iterative solution of linear systems: A poly-iterative approach

• Published in: Journal of computational and applied mathematics 1996-11, Vol.74 (1), p.91-109
• Main Authors: Barrett, Richard, Berry, Michael, Dongarra, Jack, Eijkhout, Victor, Romine, Charles
• Format: Article
• Language: English
• Subjects: Algorithmic bombardment; Exact sciences and technology; Iterative methods; Linear systems of equations; Mathematics; Methods of scientific computing (including symbolic computation, algebraic computation); Numerical analysis; Numerical analysis. Scientific computation; Numerical linear algebra; Partial differential equations, boundary value problems; Poly-iterative approach; Sciences and techniques of general use
• ISSN: 0377-0427; 1879-1778
• DOI: 10.1016/0377-0427(96)00019-2

Many algorithms employing short recurrences have been developed for iteratively solving linear systems. Yet when the matrix is nonsymmetric or indefinite, or both, it is difficult to predict which method will perform best, or indeed, converge at all. Attempts have been made to classify the matrix properties for which a particular method will yield a satisfactory solution, but “luck” still plays large role. This report describes the implementation of a poly-iterative solver. Here we apply three algorithms simultaneously to the system, in the hope that at least one will converge to the solution. While this approach has merit in a sequential computing environment, it is even more valuable in a parallel environment. By combining global communications, the cost of three methods can be reduced to that of a single method.