edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Sebastian Walter
Titel: Structured higher-order algorithmic differentiation in the forward and reverse mode with application in optimum experimental design
Gutachter: Andreas Griewank; Hans Georg Bock; Richard D. Neidinger
Erscheinungsdatum: 07.05.2012
Volltext: pdf (urn:nbn:de:kobv:11-100202184)
Fachgebiet(e): Mathematik
Schlagwörter (ger): automatische Differentiation, algorithmische Differentiation, höhere Ableitungen, QR, Cholesky, Eigenwertzerlegung
Schlagwörter (eng): automatic differentiation, algorithmic differentiation, higher-order derivatives, QR, Cholesky, eigenvalue
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung (CC BY NC)
Zitationshinweis: Walter, Sebastian: Structured higher-order algorithmic differentiation in the forward and reverse mode with application in optimum experimental design; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 07.05.2012, urn:nbn:de:kobv:11-100202184
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt.
Abstract (eng):
This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 7 Zugriffe PDF: 8 Zugriffe Startseite: 3 Zugriffe PDF: 13 Zugriffe Startseite: 4 Zugriffe PDF: 13 Zugriffe PDF: 11 Zugriffe PDF: 20 Zugriffe PDF: 20 Zugriffe PDF: 13 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe Startseite: 3 Zugriffe PDF: 18 Zugriffe Startseite: 4 Zugriffe PDF: 28 Zugriffe Startseite: 7 Zugriffe PDF: 23 Zugriffe Startseite: 6 Zugriffe PDF: 13 Zugriffe Startseite: 6 Zugriffe PDF: 11 Zugriffe Startseite: 10 Zugriffe PDF: 12 Zugriffe Startseite: 6 Zugriffe PDF: 24 Zugriffe Startseite: 4 Zugriffe PDF: 13 Zugriffe Startseite: 9 Zugriffe PDF: 20 Zugriffe Startseite: 13 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 33 Zugriffe Startseite: 12 Zugriffe PDF: 65 Zugriffe Startseite: 8 Zugriffe PDF: 69 Zugriffe Startseite: 6 Zugriffe PDF: 66 Zugriffe Startseite: 15 Zugriffe PDF: 82 Zugriffe Startseite: 13 Zugriffe PDF: 85 Zugriffe Startseite: 3 Zugriffe PDF: 52 Zugriffe Startseite: 10 Zugriffe PDF: 46 Zugriffe
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Monat Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Startseite 7 3 4         1 3 4 7 6 6 10 6 4 9 13 2 12 8 6 15 13 3 10
PDF 8 13 13 11 20 20 13 14 18 28 23 13 11 12 24 13 20 14 33 65 69 66 82 85 52 46

Gesamtzahl der Zugriffe seit Jun 2012:

  • Startseite – 152 (5.85 pro Monat)
  • PDF – 786 (30.23 pro Monat)
 
 
Generiert am 29.08.2014, 05:25:21