**Contact Info**

Department of Applied Mathematics

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext. 32700

Fax: 519-746-4319

PDF files require Adobe Acrobat Reader

Friday, September 29, 2017 9:30 AM EDT

MC 6460

Alexander Hows

Applied Mathematics, University of Waterloo

Nonlinear Preconditioning Methods for Optimization and Parallel-in-Time Methods for the Linear Advection Equation

This thesis consists of two main parts, part one addressing problems from nonlinear optimization and part two based on solving systems of time dependent differential equations, with both parts describing strategies for accelerating the convergence of iterative methods.

In part one we present a nonlinear preconditioning framework for use with nonlinear solvers applied to nonlinear optimization problems, motivated by generalizations of linear left preconditioning and linear preconditioning via a change of variables for minimizing quadratic functions. Nonlinear preconditioning is used to generate a preconditioner direction that either replaces or supplements the gradient vector throughout the optimization algorithm. This framework is used to discuss previously developed nonlinearly preconditioned nonlinear GMRES and nonlinear conjugate gradients algorithms, as well as to develop two new nonlinearly preconditioned limited memory quasi-Newton methods. These methods are compared by computing two different types of tensor decomposition, both of which are defined by optimization problems that have alternating least squares (ALS) type fixed point iterations. While these ALS type iterations may be slow to converge in practice, they can serve as efficient nonlinear preconditioners for the other optimization methods. Numerical results show that the nonlinearly preconditioned methods offer substantial improvements in terms of time-to-solution and robustness over state-of-the-art methods for large tensors, in cases where there are significant amounts of noise in the data, and when high accuracy results are required.

In part two we apply a multigrid reduction-in-time (MGRIT) algorithm to scalar 1D hyperbolic partial differential equations. This study is motivated by the observation that sequential time-stepping is an obvious computational bottleneck when attempting to implement highly concurrent algorithms, thus parallel-in-time methods are particularly desirable, but existing parallel-in-time methods can have stability and convergence issues for advection dominated problems. MGRIT primarily uses temporal coarsening, but spatial coarsening can also be incorporated to produce cheaper multigrid cycles and to ensure stability conditions are satisfied on all levels for explicit time-stepping methods. However, uniform factor-two spatial coarsening can cause extremely slow MGRIT convergence when the wave speed is near zero, even if only locally, due to the weak spatial connections that result. The use of waveform relaxation multigrid on intermediate, temporally semi-coarsened grids is identified as a potential remedy for this issue, with the downside of creating a more intrusive algorithm that cannot be easily combined with existing time-stepping routines. As a less intrusive alternative we present an adaptive spatial coarsening strategy designed to prevent the observed slowdown. Serial numerical results show this method offers significant improvements over uniform coarsening and is convergent for inviscid Burgers' equation with and without shocks. Parallel scaling tests indicate that improvements over serial time-stepping strategies are possible when spatial parallelism alone saturates, and that scalability is robust for oscillatory solutions that change on the scale of the grid spacing.

**Contact Info**

Department of Applied Mathematics

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext. 32700

Fax: 519-746-4319

PDF files require Adobe Acrobat Reader

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.