This is the page of Math 692 Graduate Seminar: Scalable algorithms in applicable mathematics in Spring 2023, in the Dept. of Mathematics and Statistics at the University of Alaska Fairbanks.

### official details

Time and place: Thursdays 4-5pm, Chapman 104

Credits: 1.0, but non-credit attendance is also strongly encouraged. (CRN 37822 for in-person section 901, 37821 for synchronous zoom section 701.) If you want to take the seminar for credit then you should expect to give a least one presentation.

## proposed content

My idea is to have a seminar where we can learn about mathematical (or somewhat mathematical) algorithms which are aimed at solving large problems. The best algorithms are optimal because they solve in $O(n)$ or $O(n\log n)$ time or memory, for data size $n$. While optimal performance is not possible for some problems, algorithms which scale well with $n$ have a chance of solving the biggest, hardest problems in areas where mathematics is applied.

The ideal presentation might explain, and show concretely with examples, how an optimal (or near-optimal, or best-known) discrete or continuous algorithm works. Each presentation should at least to try to clarify the size $n$ of the data to which the algorithm applies. Presenters should explain how the run time, amount of computation, or amount of memory of the algorithm depends on the size $n$ of the data.

Beyond such basic expectations the talks should be diverse and the topics very wide-ranging! See some possible topics below; there must be many more I don’t know about.

Big O notation will often be used in presentations here, but the goal is not to create a theory of complexity course. See CS 611 Complexity of Algorithms for that.

## possible topics

• iterative linear algebra for sparse matrices (Krylov, etc.)
• fast Fourier transform (FFT)
• fast sorting algorithms
• multigrid for solving partial differential equations
• fast multipole methods for interacting particle systems
• sparsity-exploiting direct solvers in linear algebra
• fast integer multiplication, convolutions, etc.
• spectral methods for differential equations
• limited-memory optimization schemes
• geometric algorithms in computer graphics (e.g. here)
• graph algorithms (?)
• monte carlo algorithms (?)

## schedule of talks

Date Speaker Title
19 Jan none
26 Jan Ed Bueler Making ice sheet models scale properly
2 Feb none
9 Feb none
16 Feb none
23 Feb Ed Bueler Which linear systems can be solved optimally?
2 Mar Glen Woodworth An algorithm for graph isomorphism
9 Mar none
23 Mar none
30 Mar Victor Devaux-Chupin FFTs and applications
6 Apr none
13 Apr Austin Smith Solving sparse linear systems
20 Apr none
27 Apr Oscar Hernandez Boolean satisfiability and non-determinism
4 May Ed Bueler Multigrid: optimal solvers for elliptic PDEs
S