PROGRESS OF ALGORITHMS IN
LATTICE GAUGE SIMULATIONSA D Kennedy
University of Edinburgh

Outline• Functional Integrals and Monte Carlo• Markov Chains• Hybrid Monte Carlo• Multiple Pseudofermions• Domain Wall and Overlap• Shadow Hamiltonians• Perambulation, Distillation, and all that
• Implications for Hardware•My goal is to give a broad overview for non-experts

Monday, 17 December 2012

QUCS 2012, Nara2

Introduction• The goal of LGT is to solve quantum
field theories non-perturbatively• Not solving PDE– But we end up integrating Hamilton’sequations anyhow• Lots of linear algebra• Well suited to large parallel computers
Monday, 17 December 2012

QUCS 2012, Nara

3

Functional Integrals• The basic problem is just to evaluate
the Feynman path integral for someinteresting action S and observable 

W=1Z

df
W
fe()
・iS(f )– This looks easy, but  is a field and theintegral is thus infinite dimensional
Monday, 17 December 2012

QUCS 2012, Nara

4

Euclidean Field Theory• In order to make this numericallytractable we work in Euclidean spaceiSwhere eｮ e- Sis real and positive– We will pay for this later when we want tomake measurements– Similar to statistical mechanics
Monday, 17 December 2012

QUCS 2012, Nara

5

Configurations & Measurements• Computations are split into two phases– Generate ensemble of field configurations– Make measurements on this ensemble

W=1

NW(f n )・N n=1

Monday, 17 December 2012

QUCS 2012, Nara

6

Monte Carlo• The only feasible way of evaluating ∞dimensional integrals is by Monte Carlo• Hopeless without importance sampling• Need to generate four dimensional field
configurations with probability density

P (f )df ｵ e- S(f )Monday, 17 December 2012

QUCS 2012, Naradf7

Markov Chains• Use ergodic Markov chain with thisdistribution as its fixed point– Ergodic means you can get from anywhere toanywhere with non-zero probability• Fixed point ← detailed balance ← Metropolis• We can mix different steps as long as they all
have the same fixed point distribution– Individual steps do not need to be ergodic as longas a combined steps are ergodic
Monday, 17 December 2012QUCS 2012, Nara

8

Hybrid Monte Carlo• Introduce a “fictitious” Hamiltoniansystem with action as the potential

H (f , p ) =12

2p + S (f )• Generate fields in this “phase space”
with distribution

P (f , p ) ｵ e- H (f ,p )Monday, 17 December 2012

QUCS 2012, Nara

9

Hamiltonian Monte Carlo• We then use Hamilton’s equations toproduce a reversible and area
preserving Markov step
– Perfect for Metropolis with acceptanceprobability,p )P (f ｢｢- dH (f ,p )Paccept ==e
P (f , p )Monday, 17 December 2012

QUCS 2012, Nara

10

HMC
• To make this ergodic interleave it with amomentum refreshment Markov step– This just selects new momenta from a Gaussianheatbath• Symmetric Symplectic Integrators– No step-size errors– Step-size just controls acceptance rate
– Acceptance rate and trajectory length control
autocorrelations• Still interesting questions about scaling
behaviour (Lüscher and Schaefer)
Monday, 17 December 2012

QUCS 2012, Nara

11

Fermions• Fermions are anti-commuting(Grassmann) fields- y (f )y + hy + yh

Z (h, h) = ・dy d y e= det (f )eh (f )- 1 h• This causes two nasty problems
Monday, 17 December 2012

QUCS 2012, Nara

12

Fermionic Observables• Nasty problem #1– Need inverses of the fermion kernel for
fermion correlators
2- 1( )
x ,ydZ=  (f )y x y (y ) =dh (x )dh (y )Monday, 17 December 2012

QUCS 2012, Nara

13

Pseudofermions• Nasty problem #2– Write the fermion determinant as a bosonic
functional integral

det (f ) ｵ ・d x dx e

- x - 1(f )x– These unphysical spin-half bosons are
known as pseudofermions
Monday, 17 December 2012

QUCS 2012, Nara

14

Pseudofermion Heatbath• We can easily generate pseudofermion
fields from another Gaussian heatbath• But we need to solve a linear system toupdate the gauge fields

ｶｶ
H- 1
鴿
= +p&= S
fx
fx

()
()
ff ・ｶｶｶ(f ) - 1
ｶS- 1 (f )x= + x  (f )ｶｶ
ffMonday, 17 December 2012

QUCS 2012, Nara

15

Pseudofermions Instability• For a long time it was thought that it wasprohibitively expensive to reach small (physical)
quark masses• The HMC integrator step size had to be verysmall for light fermions to avoid instabilities• This was thought to becaused by the Dirac operator(fermion kernel) becoming
almost singularMonday, 17 December 2012

QUCS 2012, Nara16

Single Pseudofermions• But this was wrong• The problem was that we wereestimating the fermion determinant
using a single pseudofermionic Monte
Carlo estimate– This is clearly a very noisy estimate– But surely the Markov process is still valid?
– True, but it becomes very slow
Monday, 17 December 2012

QUCS 2012, Nara

17

Multiple Pseudofermions• The solution is to introduce multiple
pseudofermion fields– A small number suffice– Several ways of doing this• Hasenbusch• RHMC (rational approximation)• DDHMC (Lüscher)• Computations with physical quark
masses now possible
Monday, 17 December 2012

QUCS 2012, Nara

18

Chiral Symmetry• Another long-standing problem oflattice field theories was that chirali ag5
symmetry y ｮ e y is explicitly
broken on the lattice– It is violated by both Wilson and staggered discretizations of
the Dirac operator– Only restored in the continuum limit with much fine-tuning– Chiral symmetry explains much low-energy phenomenology,
such as the  being the Goldstone boson for spontaneously
broken chiral symmetry
Monday, 17 December 2012

QUCS 2012, Nara

19

On-Shell Chiral Symmetry• Replace with Lüscher’s on-shell chiralsymmetryy ｮｮey, ye
i ag5(1- aD )i a (1- aD )g5• Which leads to the Ginsparg—Wilsonrelation

g5D + D g5 = 2aD g5D
Monday, 17 December 2012

QUCS 2012, Nara

20

Domain Wall and Overlap• This problem has been solved by the(equivalent) Domain Wall and Overlap
formulations

DN = 21 鴿1gsgng
DM+()
55
W
・– This Neuberger operator is very expensive toapply, and even more expensive to invert– We need to implement the sgn function– Most algorithms use some rational approximationand some five-dimensional Schur complement
Monday, 17 December 2012

QUCS 2012, Nara

21

Improvement• Improved actions have long been popular− Improve discretization to better approximate continuum
physics on coarse lattices– Works in context of perturbative
QFT (Symanzik)– Sadly, improvement is an
asymptotic expansion and cutn
- c/ aoff effects fall as a + e• But improved actions areless local– Not a problem in principle, butmaybe in practice as we workon finite lattices
Monday, 17 December 2012

QUCS 2012, Nara22

Shadow Hamiltonians• Numerical integration of Hamilton’s
equations use symmetric symplectic
integrators• These exactly conserve a Shadow
Hamiltonian close to the desired one– Again, only an asymptotic expansion• This can be used to “automate” tuningof integrator parameters• Higher-order integrators important forlarger lattice volume?
Monday, 17 December 2012

QUCS 2012, Nara23

Perambulation, Distillation, etc.
• Finding eigenstates of the Hamiltonian (TransferMatrix)– Measuring correlation functions is essentially just the power
method• But the state space is very large…
– Choice of basis– All-to-all solvers– Low modes and eigensolvers• Multigrid and local coherence– Helpful for many solutions on same configuration• Stochastic estimates• What is a good basis for nuclei?
Monday, 17 December 2012

QUCS 2012, Nara24

Implications for Hardware• Lattice field theory Monte Carlo computations
are ideally suited to massively parallel
computation– Current bottlenecks are streaming memory access– Future bottlenecks probably 4D grid network communications
and global reductions– Fundamental problem is getting data on/off chip

• Homogeneous or inhomogenous network?
– Mainly a balance of cost and pain (cost usually wins)• Multi-scale algorithms can be implemented but
have lower performance
Monday, 17 December 2012

QUCS 2012, Nara25

Software Matters• Cost and delay of efficient
implementation of new algorithms
on awkward new machines– Tension between efficiency and portability– Inhibits experimentation and use of newtechniques• Algorithms and architecture stable enoughto partition software stack into layers– Different people responsible for different layers– Cleaner interfaces between layers (HPCbytecode?)
Monday, 17 December 2012

QUCS 2012, Nara26

Conclusions• Lattice Gauge Simulations algorithms
have reached a mature stage• Changes have been incremental ratherthan revolutionary– No reason to expect this to change• Improved methods with better volume
scaling will help as lattices get larger– E.g., force-gradient integrators
Monday, 17 December 2012

QUCS 2012, Nara27