課程資訊

Numerical Linear Algebra

106-1

MATH5411

221 U4210

3.0

Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1061MATH5411_

The course consists of the following four parts.
• Part A. A 75-minute lecture on every Thursday (9:10-10:25) from 2017/9/14 to 2017/12/7.
• Part B. A 75-minute hands-on session on every Thursday (10:35-11:50) from 2017/9/14 to 2017/12/7.
• Part C. An online course that consists of twelve 75-minute lectures by Prof. Edmond Chow. This online course should be self-studied from 2017/9/14 to 2017/11/2.
• Part D. Twelve 75-minute lectures (12:10-13:25) on selected days from 2017/12/18 to 2018/1/5.

The tentative schedule for Parts A, B, C is listed below. The online course of Part C is available on the web page https://sites.google.com/site/school4scicomp/previous/2016-b-spring.

• Week 1 (2017/9/14)
o Lecture
♣ a. Introduction to course
♣ b. Graph Laplaician
♣ c. Applications in 3D face animation and data network analysis
o Hands-on session
♣ b. Construct the matrices by Matlab or GPU
♣ c. Check the sparsity of the matrices
♣ d. Learn mathematical software tool (web)
o Online course
♣ a. [0503-1], [0503-2], [0505-1]
• Week 2 (2017/9/21)
o Lecture
♣ a. power method for EVP
♣ b. inverse power method for EVP
o Hands-on session
♣ a. Practice mathematical software tools
♣ b. Learn basic CUDA programming
♣ c. Use csreigvsi in cuSolverSP to compute the target eigenvalues
♣ d. Try other problems by using csreigvsi
o Online course
♣ [0505-2], [0506-1], [0506-2]
• Week 3 (2017/9/28)
o Lecture
♣ a. None
o Hands-on session
♣ a. Solve the linear system (A + 1.0e-5 I) y = b by using the direct solvers (LU and Cholesky) in cuSolverSP package to solve the linear systems from http://konect.uni-koblenz.de/ with various dimensions
♣ b. Discuss the results in direct solvers
o On-line course
♣ [0509-1], [0509-2], [0510-1]
• Week 4 (2017/10/5)
o Lecture
♣ a. Learn how to use magma_dcg (Conjugate Gradient method) in MAGMA
o Online course
♣ [0510-2], [0511-1], [0511-2]
• Week 5 (2017/10/12)
o Lecture
o Hands-on session
♣ a. Use magma_dcg type functions in MAGMA to solve linear system from 3D face animation
♣ b. Use magma_dcg type functions in MAGMA to solve linear system from http://konect.uni-koblenz.de/ with various dimensions
o Online course
♣ [0512-1], [0512-2], [0516-1]
• Week 6 (2017/10/19)
o Lecture
♣ a. Preconditioning conjugate gradient method
o Hands-on session
♣ a. Learn how to use PCG with preconditioners in MAGMA
o Online course
♣ [0516-2], [0517-1], [0517-2]
• Week 7 (2017/10/26)
o Lecture
♣ a. Preconditioner
o Hands-on session
♣ a. Use CG method in MAGMA with ICC (magma_dapplycumicc_l) and ILU (magma_dapplycumilu_l and magma_dapplycumilu_r) preconditioners
o Online course
♣ [0518-1], [0518-2], [0519-1], [0519-2]
• Week 8 (2017/11/2)
o Lecture
♣ a. Preconditioner
o Hands-on session
♣ a. Compare the results of CG method in MAGMA with ICC, ILU, and other preconditioners
♣ b. Run AmgX to solve linear systems
• Week 9 (2017/11/9)
o Lecture
♣ a. BiCGSTAB
o Hands-on session
♣ a. Learn how to use un-symmetric linear solvers in MAGMA
• Week 10 (2017/11/16)
o Lecture
♣ a. BiCGSTAB
o Hands-on session
♣ a. Use BiCGSTAB (magma_dbicgstab) with ILU preconditioner to solve linear system (A - 1.0e-5) y = b
• Week 11 (2017/11/23)
o Lecture
♣ a. Lanczos method
o Hands-on session
♣ a. Learn how to use sparse eigensolver in MAGMA
• Week 12 (2017/11/30)
o Lecture
♣ a. Lanczos method
o Hands-on session
♣ a. Use LOBPCG (magma_dlobpcg) to compute the target eigenvalues
• Week 13 (2017/12/7)
o Midterm

• Krylov subspace methods
o Projection method viewpoint and unifying framework
o Specialized methods
o Avoiding communication and synchronization
o Restarting for eigenvalue solvers
• Hierarchical matrix methods
o Physical intuition and relation to fast multipole methods
o Hierarchical matrix construction and solution methods
• Domain decomposition methods
o Optimized Schwarz methods
o FETI and related methods
• Multigrid methods
o Convergence theory
o Algebraic multigrid
• Parallel Preconditioning
o Advanced ideas on incomplete factorizations
o Advanced ideas on sparse approximate inverses
o Other recent developments

This course covers some of the most basic and latest concepts, algorithms, theories, and implementations in numerical linear algebra. Students will learn and practice the subjects from the viewpoints of application, mathematics, and parallel computing.

Linear Algebra, Programming Language (e.g. MATLAB, C, C++, or CUDA), Introduction to Computational Mathematics, Calculus

Office Hours

[1] Numerical Linear Algebra By Lloyd N. Trefethen and David Bau III, SIAM
[2] Applied Numerical Linear Algebra, James W. Demmel, SIAM, 1997
[3] Iterative Methods for Sparse Linear Systems, 2nd Edition, Yousef Saad, 2003 (http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf)
[4] Matrix Computations, Fourth Edition, Gene H. Golub and Charles F. Van Loan, SIAM, 2013
[5] Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, Richard Barrett et al., SIAM, 1994
[6] 大型線性系統與特徵值問題 http://ocw.lib.ntnu.edu.tw/course/view.php?id=190

Course slides

(僅供參考)

 No. 項目 百分比 說明 1. 課堂討論，課堂報告，回家作業 60% 2. 期中考 40%

 課程進度
 週次 日期 單元主題