University of Texas at Austin

Past Event: Oden Institute Seminar

Randomized algorithms and fast solvers for elliptic PDEs

Per-Gunnar Martinsson, Professor, Oxford University

10 – 11PM
Monday Sep 18, 2017

POB 4.304

Abstract

That the linear systems arising upon the discretization of elliptic PDEs can be solved efficiently is well known, and iterative solvers that often attain linear complexity (multigrid, Krylov methods, etc) have proven very successful. Interestingly, it has recently been demonstrated that it is often possible to directly compute an approximate inverse to the coefficient matrix in linear (or close to linear) time. The talk will describe some recent work in the field and will argue that direct solvers have several advantages, including improved stability and robustness, the ability to solve certain problems that have remained intractable to iterative methods, and dramatic improvements in speed in certain environments. Moreover, the direct solvers being proposed have low communication requirements, and appear to be very well suited to parallel implementations. An important component of the new solvers is that they incorporate randomized algorithms that accelerate certain recurring dense matrix operations. The talk will describe the key ideas behind such randomized algorithms, and briefly describe how they can be used both for accelerating PDE solvers, and for a variety of tasks in data mining and machine learning.

Event information

Date
10 – 11PM
Monday Sep 18, 2017
Location POB 4.304
Hosted by Robert Moser