Embedded Files
NCTS 2016 Spring Short Courses on High-Performance Linear System Solvers
國家理論科學研究中心 2016 年春季跨校課程：「線性系統高速計算方法的新發展」
Introduction
Introduction
矩陣計算是驅動各種大型數值模擬與大量數據分析的核心引擎，快速發展中的超級電腦更是強而有力的計算工具。他們在電磁學，機器學習，流體力學，分子動力學，天文物理，統計計算等各個面向都有廣泛的應用。如何結合兩者，在超級電腦上發展矩陣計算的快速演算法與高效能軟體，是當代學術界與工業界的重要關鍵，更是極具未來性的主題。針對「線性系統高速計算方法的新發展」，我們特別規劃這個系列課程，提供與國際學術界最新發展接軌的學習機會，培養可以在國際場域發展的下一代人才。希望藉由教師講解與上機實習，讓同學從做中學，進而有信心敢動手做，解決實際的應用問題。
此課程包含下列三部分：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) 的特性，很適合在大型平行電腦上求解超大線性系統。第三部分著重在高效能計算方法的重要觀念與詳細知識，目的是讓聽眾將可以理解、使用、開發最新的平行數值線性代數方法與工具。內容包括平行數值與計算方法，以及如何利用應用問題的矩陣特性，設計更好的演算法。
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.
The contents of course series are categorized as follows :
I. Fundamentals of Iterative Linear System Solvers
From basic iterative methods, we introduce the basic concepts and background knowledge.
II. An Introductory Course on Fast Multipole Methods
We focus on Fast Multiple 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.
III. High-Performance Numerical Solvers with Applications
We concentrate on the concept and knowledge of high-performance computing (HPC) so that users 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.
【Part I】 Fundamentals of Iterative Linear System Solvers
【Part I】 Fundamentals of Iterative Linear System Solvers
Instructor
Instructor
Topic
Topic
- Matrix representation of discrete finite-difference Laplacian
- Conjugate gradient method (CG) for symmetric positive definite linear systems
- Convergence analysis of conjugate gradient methods
- Preconditioning
- Generalized minimal residual method (GMRES) for general linear systems
【Part II】 An Introductory Course on Fast Multiple Methods
【Part II】 An Introductory Course on Fast Multiple Methods
Instructor
Instructor
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.
Abstract
Abstract
This course will focus on fast multiple 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 multiple 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.
Prerequisites : C-language, Analysis, Linear Algebra, Basic Algorithms, and Basic Linux.
Course materials <Download>
Topic
Topic
- Introduction to FMM
- Multipole expansions
- Single-level FMM hands on I & II
- Tree Structure
- Interaction lists
- Multi-level FMM hands on I & II
- Morton keys
- Adaptive tree structure
- Adaptive FMM hands on I & II
- Domain decomposition
- Local essential tree
- Parallel FMM hands on I & II
- Introduction to H-matrix
- SVD and RRQR
- H-matrix hands on I & II
References
References
https://web.njit.edu/~jiang/math614/beatson-greengard.pdf
http://www.bu.edu/pasi/courses/12-steps-to-having-a-fast-multipole-method-on-gpus/
https://www.math.ucdavis.edu/~saito/courses/LapEig/lecpdf/lecture16+17.pdf
http://amath.colorado.edu/faculty/martinss/2014_CBMS/Lectures/lecture02.pdf
【Part III】 High-Performance Numerical Solvers with Applications
【Part III】 High-Performance Numerical Solvers with Applications
Instructor
Instructor
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).
Abstract
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.
Topic
Topic
- 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
Video
Video
- [0503-1] [0503-2]
- [0504-1] [0504-2] Data structure for sparse matrix
- [0505-1] [0505-2]
- [0506-1] [0506-2]
- [0509-1] [0509-2]
- [0510-1] [0510-2]
- [0511-1] [0511-2]
- [0512-1] [0512-2]
- [0516-1] [0516-2]
- [0517-1] [0517-2] Non-Overlapping Domain Decomposition
- [0518-1] [0518-2] Overlapping Domain Decomposition
- [0519-1] [0519-2]
Google Sites
Report abuse