Tutorials

Tutorials are co-organized together with Courant Institute/NYU.

Titles and Abstracts

Shivkumar Chandrasekaran, University of California Santa Barbara, USA

Fast algorithms for displacement and low-rank structured matrices

Abstract:

With the introduction of the Fast Multipole Method (FMM) of Greengard and Rokhlin there has been tremendous progress in the design of fast numerically stable matrix algorithms. The key concept is the low-rank structures that are hidden in the matrix. In this tutorial we will first give an introduction to classical fast algorithms to develop an understanding of why they may not perform well in practice. Then we introduce displacement structured matrices and the associated fast Schur algorithm and discuss some of the current open problems in that approach. Finally we will introduce the type of low-rank structures exploited by the FMM method and the associated SSS and HSS matrix representations. Along the way we will highlight important open problems.

Video of the talk

Steve Linton,
University of St Andrews, UK

GAP4 at twenty-one – algorithms, system design and applications

Abstract:

The first public beta release of GAP 4 was made on July 18 1997. Since then the system has been cited in over 2400 papers, and its distribution now includes over 130 contributed extension packages. This tutorial will review the special features of computational abstract algebra and how they are reflected in the system design; some areas of current algorithmic development, and some recent achievements.

Video of the talk

Daniel Roche,
US Naval Academy, USA

What can (and can't) we do with supersparse polynomials?

Abstract:

Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.

Video of the talk