Detailansicht

Analysis and evaluation of Binary Cascade Iterative Refinement and comparison to other iterative refinement algorithms for solving linear systems
Karl Prikopa
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Wilfried Gansterer
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.16030
URN
urn:nbn:at:at-ubw:1-29634.19428.438954-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Iterative Refinement ist eine weitverbreitete Methode um die Rundungsfehler einer Lösung eines linearen Gleichungssystems zu verbessern. Die Kosten der iterativen Verbesserung sind sehr gering im Vergleich zu den Kosten der Matrixfaktorisierung, das Verfahren führt aber zu einem Ergebnis welches bis zur Maschinengenauigkeit korrekt sein kann. Es existieren viele Variationen des Standard Iterative Refinements, welche verschiedenen Arbeitsgenauigkeiten für die Berechnungen verwenden. Extra Precise Iterative Refinement verwendet eine höhere Genauigkeit, um das Ergebnis zu verbessern. Mixed Precision Iterative Refinement versucht die Vorteile von niedrigeren Genauigkeiten auszunutzen, um das Ergebnis zu berechnen und verwendet anschließend Iterative Refinement um die höhere Genauigkeit des Ergebnisses zu gewährleisten. Der Fokus dieser Masterarbeit liegt auf dem Binary Cascade Iterative Refinement, welches die Arbeitsgenauigkeiten basierend auf den Eingabedaten wählt. Dieser Algorithmus beruht auf der Verwendung von beliebigen Genauigkeiten, welche nicht auf die IEEE Standarddatentypen beschränkt sind, welche von den meisten Hardwareherstellern unterstützt werden. Die Masterarbeit wird die Eigenschaften von BCIR analysieren und Experimente durchführen, welche diesen Algorithmus mit anderen Iterative Refinement Methoden vergleichen und besondere Aufmerksamkeit auf die numerische Genauigkeit und die Konvergenz der Verfahren legen. Die beliebige Genauigkeit wird mit Hilfe der Software Bibliothek GNU MPFR implementiert. Die verschiedenen Genauigkeiten werden in Software simuliert und liefern daher keine aussagekräftigen Informationen über einen Performancegewinn oder -verlust durch die Verwendung der verschiedenen Genauigkeiten. Daher wird ein Performancemodel vorgestellt, um die Performance der verschiedenen Methoden miteinander vergleichen zu können. Dies wird Aufschluss über mögliche Performancegewinne geben.
Abstract
(Englisch)
Iterative refinement is a widely used method to improve the round-off errors of a solution of a linear system. The cost of the iterative improvement is very low compared to the cost of the factorization of the matrix but results in a solution which can be accurate to machine precision. Many variations on the standard iterative refinement method exist, which use different working precisions to refine the solution. The extra precise iterative refinement can use extended precision to improve the result. The mixed precision iterative refinement tries to exploit the benefits of using lower precisions to compute a solution and then uses iterative refinement to achieve the higher precision accuracy. The focus of this thesis will be the binary cascade iterative refinement, which chooses the working precisions according to the input data. This algorithm depends on arbitrary precision arithmetic to support working precisions outside the IEEE standard data types provided by most hardware vendors. The thesis will analyse the properties of BCIR and conduct experiments which will compare the algorithm to other iterative refinement methods and focus on the numerical accuracy and the convergence. The arbitrary precision arithmetic will be implemented using the GNU MPFR software library. The simulated arbitrary precision does not provide accurate information about the gains and losses in performance due to the use of the different precisions. Therefore a performance model will be introduced in order to be able to compare the performance of the algorithms and to analyse the possible performance gains.

Schlagwörter

Schlagwörter
(Englisch)
Iterative Refinement Binary Cascade Iterative Refinement Mixed Precision Iterative Refinement Extra Precise Iterative Refinement Arbitrary Precision GNU MPFR Performance model
Schlagwörter
(Deutsch)
Iterative Refinement Binary Cascade Iterative Refinement Mixed Precision Iterative Refinement Extra Precise Iterative Refinement Arbitrary Precision GNU MPFR Performancemodell
Autor*innen
Karl Prikopa
Haupttitel (Englisch)
Analysis and evaluation of Binary Cascade Iterative Refinement and comparison to other iterative refinement algorithms for solving linear systems
Paralleltitel (Deutsch)
Analyse und Evaluierung des Binary Cascade Iterative Refinements und Vergleich mit anderen Iterative Refinement Algorithmen zur Lösung von linearen Gleichungssystemen
Publikationsjahr
2011
Umfangsangabe
VI, 87 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Wilfried Gansterer
Klassifikationen
54 Informatik > 54.50 Programmierung: Allgemeines ,
54 Informatik > 54.80 Angewandte Informatik
AC Nummer
AC08766627
Utheses ID
14381
Studienkennzahl
UA | 066 | 940 | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1