2016-b Spring

NCTS 2016 Short Courses on High-Performance Linear System Solvers

國家理論科學研究中心 2016 年春季跨校課程：「線性系統高速計算方法的新發展」

  • [2016/05/19] Videos of Prof. Edmond Chow's lectures: 5/19-1, 5/19-2.
  • [2016/05/18] Videos of Prof. Edmond Chow's lectures: 5/18-1, 5/18-2.
  • [2016/05/17] Videos of Prof. Edmond Chow's lectures: 5/17-1, 5/17-2.
  • [2016/05/16] Videos of Prof. Edmond Chow's lectures: 5/16-1, 5/16-2.
  • [2016/05/12] Videos of Prof. Edmond Chow's lectures: 5/12-1, 5/12-2.
  • [2016/05/11] Videos of Prof. Edmond Chow's lectures: 5/11-1, 5/11-2.
  • [2016/05/10] Videos of Prof. Edmond Chow's lectures: 5/10-1, 5/10-2.
  • [2016/05/09] Videos of Prof. Edmond Chow's lectures: 5/9-1, 5/9-2.
  • [2016/05/06] Videos of Prof. Edmond Chow's lectures: 5/6-1, 5/6-2.
  • [2016/05/05] Videos of Prof. Edmond Chow's lectures: 5/5-1, 5/5-2.
  • [2016/05/04] Videos of Prof. Edmond Chow's lectures: 5/4-1, 5/4-2.
  • [2016/05/03] Videos of Prof. Edmond Chow's lectures: 5/3-1, 5/3-2.
  • [2016/03/25] Videos of Prof. Rio Yokota's lectures: 3/25-1, 3/25-2, 3/25-3.
  • [2016/03/24] Videos of Prof. Rio Yokota's lectures: 3/24-1, 3/24-2, 3/24-3, 3/24-4.
  • [2016/03/23] Videos of Prof. Rio Yokota's lectures: 3/23-1, 3/23-2, 3/23-3, 3/23-4.
  • [2016/03/22] Videos of Prof. Rio Yokota's lectures: 3/22-1, 3/22-2.
  • [2016/03/21] Videos of Prof. Rio Yokota's lectures: 3/21-1, 3/21-2.
  • [2016/03/21] You may download course materials provided by Prof. Rio Yokota from this link.
  • [2016/02/03] 課程報名表：http://goo.gl/forms/x9Aikcx45W (本課程不收費用，但需事先報名。)

上課時間

Part 1. 2016/2/23, 3/1, 8, 15, 29 (9:10-12:00): 黃聰明 (台灣師範大學)，王偉仲 (台灣大學)

Part 2. March 21-25, 2016 (9:10-13:10) Rio Yokota (Tokyo Institute of Technology, Japan) 英文授課

Part 3. May 3-6, 9-12, 16-19, 2016 (12:10-13:25) Edmond Chow (Georgia Institute of Technology, USA) 英文授課

上課地點

R. 201, Astro-Mathematics Building, NTU (台灣大學 天文數學館 201室)

Part 3. High-Performance Numerical Solvers with Applications

Abstract:

Numerical solvers are at the core of most scientific and engineering computations. For large problems, these solvers are computationally and data-movement intensive and require high-performance computing techniques and implementations. Thus, the design of practical numerical solvers today requires knowledge of a combination of numerical and computing techniques. This intensive short course will present the background for you to understand, use, and develop state-of-the-art techniques for numerical solvers. Our focus will be on numerical linear algebra techniques and parallel computing. The course will also introduce several applications and describe the structure of the problems to be solved.

Topics:

  • PDE governing equations
  • Discretizations and sparse matrices
  • Basic iterative methods
  • Parallel computer architectures
  • Shared and distributed memory computing
  • Asynchronous computations
  • Algebraic preconditioners
  • Parallel partitioning techniques
  • Domain decomposition methods
  • Multigrid methods
  • Rank-structured methods

Instructor: Edmond Chow (Website)

Edmond Chow is an Associate Professor in the School of Computational Science and Engineering at Georgia Institute of Technology, USA. He previously held positions at D. E. Shaw Research and Lawrence Livermore National Laboratory. His research is in developing and applying numerical methods and high-performance computing to solve large-scale scientific computing problems and seeks to enable scientists and engineers to solve larger problems more efficiently using physical simulation. Specific interests include numerical linear algebra (preconditioning, multilevel methods, sparse matrix computations) and parallel methods for quantum chemistry, molecular dynamics, and Brownian/Stokesian dynamics. Dr. Chow earned an Honors B.A.Sc. in Systems Design Engineering from the University of Waterloo, Canada, in 1993, and a Ph.D. in Computer Science with a minor in Aerospace Engineering from the University of Minnesota in 1997. Dr. Chow was awarded the 2009 ACM Gordon Bell prize and the 2002 U.S. Presidential Early Career Award for Scientists and Engineers (PECASE).

Topics day-by-day

  • 5/17: Non-Overlapping Domain Decomposition, Laplacian BVP, Discrete/Algebraic View (decompose Au=f into subdomains), Algebraic View & Equivalent Problem (relation between PDEs and decomposition), Dirichlet-Neumann Algorithm (using Schur component to simplify the iteration), Neumann-Neumann Algorithm
  • 5/18: Overlapping Domain Decomposition
  • Alternating Schwarz Method (sequential: overlapping region has overwrite memory), Jacobi-Schwarz Method (Solve local solutions, average on overlapping region, has convergent issue), Discrete View for Alternating Schwarz Method, Multiplicative Schwarz Method (via Algebraic Viewpoint of A.S.)

Organizers:

Tsung-Ming Huang (NTNU), Wen-Wei Lin (NCTU), and Weichung Wang (NTU)

Sponsor:

The National Center for Theoretical Sciences (website)

矩陣計算是驅動各種大型數值模擬與大量數據分析的核心引擎，快速發展中的超級電腦更是強而有力的計算工具。他們在電磁學，機器學習，流體力學，分子動力學，天文物理，統計計算等各個面向都有廣泛的應用。如何結合兩者，在超級電腦上發展矩陣計算的快速演算法與高效能軟體，是當代學術界與工業界的重要關鍵，更是極具未來性的主題。針對「線性系統高速計算方法的新發展」，我們特別規劃這個系列課程，提供與國際學術界最新發展接軌的學習機會，培養可以在國際場域發展的下一代人才。希望藉由教師講解與上機實習，讓同學從做中學，進而有信心敢動手做，解決實際的應用問題。

此課程包含下列三部分：Part 1. Fundamentals of Iterative Linear System Solvers； Part 2. An Introductory Course on Fast Multipole Methods；Part 3. High-Performance Numerical Solvers with Applications。第一部分將從基本的迭代法開始入門，介紹基本觀念與背景知識。第二部分著重在 Fast Multipole Methods (FMM)，此方法具有高計算密集 (high arithmetic intensity) 與少量的非同步通訊 (low communication) 的特性，很適合在大型平行電腦上求解超大線性系統。第三部分著重在高效能計算方法的重要觀念與詳細知識，目的是讓聽眾將可以理解、使用、開發最新的平行數值線性代數方法與工具。內容包括平行數值與計算方法，以及如何利用應用問題的矩陣特性，設計更好的演算法。

我們歡迎研究生或高年級大學生參加這些短期課程，藉以掌握未來的大型計算趨勢與研發能力。若有意願參與全部課程，可以選修台師大數學系開設的「矩陣計算」或台大數學系暨應數所開設的「科學計算導論」課程，完成後可獲得三學分。部分課程也會透過 YouTube 即時轉播，詳請請參見課程網頁：https://goo.gl/8idGpl。

Matrix computation is a kernel of various large-scale numerical simulations and data analytics. Supercomputers are powerful tools for computation of these large-scale problems and under rapid development. Algorithm and software developments for high-performance matrix computations are vital to academic and industrial communities. As a great opportunity to learn cutting-edge knowledge from these world-leading experts, the special course series on high-performance linear system solvers are provided to train young research talents. The aim is to learn from course lectures and classroom hands-on practice, confidence buildup, and application to practical problems.

The contents of course series are categorized as follows.

1. Fundamentals of Iterative Linear System Solvers

From basic iterative methods, we introduce the basic concepts and background knowledge.

2. An Introductory Course on Fast Multipole Methods

We focus on Fast Multipole Methods (FMM), which features high arithmetic intensity and low communication. Due to these properties, FMM is very suitable for solving large-scale linear systems in highly parallel computing environment.

3. High-Performance Numerical Solvers with Applications

We concentrate on concept and knowledge of high-performance computing (HPC) so that students can learn the usage and development of parallel numerical and linear algebra packages. The lectures include parallel numerical and computational methods, application-dependent and matrix-based algorithm design.

We encourage graduate and senior undergraduate students to these short courses to keep up with modern large-scale computing and develop relating research capability. The courses "Matrix Computing" in NTNU and "Introduction to Scientific Computing" in iAMS NTU are recommended to students who want to join the full lectures, and students get three credits if passing each course. Partial sections of the courses will be streamed on Youtube. Please visit the course website for further details.

Tentative Schedule

Part 1. 2016/2/23, 3/1, 8, 15, 29 (9:10-12:00): 黃聰明 (台灣師範大學)，王偉仲 (台灣大學)

Part 2. 2016/3/21-3/25 (9:10-13:10): Rio Yokota (Tokyo Institute of Technology, Japan) 英文授課

Part 3. 2016/5/3-6, 9-12, 16-19 (12:10-13:25): Edmond Chow (Georgia Institute of Technology, USA) 英文授課

Student Presentations: 2016/4/19 and 2016/6/7 (9:10-12:00)

Place

R. 201, Astro-Mathematics Building, NTU

Part 1. Fundamentals of Iterative Linear System Solvers

Topics:

  1. Matrix representation of discrete finite-difference Laplacian
  2. Conjugate gradient method (CG) for symmetric positive definite linear systems
  3. Convergence analysis of conjugate gradient methods
  4. Preconditioning
  5. Generalized minimal residual method (GMRES) for general linear systems

Instructor:

  • Tsung-Ming Huang (National Taiwan Normal University)
  • Weichung Wang (National Taiwan University)

Part 2. An Introductory Course on Fast Multipole Methods

This course will focus on fast multipole methods (FMM) and H-matrices. The FMM is considered one of the top ten algorithms of the 20th century along with FFT and Krylov subspace methods. The FMM has O(N) complexity with high arithmetic intensity, and O(logP) communication with high asynchronicity. We start out with single level multipole expansions and then proceed to multilevel versions of the FMM. Then, adaptive tree structures and their parallelization are discussed. We finish the course with a brief description of H-matrices. For every two lectures, there will be two hands-on sessions to practice what you have learned.

Topics:

  1. Introduction to FMM
  2. Multipole expansions
  3. Single-level FMM hands on
  4. Single-level FMM hands on II
  5. Tree Structure
  6. Interaction lists
  7. Multi-level FMM hands on
  8. Multi-level FMM hands on II
  9. Morton keys
  10. Adaptive tree structure
  11. Adaptive FMM hands on
  12. Adaptive FMM hands on II
  13. Domain decomposition
  14. Local essential tree
  15. Parallel FMM hands on
  16. Parallel FMM hands on II
  17. Introduction to H-matrix
  18. SVD and RRQR
  19. H-matrix hands on
  20. H-matrix hands on II

Prerequisites: C language, analysis, linear algebra, basic algorithms, basic Linux

References:

Instructor: Rio Yokota (Website)

Rio Yokota is an Associate Professor at Tokyo Institute of Technology where he does research on FMM and H-matrices on large-scale supercomputers. Dr. Yokota received his Ph.D. from Keio University, Japan in Mechanical Engineering. During his post-doc at University of Bristol, UK and Boston University, USA he developed a highly parallel FMM code —exaFMM. He is won the 2009 Gordon Bell prize (price/performance) using his FMM code. He was a Research Scientist at the King Abdullah University of Science and Technology (KAUST), Saudi Arabia from 2011-2015, where he worked with David Keyes on FMM preconditioners.

Student Presentations: 2016/4/19 and 2016/6/7 (9:10-12:00)