Democritus University of Thrace (DUTH)
Parallel computational methods for solving large linear systems
Abstract
dc:descriptionIn 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- Προσυντονισμένες επαναληπτικές μέθοδοι
- Διαχωρισμός του χωρίου
- Παράλληλος προγραμματισμός
- Αριθμητικές μέθοδοι
- Preconditioned iterative methods
- Domain decomposition
- Parallel programming
- Numerical methods
- Μαθηματικά
- Φυσικές Επιστήμες
- Υπολογιστικά μαθηματικά
- Mathematics
- Natural Sciences
- Computational Mathematics
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/49599