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

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.

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 | |

Detailansicht

Abstracts

Schlagwörter