Provably Efficient Algorithms for Numerical and Combinatorial Problems (CS 598 EVS) Spring 2020
|Time/place||Tu/Th 3:30pm-4:45pm, (virtual, email or see piazza for link to zoom, previously 1131 Siebel Center)|
|Office Hours||After class, Tu/Th 4:45-5:30 (virtual, stay in zoom after lecture)|
|Web forum||View Piazza »|
|Calendar||View Calendar »|
Bridging the theory and practice of algorithms requires going beyond computational complexity to more sophisticated models of computer architecture and algorithmic cost. This course covers multiple analytical techniques that quantify the efficacy of an algorithm: parallel scalability, memory traffic, interprocessor communication, and numerical stability. General representations of algorithms (dependency graphs, bilinear algorithms) will be introduced as well as techniques for communication lower bound analysis. The course will look at problems from a variety of application domains, ranging from sorting and graph algorithms to numerical solvers and optimization. Special focus will be given to tensor computations.
The learning objective of the course is to develop techniques for mathematical representation and analysis of algorithms. Focus will be on numerical algorithms for matrix and tensor computations, but miscellaneous problems and algorithmic models will be considered. Topics of consideration will incorporate student interest/presentations.
Students will be expected to give a presentation relevant to the course, which may involve a discussion/activity, as well as to complete some assignments The assignments are planned to be given as in-class activities, but can also be completed offline. The presentation will comprise 70% and assignments 30% of the overall grade.
Quizzes (in-class activities)
Quiz 2: Computing the Maximum Ritz Value »
Quiz 3: Finding Minimum of Quadratic Function in a Subspace »
Quiz 6: Algebraic Graph Algorithms »
Quiz 7: Bilinear Algorithms for Convolution »
Quiz 8: Triangular Matrix Inversion with Poly-Logarithmic Depth »
Quiz 9: General Matrix Inversion with Poly-Logarithmic Depth »
Quiz 10: Cache-Oblivious Fast Fourier Transform »
Quiz 11: Approximate Algorithms for Convolution »
Quiz 13: Alternating Least Squares for CP Decomposition of Tensors »
Quiz 14: Tensor Network Evolution »
Quiz 15: Eigenvalue Computation for Kronecker-Product Matrices using Imaginary Time Evolution »
Quiz 16: Eigenvalue Computation for Kronecker-Product Matrices using DMRG »
Quiz 17: Accelerated Bellman-Ford »
Quiz 18: Neural Network Robustness Verification »
Quiz 19: Bayesian Matrix Factorization with Monte Carlo »
Quiz 20: Computing Layer Potentials using Quadrature by Expansion »
Background Numerical Analysis Tools
- Lecture Notes
- Demo: Conjugate Gradient Parallel Tangents as Krylov Subspace Method
- Demo: Krylov Subspace Methods for Extremal Eigenvalue Problems
- Algorithm Representation
- Parallelism in Algorithms
- Communication Cost of Algorithms
- Tensor Computations
CS 598 EVS: Communication Cost Analysis of Algorithms, Fall '16
CS 554: Parallel Numerical Algorithms, Fall '19
CS 450: Numerical Analysis, Fall '18
- Applied Numerical Linear Algebra James Demmel, SIAM, 1997.
- Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
- Numerical Linear Algebra Lloyd Trefethen and David Bau, SIAM, 1997.
- An Introduction to Parallel Algorithms Joseph JaJa, 1992.
We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments.
- Python tutorial
- Facts and myths about Python names and values
- Learn Python the hard way
- Project Euler (Lots of practice problems)
Python Workshop Material
- Video: Located on Echo 360 along with the other class recordings
- Tutorial material
- Scipy lecture notes
- CSE workshop training material
- Introduction to Python for Science
- The SciPy lectures
- The Numpy MedKit by Stéfan van der Walt
- The Numpy User Guide by Travis Oliphant
- Numpy/Scipy documentation
- More in this reddit thread
- Spyder (a Python IDE, like Matlab) is installed in the virtual machine. (Applications Menu > Development > Spyder)
- An introduction to Numpy and SciPy