Testing SSOR preconditioner for
Domainwall/Overlap normalfermions
Ken-Ichi Ishikawa（Hiroshima Univ.）[A04 & A01]

2012/12/13

QUCS 2012 (2012/12/13-16)

1

Contents
1. Lattice Chiral fermions and chiral symmetry
2. Even/Odd site preconditioning
3. SSOR preconditioning for normal equations
4. Results
5. Summary

2012/12/13

QUCS 2012 (2012/12/13-16)

2

1. Lattice Chiral fermions andchiral symmetry• Lattice Chiral fermions– Lattice chiral symmetry: extends continuum chiralsymmetry on the lattice– Avoids additive mass renormalization– Important phenomenologically and theoretically• Low energy QCD/finite temp/chiral condensate,…

• Overlap/Domainwall fermions• Needs huge computational resources– Overlap/Domainwall type >> Wilson type >Staggered type2012/12/13

QUCS 2012 (2012/12/13-16)

31. Lattice Chiral fermions and chiralsymmetry• Needs huge computational resources– Overlap/Domainwall type >> Wilson type > Staggeredtype– This is due to maintain the lattice chiral symmetry or
to maintain accuracy of signum function of
Wilson/Dirac operator– Overlap operator inversion solver• In this talk– Testing solver improvement for• Domainwall fermion inversion (as a 5-D effective form ofOverlap fermions)• On a small lattice
2012/12/13

QUCS 2012 (2012/12/13-16)

4

1. Lattice Chiral fermions and chiral symmetry• Linear equations for Chiral fermions– Overlap operator
1
DOV  (1  m f )  (1  m f ) 5 sign( 5 D4 DW )2

– GW-relation

 5 DOV  DOV  5 

2m f  5  DOV  5 DOV
1 mf



– Linear equation
DOV x  b  x  ( DOV ) 1 b• 5-Dimensional effective form
– By introducing a signum function approximation(matrixfunction)
b5 D  Qb, D5 DEff x5 D  b5 D  x5 D  ( D5 DEff ) 1 b5 D

 x  Px5 D  ( DOV ) 1 b
– at a desired accuracy (sign-func).
2012/12/13

QUCS 2012 (2012/12/13-16)

5

1. Lattice Chiral fermions and chiral symmetry• The form of the 5-Dimensional effective operator– Overlap fermion solver can be converted into 5-Dimensional effectiveform (at a accuracy for signmum function)

D5 Deff  ; (n, r; m, s)   X  ; (r; s) Da ;b

a ,b4 DW  ; (n; m)  Y ; (r; s) a;b (n; m)– n, m : 4-D lattice index, r, s : 5th index, a, b : color, αβγ: spin
– There are several types for the matrixes X and Y. Based on theapproximation type of the signum function.
– D４DW : 4-D Wilson/Dirac matrix with a negative bare mass1     U  a;b (n) (n  ˆ ; m) ;a ,ba ;b

D4 DW  ; (n; m)  (4  M )  ; (n; m)   b;a* 1  1    U  (n  ˆ )  (n  ˆ ; m)
 ;

4– D5Deff has sparse matrix structure on 4D lattice site index. Easy toimplement.

• improve and speed up to solve D5 DEff x5 D  b5 D
2012/12/13

QUCS 2012 (2012/12/13-16)

6

1. Lattice Chiral fermions and chiral symmetry• Properties of the 5-D effective coefficient matrix
D5 Deff  ; (n, r; m, s)   X  ; (r; s) Da ;ba ,b4 DW  ; (n; m)  Y ; (r; s) a;b (n; m)– This contains negative real-part eigenvalues. (at least in free cases)

Continuued fraction approximation
with Shamier kernel– Linear equationsolvers.
2012/12/13

Domainwall type approximation
with Shamier type

D5 DEff x5 D  b5 D is not suitable for iterative
QUCS 2012 (2012/12/13-16)

7

1. Lattice Chiral fermions and chiral symmetry•D5 Deff x  b is not suitable for any iterative solvers as D5 Deff

contains eigenvalues with negative real-part.
• Usually this is solved by normalizing the equatoin:
• Or

DD

†

5 Deff

5 Deff

D5 Deff

D5 Deff

x  D b
z  b, x  D†

5 Deff†

5 Deff†z• The coefficient matrix is now non-negative and Hermit. We
can solve them with CG iterative algorithm.
• However the convergence is slow as the coefficient matrix isdoubled and could have a large condition number.
• Preconditioning for the normal equation is desired to improvethe convergence property.
2012/12/13

QUCS 2012 (2012/12/13-16)

8

1. Lattice Chiral fermions and chiral symmetry• In this talk, I tried two types of preconditioning for theDomainwall quark sovler and compared them on asmall lattice.
• (1) Even/odd site precidiotioning forDx
b5Deff+ then Normalized• (2) SSOR preconditioner for the normal equaiton:

D

5 Deff†

†

D5 Deff x  D5 Deff b– No-lattice parallelism. Single computer test.
– Type(1) preconditioning has been used in the literature.
– Tyep(2) the direct use of the SSOR for the normal equation is not seen.

• Conclusion from my test:• Type(2) is not good at the elapse time level even if thereduction of the iteration counts of the CG solver is seen.
2012/12/13

QUCS 2012 (2012/12/13-16)

9２. Even/Odd preconditioning + normalize• Preconditioning based on Even/Odd (or Red/Black) siteordering– 4D lattice index is colored by mod(nx+ny+nz+nt, 2). D5Deff is Sparse matrix(w.r.t. 4D lattice site index)– The linear equation D5 Deff ee D5 Deff eo D5 Deff   D5 Deff oe D5 Deff oo 
D5 Deff x  b is transformed to1
1
Dˆ 5 Deff ee  1  D5 Deff ee  D5 Deff eo D5 Deff oo  D5 Deff oe11bˆe  D5 Deff ee  be  D5 Deff eo D5 Deff oo  boDˆ 5 Deff ee xe  bˆexo  D5 Deff oo  bo  D5 Deff oe xe 1

Dˆ 5 Deff ee is still ill conditioned (e-values with negative real part). Normal–equation is applied.

Dˆ

2012/12/13

†Dˆ 5 Deff ee xe  Dˆ 5 Deff ee bˆe†
5 Deff ee

QUCS 2012 (2012/12/13-16)(1)Even/odd-NRCG
10

３. SSOR preconditioning for Normalequations• SSOR Preconditioning by the 4D-site index structure:†A  D5 Deff D5 Deff  C  L  U

C : Diagonal part
L : Strictly Lower triangular partU : Strictly Upper triangular part

• SSOR preconditioning by multiplying the inverse of1  C L  and 1  C U 
1



1

Aˆ  1  C L C A 1  C U
11



1

1

1

SSOR preconditioned matrix

• The inversion of 1  C 1L and 1  C 1U is done byforward or backward substitution.
2012/12/13

QUCS 2012 (2012/12/13-16)

11

3. SSOR preconditioning for Normal equations†5 Deff

D5 Deff x  DD1  C L  C D
1

1

1

†5 Deff





†

1

5 Deff D5 Deff 1  C U

 Aˆ y  c, c  1  C L  C Db

 y  1  C L  C D
1

1

1

15 Deff†b(B) NRSSOR-CG SSOR preconditioned matrixb, x  1  C U  y,1
1ˆA  1  C 1 L 1 C 1 D †D,5 Deff
5 Deff 1  C U
1

1

15 Deff†11• Â is still non-negative and has a reduced condition number.
• Expected that CG solver for (B) converges faster than original equation.
• However the implementation of the forward and backward solver isdifficult. This is because of the extended hopping structure of†AD
5 Deff D5 Deff
• Here we consider– Normal site ordering.
1
D
D
K

1  M hop
5 Deff
DWF– Domainwall operator.
2
2012/12/13

QUCS 2012 (2012/12/13-16)

12Hopping structure of• 4D lattice site access†Dpattern of DWF DDWF
• Two-hopping
operations（orange andyellow）• L-type link vars.
• L-type access is tensor.
• Computational cost ismuch larger if we do
not use intermediatevectors.
• SSOR requires hopping
access decomposition.
2012/12/13†

DDWF DDWF .

†DDWF DDWF

Upper part

QUCS 2012 (2012/12/13-16)

Lower part13

Difficulty of SSOR†
DWF

• Two hopping operations in D

DDWF v1    1    U  (n)U (n  ˆ )v(n  ˆ ˆ) 44

1 1

1    1    U  (n)U (n  ˆ ˆ)v(n  ˆ ˆ) 44†

1 1

1    1    U  (n  ˆ )U (n  ˆ )v(n  ˆ ˆ) 44†

1 1

1    1    U  (n  ˆ )U (n  ˆ ˆ)v(n  ˆ ˆ) 44

†

†

1 1

• Tensor summation => Too many computations.
• We must keep intermediate vector site by site as
done usualy for†
DWFwD2012/12/13†DWFDDWF v  s  DDWF v, w  DQUCS 2012 (2012/12/13-16)

s14

Textbook:”Iterative Methods for Sparse Linear Systems”, Y.Saad, 2nd ed., 2003.SIAM.

SSOR for Normal equation by Saad (NRSSOR)†• Site access pattern for DDWF DDWF

• Keeping working vector z s.t. z  DDWF x holds
2012/12/13

QUCS 2012 (2012/12/13-16)

15

3. SSOR preconditioning for Normal equations by Saad
1(1CL) x  b• Solver algorithm for1
D5 Deff  DDWF  K  1  M hop
2x(:)  0; z (:)  0for n (4D lattice site, ascending order for L part)

Global Working vector zv0z  DDWF x†v  ( M hop z )(n)for   1,2,3,4v  v  1    U  (n) z (n  ˆ )  1    U  (n  ˆ ) z (n  ˆ )†end for

Local update vector v

1v  b(n)  C 1 ( K†z (n)  v)
2x ( n)  v

Update x at n1

†DWFv  b( n)  C D

z ( n)z (n)  z (n)  Kv
for   1,2,3,41
1    U  (n  ˆ )v
21†z (n  ˆ )  z (n  ˆ )  1    U  (n)v
2end forz (n  ˆ )  z (n  ˆ ) end for2012/12/13

Keep the relation between x and z
QUCS 2012 (2012/12/13-16)

16

4. Results• Benchmarking Parameters– 12^3x24,β=5.7 Wilson gauge Quenched one config– DWF (Borici) Domainwall,– DW height M = 1.6– mass mq=0.03– SSOR over relaxation parameter omega=1.0, 1.5– ５th length N5=24– mres = －0.01655– We compare• Iteration counts, timing, and Flop counts for CG
convergence between(1) Even/Odd-NRCG and (2) NRSSOR-CG
2012/12/13

QUCS 2012 (2012/12/13-16)

17

4. Results• CG residual history
Reduced Iteration counts
for NRSSOR-CG
By ¾.

NRSSOR actually reduces
the condition number

2012/12/13

QUCS 2012 (2012/12/13-16)

18

4. Results• CG Floating point number operation history
Total Flop count:
NRSSOR-CG is a factor 2 larger
than E/O-NRCG
CG one iteration:
NRSSOR-CG requires 1.5x
computation than E/O-NRCG
during one CG-iteration.

2012/12/13

QUCS 2012 (2012/12/13-16)

19

4. Results• Timing for CG convergence
The convergence time isslightly slower for NRSSOR-CG
than E/O-NRCG.
NRSSOR has some benefit
from the local update
algorithm as it helps cache
usage. The good cache
property of NRSSOR cureslarger computational cost ofNRSSOR.

NRSSOR is slow.
2012/12/13

QUCS 2012 (2012/12/13-16)

20

5. Summary• We tested the SSOR preconditioner for the normal equation of theDomainwall fermion.
• We compared the NRSSOR-CG and Even/odd-NRCG.
• The CG iteration count is reduced by a factor 3/4• The computational cost is 1.5x larger for single CG-iteration.
• The convergence time of the NRSSOR-CG is slower than theEven/Odd-NRCG• The Origin of the larger computational cost
– My implementation for the NRSSOR keeps the relation z  DDWF x
during the SSOR iteration. This computation contains redundant
computation. Some component of z is not reused.

2012/12/13

QUCS 2012 (2012/12/13-16)

21