Progress in Lattice Field Theory Algorithms

arXiv:hep-lat/9212017v114Dec1992ProgressinLatticeFieldTheoryAlgorithmsA.D.Kennedy∗SupercomputerComputationsResearchInstituteFloridaStateUniversityTallahasseeFL32306–4052,U.S.A.October30,1992SCRIpreprintFSU–SCRI–92–160CRS4preprintCRS4–PARCOMP–92–1hep-lat/9212017AbstractIpresentasummaryofrecentalgorithmicdevelopmentsforlatticefieldtheories.InparticularIgiveapedagogicalintroductiontothenewMulticanonicalalgorithm,anddiscusstherelationbetweentheHybridOverrelaxationandHybridMonteCarloalgorithms.Ialsoattempttoclarifytherˆoleofthedynamicalcriticalexponentzanditsconnectionwith“computationalcost.”∗ThisresearchwassupportedbytheFloridaStateUniversitySupercomputerCompu-tationsResearchInstitutewhichispartiallyfundedbytheU.S.DepartmentofEnergythroughcontract#DE–FC05–85ER250000.ThisresearchhasbeencarriedoutwiththepartialsupportoftheSardiniaRegionalAuthorities.IwouldliketothanktheUniversityofEdinburghandCRS4(Cagliari)fortheirhospitalitywhilethisreviewwasbeingwritten.11INTRODUCTIONInthisreviewIshallconcentrateontwoareasinwhichtherehasbeencon-siderableworkandsignificantprogressduringthelastyear.ThefirstistheMulticanonicalalgorithmwhich,althoughtheunderlyingideashavebeenknownforsometime,hasbeensuccessfullyappliedtostudyingmanyprop-ertiesoffirst-ordertransitionsinlatticefieldtheories.Ishallattempttogiveasomewhatpedagogicalintroductiontothismethod.ThesecondistheHybridOverrelaxationalgorithm;thismethodhasbeenusedforsomeyears,butrecentanalysisofitsperformancefortheGaussianmodelandofitsrelationshipwiththeHybridMonteCarloalgorithmareilluminating.UnfortunatelytherehasbeenlittleactivityorprogressonwhatIconsiderthetwooutstandingalgorithmicchallengesfacinglatticefieldtheorytoday:dynamicalfermionsandcomplexactions.Fortheformerthealgorithmsseemtoworkquitewell,albeitslowly,whereasforthelatterthesituationismuchworse.Therehasbeenalotofworkonmultigridandclustermethods.Bothhavebeenshowntoworkwellinsomesimplemodels(usuallyintwodimensions),buttheirefficacyhasnotyetbeendemonstratedforfourdimensionalnon-abeliangaugetheories.SincethesemethodswerediscussedinconsiderabledetailinpreviouslatticeconferencesIshallonlysurveytheprogressverybrieflyhere.IshallalsotrytoclarifythesituationregardingwhatisknownaboutcriticalslowingdownfortheHybridMonteCarloalgorithm.2MULTICANONICALMETHODSAlthoughtheapplicationofthemulticanonicalalgorithmtolatticefieldthe-oryisnew[1,2,3],similartechniqueshavebeenusedforsometime[4,5,6].Forarecentreviewofdevelopmentsinthissubjectsee[7].2.1MarginalDistributionsAstatisticalmechanicalsystemoraquantumfieldtheorymaybedescribednotonlyintermsoftheirdetailedmicroscopicstates,butalsointermsofasetofmacroscopicparameters(e.g.,energy,density,magnetization)which2sufficetospecifyallofitsthermodynamicproperties.WeshalldenotethespaceofmicrostatesbyM,whichhas“volume”Z≡RMdφwithrespecttothenaturalmeasuredφ,andweshallwriteh·iftoindicateanaverageoverMwithrespecttothemeasure∝dφf(φ).Similarly,weshallcallthespaceofmacrostatesO,withvolumeZ′≡ROdEandaveragesoverthisspacewithrespecttothemeasure∝dEg(E)willbewrittenashh·iig.IfΩissomether-modynamicobservablewhichdependsonlyonsomemacroscopicparametersEthenthesituationmaybesummarizedbythefollowingequationME−→OΩ−→R.(1)Microscopicandmacroscopicaveragesarerelatedinatrivialway:1hΩ◦Ei=1ZZMdφΩ(E(φ))(2)=1ZZMdφZOdEδ(E−E(φ))Ω(E)(3)=ZOdEρ(E)Ω(E)=hhΩiiρ(4)wherewehaveintroducedthedensityofstatesρ(E)≡1ZZMdφδ(E−E(φ)).(5)Theprobabilitydistributiongeneratedbyρ(E)isthemarginaldistributiononO,meaningthatitisobtainedfromthefulldistributionoverthemuchlargerspaceMbyaveragingoveralltheothervariables.2.2ImportanceSamplingImportancesamplingisafundamentaltechniquetoreducethestatisticalerrorsinaMonteCarlocomputation.Supposewewishtomeasuretheexpectationvalueofsomequantityf:M→R:tothisendweintroduceanestimatorEμfμ#=1TTXt=1f(φt)μ(φt)(6)1WeusethenotationΩ◦Etoindicatefunctionalcomposition:(Ω◦E)(φ)=ΩE(φ)
.3wheresamples{φt}arechosenfromthedistributionμ(φt).ItiseasytoseethattheexpectationvaluehEμ[f/μ]iμ=hfiisindependentofthechoiceofdistributionμ;infactthecentrallimittheoremtellsusthestrongerresultthatEμfμ#=hfi+OsVμ[f/μ]T,(7)wherethevarianceofasinglesampleisVμfμ#=*fμ−*fμ+μ2+μ(8)=*f2μ+−hfi2.(9)ObservethatwecanreducetheerrornotonlybyincreasingTbutalsobychoosingμsoastomakeVμ[f/μ]smaller.WemayfindtheoptimalimportancesamplingbyasimplevariationalcalculationδδμVμfμ#+λhμiμ=μopt==−*f2μ2opt++λ=0.Thesolutionofthisequationgivestheoptimalprobabilitydistributionμopt=|f|h|f|i;(10)thisgivesavariancepersampleofVμoptfμopt#=h|f|i2−hfi2,(11)whichvanishesifffhasthesamesign∀φ.Whilewecannotoftenachievethisidealsituation,generatingaprobabilitydistributionwhichapproximatestheoperatorbeingmeasuredcangreatlyreducetheamountofcomputertimenecessarytogetareliablemeasurementoftheoperator’sexpectationvalue.42.3CanonicalDistributionInfieldtheoryaswellasforstatisticalsystemswearemostofteninterestedfindingtheexpectationvaluesofoperatorswithrespecttothecanonicaldis-tribution.ForstatisticalsystemsthisdistributionisobtainedbymaximizingtheentropyS≡−hlogPiPwithrespecttotheprobabilitydistributionP