Minimizing synchronization in IDR(s)

作者：Collignon Tijmen P; van Gijzen Martin B^*

来源：Numerical Linear Algebra with Applications, 2011, 18(5): 805-825.

DOI：10.1002/nla.764

• iterative methods
• numerical linear algebra
• nonsymmetric linear systems
• IDR(s)
• cluster and Grid computing
• performance model

IDR(s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR(s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so-called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi-cluster environments. Finally, a methodology is presented for a-priori estimation of the optimal value of s using only problem and machine-based parameters. Numerical experiments applied to a 3D convection-diffusion problem are performed on the DAS-3 Grid computer, demonstrating the effectiveness of our approach.

• 出版日期2011-10