The ANOVA decomposition and generalized sparse grid methods for the high-dimensional backward Kolmogorov equation

Abstract

In this thesis, we discuss numerical methods for the solution of the high-dimensional backward Kolmogorov equation, which arises in the pricing of options on multi-dimensional jump-diffusion processes.<br /> First, we apply the ANOVA decomposition and approximate the high-dimensional problem by a sum of lower-dimensional ones, which we then discretize by a θ-scheme and generalized sparse grids in time and space, respectively. We solve the resultant systems of linear equations by iterative methods, which requires both preconditioning and fast matrix-vector multiplication algorithms. We make use of a Linear Program and an algebraic formula to compute optimal diagonal scaling parameters. Furthermore, we employ the OptiCom as non-linear preconditioner. We generalize the unidirectional principle to non-local operators and develop a new matrix-vector multiplication algorithm for the OptiCom.<br /> As application we focus on the Kou model. Using a new recurrence formula, the computational complexity of the operator application remains linear in the number of degrees of freedom. The combination of the above-mentioned methods allows us to efficiently approximate the solution of the backward Kolmogorov equation for a ten-dimensional Kou model.

<strong>Die ANOVA-Zerlegung und verallgemeinerte dünne Gitter für die hochdimensionale Kolmogorov-Rückwärtsgleichung</strong><br /> In der vorliegenden Arbeit betrachten wir numerische Verfahren zur Lösung der hochdimensionalen Kolmogorov-Rückwärtsgleichung, die beispielsweise bei der Bewertung von Optionen auf mehrdimensionalen Sprung-Diffusionsprozessen auftritt.<br /> Zuerst wenden wir eine ANOVA-Zerlegung an und approximieren das hochdimensionale Problem mit einer Summe von niederdimensionalen Problemen, die wir mit einem θ-Verfahren in der Zeit und mit verallgemeinerten dünnen Gittern im Ort diskretisieren. Wir lösen die entstehenden linearen Gleichungssysteme mit iterativen Verfahren, wofür eine Vorkonditionierung als auch schnelle Matrix-Vektor-Multiplikationsalgorithmen nötig sind. Wir entwickeln ein Lineares Programm und eine algebraische Formel, um optimale Diagonalskalierungen zu finden. Des Weiteren setzen wir die OptiCom als nicht-lineares Vorkonditionierungsverfahren ein. Wir verallgemeinern das unidirektionale Prinzip auf nicht-lokale Operatoren und entwickeln einen für die OptiCom optimierten Matrix-Vektor-Multiplikationsalgorithmus.<br /> Als Anwendungsbeispiel betrachten wir das Kou-Modell. Mit einer neuen Rekurrenzformel bleibt die Gesamtkomplexität der Operatoranwendung linear in der Anzahl der Freiheitsgrade. Unter Einbeziehung aller genannten Methoden ist es nun möglich, die Lösung der Kolmogorov-Rückwärtsgleichung für ein zehndimensionales Kou-Modell effizient zu approximieren.