Show simple item record

2012-05-07Dissertation DOI: 10.18452/16514
Structured higher-order algorithmic differentiation in the forward and reverse mode with application in optimum experimental design
dc.contributor.authorWalter, Sebastian
dc.date.accessioned2017-06-18T11:27:51Z
dc.date.available2017-06-18T11:27:51Z
dc.date.created2012-05-30
dc.date.issued2012-05-07
dc.identifier.urihttp://edoc.hu-berlin.de/18452/17166
dc.description.abstractIn 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.ger
dc.description.abstractThis 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.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rightsNamensnennung - Keine kommerzielle Nutzung
dc.rights.urihttp://creativecommons.org/licenses/by-nc/3.0/de/
dc.subjectautomatische Differentiationger
dc.subjectalgorithmische Differentiationger
dc.subjecthöhere Ableitungenger
dc.subjectQRger
dc.subjectCholeskyger
dc.subjectEigenwertzerlegungger
dc.subjectautomatic differentiationeng
dc.subjectalgorithmic differentiationeng
dc.subjecthigher-order derivativeseng
dc.subjectQReng
dc.subjectCholeskyeng
dc.subjecteigenvalueeng
dc.subject.ddc510 Mathematik
dc.titleStructured higher-order algorithmic differentiation in the forward and reverse mode with application in optimum experimental design
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-100202184
dc.identifier.doihttp://dx.doi.org/10.18452/16514
dc.identifier.alephidBV040158969
dc.date.accepted2011-12-07
dc.contributor.refereeGriewank, Andreas
dc.contributor.refereeBock, Hans Georg
dc.contributor.refereeNeidinger, Richard D.
dc.subject.dnb27 Mathematik
dc.subject.rvkSK 905
local.edoc.pages221
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät II

Show simple item record