<div>The focus of this Dissertation is to provide a unified and efficient solution method for an important class of nonconvex, nonsmooth, constrained optimization problems. Specifically, we are interested in problems where the objective function can be written as the sum of a smooth, nonconvex term, plus a convex, but possibly nonsmooth, regularizer. It is also considered the presence of nonconvex constraints. This kind of structure arises in many large-scale applications, as diverse as information processing, genomics, machine learning, or imaging reconstruction.</div><div></div><div>We design the first parallel, asynchronous, algorithmic framework with convergence guarantees to stationary points of the class of problems under exam. The method we propose is based on Successive Convex Approximation techniques; it can be implemented with both fixed and diminishing stepsizes; and enjoys sublinear convergence rate in the general nonconvex case, and linear convergence case under strong convexity or under less stringent standard error bound conditions.The algorithmic framework we propose is very abstract and general and can be applied to different computing architectures (e.g., message-passing systems, cluster of computers, shared-memory environments), always converging under the same set of assumptions. </div><div></div><div>In the last Chapter we consider the case of distributed multi-agent systems. Indeed, in many practical applications the objective function has a favorable separable structure. In this case, we generalize our framework to take into consideration the presence of different agents, where each one of them knows only a portion of the overall function, which they want cooperatively to minimize. The result is the first fully decentralized asynchronous method for the setting described above. The proposed method achieve sublinear convergence rate in the general case, and linear convergence rate under standard error bound conditions.</div><div></div><div>Extensive simulation results on problems of practical interest (MRI reconstruction, LASSO, matrix completion) show that the proposed methods compare favorably to state-of-the art-schemes.</div>

Cette thèse s’intéresse à la simulation acoustique de problèmes de grandes tailles. La parallélisation des méthodes numériques d’acoustique est le sujet principal de cette étude. Le manuscrit est composé de trois parties : lancé de rayon, méthodes de décomposition de domaines et algorithmes asynchrones. / This thesis studies numerical methods for large-scale acoustic problems. The parallelization of the numerical acoustic methods is the main focus. The manuscript is composed of three parts: ray-tracing, optimized interface conditions for domain decomposition methods and asynchronous iterative algorithms.

The components of high-performance systems continue to become more complex on the road to exascale. This complexity is exposed at the level of: multi/many-core CPUs, accelerators (GPUs), interconnects (horizontal communication), and memory hierarchies (vertical communication). A crucial task is designing an algorithm and a programming model that scale to the same order of the HPC system size at multiple levels. This trend in HPC architecture more critically affects memory-intensive appli- cations than compute-bound applications. Accomplishing this task involves adopting less synchronous forms of the mathematical algorithm, reducing synchronization in the computational implementation, introducing more SIMT-style concurrency at the finest level of system hierarchy, and increasing arithmetic intensity as the bottleneck shifts from number of floating-point operations to number of memory accesses. This dissertation addresses these challenges in scientific simulation focusing in the dominant kernels of a memory-bound application: sparse solvers in implicit model- ing, and I/O in explicit reverse time migration in seismic imaging. We introduce asynchronous task-based parallelism into iterative algebraic preconditioners. We also introduce a task-based framework that hides the latency of I/O with computation. This dissertation targets two main applications in the oil and gas industry: reservoir simulation and seismic imaging simulation. It presents results on multi- and many- core systems and GPUs on four Top500 supercomputers: Summit, TSUBAME 3.0, Shaheen II, and Makman-2. We introduce an asynchronous implementation of four major memory-bound kernels: Algebraic multigrid (MPI+OmpSs), tridiagonal solve (MPI+OpenMP), Additive Schwarz Preconditioned Inexact Newton (MPI+MPI), and Reverse Time Migration (StarPU/StarPU+MPI and CUDA).

This thesis proposes and analyzes several first-order methods for convex optimization, designed for parallel implementation in shared and distributed memory architectures. The theoretical focus is on designing algorithms that can run asynchronously, allowing computing nodes to execute their tasks with stale information without jeopardizing convergence to the optimal solution. The first part of the thesis focuses on shared memory architectures. We propose and analyze a family of algorithms to solve an unconstrained, smooth optimization problem consisting of a large number of component functions. Specifically, we investigate the effect of information delay, inherent in asynchronous implementations, on the convergence properties of the incremental prox-gradient descent method. Contrary to related proposals in the literature, we establish delay-insensitive convergence results: the proposed algorithms converge under any bounded information delay, and their constant step-size can be selected independently of the delay bound. Then, we shift focus to solving constrained, possibly non-smooth, optimization problems in a distributed memory architecture. This time, we propose and analyze two important families of gradient descent algorithms: asynchronous mini-batching and incremental aggregated gradient descent. In particular, for asynchronous mini-batching, we show that, by suitably choosing the algorithm parameters, one can recover the best-known convergence rates established for delay-free implementations, and expect a near-linear speedup with the number of computing nodes. Similarly, for incremental aggregated gradient descent, we establish global linear convergence rates for any bounded information delay. Extensive simulations and actual implementations of the algorithms in different platforms on representative real-world problems validate our theoretical results. / <p>QC 20170317</p>