研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Damped Jacobi-type
Preconditioner
for Supernova Simulation
今倉 暁 / Akira IMAKURA
Center for Computational Sciences, University of Tsukuba
Joint work with
櫻井鉄也（筑波大学）, 住吉光介（沼津高専）, 松古栄夫（KEK）
1 / 24

2011 / 12/ 4

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

Introduction

Target simulation

Supernova simulation-- 3D Neutrino transfer (time evolution of neutrino distribution)
νe

νe

νµνe
flux
r-direction[Sumiyoshi, 2011]2 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Introduction

Target simulationScale-- NrxNqxNf = 200 x 9 x 9, NexNnqxNnf = 14 x 6 x 12-- 1/8 circle, r = 0~1140 km
Outline-- Time evolution : Implicit method→ It is required to solve large and sparse linear systems-- The most time consuming part is to solve the systems-- Required time evolution : t = 1 [sec.]→ Larger time step (Δt) is required (Δt ≈ 10-5 [sec.])-- Larger Δt leads to more ill-conditioned systems
3 / 24

2011 / 12/ 4

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷Introduction

Traditional code for linear systems
did not converge

Number of iterations

Bi-CGSTAB with diagonal scaling

Time step (Δt)

Our main goal of this talk

Propose a Damped Jacobi-type preconditioner(with parameter estimation) for supernova simulation

4 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

OutlineIntroduction

Solvers and preconditioners for linear systems
Parameter estimation for damped Jacobi-type
preconditioner
Damped Jacobi-type method
Parameter estimation
Application to supernova simulation
Conclusion
5 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Solvers and preconditionersTarget problem

Large, sparse, real and non-symmetric linear systems:
obtained from supernova simulation.

Solvers for linear systems

Direct methods-- Gaussian elimination, LU decomposition, ...
Stationary iterative methods-- Jacobi, Gauss-Seidel, SOR, ...
Preconditioned Krylov subspace (iterative) methods-- Conjugate Gradient (CG) , GMRES, Bi-CGSTAB, ...
6 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Solvers and preconditioners

Krylov subspace method

Basic ideal: Projection method based on the Krylov subspace
Rough sketch (initial guess:)

7 / 24

2011 / 12/ 4

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

Solvers and preconditioners

Preconditioners for Krylov subspace methods

Convergence of Krylov subspace methods
Convergence depend on distribution of eigenvalues
Preconditioners

Convergence history
relative residual norm

Distribution of eigenvalues

ImRe

Number of iteration
8 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Solvers and preconditioners

Preconditioners for Krylov subspace methods
Incomplete factorization type-- IC, ILU, ...

Approximate inverse type-- SPAI, polynomial preconditioner, (diagonal) scaling, ...
Variable type (use some iterative method)-- GMRES, Jacobi, Damped Jacobi-type method

Our goals of this talk

Propose a parameter estimation techniquefor damped Jacobi-type preconditioner

Examine the performance of the proposed preconditioner
for linear systems from supernova simulation

9 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

OutlineIntroduction

Solvers and preconditioners for linear systems
Parameter estimation for damped Jacobi-type
preconditioner
Damped Jacobi-type method
Parameter estimation
Application to supernova simulation
Conclusion
10 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Stationary iterative methods
Initial partition
whereis assumed to be nonsingular

Recurrence formula

Convergence of stationary iterative method
Convergence depend on spectral radius of iteration matrix:

11 / 24

2011 / 12/ 4

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

Parameter estimation for Damped Jacobi-type prec.
Ideal Stationary iterative methods
High convergence-- It has smallHigh speed-- It requires small computational costs per iteration
High parallelization efficiency-- It has less sequential process (in each iteration)

Traditional stationary iterative methods
ConvergenceMSpeedN Parallelizationparallelization) GoodJacobi Jacobi method
Bad (suitable for GoodGauss-SeidelGoodGoodBadSOR
Bad -- Excellent
GoodBad12 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Damped Jacobi methods
Basic ideal:

Damped Jacobi method transforms the Jacobi’s recurrence formula:intoby using damping parameter
convergence rate of Jacobi method.

in order to improve the13 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4Parameter estimation for Damped Jacobi-type prec.
Damped Jacobi-type methods
Basic ideal:

Damped Jacobi method transforms the Jacobi’s recurrence formula:intoby using damping parameterand some diagonal matrix
in order to improve the convergence rate of Jacobi method.
Users need to set the parameter α,
and the convergence depend strongly on the parameter α

14 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Convergence theorem of damped Jacobi-type method
Theorem 1: Optimal damping parameter
Letbe the inner region of the circle with centerand radiuson the complex plane, and let
defined by

beThen the spectral radiusof iteration matrix of damped
Jacobi-type method is minimized by, and the minimized value is15 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Convergence theorem of damped Jacobi-type method
Theorem 2: Convergence condition
The minimized spectral radius of iteration matrix of damped
Jacobi-type method satisfies the following inequality:

if and only ifor16 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Convergence theorem of damped Jacobi-type method
Remark: Distribution of eigenvalues and Optimal parameter
Distribution ofDamping
Damping
parameterparametercancanbe beoptimized
optimized
distribution
extreme eigenvaluesof eigenvalues
17 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Parameter estimation for Damped Jacobi-type prec.
Parameter estimation (proposal preconditioner)
Basic ideal: Offline tuning-- Damping parameter is estimated before algorithms run.
Input

Initial guess
Diagonal matrix

Approximate extreme eigenvalues ofParameterby some iterations of Arnoldi method

estimation I

Estimate
Parameterfrom approximated extreme eigenvalues

estimation IIRun damped Jacobi-type preconditined Krylov subspacemethod with estimated damping parameter

Preconditioned
Krylov

18 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

OutlineIntroduction

Solvers and preconditioners for linear systems
Parameter estimation for damped Jacobi-type
preconditioner
Damped Jacobi-type method
Parameter estimation
Application to supernova simulationConclusion
19 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Application to supernova simulation

Supernova simulation

Scale-- NrxNqxNf = 200 x 9 x 9, NexNnqxNnf = 14 x 6 x 12-- 1/8 circle, r = 0~1140 km
Obtained linear systems-- Dimension≈ 16 million-- Number of nonzeros ≈ 1.28 billion(Average nonzeros per row or column ≈ 80)

Experimental condition

KEK SR16000/M1-- 1 node 32 cores (logical CPU 64 cores)
20 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Application to supernova simulationProposed preconditioner

Bi-CGSTAB with Damped Jacobi-type preconditioner-- Iteration for preconditioner :20-- Approximate extreme eigenvalues : 20 iters of Arnoldi-- Cutoff parameter :0.01-- Diagonal matrix :21 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Application to supernova simulation

Numerical results

Number of iterations

Time step (Δt) v.s. number of iterations-- Bi-CGSTAB with Diagonal scaling / Proposed precond.

Time step (Δt)

Computational time [sec.]-- Diagonal scaling: 0.3 / iter-- Proposed: 3.0 / iter (estimation: 3.0 / 1 diagonal matrix)

22 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

OutlineIntroduction

Solvers and preconditioners for linear systems
Parameter estimation for damped Jacobi-type
preconditioner
Damped Jacobi-type method
Parameter estimation
Application to supernova simulation
Conclusion
23 / 24

研究会「素核宇融合による計算基礎物理学の進展」 @合歓の郷

2011 / 12/ 4

Conclusion

Conclusion

In this talk, we proposed
Damped Jacobi-type preconditioner with parameter estimation.
From our numerical experiments, we leaned that the proposedpreconditioner will be efficient for supernova simulation.

Further investigation

Further improvement of the proposed preconditioner-- Implementation-- Another acceleration techniques

24 / 24