Title (eng)
Joint spectral radius and subdivision schemes
Parallel title (deu)
Gemeinsamer Spektralradius und Unterteilungsalgorithmen
Author
Thomas Mejstrik
Advisor
Maria Charina
Assessor
Ulrich Reif
Tomas Sauer
Abstract (deu)
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 (eng)
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.
Keywords (eng)
subdivision schemesrefinement equationrefinable functionsmultiple subdivision schemesjoint spectral radiusinvariant polytope algorithmGripenberg algorithmDaubechies matricescapacity of codes
Keywords (deu)
UnterteilungsalgorithmenVerfeinerungsgleichungVerfeinerbare Funktionenmultiple UnterteilungsalgorithmenGemeinsamer SpektralradiusInvarianter Polytope AlgorithmusGripenberg AlgorithmusDaubechies MatrizenKapazität von Codes
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1352544
rdau:P60550 (deu)
111 Seiten : Illustrationen, Diagramme
Number of pages
1183
Association (deu)
Title (eng)
Joint spectral radius and subdivision schemes
Parallel title (deu)
Gemeinsamer Spektralradius und Unterteilungsalgorithmen
Author
Thomas Mejstrik
Abstract (deu)
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 (eng)
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.
Keywords (eng)
subdivision schemesrefinement equationrefinable functionsmultiple subdivision schemesjoint spectral radiusinvariant polytope algorithmGripenberg algorithmDaubechies matricescapacity of codes
Keywords (deu)
UnterteilungsalgorithmenVerfeinerungsgleichungVerfeinerbare Funktionenmultiple UnterteilungsalgorithmenGemeinsamer SpektralradiusInvarianter Polytope AlgorithmusGripenberg AlgorithmusDaubechies MatrizenKapazität von Codes
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1352545
Number of pages
1183
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0