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.
Jump to schedule of talks at bottom.
official details
Organizer: Ed Bueler, elbueler@alaska.edu.
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 |