Denna rapport ("GMRES på en minnesdistribuerad parallelldator med QR-faktorisering") undersöker Krylovmetoder i en distribuerad miljö. Den iterativa metod av intresse i denna rapport är GMRES, så som den presenteras av Saad & Schultz. Denna metod optimerades på två olika sätt för att ge god parallell prestanda. En första optimering gjordes för att anpassa den utsprungliga algoritmen till en distribuerad värld. Vid nästa optimering byttes den kommunikationsintensiva Krylov-kärnan -- Arnoldiprocessen -- ut mot att göra en QR-faktorisering på en tät matris. Detta ger teoretiskt mindre kommunikation men mera beräkningar. Tester gjorda på en IBM SP2 hos PDC, KTH, visade att den QR-baserade algoritmen gav väldigt bra parallell prestanda, medan den parallellt optimerade GMRES hade bättre konvergensegenskaper, något som värderas högt vid valet av iterativ metod. Eftersom den ursprungliga GMRES redan är välanpassade för parallel användning, bekräftar testresultaten att det enda GMRES behöver är lite optimering för att fungera bra i en distribuerad omgivning.
This paper ("GMRES on a distributed-memory multiprocessor system using QR factorisation") looks at Krylov subspace methods in a distributed environment. The iterative method of interest in this paper is the popular GMRES by Saad & Schultz, which was optimised in two different ways to give good parallel performance. The first optimisation involved parallel optimisation of the original algorithm without altering its structure. With the second optimisation, the communicationally heavy Krylov subspace kernel---the Arnoldi process---was replaced by doing QR on a dense matrix. Theoretically, this leads to less communication, but more computations. Numerical experiments on the IBM SP2 at PDC, KTH, shows that the QR-based algorithm yields better parallel performance, but the parallel optimised GMRES has better convergence properties, which is an important factor when selecting an iterative method. Since the original GMRES is already well-suited for parallel usage, the result from the IBM SP2 concludes that GMRES only needs some additional optimisation to work well in a parallel environment.
Upp till sidan
Examensarbeten i datalogi vid SU.