Beiträge zu effizienten Algorithmen basierend auf Rang-1 Aufdatierungen
Das zentrale Thema dieser Arbeit ist die Entwicklung effizienter Algorithmen zur Rang-1 Aufdatierung in verschiedenen Problemstellungen. Die aufdatierte Matrix A+ ergibt sich hierbei aus der ursprünglichen Matrix A sowie der additiven Rang-1 Korrektur ab^T der Vektoren a und b. Im ersten Teil dieser Arbeit wird die Rang-1 Aufdatierung der LU-Faktorisierung betrachtet. Hierzu werden bekannte Algorithmen durch die Möglichkeit der Spaltenpermutation auf rechteckige Probleme erweitert sowie durch effiziente Matrixzugriffe in ihrer Laufzeit optimiert. Zusätzlich wird ein hybrider Algorithmus vorgestellt, welcher verschiedene Verfahren vereint und speziell zur Verwendung im hier vorgestellten Optimierungspaket entwickelt wurde. Im zweiten Teil wird die Rang-1 Aufdatierung der Singulärwertzerlegung für den Fall unsymmetrischer Matrizen betrachtet. Hierbei liegt das Hauptaugenmerk auf der schnellen Multiplikation von Cauchy-Matrizen mit allgemeinen Matrizen. Dazu werden verschiedene Matrixapproximationen näher untersucht. Weiterhin wird durch einen Korrekturschritt eine hohe Lösungsgenauigkeit der aufdatierten Matrizen sichergestellt. Im letzten Kapitel werden zwei verschiedene Verfahren zur Rang-1 Aufdatierung der Matrixexponentialfunktion vorgestellt. Zunächst wird hierzu die Darstellung der Matrixfunktion durch das Cauchy-Integral verwendet. Der Schwerpunkt liegt dabei auf der theoretischen Untersuchung des Quadraturfehlers sowie der effizienten Berechnung von Integrationsweg und Trapezsumme. Des weiteren wird als weiteres Aufdatierungsverfahren eine auf dem Scaling und Squaring Algorithmus beruhende Methode vorgestellt.
The main contribution of this work is the development of efficient algorithms for the rank-1 update in different applications. The updated matrix A+ is obtained from the original matrix A as well as from the vectors a and b, which form an additive correction ab^T. The first part of this work is concerned with the rank-1 update of the LU factorization. At first two existing algorithms are extended with the option of column pivoting, which is necessary for updating rectangular problems. The computational time is further reduced by efficient memory access. Additionally, a hybrid algorithm which combines the advantages of different updating strategies is presented. It was developed for the use within an optimization code. In the second part the rank-1 update of the Singular Value Decomposition for unsymmetric matrices is investigated. The focus on the development of an efficient updating algorithm is put on the fast multiplication of arbitrary matrices by Cauchy-matrices. The Cauchy-matrix structure allows using different matrix approximations which are examined. To ensure the accuracy of the updated matrices an additional correction step is performed. In the last chapter different methods for updating the matrix exponential are presented. At first the Cauchy-integral representation of the matrix function is used. The focus of this part lies in the theoretical investigation of the quadrature error as well as in presenting efficient strategies for applying the updating method in practice. Regarding this, two points of interest are the choice of the path of the integration and the efficient computation of the trapezoidal sum. In the end another updating algorithm for the matrix exponential, which is based on the Scaling and Squaring algorithm, is introduced.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved