Parallel asynchronous iterative algorithms exhibit features that are extremely well-suited for Grid computing, such as lack of synchronization points. Unfortunately, they also suffer from slow convergence rates. In this paper we propose using asynchronous methods as a coarse-grained preconditioner in a flexible iterative method, where the preconditioner is allowed to change in each iteration step. A full implementation of the algorithm is presented using Grid middleware that allows for both synchronous and asynchronous communication. Advantages and disadvantages of the approach are discussed. Numerical experiments on heterogeneous computing hardware demonstrate the effectiveness of the proposed algorithm on Grid computers, with application to large 2D and 3D bubbly flow problems.
AxelssonO
(1994) Iterative Solution Methods. New York: Cambridge University Press.
2.
BahiJMContassot-VivierSCouturierR (2002) Asynchronism for iterative algorithms in a global computing environment. In: HPCS ’02: Proceedings of the 16th Annual International Symposium on High Performance Computing Systems and Applications. Washington, DC: IEEE Computer Society Press, pp. 90–97.
3.
BahiJMContassot-VivierSCouturierR (2005) Evaluation of the asynchronous iterative algorithms in the context of distant heterogeneous clusters. Parallel Computing31: 439–461.
4.
BazDE (1996) A method of terminating asynchronous iterative algorithms on message passing systems. Parallel Algorithms and Applications9: 153–158.
5.
BazDESpiteriPMiellouJCGazenD (1996) Asynchronous iterative algorithms with flexible communication for nonlinear network flow problems. Journal of Parallel and Distributed Computing38: 1–15.
6.
BertsekasDPTsitsiklisJN (1989) Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice-Hall. (Republished by Athena Scientific, 1997.).
7.
BjörckÅ (1967) Solving linear least squares problems by Gram–Schmidt orthogonalization. BIT7: 1–21.
8.
CollignonTPvan GijzenMB (2010) Solving large sparse linear systems efficiently on Grid computers using an asynchronous iterative method as a preconditioner. In: KreissGLötstedtPMålqvistANeytchevaM (Eds.), Numerical Mathematics and Advanced Applications 2009: Proceedings of ENUMATH 2009, the 8th European Conference on Numerical Mathematics and Advanced Applications, Uppsala, July 2009. Berlin: Springer, pp. 261–268.
9.
CouturierRDenisCJézéquelF (2008) GREMLINS: a large sparse linear solver for grid environment. Parallel Computing34: 380–391.
10.
CouturierRDomasS (2007) CRAC: a Grid environment to solve scientific applications with asynchronous iterative algorithms. In: 21th IEEE and ACM International Symposium on Parallel and Distributed Processing Symposium, IPDPS’2007. Long Beach, CA: IEEE Computer Society Press, pp. 289–296.
11.
DanielJGraggWBKaufmanLStewartGW (1976) Reorthogonalization and stable algorithms for updating the Gram–Schmidt QR factorization. Mathematics of Computation30: 772–795.
12.
EisenstatSCElmanHCSchultzMH (1983) Variational iterative methods for nonsymmetric systems of linear equations. SIAM Journal on Numerical Analysis20: 345–357.
13.
FrommerASzyldDB (1998) Asynchronous iterations with flexible communication for linear systems. Calculateurs Parallèles Réseaux et Systèmes Répartis10: 421–429.
14.
FrommerASzyldDB (2000) On asynchronous iterations. Journal of Computational and Applied Mathematics123: 201–216.
15.
GroppWLuskEThakurR (1999) Using MPI-2: Advanced Features of the Message-Passing Interface. Cambridge, MA: MIT Press.
16.
HestenesMRStiefelE (1952) Methods of conjugate gradients for solving linear systems. Journal of Research of National Bureau Standards49: 409–436.
17.
MiellouJCBazDESpiteriP (1998) A new class of asynchronous iterative algorithms with order intervals. Mathematics of Computation67: 237–255.
TangJMVuikC (2007a) Efficient deflation methods applied to 3-D bubbly flow problems. Electronic Transactions on Numerical Analysis26: 330–349.
22.
TangJMVuikC (2007b) On deflation and singular symmetric positive semi-definite matrices. Journal of Computational and Applied Mathematics206: 603–614.
23.
van der PijlSSegalAVuikCWesselingP (2005) A mass-conserving Level-set method for modelling of multi-phase flows. International Journal for Numerical Methods in Fluids47: 339–361.
24.
van der VorstHAVuikC (1994) GMRESR: a family of nested GMRES methods. Numerical Linear Algebra with Applications1: 369–386.
25.
van KanJ (1986) A second-order accurate pressure correction scheme for viscous incompressible flow. SIAM Journal on Scientific and Statistical Computing7: 870–891.
26.
YarKhanASeymourKSagiKShiZDongarraJ (2006) Recent developments in GridSolve. International Journal of High Performance Computing Applications20: 131–141.
