Deterministic and stochastic acceleration techniques for Richardson-type iterations Open Access
Lupo Pasini, Massimiliano (Spring 2018)
Published
Abstract
Since scientific computing is involved in increasingly demanding and challenging applications from various disciplines, upcoming computing architectures are going to provide more efficient hardware resources by moving towards exascale capacities, that is O(10 18 ) floating point operations per second (FLOPS). This computational capacity is obtained by computer manufacturers via an increase of the number of computing nodes composing the network. Therefore, the cost of global communications is expected to become more and more expensive. Because of this, the performance of state-of-the-art algorithms is expected to be highly deteriorated due to frequent global communications across the processors. On the one hand, global communications impact the computational time by constraining the parallelization. On the other hand, they make the algorithm more vulnerable to faulty phenomena (i.e. power loss, core crash, bit flips). Therefore, reducing the inter-processor communication is needed to preserve computational efficiency and reliability. The goal of this thesis is to analyze and develop techniques to solve large scale sparse linear systems in this new computational framework. The common feature with all the approaches presented in this work is the attempt to minimize the global operations needed to solve a linear system in a multiprocessor environment. In particular, the focus of this thesis is on linear fixed point iterations, since these techniques are characterized by computational locality and simplicity. Their use to solve sparse linear systems in parallel thus opens a path towards scalability and resilience on exascale machines. However, standard fixed point schemes are renown for their deteriorated asymptotic convergence rate. To cope with this, we analyze deterministic and stochastic accelerations. The former aim to increase the efficiency by improving the convergence rate, the latter aim to enhance the robustness against faults byavoiding the propagation of locally corrupted calculations. The deterministic acceleration we consider is the Anderson mixing. Many approaches to accelerate relaxation schemes through Anderson mixing have been studied in the literature. The approach analyzed here is called Alternating Anderson-Richardson. An analysis for this scheme is presented, highlighting the theoretical and computational advantages over more standard linear solvers to achieve scalability in a parallel framework. Furthermore, an augmented variant of Alternating Anderson-Richardson is proposed which guarantees convergence on positive definite linear systems. As concerns stochastic accelerations for relaxation schemes, we analyze Monte Carlo linear solvers (MCLS) based on a stochastic reinterpretation of the fixed point algorithm. In this context, we identify classes of matrices and preconditioners that produce a convergent splitting for the stochastic fixed point iteration. Moreover, stopping criteria based on the apparent standard deviation are proposed to determine the number of statistical samplings needed to achieve a prescribed accuracy.
Table of Contents
1 Introduction 1
2 Standard Iterative Methods for Sparse Linear Systems 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The Richardson scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Two-Level Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Matrix representation . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Aggregation methods . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Minimization methods . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Anderson-Richardson method . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Generalized Minimum Residual Method . . . . . . . . . . . . . . . . . 34
2.5.1 Restarted and truncated versions of GMRES . . . . . . . . . . 38
2.6 Comparison between GMRES and Anderson-Richardson . . . . . . . 39
2.6.1 Convergence Analysis for Anderson-Richardson . . . . . . . . 49
2.7 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.7.1 Comparison between Truncated AR and Truncated GMRES . 51
2.7.2 Comparison between Restarted AR and Restarted GMRES . . 52
3 Alternating Anderson-Richardson 54
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.2 Alternating Anderson-Richardson method . . . . . . . . . . . . . . . 55
3.2.1 Comparison between GMRES and Alternating Anderson-Richardson 57
3.2.2 Convergence analysis for Alternating Anderson-Richardson . . 79
3.2.3 Augmented Alternating Anderson-Richardson . . . . . . . . . 81
3.3 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.3.1 Software and hardware configuration . . . . . . . . . . . . . . 88
3.3.2 Stagnation of AAR . . . . . . . . . . . . . . . . . . . . . . . . 88
3.3.3 Experiments to support Theorem 3.2.2 . . . . . . . . . . . . . 90
3.3.4 Error mode analysis for AAR . . . . . . . . . . . . . . . . . . 90
3.3.5 Comparison between Truncated AR and Truncated AAR . . . 92
3.3.6 Comparison between Preconditioned Conjugate Gradient and Truncated AAR . . 93
3.3.7 Comparison between Truncated AAR and Restarted GMRES 98
3.3.8 Comparison between Truncated AAR and Augmented AAR . 114
3.4 Conclusions and future work . . . . . . . . . . . . . . . . . . . . . . . 122
4 Distributed memory parallelization of Alternating Anderson-Richardson 142
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.2 Implementation in MPI . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.3 Hardware configuration . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.4 Preconditioning approaches . . . . . . . . . . . . . . . . . . . . . . . 146
4.5 Memory storage requirements . . . . . . . . . . . . . . . . . . . . . . 147
4.6 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.7 Conclusions and future work . . . . . . . . . . . . . . . . . . . . . . . 154
5 Monte Carlo Linear Solvers 157
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.2 Stochastic linear solvers . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.2.1 Forward method . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.2.2 Adjoint method . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.2.3 Hybrid stochastic/deterministic methods . . . . . . . . . . . . 167
5.3 Convergence behavior of stochastic methods . . . . . . . . . . . . . . 170
5.3.1 Necessary and sufficient conditions . . . . . . . . . . . . . . . 171
5.3.2 Construction of transition probabilities . . . . . . . . . . . . . 173
5.3.3 Classes of matrices with guaranteed convergence . . . . . . . . 174
5.3.4 Adaptive methods . . . . . . . . . . . . . . . . . . . . . . . . 181
5.3.5 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.3.6 Considerations about computational complexity . . . . . . . . 186
5.4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.4.1 Numerical tests with adaptive methods . . . . . . . . . . . . . 189
5.4.2 Preconditioning approaches . . . . . . . . . . . . . . . . . . . 192
5.4.3 Hybrid methods . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.5 Conclusions and future work . . . . . . . . . . . . . . . . . . . . . . . 202
6 Remarks and future developments 206
Bibliography 210
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Deterministic and stochastic acceleration techniques for Richardson-type iterations () | 2018-04-04 15:38:16 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|