Detailansicht

Joint spectral radius and subdivision schemes
Thomas Mejstrik
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium NAWI aus dem Bereich Naturwissenschaften (Dissertationsgebiet: Mathematik)
Betreuer*in
Maria Charina
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.56989
URN
urn:nbn:at:at-ubw:1-17286.88357.848764-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Die vorliegende Arbeit verallgemeinert die Matrix-Methode für die Konvergenzanalyse von Unterteilungsalgorithmen auf multiple Unterteilungsalgorithmen, wie sie von Sauer (2012) eingeführt wurden. Multiple Unterteilungsalgorithmen erlauben, anders als stationäre und nicht-stationäre Unterteilungsalgorithmen, level-unabhängige Verfeinerungsgewichte und Verfeinerungsmatrizen. Letztere Eigenschaft erfordert eine neue Definition der Übergangsmatrizen, welche ein grundlegendes Objekt der Matrix Methode darstellen. Wir zeigen wie Übergangsmatrizen im multiplen Rahmen konstruiert werden und charakterisieren über den gemeinsamen Spektralradius dieser Matrizen die Konvergenz von multiplen Unterteilungsalgorithmen. Die Charakterisierung der Konvergenz von multiplen Unterteilungsalgorithmen mittels Übergangsmatrizen ist zwar elegant, die numerische Berechnung des gemeinsamen Spektralradius birgt jedoch Schwierigkeiten. Der invariante Polytop Algorithmus von Guglielmi und Protasov (2013 - 2016) stellt einen Durchbruch in der Berechnung des gemeinsamen Spektralradius dar. Der invariante Polytop Algorithmus findet für eine große Klasse von Matrixfamilien den genauen Wert ihres gemeinsamen Spektralradius. Der Algorithmus fand Anwendung bei der Lösung diverser Probleme, unter anderem in der Funktionalanalysis, Approximationstheorie und Kombinatorik. In dieser Arbeit schlagen wir Modifikationen des invarianten Polytop Algorithmus vor, um ihn schneller, robuster und für Matrizen höherer Dimensionen tauglich zu machen. Der modifizierte Algorithmus berechnet den exakten gemeinsamen Spektralradius für die meisten Matrixfamilien bis zu Dimension 25, für nicht-negative Matrizen bis zu Dimension 3000. Weiters stellen wir einen neuen Algorithmus, genannt modifizierter Gripenberg Algorithmus, vor, der sehr gute untere Schranken für den gemeinsamen Spektralradius von Matrizen in weniger als fünf Sekunden berechnet. In den meisten unserer Tests fand der modifizierte Gripenberg Algorithmus sogar den genauen Wert des gemeinsamen Spektralradius. Wir demonstrieren die numerische Effizienz der Algorithmen an zahlreichen Testbeispielen.
Abstract
(Englisch)
This thesis extends the matrix based approach to the setting of multiple subdivision schemes studied in Sauer (2012). Multiple subdivision schemes, in contrast to stationary and non-stationary schemes, allow for level dependent subdivision weights and for level dependent choice of the dilation matrices. The latter property of multiple subdivision makes the standard definition of the transition matrices, crucial ingredient of the matrix approach in the stationary and non-stationary settings, inapplicable. We show how to avoid this obstacle and characterize the convergence of multiple subdivision schemes in terms of the joint spectral radius of certain square matrices derived from subdivision weights. Albeit the characterization of the convergence of multiple subdivision schemes in terms of the joint spectral radius is elegant, the numerical computation of the joint spectral radius still poses big problems. In several papers of 2013 - 2016, Guglielmi and Protasov made a breakthrough in the problem of the joint spectral radius computation, developing the invariant polytope algorithm, which for most matrix families finds the exact value of the joint spectral radius. This algorithm found many applications in problems of functional analysis, approximation theory, combinatorics, etc.. In this thesis we propose a modification of the invariant polytope algorithm making it roughly three times faster and suitable for higher dimensions. The modified version works for most matrix families of dimensions up to 25, for non-negative matrices the dimension is up to 3000. Besides, we introduce a new, fast algorithm for computing good lower bounds for the joint spectral radius, which finds in most cases the exact value of the joint spectral radius in less than 5 seconds. Corresponding examples and statistics of numerical results are provided.

Schlagwörter

Schlagwörter
(Englisch)
subdivision schemes refinement equation refinable functions multiple subdivision schemes joint spectral radius invariant polytope algorithm Gripenberg algorithm Daubechies matrices capacity of codes
Schlagwörter
(Deutsch)
Unterteilungsalgorithmen Verfeinerungsgleichung Verfeinerbare Funktionen multiple Unterteilungsalgorithmen Gemeinsamer Spektralradius Invarianter Polytope Algorithmus Gripenberg Algorithmus Daubechies Matrizen Kapazität von Codes
Autor*innen
Thomas Mejstrik
Haupttitel (Englisch)
Joint spectral radius and subdivision schemes
Paralleltitel (Deutsch)
Gemeinsamer Spektralradius und Unterteilungsalgorithmen
Publikationsjahr
2019
Umfangsangabe
111 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*innen
Ulrich Reif ,
Tomas Sauer
Klassifikationen
31 Mathematik > 31.25 Lineare Algebra, multilineare Algebra ,
31 Mathematik > 31.35 Harmonische Analyse ,
31 Mathematik > 31.76 Numerische Mathematik ,
31 Mathematik > 31.80 Angewandte Mathematik ,
54 Informatik > 54.25 Parallele Datenverarbeitung ,
54 Informatik > 54.81 Anwendungssoftware
AC Nummer
AC15427162
Utheses ID
50336
Studienkennzahl
UA | 796 | 605 | 405 |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1