Keywords: alternating two-stage methods, parallel algorithms, linear systems, block methods, Markov chains.

We consider the linear system

where A is a matrix such that b is in , the range of A. Given a splitting (M nonsingular), a classical iterative method produces the following iteration

where is called the iteration matrix of the method. On the other hand, a two-stage method consists of approximating the linear system (81) by using another iterative procedure (inner iterations). That is, consider the splitting and perform, at each outer step , inner iterations of the iterative procedure induced by this splitting. Thus, the resulting method is

Two-stage iterative methods have been studied, e.g., in [2,3,4]. We know (e.g. from the experiments in [1]) that block iterative methods, including two-stage (or inner-outer) methods are some of the most competitive methods for the solution of Markov chains on sequential computers. In this paper, our study concentrates on two-stage methods, where at each outer iteration the linear system is approximated by alternating iterations. That is, a two-stage iterative process is developed for the solution of the linear system (80), where at each outer iteration the linear system 81 is approximated by using an alternating iterative procedure. More specifically, let be two splittings of the matrix M. In order to approximate the linear system (81), for each and setting , we perform inner iterations of the general class of iterative methods of the form

The alternating two-stage method can be written as follows, for

In a similar manner as the two-stage methods, we say that an alternating two-stage method is stationary when , for all , while an alternating two stage method is non-stationary if different iterations are performed at each outer iterative step . Convergence of these methods, for nonsingular linear systems, is shown for monotone matrices, H-matrices and Hermitian positive definite matrices. Furthermore, for consistent singular linear systems, convergence theorems when the matrix of the linear system is either M-matrix or symmetric positive semidefinite are given.

These methods are suitable for parallel computation. These alternating two-stage methods have been implemented on two different parallel operating systems. One of them is a distributed multiprocessor IBM RS/6000 SP with 8 nodes. These nodes are 120 MHz Power2 Super Chip and are connected through a high performance switch with latency time of 40 microseconds and a bandwidth of 110 Mbytes per second. The second system used is an Ethernet network of six Pentiums IV running Linux and connected through a switch with a bandwidth of 1 Gbit per second. The parallel environment has been managed using the MPI library of parallel routines. The algorithms have been applied to the solution of singular linear systems arising from Markov chain modeling. These experiments demonstrate that the parallel implementation of these methods can solve singular systems of linear equations in substantially less time that the sequential counterparts. Furthermore, different versions of these methods and implementation strategies are explored and their relative merit discussed.

1

T. Dayar, W. J. Stewart, "Comparison of partitioning techniques for two-level iterative methods on large, sparse Markov chains", SIAM Journal on Scientific Computing, 21(5), 1691-1705, 2000. doi:10.1137/S1064827598338159

2

A. Frommer, D. B. Szyld, "H-splittings and two-stage iterative methods", Numerische Mathematik, 63, 345-356, 1992. doi:10.1007/BF01385865

3

V. Migallón, J. Penadés, "Convergence of two-stage iterative methods for Hermitian positive definite matrices", Applied Mathematics Letters, 10(3), 79-83, 1997. doi:10.1016/S0893-9659(97)00039-6

4

V. Migallón, J. Penadés, D. B. Szyld, "Block two-stage methods for singular systems and Markov chains", Numerical Linear Algebra with Applications, 3(5), 413-426, 1996. doi:10.1002/(SICI)1099-1506(199609/10)3:5<413::AID-NLA91>3.0.CO;2-S

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)