Math P K U

Multilevel Algorithms and Randomized Algorithms

Course Information

• Room: The Third Classroom Building 205
• Lecture time: Th 8:00 - 9:50 am (Odd week), M, Th 8:00 - 9:50 am (Even week)
• Office and hours: 1287, Tu 9:00 am - 11:00 am or by appointment.

Homework and Project

1. Exercises in quick-sort and FFT notes. (Due date: Oct 8)
2. Project: Fast Multipole Methods. (Due date: Oct 8)
3. Exercises in Classic Iterative Methods and Multigrid Methods. (Due date: Oct 28)
4. Project: Multigrid Methods. (Due date: Nov 5)
5. Exercise in J-L Transform. (Due date: Dec 3)
6. Project: Reproduce results in the following paper. You can skip the test with real data first. (Due date: Dec 10)
7. Exercise in Tail bound of random matrices. (Due date: Dec 21)
8. Project: Fast Least Square Solvers. (Due date: Dec 25)
9. Final Project: Reproduce results in Section 7.1 and 7.4 in the SIAM Review paper (2011), 53(2), 217-288. (Due date: Jan 11)

Course Description

We shall present several fast algorithms in numerical computation. In the first half of this course, we shall discuss algorithms based on the multilevel structure which reduces the complexity from $O(N^2)$ or $O(N^3)$ to $O(N\log N)$ or $O(N)$ for a problem of size $N$. Selected algorithms are:

• Quick sort. quick-sort notes
• FFT (Fast Fourier Transform). FFT notes
• FMM (Fast Multipole Method). FMM notes
• Multi-Grid (MG) Method.

1. Classic Iterative Methods
2. Introduction to Multigrid Methods
3. Subspace Correction Methods
4. Programming of Multigrid Methods
5. Recrusive Proofs of Multigrid Methods

In the second half, we shall discuss randomized numerical linear algebra which is a very active subject now, with ideas from and impacts on various fields, including analysis of big data sets, probability and statistics, numerical analysis, and computational complexity. Selected topics are:

• Introduction to the Probability Theory Probability
• Johnson-Lindenstrauss transform JL Transform
• Fast Least Squares Approximation

1. Least square problem, QR and SVD decomposition Least square
2. Fast Least Squares Approximation Drineas, P., Mahoney, M. W., Muthukrishnan, S., and Sarlos, T. (2011). Numerische Mathematik, 117(2), 219-249.
3. Preconditioner version. Rokhlin, V., and Tygert, M. (2008). PNAS, 105(36), 13212-13217.
4. Improve algorithm and computational Results. Avron, H., Maymounkov, P., and Toledo, S. (2010). SIAM Journal on Scientific Computing, 32(3), 1217-1236.

• Random Matrix Theory

1. Approximating Matrix Multiplication. Notes by M. Mahoney matrixmultiplication
2. Tail bound of random matrices matrixconcentration

• Low rank matrix approximation

1. Review article. Halko, N., Martinsson, P.G., and Tropp, J.A. (2011). Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53(2), 217-288.
2. Improved algorithm and analysis for SVD. Subspace Iteration Randomization and Singular Value Problems. M. Gu. 2014.

Syllabus