On solution of large linear system : iterative solver

Abstract

    In this seminar, Krylov subspace methods, which are frequently used to solve a large sparse linear system, are reviewed. Usage of CG/GMRES methods included in Intel Math Kernel Library (MKL) on supercomputer OCTOPUS will be instructed as hands-on training. A preconditioning technique by using additive Schwarz method consisting of direct solver in sub-matrices is introduced.
     

Contents

    - Overview of Krylov subspace methods and details of preconditioned CG/GMRES methods
    - Preconditioner by incomplete LU factorization
    - Preconditioner by additive Schwarz method that is constructed by combination of decomposition of the sparse matrix using METIS graph partitioner and direct solver in sub-matrices
    - Data structure to store sparse matrix, CSR
    - Usage of CG/GMRES method in Intel MKL through Reverse Communication Interface (RCI)
    - How to link your code to these libraries on OCTOPUS supercomputer.
     

Recommended to whom

    - wants to solve large sparse linear system in a numerical simulation of fluid dynamics, structural analysis, or electromagnetic analysis
    - has experience to write simulation code by C or Fortran.
     

Note

    - This seminar consists of lecture and hands-on training. Please bring your own note PC, which can connect to network and with terminal software installed.
    - A trial account of OCTOPUS without a fee will be provided for this seminar.
     

About iterative solver

    In numerical simulation of fluid dynamics, structural analysis, or electromagnetic analysis, large linear and/or nonlinear systems, which are obtained by discretization process of partial differential equations (PDEs), need to be solved. Nonlinear problem can be linearized by a Newton iteration, hence linear system with large sparse matrix should be treated.
     
    There are two methods to solve sparse the matrix problem, direct method, e.g., LU-factorization and iterative method, e.g., conjugate gradient method. Direct solver can robustly find a solution of the linear system of matrix with large condition number, which is obtained from strong nonlinear problem or originated from phenomena with large jump of physical coefficients. Usually, these matrices are hard to solve by iterative methods. A drawback of direct solver is that it has large complexity of computation and consumes large memory. On the contrary, iterative method has lower complexity of computation but iterative process strongly depends on character of the matrix and it often does not converge in realistic time.
     
    In this seminar, we deal with Krylov subspace method, which is one of the most common iterative solvers. We aim to accelerate the convergence of the Krylov subspace method by introducing a preconditioner based on direct solver in subdomains. Krylov subspace method finds an approximate solution in a subspace called as Krylov subspace, which is generated by multiplications of the sparse matrix to the initial residual induced from the initial solution. Conjugate Gradient (CG) method is designed for symmetric positive definite matrix and Generalized Minimum Residual (GMRES) method for general unsymmetric matrix. It is very important to select an appropriate preconditioner based on multiplication of approximate inverse of the sparse matrix to the both sides of the linear equation. GMRES achieves the most robust iterative procedure in the Krylov subspace methods, but it has large complexity in the computation, i.e., longer iteration leads to larger computational costs. An additive Schwarz method, where the inverse operation is approximated by union of solutions obtained from direct solver in each subdomain, can be constructed only from the matrix data without any knowledge on physical characteristics of the PDE system. This property is similar to a well-known preconditioner based on incomplete LU factorization. Since the additive Schwarz method has more strong approximation property in inversion of the matrix than ILU-factorization, the preconditioned GMRES can converge quickly and the method becomes a practical tool to solve a large linear system.

 

Materials


Date : Nov 21, 1:15 p.m. - 5:00 p.m. (registration from 1:00 p.m.)
Instructor: Cybermedia Center, Osaka University
Lecturer : Dr. Atsushi Suzuki, Guest associate professor
Venue: Cybermedia Commons, the first floor main hall at Cybermedia Center, Suita Campus
Type : classroom study and hands-on training
Quota: 30 persons (registration will be closed when number of participants exceeds 30)
Application deadline: Nov 21, 5:00 p.m.

Reception has been closed.