2013 Winter
2013 臺大數學科學中心 科學計算冬季學校
新世代的高效能矩陣計算
(2013 TIMS Winter School for Scientific Computing)
最新訊息
- [2013/12/04] 參加12月6,7日「高效能線性系統求解」課程聽眾，請依下列步驟在您的筆電事先安裝相關軟體。謝謝！
- (1) Download the files from “http://goo.gl/wya3Lm".
- (2) Unzip the file “Test.vdi.bz2”.
- (3) Follow the instruction in the file "VirtualBox.install" to install it the software.
- [2013/12/01] 上課地點更動為「臺灣大學天文數學館，102教室」（地圖）。
- [2013/12/01] 課程投影片已經可以下載，現場不提供紙本。
- [2013/12/01] 參加12月6,7日「高效能線性系統求解」課程聽眾，請攜帶筆電。我們會協助安裝 Linux virtualbox，並利用 MPI 與 OpenMP 進行平行計算。
課程資訊
2013年12月的前兩周，將有個特別的學術盛會。數位美國國家工程院士，以及來自全球學界、國家實驗室、產業界頂尖研究人員，將齊聚一堂，針對新世代的高效能矩陣計算，以「科學計算冬季學校」短期課程與「NCTS Workshop on Numerical Linear Algebra and High Performance Computing (NLAHPC)」 國際學術會議的方式，暢談最新重要研究與應用議題，引領聽眾進入新世代高效能矩陣計算的廣闊殿堂。在「科學計算冬季學校」短期課程的部分，將包含下列主題與講者：
- 12/3,4：高效能特徵值計算 (Ren-Cang Li, University of Texas at Arlington)
- 12/5：GPU 上的線性系統直接法。如何應用 GPU 在半導體電路模擬器 (Lung-Sheng Chien, NVIDIA Corporation)
- 12/5：以疊代法求解奇異線性系統 (Sou-Cheng Choi, Argonne National Laboratory)
- 12/5：子空間學習中的數值線性代數 (a related event by Lek-Heng Lim, University of Chicago)
- 12/6,7：高效能線性系統求解 (Xiaoye Sherry Li, Lawrence Berkeley National Laboratory)
其中「高效能特徵值與線性系統求解」，是 2013 Gene Golub SIAM Summer School 的主題課程之一。Prof. Choi 的演講部分內容也獲得 2012 SIAM Activity Group on Linear Algebra Prize。歡迎各界研發人員與同學參加！
日期：2013年 12月 3日至 7日 (星期二至星期六)
地點：國立臺灣大學，天文數學館102教室 數學研究中心308室 (原新數館)
主辦：臺大數學科學中心
聯絡人：王偉仲教授 (臺灣大學應數所，wwang@ntu.edu.tw)，
劉英貝小姐 (臺大數學科學中心，tassist4@tims.ntu.edu.tw，02-3366-9901)
1. Course
Course Schedule
Titles and Speakers
EV 1-8
High Performance Eigenvalue Computations
Ren-Cang Li, University of Texas at Arlington
GPU 1
How to Avoid Global Synchronization by Domino Scheme for Sparse Triangular Solve, Incomplete Cholesky Factorization and Incomplete LU Factorization?
Lung-Sheng Chien, NVIDIA Corporation, USA
GPU 2
What Does It Take to Accelerate SPICE on the GPU?
Lung-Sheng Chien, NVIDIA Corporation, USA
GMRES 1
Minimal Residual Methods for Solving Singular Hermitian, Complex Symmetric, or Skew Hermitian Linear Equations
Sou-Cheng (Terrya) Choi, University of Chicago/Argonne National Laboratory
GMRES 2
Minimal Residual Methods for Solving Singular Unsymmetric or Non-Hermitian Linear Equations
Sou-Cheng (Terrya) Choi, University of Chicago/Argonne National Laboratory
SL
Numerical Linear Algebra for Subspace Learning
Lek-Heng Lim, University of Chicago
LS 1-8
High Performance Linear Solvers
Xiaoye Sherry Li, Lawrence Berkeley National Laboratory/University of California, Berkeley
2. Abstracts
Course Schedule
Abstracts
EV 1-8 (12/3/Tue-12/4/Wed, 10:10-15:20)
LS 1-8 (12/6/Fri-12/7/Sat, 10:10-15:20)
High Performance Linear Solvers and Eigenvalue Computations
by Ren-Cang Li and Xiaoye Sherry Li
Efficient algorithms for matrix functions and equations depend critically on the solutions of underlying linear systems and eigenvalue problems. This course aims at bringing to the students the state-of-the-art high performance methods for sparse linear systems and eigenvalue computations. Many practical aspects will be addressed to deliver high speed and robustness to the users of today's sophisticated high performance computers.
For the part of linear systems, we will discuss sparse factorization techniques for building sparse direct, and hybrid direct/iterative solvers, and efficient preconditioners. An outline of this part is
- Sparse matrix data structures;
- High performance computer architectures, parallel programming;
- Sparse direct solvers;
- Domain decomposition, hybrid direct/iterative solvers;
- Advanced topics, such as scalable memory- and communication-reducing algorithms;
- Applications and software issues.
For the part of eigenvalue computations, we will review existing work on Rayleigh quotient-based methods and present recent developments. An outline of this part is
- Basic theory;
- minimization principles;
- Rayleigh quotient-based optimization techniques;
- Convergence theory and asymptotic analysis;
- Preconditioning techniques;
- Applications and software issues;
- Other eigenvalue problems that admit certain minimization/maximization, including the singular value decomposition problems and the linear response eigenvalue problems.
GPU 1 (12/5/Wed/10:10-11:00)
How to Avoid Global Synchronization by Domino Scheme for Sparse Triangular Solve, Incomplete Cholesky Factorization and Incomplete LU Factorization?
(by Lung-Sheng Chien)
- Abstract. GPU has shown its power on several applications, including FFT, BLAS3 and molecule dynamics which are computational-intensive and have regular structure to take advantage of wide I/O. However GPU so far does not perform well on sequential-nature problems, for example, sparse linear algebra. There are three operations we want to focus in this talk, sparse triangular solve, incomplete Cholesky factorization and incomplete LU factorization, which are heavily used as preconditioners of a linear system. There are several issues we want to address, including 1) How to reproduce the result without atomics, 2) How to keep one kernel to track dependence graph, 3) How to keep small working space because GPU has limited device memory.
GPU 2 (12/5/Wed/11:10-12:00)
What Does It Take to Accelerate SPICE on the GPU?
by Lung-Sheng Chien
- Abstract. In this talk we will introduce the basic concepts behind The Simulation Program with Integrated Circuit Emphasis (SPICE) and discuss in detail the two most time consuming parts of the circuit simulation: the device model evaluation and the solution of large sparse linear systems. In particular, we focus on the evaluation of the basic models, such as resistor, capacitor and inductor as well as more complex transistor (BSIM4v7) model on the GPU. Also, we discuss the solution of sets of linear systems that are performed throughout the simulation. We take advantage of the fact that the coefficient matrices in these linear systems have the same sparsity pattern (and often end up with the same pivoting strategy) and show how to obtain their solution using a direct method on the GPU. Finally, we present numerical experiments and discuss future work.
GMRES 1 (12/5/Wed, 13:30-14:20)
Minimal Residual Methods for Solving Singular Hermitian, Complex Symmetric, or Skew Hermitian Linear Equations
by Sou-Cheng (Terrya) Choi
- Abstract. Most existing Krylov subspace algorithms for linear systems assume non-singularity of the matrices or linear operators. MINRES-QLP (Choi, Paige, and Saunders 2011) is a MINRES-like algorithm but designed for computing the unique minimum-length and minimum-residual solutions of singular symmetric or Hermitian problems using efficient short-recurrent solution updates and stopping conditions. On nonsingular systems, MINRES-QLP is more stable than MINRES (Paige and Saunders 1975). In this talk we present a common framework that evolves similarly stable and effective algorithms for solving complex-symmetric, skew symmetric, and skew Hermitian linear systems or least-square problems.
GMRES 2 (12/5/Wed, 14:30-15:20)
Minimal Residual Methods for Solving Singular Unsymmetric or Non-Hermitian Linear Equations
by Sou-Cheng (Terrya) Choi
- Abstract. GMRES (Saad and Schultz 1986) is a famed minimal-residual method for solving nonsingular unsymmetric or non-Hermitian linear systems. It may suffer non-benign breakdown on nearly singular systems (Brown and Walker 1997). When working, the solver returns only a least-squares solution for a singular problem (Reichel and Ye 2005). We present GMRES-QLP and GMRES-URV, both successful revamps of GMRES, for returning the unique pseudoinverse solutions of (nearly) singular linear systems or linear least-squares problems. On nonsingular problems, they are numerically more stable than GMRES. In any case, users do not need to know a priori whether the systems are singular, ill-conditioned, or compatible; the solver constructively reveal such properties. The solvers leverage the QLP and URV decompositions (Stewart 1998 and 1999) to reveal the rank of the Hessenberg matrix from the Arnoldi process, incurring only minor additional computational cost in comparison to GMRES. We present extensive numerical experiments to demonstrate the scalability and robustness of the solver, with or without preconditioners or restart.
SL (12/5/Wed, 15:30-16:20) (related event)
Numerical Linear Algebra for Subspace Learning
by Lek-Heng Lim
- Abstract. Modern data are most commonly described by an object-by-feature matrix where the rows correspond to objects, which may be genes, tweets, movies, etc, and the columns correspond to measured features, which may be microarrays, keywords, ratings, etc. Such a matrix may often be viewed as representing a subspace spanned by its rows or its columns. Comparing different data then often boils down to measuring distances (and angles) between subspaces. This is classical if the subspaces are of the same dimension but presents difficulties when they are not. In this talk, we will discuss how one may address this problem. The first part of this talk is joint work with Lizhen Lin, Sayan Mukherjee, and Brian St. Thomas of Duke. The second part is joint work with Ke Ye of Chicago.
3. Poster
Poster in PDF
4. Organizers
Tsung-Min Huang, National Taiwan Normal University (黃聰明)
Feng-Nan Hwang, National Central University (黃楓南)
Che-Rung Lee, National Tsing Hua University (李哲榮)
Wen-Wei Lin, National Chiao Tung University (林文偉)
Chern-Shuh Wang, National Cheng Kung University (王辰樹)
Weichung Wang, National Taiwan University (王偉仲)