Back to search

Democritus University of Thrace (DUTH)

Parallel computational methods for solving large linear systems

Abstract

dc:description

In this thesis, numerical methods, based on the algebraic domain decomposition techniques, have been developed for solving large linear systems on high performance computing (HPC) infrastructures. In particular, a class of algebraic domain decomposition preconditioning schemes, using semi-aggregated subdomains, is proposed. Moreover, an interface semi-aggregation process has been proposed for solving the Schur complement linear system. Additionally, a novel two-stage domain decomposition method has been developed for solving large linear systems on hybrid parallel systems. Algebraic domain decomposition preconditioning schemes have been designed, along with a load balancing algorithm, for distributed memory systems with accelerators, such as manycore processors or GPGPUs. The performance of the algebraic domain decomposition preconditioning schemes has been examined in a cloud computing environment. Furthermore, a time-domain decomposition method in conjunction with semi-aggregated subdomains has been proposed. In Chapter 1, an introduction of the basic mathematical elements in the fields of linear algebra and partial differential equations are given. Further, preconditioned iterative methods for solving linear systems are introduced including domain decomposition methods. Moreover, an introduction of the modern parallel systems is provided, while, the scientific computing software libraries and environments, which have been used, are presented. In Chapter 2, the hybrid parallel Multiprojection method (MPM) for solving large linear systems, using semi-aggregated subdomains, is presented. The class of Multiprojection methods are classified in the algebraic domain decomposition methods, where the local linear systems contain both fine and aggregated (coarse) unknowns. In addition, a subspace compression algorithm has been developed for reducing the memory requirements of the Multiprojection method, namely (MPMSC). This algorithm is based on a breadth first search procedure with limited depth, which is performed on the graph corresponding to the already aggregated components. Neighborhoods of aggregated components are resulted by the aforementioned algorithm and each neighborhood is re-aggregated into one component. In Chapter 3, a hybrid parallel Schur complement solver, using an interface semi-aggregation procedure, has been proposed. Additionally, a hybrid parallel two-stage algebraic domain decomposition method, designed appropriately for distributed memory systems with multicore processors, is proposed. The two-stage Multiprojection method (2s-MPM) is based on upper Schur complement techniques, applied to the local linear systems, and two semi-aggregation procedures, one for each stage. The subdomains are assigned to the workstations of the distributed memory system and the first semi-aggregation procedure is performed in order to formulate the local semi-aggregated linear systems related to the workstations. Upper Schur complement techniques have been used for separating the fine components from the aggregated components of each local semi-aggregated linear system. The second semi-aggregation procedure is performed on the fine components of each workstation, leading to the final local linear systems related to the cores of each multicore processor. Furthermore, a subspace compression technique has been combined with the two-stage Multiprojection method (2s-MPMSC), in order to reduce the memory requirements of the method. The aggregated components outside the workstation are re-aggregated by the subspace compression algorithm, which is based on a breadth first search process with limited depth. In Chapter 4, the Multiprojection preconditioning scheme has been re-designed, using preconditioned iterative methods for solving the local linear systems, in order to be appropriate for distributed memory systems with accelerators. In particular, the preconditioned conjugate gradient method in conjunction with the symmetric factored approximate sparse inverse (SFASI) matrix has been used for solving the local linear systems on an Intel Xeon Phi cluster. The SFASI matrices are computed in the preprocessing phase of the preconditioning scheme. The semi-aggregated subdomains are assigned so that each multicore processor and each manycore processor is responsible for solving one local linear system. Moreover, flexible Krylov subspace methods have been used along with the re-designed iterative MPM scheme for solving linear systems on GPU clusters. The flexible GMRES(m) method and the inexact preconditioned conjugate gradient method for unsymmetric and symmetric coefficient matrices, respectively, have been implemented in order to exploit the available computational resources of a GPU cluster. The local iterative schemes include the preconditioned BiCGSTAB (PBiCGSTAB) method enhanced with the modified generic factored approximate sparse inverse (MGenFASpI) matrix for solving the unsymmetric linear systems. Whereas, the preconditioned conjugate gradient method in conjunction with the SFASI matrix is used for solving the symmetric cases. Additionally, a load balancing algorithm has been designed and implemented for distributing the workload among the available multicore processors and GPUs, aiming to exploit simultaneously the two types of computational resources. Hence, each core of the multicore processor is responsible for the computations concerning one local linear system, while, w local linear systems are assigned to each GPU. Furthermore, the various phenomena, related to performance degradation on cloud computing infrastructures, have been examined by conducting numerical experiments on cloud environment. The "noisy neighbor" phenomenon, where multiple virtual processors that are part of the same physical processor are deployed to different users, is a major factor for degradation of the performance on the cloud. The bandwidth and the latency of the software defined virtual networks is also related to the performance. The hardware heterogeneity in the virtual computational resources, for instance the different clock frequency, cache memory and SIMD register units, often cause performance issues. In Chapter 5, a hybrid parallel time-domain decomposition numerical scheme has been designed and implemented for solving parabolic partial differential equations. The proposed method is based on discretization of the time variable with the backward differences or the Crank-Nicolson method, whereas, the spatial variables are discretized by the finite differences method. The linear equations of multiple time steps are grouped in a sparse linear system. Solving the aforementioned linear system in parallel leads to the solution of the parabolic partial differential equation in multiple time steps, concurrently. The parallel preconditioned GMRES(m) (PPGMRES(m)) method in conjunction with the Multiprojection method is used for solving the aforementioned linear system. The local linear systems are solved by a direct method. Solving multiple time steps in parallel enables the better exploitation of supercomputing infrastructures, on the contrary to the traditional methods that compute one time step per iteration. Two different model problems have been solved in order to assess the performance of the proposed scheme on supercomputing infrastructures: a) a two dimensional thin composite plate cooling model problem and b) a heat transfer model problem in three space variables. In Chapter 6, numerical results for the proposed numerical schemes are given. Numerical experiments concerning the scalability of the proposed schemes have been conducted on high performance computing systems, such as the ARIS HPC supercomputing infrastructure, provided by the GRNET. Moreover, the convergence behavior and the performance of the proposed methods have been examined for several model problems. Comparative results with standard methods, proposed by other researchers, are presented. Finally, concluding remarks are provided concerning the proposed schemes as well as propositions for future research.

Degree

thesis:*
Grantor dc:publisher
Democritus University of Thrace (DUTH)
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Moutafis, Vyron
  • Μουτάφης, Βύρων

Subjects

dc:subject × 14

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/49599

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Moutafis, Vyron; Μουτάφης, Βύρων. Parallel computational methods for solving large linear systems. Democritus University of Thrace (DUTH), 2020. http://hdl.handle.net/10442/hedi/49599