Analysis of parallel preconditioned conjugate gradient algorithms

Abstract

The conjugate gradient method is an iterative technique used to solve systems of linear equations. The paper analyzes the performance of parallel preconditioned conjugate gradient algorithms. First, a theoretical model is proposed for estimation of the complexity of PPCG method and a scalability analysis is done for three different data decomposition cases. Computational experiments are done on IBM SP4 computer and some results are presented.. It is shown that theoretical predictions agree well with computational results.

Jungtinių gradientų metodas yra iteracinis algoritmas, kuris naudojamas tiesinių simetrinių lygčių sistemų sprendimui. Šiame darbe nagrinėjame lygiagretųjį neišreikštinį jungtinių gradientų algoritmą. Pirmiausia pateiktas teorinis modelis, leidžiantis įvertinti šio metodo skaičiavimo sudėtingumą ir atlikta algoritmo išplečiamumo analizė, kai duomenų matrica skaidoma naudojant vienmatę, dvimatę ir trimatę topologijas. Skaičiavimo eksperimentai atlikti IBM SP4 kompiuteriu, pateikiami šių eksperimentų rezultatai. Parodyta, kad jie artimi teorinio modelio prognozėms.