Schnelleinstieg Reader

Home|Suche|Sitemap|Webmail

Startseite FSU

Algorithmen fur hochdimensionale Systeme


Funktionalintegrale von Gitterfeldtheorien sind hochdimensionale (∼ 106) Integrale, die möglichst gut approximiert werden müssen. Die Wahl der Verfahren und deren Güte hängen stark vom Integranden ab. Es sollen für Quantenfeldtheorien mit Fermionen, die auf nicht-lokale und stark variierende Integranden führen, möglichst schnelle Algorithmen sowie effektive Inverter fur auftretende Matrizen entwickelt und angewandt werden. Es soll untersucht werden, welche hochdimensionalen Probleme in der Quantentheorie mit vertretbarem Aufwand numerisch lösbar sind.

Fragen der hochdimensionalen Integration werden seit etwa 15 Jahren systematisch untersucht, der begriffliche Rahmen und die wichtigsten Ergebnisse stammen von Wozniakowski und seinen Kollegen auch aus Jena. Entscheidend für die Antwort ist neben dem Lösungsoperator die Funktionenklasse der Inputs, die problemabhängig betrachtet werden muss.

Viele der bekannten Ergebnisse beziehen sich auf deterministische Algorithmen. Nun sind aber randomisierte Algorithmen (MC-Methoden) gerade im Fall hoher Dimension gebräuchlich und es ist bekannt, dass viele Probleme durch den Übergang zu randomisierten Algorithmen tractable werden. Über die Klassifikation derjenigen Probleme, die im randomisierten Fall tractable sind, ist noch wenig bekannt, es gibt aber erste Ergebnisse.

Stand der Forschung

Es sei Fd eine Klasse von Integranden, die auf Rd oder auf [0, 1]d definiert und integrierbar sind. Das Integrationsproblem heißt tractable für die Klassen Fd für deterministische Algorithmen, falls die Rechenzeit t eines optimalen (deterministischen bzw. stochastischen) Algorithmus polynomial abhängt von d und ε-1 , wobei ε der erlaubte Fehler ist. Es gilt dann also die Abschätzung  t(d,ε) ≤ C·dα ε−β mit gewissen Konstanten C, α, β > 0. Für die klassischen Funktionenklassen C k ([0, 1]) gilt t(d, ε) ≍ε-d/k und das heißt, dass für diese Klassen das Integrationsproblem nicht tractable ist. Seit etwa 15 Jahren wird untersucht, welche Integrationsprobleme tractable sind. Durch die Einfuhrung gewichteter Sobolevräume für die zu untersuchenden Funktionenklassen konnten für deterministische Algorithmen bereits interessante Resultate gefunden werden. Neben den dort untersuchten deterministischen Algorithmen bieten randomisierte Algorithmen (Monte-Carlo-Methoden) viel mehr Möglichkeiten und die Frage, ob bestimmte Funktionenklassen tractable sind, stellt sich erneut. Jedoch ist die Zahl der hierzu bereits erschienen Arbeiten noch überschaubar.

Eine wichtige Klasse randomisierter Algorithmen bilden die Markov-Ketten-Monte-Carlo (MCMC) Algorithmen. Von zentraler Bedeutung ist hierbei die Konstruktion einer geeigneten schnell-mischenden Markov-Kette. Es ist bekannt, daß sich die Eigenschaft der schnellen Mischung asymptotisch charakterisieren lässt durch den zweiten Eigenwert, die Autokorrelationszeit bzw. die Leitfähigkeit (conductance) der Kette.

Enthalten die Integranden Determinanten großer Matrizen, die von den Integrationsvariablen abhängen, dann existieren hierfür eine Reihe sogenannter hybrider Methoden. Diese Klasse von Integranden spielt bei der numerischen Behandlung von Quantenfeldtheorien mit dynamischen Fermionen eine tragende Rolle und so gibt es bis in die Gegenwart Anstrengungen, die verwandten Methoden und Techniken zu verbessern. Insbesondere Multigrid-Monte-Carlo oder Mehrgitterverfahren haben dabei stark an Bedeutung zugenommen.

Eigene Vorabeiten

Wir haben uns schon lange mit Monte-Carlo-Methoden beschäftigt. Seit Ende der neunziger Jahre beschäftigen wir uns intensiv mit hochdimensionalen Problemen, siehe die Übersicht. Die erste Monographie zu diesem Thema ist in Vorbereitung. Interessant ist wohl, dass einerseits die Stern-Diskrepanz (bzw. das äquivalente Integrationsproblem) tractable ist, aber andererseits die L2 -Diskrepanz nicht tractable ist.

Asymptotische Fehlerabschätzungen für MCMC sind bekannt. Grundlegend ist der Begriff der schnellen Mischung bzw. der conductance (Leitfähigkeit).

Ziele und Arbeitsprogramm

Eine wesentliche Frage ist schon ausgesprochen worden: Welche Integrationsprobleme sind tractable für randomisierte Algorithmen und was sind (in Abhängigkeit vom Integranden) optimale Algorithmen? Diese Frage hat mehrere Aspekte, die teilweise getrennt behandelt werden können. Die beschriebenen nicht-asymtotischen Fehlerabschätzungen sollen zunächst auf Spinsysteme übertragen werden. Von besonderem Interesse ist dabei die Bestimmung der Leitfähigkeit für existierende und Verwendung findende lokale und globale Algorithmen, wie z.B den Metropolis-, Heatbath oder Clusteralgorithmus.

Eine direkte feldtheoretische Verallgemeinerung von Spinsystemen stellen die nichtlinearen Sigmamodelle, insbesondere die O(N)-Modelle dar. Sie sollen im Anschluss unter denselben Gesichtspunkten untersucht werden. Im Hinblick auf ihre supersymmetrischen Erweiterungen sind während dieser Phase ferner die sogenannten hybriden Algorithmen von besonderer Bedeutung. Ausgehend von diesen Ergebnissen können die weiteren Untersuchungen zwei weiteren aber verschiedenen Verallgemeinerungen zugeordnet werden. Sind die Integrationsgebiete von Spinsystemen und nicht-linearen Sigma-Modellen noch kompakt, soll nun einerseits der Frage nachgegangen werden, inwieweit sich die gefundenen Ergebnisse auf Probleme mit nicht-kompakten Integrationsgebieten erweitern lassen. In diese Klasse fallen insbesondere die linearen Sigma- und Wess-Zumino-Modelle. Andererseits sind für die Behandlung von supersymmetrischen Sigma-Modellen effiziente Algorithmen zur Behandlung der notwendigerweise zu berücksichtigenden Fermiondeterminante wichtig. Fur die damit auf die Form μ[φ] = exp (−S[φ]) · det(M [φ])) verallgemeinerte Integrandenklasse sollen eingeschränkt auf nicht-lineare supersymmetrische Sigma- Modelle vergleichende Aussagen über die in der Literatur verwandten Algorithmen gewonnen werden. Die beiden letztgenannten Schwerpunkte stehen gleichberechtigt nebeneinander und können wertvolle Impulse für die Untersuchung von supersymmetrischen Eichtheorien geben.