Thesis (MEng)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: In this thesis we set out to design an algorithm for solving the all-pairs fixed-radius nearest neighbours search problem for a massively parallel heterogeneous system. The all-pairs search problem is stated as follows: Given a set of N points in d-dimensional space, find all pairs of points within a horizon distance of one another. This search is required by any nonlocal or meshless numerical modelling method to construct the neighbour list of each mesh point in the problem domain. Therefore, this work is applicable to a wide variety of fields, ranging from molecular dynamics to pattern recognition and geographical information systems. Here we focus on nonlocal solid mechanics methods. The basic method of solving the all-pairs search is to calculate, for each mesh point, the distance to each other mesh point and compare with the horizon value to determine if the points are neighbours. This can be a very computationally intensive procedure, especially if the neighbourhood needs to be updated at every time step to account for changes in material configuration. The problem also becomes more complex if the analysis is done in parallel. Furthermore, GPU computing has become very popular in the last decade. Most of the fastest supercomputers in the world today employ GPU processors as accelerators to CPU processors. It is also believed that the next-generation exascale supercomputers will be heterogeneous. Therefore the focus is on how to develop a neighbour searching algorithm that will take advantage of next-generation hardware. In this thesis we propose a CPU - multi GPU algorithm, which is an extension of the fixed-grid method, for the fixed-radius nearest neighbours search on massively parallel systems. / AFRIKAANSE OPSOMMING: In hierdie tesis het ons die ontwerp van ’n algoritme vir die oplossing van die alle-pare vaste-radius naaste bure soektog probleem vir groot skaal parallele heterogene stelsels aangepak. Die alle-pare soektog probleem is as volg gestel: Gegewe ’n stel van N punte in d-dimensionele ruimte, vind al die pare van punte wat binne ’n horison afstand van mekaar af is. Die soektog word deur enige nie-lokale of roosterlose numeriese metode benodig om die bure-lys van alle rooster-punte in die probleem te kry. Daarom is hierdie werk van toepassing op ’n wye verskeidenheid van velde, wat wissel van molekulêre dinamika tot patroon herkenning en geografiese inligtingstelsels. Hier is ons fokus op nie-lokale soliede meganika metodes. Die basiese metode vir die oplossing van die alle-pare soektog is om vir elke rooster-punt, die afstand na elke ander rooster-punt te bereken en te vergelyk met die horison lente, om dus so te bepaal of die punte bure is. Dit kan ’n baie berekenings intensiewe proses wees, veral as die probleem by elke stap opgedateer moet word om die veranderinge in die materiaal konfigurasie daar te stel. Die probleem word ook baie meer kompleks as die analise in parallel gedoen word. Verder het GVE’s (Grafiese verwerkings eenhede) baie gewild geword in die afgelope dekade. Die meeste van die vinnigste superrekenaars in die wêreld vandag gebruik GVE’s as versnellers te same met SVE’s (Sentrale verwerkings eenhede). Dit is ook van mening dat die volgende generasie exa-skaal superrekenaars GVE’s sal implementeer. Daarom is die fokus op hoe om ’n bure-lys soektog algoritme te ontwikkel wat gebruik sal maak van die volgende generasie hardeware. In hierdie tesis stel ons ’n SVE - veelvoudige GVE algoritme voor, wat ’n verlenging van die vaste-rooster metode is, vir die vaste-radius naaste bure soektog op groot skaal parallele stelsels.

Zur Simulation technischer Prozesse ist eine hinreichend genaue Beschreibung des Materialverhaltens notwendig. Die hierfür häufig verwendeten phänomenologischen Ansätze, wie im vorliegenden Fall die HILLsche Fließbedingung, enthalten materialspezifische Parameter, welche nicht direkt messbar sind. Die Identifikation dieser Materialparameter erfolgt in der Regel durch Minimierung eines Fehlerquadratfunktionals, welches Differenzen von Messwerten und zugehörigen numerisch berechneten Vergleichswerten enthält. In diesem Zusammenhang haben sich zur Lösung dieser Minimierungsaufgabe die Trust-Region Verfahren als gut geeignet herausgestellt. Die Aufgabe besteht darin, die verschiedenen Möglichkeiten zur Steuerung eines Trust-Region Verfahrens, im Hinblick auf die Eignung für das vorliegende Identifikationsproblem, zu untersuchen. Dazu werden die Quadratmittelprobleme und deren Lösungsverfahren überblicksmäßig betrachtet. Danach wird näher auf die Trust-Region Verfahren eingegangen, wobei sich im Weiteren auf Verfahren mit positiv definiten Ansätzen für die Hesse-Matrix, den Levenberg-Marquardt Verfahren, beschränkt wird. Danach wird ein solcher Levenberg-Marquardt Algorithmus in verschiedenen Ausführungen implementiert und an dem vorliegenden Identifikationsproblem getestet. Als Ergebnis stellt sich eine gute Kombination aus verschiedenen Teilalgorithmen des Levenberg-Marquardt Algorithmus mit einer hohen Konvergenzgeschwindigkeit heraus, welche für das vorliegende Problem gut geeignet ist.

Zur Simulation technischer Prozesse ist eine hinreichend genaue Beschreibung des Materialverhaltens notwendig. Die hierfür häufig verwendeten phänomenologischen Ansätze, wie im vorliegenden Fall die HILLsche Fließbedingung, enthalten materialspezifische Parameter, welche nicht direkt messbar sind. Die Identifikation dieser Materialparameter erfolgt in der Regel durch Minimierung eines Fehlerquadratfunktionals, welches Differenzen von Messwerten und zugehörigen numerisch berechneten Vergleichswerten enthält. In diesem Zusammenhang haben sich zur Lösung dieser Minimierungsaufgabe die Trust-Region Verfahren als gut geeignet herausgestellt. Die Aufgabe besteht darin, die verschiedenen Möglichkeiten zur Steuerung eines Trust-Region Verfahrens, im Hinblick auf die Eignung für das vorliegende Identifikationsproblem, zu untersuchen. Dazu werden die Quadratmittelprobleme und deren Lösungsverfahren überblicksmäßig betrachtet. Danach wird näher auf die Trust-Region Verfahren eingegangen, wobei sich im Weiteren auf Verfahren mit positiv definiten Ansätzen für die Hesse-Matrix, den Levenberg-Marquardt Verfahren, beschränkt wird. Danach wird ein solcher Levenberg-Marquardt Algorithmus in verschiedenen Ausführungen implementiert und an dem vorliegenden Identifikationsproblem getestet. Als Ergebnis stellt sich eine gute Kombination aus verschiedenen Teilalgorithmen des Levenberg-Marquardt Algorithmus mit einer hohen Konvergenzgeschwindigkeit heraus, welche für das vorliegende Problem gut geeignet ist.:1 Einleitung 8 2 Nichtlineare Quadratmittelprobleme 9 2.1 Herkunft der Residuen: Das Prinzip der kleinsten Fehlerquadrate 10 2.2 Auftretende Differentialmatrizen 11 2.2.1 Lipschitzbedingung für die Unterscheidung der Aufgabenklasse im Hinblick auf die Residuen 12 2.3 Aufgabenklassen 13 2.3.1 Kleine und Null-Residuen 13 2.3.2 Große Residuen 13 2.3.3 Große Probleme 14 2.4 Modellstufen für f(x) um eine lokale Konstellation xk 15 2.5 Eigenschaften der Gauß-Newton Approximation der Hesse-Matrix 16 3 Identifikation der Materialparameter der HILLschen Fließbedingung für die plastische Verformung anisotroper Werkstoffe 17 4 ¨Ubersicht über monoton fallende Optimierungsverfahren für nichtlineare Funktionen 19 4.1 Die Idee der Line-Search Verfahren 19 4.2 Die Idee der Trust-Region Verfahren 20 4.3 Übersichtstabelle Über die Verfahren zur unrestringierten Optimierung 21 4.4 Ermittlungsmethoden fÜr die Suchrichtung sk bei Line-Search Methoden 22 4.4.1 Gradientenverfahren 22 4.4.2 Das Newton Verfahren 22 4.4.3 Quasi-Newton Verfahren 23 4.4.4 Gauß-Newton Verfahren 24 4.4.5 Methode der konjugierten Gradienten 25 4.4.6 Koordinatenabstiegsmethode nach Ahlers,Schwartz,Waldmann [1] 25 4.5 Modelle für die Trust-Region Verfahren 26 4.5.1 Der Cauchy Punkt 26 4.5.2 Das Newton Trust-Region Verfahren 27 4.5.3 Quasi-Newton Trust-Region Verfahren 27 4.5.4 Gauß-Newton Trust-Region: Levenberg-Marquardt Verfahren 27 4.6 Vergleich der Hauptstrategien 27 5 Die Trust-Region Verfahren 29 5.1 Die Konvergenz des Trust-Region Algorithmus zu stationären Punkten 34 5.2 Die Berechnung des Trust-Region Schrittes 35 5.3 Der Cauchy Punkt 37 5.4 Die Lösungsverfahren 38 5.5 Nahezu exakte Lösung des Trust-Region Problems, Regularisierung . 38 5.6 Struktur und Lösung der nahezu exakten Methode für den Normalfall 42 5.6.1 Ermitteln des Minimums s( lambda) des aktuellen Modells 46 5.6.1.1 Lösung mittels Cholesky Faktorisierung 47 5.6.1.2 Lösung mittels QR-Faktorisierung 47 5.6.1.3 Lösung mittels Singulärwertzerlegung 47 5.6.2 Das Ermitteln des Regularisierungsparameters 48 5.6.3 Ermitteln der Ableitung 0i( ) 51 5.6.4 Abbruch der -Iteration 52 5.6.5 Absichern der -Iteration 52 5.6.6 Ermitteln des Verhältnisses k 52 5.6.7 Auffrischen der Schrittnebenbedingung k 53 5.6.8 Startwerte für den Trust-Region Algorithmus 56 5.6.8.1 Startwerte 0 für den Trust-Region Radius 56 5.6.8.2 Startwerte für den Regularisierungsparameter 0 56 5.6.9 Konvergenz von Algorithmen, basierend auf nahezu exakten Lösungen 57 5.7 Approximation des Trust-Region Problems 57 5.7.1 Die Dogleg Methode 58 5.7.2 Die zweidimensionale Unterraumminimierung 60 5.7.3 Das Steihaug Vorgehen 61 5.7.4 Konvergenz der Approximationsverfahren 62 6 Trust-Region Verfahren mit positiv definiter Approximation der Hesse-Matrix: Das Levenberg-Marquardt Verfahren 63 6.1 Vorhandene Matrizen und durchführbare Methoden 64 6.2 Lösen des Levenberg-Marquardt Problems 66 6.2.1 Ermitteln von s( ) 68 6.2.1.1 Cholesky Faktorisierung 68 6.2.1.2 QR-Faktorisierung 68 6.2.1.3 Singulärwertzerlegung 68 6.2.2 Ermittlung des Regularisierungsparameter 69 6.2.3 Absichern der -Iteration 71 6.2.3.1 Absichern für die Strategie von Hebden 71 6.2.3.2 Absichern für die Newtonmethode 72 6.2.4 Weitere Teilalgorithmen 73 6.3 Ein prinzipieller Levenberg-Marquardt Algorithmus 73 7 Skalierung der Zielparameter 74 8 Abbruchkriterien für die Optimierungsalgorithmen 76 8.1 Abbruchkriterien bei Erreichen eines lokalen Minimums 76 8.2 Abbruchkriterien bei Erreichen der Maschinengenauigkeit für Trust-Region Verfahren 77 9 Test der Implementation des Levenberg-Marquardt Verfahrens 78 9.1 Test der Leistung für einzelne Parameter 79 9.2 Test der Leistung für Optimierungen mit mehreren Parametern 80 9.3 Test des Moduls 1 80 9.4 Test Modul 2 und Modul 3 81 9.5 Test des Moduls 4 81 9.6 Test des Moduls 5 81 9.7 Test des Modul 6 82 9.8 Test des Modul 7 83 9.9 Test des Modul 8 84 9.10 Modul 9 und Modul 10 84 9.11 Test mit verschiedenen Verfahrensparametern 85 9.12 Optimale Konfiguration 86 10 Zusammenfassung 87 11 Ausblick 88 11.1 Weiterführendes zu dem bestehenden Levenberg-Marquardt Verfahren 88 11.2 Weiterführendes zu den Trust-Region Verfahren 88 11.3 Weiterführendes zu den Line-Search Verfahren 89 11.4 Weiterführendes zu den Gradientenverfahren 89 Literaturverzeichnis 93 A Implementation: Das skalierte Levenberg-Marquardt Verfahren 95 A.1 Modul 1.x: 0-Wahl 95 A.1.1 Modul 1.1 95 A.1.2 Modul 1.2 96 A.1.3 Modul 1.3 96 A.1.4 Programmtechnische Umsetzung Modul 1 96 A.2 Modul 2.x: Wahl der Skalierungsmatrix 96 A.2.1 Modul 2.1 96 A.2.2 Modul 2.2 97 A.2.3 Programmtechnische Umsetzung Modul 2 97 A.3 Modul 3.x: Wahl der oberen und unteren Schranke l0, u0 für die - Iteration 97 A.3.1 Modul 3.1 97 A.3.2 Modul 3.2 97 A.3.3 Programmtechnische Umsetzung Modul 3 98 A.4 Modul 4.x: Wahl des Startwertes für den Regularisierungsparameter 0 98 A.4.1 Modul 4.1 98 A.4.2 Modul 4.2 99 A.4.3 Modul 4.3 99 A.4.4 Modul 4.4 99 A.4.5 Programmtechnische Umsetzung Modul 4 100 A.5 Modul 5.x: Die abgesicherte -Iteration 100 A.5.1 Modul 5.1 Die Iteration nach dem Schema von Hebden für 1 101 A.5.2 Modul 5.2 Die abgesicherte Iteration mit dem Newtonverfahren für 2 101 A.5.3 Die abgesicherte Iteration mit dem Newtonverfahren für 2 mittels Cholesky Zerlegung 102 A.5.4 Programmtechnische Umsetzung Modul 5 102 A.6 Modul 6.x: Die Ermittlung des Verhältnisses k 103 A.6.1 Modul 6.1: Herkömmliche Ermittlung 103 A.6.2 Modul 6.2: Numerisch stabile Ermittlung 104 A.6.3 Programmtechnische Umsetzung Modul 6 104 A.7 Modul 7.x: Auffrischen der Schrittnebenbedingung 105 A.7.1 Modul 7.1: Einfache Wahl 105 A.7.2 Modul 7.2: Wahl mit Berücksichtigung von Werten k < 0 105 A.7.3 Modul 7.3: Wahl mit Approximation von ffl 105 A.7.4 Programmtechnische Umsetzung Modul 7 106 A.8 Modul 8.x: Entscheidung über Akzeptanz des nächsten Schrittes sk . 107 A.8.1 Modul 8.1: Eine Akzeptanzbedingung 107 A.8.2 Modul 8.2: Zwei Akzeptanzbedingungen 107 A.8.3 Programmtechnische Umsetzung Modul 8 107 A.9 Modul 9.x: Abbruchbedingungen für den gesamten Algorithmus 107 A.9.1 Programmtechnische Umsetzung Modul 9 108 A.10 Modul 10.x: Berechnung des Schrittes s( ) 108 A.10.1 Modul 10.1 108 A.10.2 Modul 10.2 108 A.10.3 Programmtechnische Umsetzung Modul 10 108 A.11 Benötigte Prozeduren 109 A.11.1 Vektormultiplikation 109 A.11.2 Matrixmultiplikation 109 A.11.3 Matrixaddition 109 A.11.4 Cholesky Faktorisierung 110 A.11.5 Transponieren einer Matrix 111 A.11.6 Invertieren einer Matrix 111 A.11.6.1 Determinante einer Matrix 111 A.11.7 Normen 112 A.11.7.1 Euklidische Vektornorm 112 A.11.7.2 Euklidische Matrixnorm 112 A.11.8 Ermittlung von 1 112 A.11.9 Ermittlung von 2 112 A.11.10Ermittlung von 01 112 A.11.11Ermittlung von 02 .112 A.11.12Ermittlung von mk(s) 113 A.12 Programmablauf 113 A.13 Fehlercodes 114 B Weiterführendes: Allgemeines 116 B.1 Total Least Squares, Orthogonal distance regression 116 B.2 Lipschitz Konstante und Lipschitz Stetigkeit in nichtlinearen Quadratmittelproblemen 116 B.3 Beweis für das Prinzip der kleinsten Fehlerquadrate als beste Möglichkeit der Anpassung von Modellgleichungen an Messwerte 117 B.4 Konvergenzraten 119 B.5 Betrachtung der Normalengleichung als äquivalente Extremalbedingung 119 B.6 Der Cauchy Punkt 120 B.7 Minimumbedingungen 122 C Weiterführendes: Matrizen 123 C.1 Reguläre und singuläre Matrizen 123 C.2 Rang einer Matrix 123 C.3 Definitheit von quadratischen Matrizen 124 C.4 Kondition einer Matrix 125 C.5 Spaltenorthonormale und orthogonale Matrizen 125 C.6 Singulärwertzerlegung einer Matrix, SVD 126 C.7 Der Lanczos Algorithmus 127 C.8 Die QR Zerlegung einer Matrix 127 C.8.1 Gram Schmidt Orthogonalisierung 127 C.8.2 Householder Orthogonalisierung 127 C.9 Die Cholesky Faktorisierung 130 C.10 Die LINPACK Technik 131 D Daten und Bilder zum Levenberg-Marquardt Verfahren 132 D.1 Wichtige Funktionsverläufe des LM-Verfahrens 134 D.2 Einzelne Parameteroptimierungen 136 D.3 Kombinierte Parameteroptimierungen, P1,P2,P3 139 D.4 Vergleich Ableitungsgüte, Konvergenzproblem 142 D.5 Test des Modul 1 145 D.6 Test Modul 4 und 5 146 D.7 Test des Modul 6 147 D.8 Test des Modul 7 148 D.9 Test des Modul 8 151 D.10 Test verschiedener Algorithmusparameter 152 D.11 Standartalgorithmus und Verbesserter 155