# Presentation: 474763

## Algorithms for Lattice QCD with Dynamical Fermions 

- A D Kennedy
- University of Edinburgh

## ...The lattice conferences have had a steady diet of spectroscopy and matrix element calculations from these projects. But this year there seemed to be a pause. I think many people have decided that they just cannot push the quark masses down far enough to be interesting, and have gone back to studying algorithms.

Tom DeGrand hep-ph/0312241

- Tom DeGrand _[hep-ph/0312241](http://arxiv.org/pdf/hep-ph/0312241)_

- Testimonial

*                    **(I expect to get a lot of unhappy mail about this sentence.)*

## Numerical Simulations under Battlefield Conditions: I

## Numerical Simulations under Battlefield Conditions: II

- No continuum limit
- Two lattice spacings or fewer
- Autocorrelations ignored
- Depend on the physics anyhow
- Naïve volume scaling
- V for *R* algorithm
- V5/4 for HMC
- Dynamical quarks
- No valence mass
- Two or three flavours
- CAVEAT EMPTOR!

- S Gottlieb (MILC) _[hep-lat/0402030](http://arxiv.org/PS_cache/hep-lat/pdf/0402/0402030.pdf)_
- K Jansen (tmlQCD and χLF)
- R Mawhinney (Columbia and RBRC)
- CP-PACS _[hep-lat/0404014](http://arxiv.org/PS_cache/hep-lat/pdf/0404/0404014.pdf)_
- CP-PACS and JLQCD _[Nucl. Phys. B](http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TVD-45XSH59-Y-1&_cdi=5532&_orig=search&_coverDate=03/31/2002&_qd=1&_sk=998929999&view=c&wchp=dGLbVzz-zSkWA&_acct=C000043939&_version=1&_userid=809099&md5=63452db7defc3cc97100acd8686d8384&ie=f.p)__[106 ](http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TVD-45XSH59-Y-1&_cdi=5532&_orig=search&_coverDate=03/31/2002&_qd=1&_sk=998929999&view=c&wchp=dGLbVzz-zSkWA&_acct=C000043939&_version=1&_userid=809099&md5=63452db7defc3cc97100acd8686d8384&ie=f.p)__[(2002) 195-196](http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TVD-45XSH59-Y-1&_cdi=5532&_orig=search&_coverDate=03/31/2002&_qd=1&_sk=998929999&view=c&wchp=dGLbVzz-zSkWA&_acct=C000043939&_version=1&_userid=809099&md5=63452db7defc3cc97100acd8686d8384&ie=f.p)_

## Numerical Simulations under Battlefield Conditions: III

- Wilson (Clover)
- Very expensive
- Dirac spectrum not bounded
- ASQTAD (KS/Staggered)
- Relatively cheap
- Dirac spectrum bounded
- Twisted Mass (QCDTM)
- Relatively cheap
- Dirac spectrum bounded
- Domain Wall (GW/Overlap)
- Chiral limit for non-vanishing lattice spacing
- How much chiral symmetry is wanted?
- 10—100 times ASQTAD
- At today’s parameters
- Dirac spectrum bounded

## If a QFT is local then...
Cluster decomposition
(Perturbative) Renormalisability
Power counting
Universality
Improvement
...otherwise
Who knows?

- Cluster decomposition
- (Perturbative) Renormalisability
- Power counting
- Universality
- Improvement
- ...otherwise
- Who knows?

- Why Locality?

## Locality

## Is M1/2 Local?

**[1]** B Bunk, M Della Morte, K Jansen & F Knechtli _[hep-lat/0403022](http://arxiv.org/PS_cache/hep-lat/pdf/0403/0403022.pdf)_
**[2,3]** A Hart and E Müller _[hep-lat/0406030](http://arxiv.org/abs/hep-lat/0406030)_
- S Dürr & C Hoebling _[hep-lat/0311002](http://arxiv.org/PS_cache/hep-lat/pdf/0311/0311002.pdf)_

- Finite Volume

- Improvement

- Lattice Spacing

## Hidden Locality

- It is easy to transform a manifestly local theory into an equivalent but non-manifestly local form...
- We use this freedom to replace fermion fields with a non-manifestly local fermion determinant
- To introduce a pseudofermion representation
- To simulate the square root of a determinant
- ...but in general a non-local theory has no reason to be equivalent to a local one

## Fewer Staggered “Tastes”

- Staggered quarks come in four degenerate tastes
- det(M) in functional integral
- det(M)1/2 for two tastes
- Generate gauge configurations with square root weight using *R*, PHMC, or RHMC algorithms
- Is this a local field theory?
- ** **_**local**_** M’ such that ****det(M’)**** = det(M****1/2****)?**
- Must use M’ for valence quarks too for a consistent unitary theory
- Mixed action computations?
- 4 taste valence + 2 taste sea
**Unitarity? **(same disease as quenched)
- Which are the physical valence states?

## Why Fat Links?

- Construct good sources & sinks
- Better overlap with ground state
- Spatial smearing
- Suppress UV fluctuations
- Improved actions for dynamical computations

## DBW2
HYP
APE
Stout
FLIC
Lüscher-Weiss
Iwasaki
Symanzik

- HYP
- APE
- Stout
- FLIC
- Lüscher-Weiss
- Iwasaki
- Symanzik

- Fat Links: Buyer’s Guide

## Fat Links: Dynamical FLIC

- W Kamleh, D B Leinweber & A G Williams _[hep-lat/0403019](http://arxiv.org/PS_cache/hep-lat/pdf/0403/0403019.pdf)_

## Stout Links

- C Morningstar & M Peardon _[hep-lat/0311018](http://arxiv.org/PS_cache/hep-lat/pdf/0311/0311018.pdf)_

## Does Stoutness Pay?

- These methods can be applied iteratively to produce differentiable links of arbitrary obesity

- Stout links seem to be about as good as ordinary projected links, but require more tuning

## Schwartz Alternating Procedure

- M Lüscher _[hep-lat/0304007](http://arxiv.org/PS_cache/hep-lat/pdf/0304/0304007.pdf)_

## SAP Preconditioner

- #2: Preconditioner for linear solver
- Use GCR or FGMRES solver
- Accurate block solves not required
- 4 block MR steps, 5 Schwarz cycles
- Parallelises easily
- Especially on coarse-grained architectures such as PC clusters
- Reduces condition number by preconditioning high frequency modes

- M Lüscher _[hep-lat/0310048](http://arxiv.org/PS_cache/hep-lat/pdf/0310/0310048.pdf)_

## R Algorithm

- Inexact algorithm
- Distribution has errors of *O(*******
- Clever combination of non-reversibility and area non-preservation
- Asymptotic expansion in **
- Results for large **do _not_ just correspond to a renormalisation of the parameters
- C.f., perturbation theory is also asymptotic (or worse)

- C.f., “improvement” expansion in the cut-off *a* (lattice spacing) is also asymptotic
- Scaling for highly-improved theories breaks down at _smaller_ values of *a*
**independent of volume
- But probably so for HMC too, because of instability

- S Gottlieb, W Liu, D Toussaint, R Renken, & R Sugar _[Phys.Rev.D35:2531-2542,1987](http://prola.aps.org/pdf/PRD/v35/i8/p2531_1)_

## PHMC and RHMC

- Use polynomial or rational function approximation for action
- Approximate action suffices for MD
- Accurate action need for acceptance
- Functions on matrices
- Defined for a Hermitian matrix by diagonalisation
*H = UDU **-1*
*f(H) = f(UDU **-1**) = U f(D)U **-1*
- Polynomials and rational functions do not require diagonalisation
*** **H**m** + **** **H**n** = U(**** **D**m** + **** **D**n**) U** **-1*
*H **-1** = U D **-1**U **–1*

- T Takaishi & Ph de Forcrand _[hep-lat/9608093](http://arxiv.org/PS_cache/hep-lat/pdf/9608/9608093.pdf)_
- R Frezzotti & K Jansen _[hep-lat/9702016](http://arxiv.org/PS_cache/hep-lat/pdf/9702/9702016.pdf)_
- A D Kennedy, I Horváth, & S Sint _[hep-lat/9809092](http://arxiv.org/PS_cache/hep-lat/pdf/9809/9809092.pdf)_
- M Clark & A D Kennedy _[hep-lat/0309084](http://arxiv.org/PS_cache/hep-lat/pdf/0309/0309084.pdf)_

## Theory of optimal L∞ (Чебышев) approximation is well understood
Equal alternating error maxima
Ремез algorithm to find coefficients
Золотарев analytic solution for sgn(x) and x±1/2
Rational approximations to sgn(x) of degree (20,21)
Чебышев/Золотарев for 10-6 < |x| < 1
tanh[20 tanh-1(x)]
Чебышев polynomials
Tn(x) ≡ cos[n cos-1(x)]
Give optimal approximation to higher degree polynomials
Not optimal approximation in general
Polynomial or Rational?
Maximum L∞ [-1,1] error for |x| proportional to
Rational: exp(n/ln ε)
Polynomial: 1/n
Polynomial approximation to 1/x correspondsto matrix inversion
Basically Jacobi method
Compare with Крылов solvers
Partial fraction expansion and multi-shift Крылов solver to apply rational function

- Equal alternating error maxima
- Ремез algorithm to find coefficients
- Золотарев analytic solution for *sgn(x)** *and *x**±1/2*
- Rational approximations to *sgn(x)** *of degree (20,21)
- Чебышев/Золотарев for *10**-6 **< |x| < 1*
*tanh*[*20 tanh**-1**(x)*]
- Чебышев _polynomials_
*T**n**(x) **≡** cos*[*n cos**-1**(x)*]
- Give optimal approximation to higher degree polynomials
- Not optimal approximation in general
- Polynomial or Rational?
- Maximum *L**∞ *[-1,1] error for *|x| *proportional to
- Rational: *exp(n/ln **ε)*
- Polynomial: *1/n*
- Polynomial approximation to *1/x *correspondsto matrix inversion
- Basically Jacobi method
- Compare with Крылов solvers
- Partial fraction expansion and multi-shift Крылов solver to apply rational function

- Чебышев Approximation

## Instability of Symplectic Integrators

- Symmetric symplectic integrator
- Leapfrog
- Exactly reversible...
- ...up to rounding errors
- Ляпунов exponent **
**
- Chaotic equations of motion
**when**exceeds critical value ***c*
- Instability of integrator
***c** *depends on quark mass

- C Liu, A Jaster, & K Jansen _[hep-lat/9708017](http://arxiv.org/PS_cache/hep-lat/pdf/9708/9708017.pdf)_
- R Edwards, I Horváth, & A D Kennedy _[hep-lat/9606004](http://arxiv.org/PS_cache/hep-lat/pdf/9606/9606004.pdf)_
- B Joó *et al. *(UKQCD) _[hep-lat/0005023](http://arxiv.org/PS_cache/hep-lat/pdf/0005/0005023.pdf)_

## Multipseudofermions

## Reduction of Maximum Force

- Hasenbusch trick
- Wilson fermion action *M=1-****H*
- Introduce the quantity *M’=1-****’H*
- Use the identity *M = M’(M’**-1**M)*
- Write the fermion determinant asdet M* = *det *M’ *det *(M’**-1**M)*
- Separate pseudofermion for each determinant
- Tune ***’* to minimise the cost
- Easily generalises
- More than two pseudofermions
- Wilson-clover action

- M  Hasenbusch _[hep-lat/0107019](http://arxiv.org/PS_cache/hep-lat/pdf/0107/0107019.pdf)_

## RHMC Force Reduction

- Use RHMC technique to implement *n**th** *root for multipseudofermions
- Use partial fractions & multishift for *n**th** *root
- No tuning required
- Cost proportional to condition number ***(M)*
- Maximum force reduction
- Condition number ***(r(M))=****(M)**1/n*
- Force reduced by factor *n****(M)**(1/n)-1*
- Increase step size to instability again
- Cost reduced by a factor of *n****(M)**(1/n)-1*
- Optimal value *n*opt ***  *ln ***(M)*
- So optimal cost reduction is (*e* ln**)* /***
- Cannot reduce exact (mean) force

- A D Kennedy & M Clark

## Reducing δH fluctuations

- M Lüscher & R Sommer

## Old Integrator Tricks

- Sexton-Weingarten
- Split MD Hamiltonian into parts
- Boson and fermion actions
- Construct symmetric symplectic integrator with larger steps for more expensive (fermion) part
- Use BCH formula
- Helps if step size limited by cheaper (boson) part
- Unfortunately, becomes less useful as *m**Q **→** **0*

- D Weingarten & J Sexton Nucl. Phys.Proc.Suppl. **26**, 613-616 (1992)

## Dynamical Chiral Fermions

## On-shell chiral symmetry

- Is it possible to have chiral symmetry on the lattice without doublers if we only insist that the symmetry holds on shell?

## Neuberger’s operator: I

## Neuberger’s operator: II

## Into Five Dimensions

- H Neuberger hep-lat/9806025
- A Boriçi, A D Kennedy, B Pendleton, U Wenger hep-lat/0110070
- A Boriçi _[hep-lat/9909057](http://arxiv.org/PS_cache/hep-lat/pdf/9909/9909057.pdf)_, _[hep-lat/9912040](http://arxiv.org/PS_cache/hep-lat/pdf/9912/9912040.pdf)_, hep-lat/0402035
- R Edwards & U Heller hep-lat/0005002
- T-W Chiu hep-lat/0209153 , hep-lat/0211032, hep-lat/0303008

## Overlap Algorithms

-  many formulations of overlap fermions
- All satisfy GW relation
- Equivalent in continuum limit
- Different lattice Dirac operators within *sgn* function
- Different approximations to *sgn* function
- Presumably also true for perfect actions
- Trade-off between speed and amount of chirality
- Choice of inversion algorithm
- Inner-outer Krylov iterations
- Various five dimensional formulations
- Several possible preconditioners

## Dynamical Overlap

*Fodor**, Katz, & **Szabó**:* dynamical overlap on ridiculously small lattices
- Reflection & refraction
*Brower, **Originos**, & Neff:* Interpolate between DW & Truncated Overlap
- Topology change in chiral limit?
*van der Eshof** et al.:* Preconditioners, flexible inverters
*NIC/DESY:* Inverter tests for QCDTM & overlap

- Z Fodor, S Katz, and K Szabó _[hep-lat/0311010](http://arxiv.org/PS_cache/hep-lat/pdf/0311/0311010.pdf)_
- R Brower, K Originos, & H Neff
- van der Eshof *et al.* hep-lat/0202025, hep-lat/0311025, hep-lat/0405003

## Other Topics

- Keh-Fei Liu & Andrei Alexandru
- Noisy non-vanishing baryonnumber density on tiny lattices
- Shailesh Chandrasekharan
- Strong coupling algorithm for QCD
- Strong coupling, but chiral limit

## The Future: Faster Monte Carlo