A new backward stable, structure preserving method of complexity O(n^3) is presented for computing the stable invariant subspace of a real Hamiltonian matrix and the stabilizing solution of the continuous-time algebraic Riccati equation. The new method is based on the relationship between the invariant subspaces of the Hamiltonian matrix H and the extended matrix /0 H\ and makes use \H 0/ of the symplectic URV-like decomposition that was recently introduced by the authors.

Rank-revealing ULV and URV factorizations are useful tools to determine the rank and to compute bases for null-spaces of a matrix. However, in the practical ULV (resp. URV ) factorization each left (resp. right) null vector is recomputed from its corresponding right (resp. left) null vector via triangular solves. Triangular solves are required at initial factorization, refinement and updating. As a result, algorithms based on these factorizations may be expensive, especially on parallel computers where triangular solves are expensive. In this paper we propose an alternative approach. Our new rank-revealing ULV factorization, which we call ¨top-down¨ ULV factorization ( TDULV -factorization) is based on right null vectors of lower triangular matrices and therefore no triangular solves are required. Right null vectors are easy to estimate accurately using condition estimators such as incremental condition estimator (ICE). The TDULV factorization is shown to be equivalent to the URV factorization with the advantage of circumventing triangular solves.

This paper is concerned with a specific finite element strategy for solving elliptic boundary value problems in domains with corners and edges. First, the anisotropic singular behaviour of the solution is described. Then the finite element method with anisotropic, graded meshes and piecewise linear shape functions is investigated for such problems; the schemes exhibit optimal convergence rates with decreasing mesh size. For the proof, new local interpolation error estimates for functions from anisotropically weighted spaces are derived. Finally, a numerical experiment is described, that shows a good agreement of the calculated approximation orders with the theoretically predicted ones.

Vorlesungsscript zur Lehrveranstaltung ¨Differentialgeometrie¨ fuer Mathematiker, Lehramtsstudenten/Gymnasiallehrer Mathematik, Ingenieure und andere Interessenten. Dieses Vorlesungsscript gibt Einblicke in die Grundlagen der Vektorrechnung, der Kurventheorie und der Flaechentheorie im zwei- bzw. dreidimensionalen Raum. Die entwickelten Theorien werden durch Anwendungsbeispiele untermauert. Weiterhin ist eine Formelsammlung zur Kurven- und Flaechentheorie enthalten.

Die in dieser Arbeit vorgestellte Kompositionsmethode beschäftigt sich damit, bestimmte Aufgabenstellungen aus dem Bereich der Berechnung von Graphenkenngrößen und Grapheninvarianten in endlichen ungerichteten Graphen und Hypergraphen in ein einheitliches Schema einzuordnen und so die Umsetzung in Algorithmen zu erleichtern. Dabei werden zwei Hauptziele verfolgt. Zum einen soll die Menge der mit der Methode lösbaren Aufgaben möglichst groß sein, und zum anderen sollen die entstandenen Algorithmen tatsächliche Berechnungen in einigen Netzen praxisrelevanter Größe ermöglichen. Die Kompositionsmethode belegt mit ihren Zielen somit den Bereich zwischen zwei Extremen der Algorithmenentwicklung: Auf der einen Seite steht die Erzeugung von Spezialalgorithmen, die oft so stark an bestimmte Eigenschaften der zu berechnenden Größen gekoppelt sind, dass eine Anpassung an leicht veränderte Aufgabenstellungen nur schwer möglich ist bzw. unter Umständen der Entwicklung eines völlig neuen Algorithmus gleichkommt; auf der anderen Seite stehen die allgemeingültigen Ansätze, deren Umsetzung häufig zu Algorithmen führt, die bereits für sehr kleine Netze nicht mehr praktisch durchführbar sind. Die gestellten Ziele werden durch eine Formalisierung der Aufgabenstellungen erreicht, deren Ergebnisse direkt in Algorithmen umgesetzt werden können. Dabei müssen jeweils nur wenige aufgabenspezifische Details formuliert werden, die anschließend in einen von der konkreten Aufgabe unabhängigen Rahmenalgorithmus eingebunden werden. Ein solches Verfahren ist aus Sicht eines Anwenders aus der Praxis besonders interessant, da der Rahmenalgorithmus nur ein einziges Mal implementiert werden muss und somit bei wiederholter Verwendung der Methode der Entwicklungsaufwand für die erzeugten Kompositionsalgorithmen erheblich sinkt. Bislang wurden mit Hilfe der Kompositionsmethode zirka dreißig Problemstellungen von der Berechnung chromatischer Invarianten über das Zählen von Hamiltonkreisen bis hin zur Bestimmung von Zuverlässigkeitskenngrößen von stochastischen Netzen bearbeitet. Die von der Methode erzeugten Algorithmen sind dabei in aller Regel nicht optimal in Bezug auf Laufzeit und Speicherbedarf. Dieser Nachteil wird allerdings durch den extrem geringen Entwicklungsaufwand und durch die Anwendbarkeit der Methode auf neue Aufgabenstellungen, für die noch keine Spezialalgorithmen existieren, kompensiert. Besonders bei der Berechnung bestimmter Zuverlässigkeitskenngrößen sowie bei der Lösung von #P-vollständigen Abzählproblemen können die Kompositionsalgorithmen aber auch aktuelle Spezialalgorithmen übertreffen.

Ein zentrales Problem der quantitativen Texturanalyse ist die numerische Inversion der eindimensionalen Radontransformation auf der Lie--Gruppe SO(3) aller Rotationen im dreidimensionalen euklidischen Raum. In der vorliegenden Dissertation wird die Lösbarkeit und Eindeutigkeit dieses inversen Problems untersucht und Fehlerabschätzungen unter Berücksichtigung unvollständiger und fehlerbehafteter Daten hergeleitet. Weiterhin wird ein Algorithmus zur Lösung des inversen Problems vorgeschlagen, welcher auf einer Diskretisierung mittels radialer Basisfunktionen basiert und schnelle Fouriermethoden auf der Kugel und der Lie-Gruppe SO(3) benutzt. In numerischen Tests wird gezeigt, dass der Algorithmus für die Rekonstruktion scharfer Texturen aus Beugungsdaten gemessen auf einem hochauflösenden, ungleichmäßigen Messraster geeignet ist.

No description available.

We introduce the notion of nested distance desert automata as a joint generalization and further development of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n2) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration). We also show some decidability results for some substitution problems for recognizable languages.

We present a method for determining the reduced Gröbner basis with respect to a given admissible term order of order type ! of the intersection ideal of an infinite sequence of polynomial ideals. As an application we discuss the Lagrange type interpolation on algebraic sets and the 'approximation' of the ideal I of an algebraic set by zero dimensional ideals, whose affine Hilbert functions converge towards the affine Hilbert function of I.

Human mobility is central to socioeconomic interactions in modern society. Unprecedented reliance on individual transportation has resulted in widespread challenges globally, including congestion, emissions, and socioeconomic inequalities. These issues are anticipated to worsen with climate change, presenting a significant risk to human civilization. Notably, human mobility accounts for over 15% of total carbon emissions, with the bulk stemming from private transportation. Therefore, there is a pressing need to transition to sustainable alternatives like public transport to address these challenges effectively. Public transport comprises a complex system with multiple interacting parts, including users, drivers, service providers, and evolving urban infrastructure. The interactions among these elements give rise to multiple self-organized states, which play a pivotal role in determining the attractiveness and efficiency of public transport systems. In this thesis, we combine tools from network dynamics, statistical physics, nonlinear dynamics, transport science, and data analysis to understand emergent behavior in public transport worldwide. Public transport infrastructure highlights the disparities in cities across the globe. Developed countries in the Global North generally feature centrally organized formal transport systems, while developing nations in the Global South are served by informal transport operated by private individuals. In our study of complex self-organized states within both formal and informal transport, we explore how self-organization enhances mode attractiveness in some contexts whereas it may reduce ridership in others. We find that in urbanizing cities with formal transport, the interaction between users and service providers can lead to sub-optimal transport outcomes. With the rise of app-based technologies, on-demand transport services like bike taxis are becoming increasingly popular within cities in the Global South. Our results suggest that as congestion grows, a transition may occur, leading users to shift from shared transport to single-passenger options like bike taxis. Finally, our analysis of transport systems in cities across the globe shows that informal transport often self-organizes into more efficient route structures compared to formal transport, indicating that lessons from these informal systems could lead to the improvement of formal transport systems. Our findings provide a foundation for developing intervention strategies to enhance public transportation, by bridging the gap between physics, graph theory, transportation research, data science, and public policy. The results offer valuable insights into reducing congestion and emissions, contributing to a more sustainable and livable urban future, while highlighting the importance of further studies into the collective dynamics of human mobility systems. / Die menschliche Mobilität ist für die sozioökonomischen Interaktionen in der modernen Gesellschaft von zentraler Bedeutung. Die beispiellose Abhängigkeit vom Individualverkehr hat weltweit zu weitreichenden Problemen geführt, darunter Verkehrsstaus, Emissionen und sozioökonomischen Ungleichheiten. Es wird erwartet, dass sich diese Probleme mit dem Klimawandel noch verschärfen werden, was ein erhebliches Risiko für die menschliche Zivilisation darstellt. Vor allem die menschliche Mobilität ist für über 15% der gesamten Kohlenstoffemissionen verantwortlich, wobei der Großteil auf den Individualverkehr entfällt. Daher besteht die dringende Notwendigkeit, auf nachhaltige Alternativen wie den öffentlichen Verkehr umzusteigen, um diesen Herausforderungen wirksam zu begegnen. Der öffentliche Verkehr ist ein komplexes System mit zahlreichen interagierenden Komponenten, darunter Nutzer, Fahrer, Dienstleister und die sich entwickelnde städtische Infrastruktur. Die Wechselwirkungen zwischen diesen Elementen führen zu zahlreichen selbstorganisierten Zuständen, die eine zentrale Rolle bei der Bestimmung der Attraktivität und Effizienz von öffentlichen Verkehrssystemen spielen. In dieser Arbeit kombinieren wir Werkzeuge aus der Netzwerkdynamik, der statistischen Physik, der nichtlinearen Dynamik, der Verkehrswissenschaft und der Statistik, um das emergente Verhalten im öffentlichen Verkehr weltweit zu verstehen. Die Infrastruktur des öffentlichen Verkehrs verdeutlicht die Ungleichheiten in den Städten der Welt. In den Industrieländern des globalen Nordens gibt es in der Regel zentral organisierte formale Verkehrssysteme, während in den Entwicklungsländern des globalen Südens der informelle Verkehr von Privatpersonen betrieben wird. In unserer Studie über komplexe selbstorganisierte Zustände sowohl im formellen als auch im informellen Verkehr untersuchen wir, wie die Selbstorganisation die Attraktivität der Verkehrsmittel in einigen Kontexten erhöht, während sie in anderen die Fahrgastzahlen verringern kann. Wir stellen fest, dass in Städten mit formellem Verkehr die Interaktion zwischen Nutzern und Dienstleistern zu suboptimalen Verkehrsergebnissen führen kann. Mit dem Aufkommen von App-basierten Technologien werden On-Demand-Verkehrsdienste wie Fahrradtaxis in Städten des globalen Südens immer beliebter. Unsere Ergebnisse deuten darauf hin, dass mit zunehmender Überlastung ein Übergang stattfinden kann, der die Nutzer dazu veranlasst, von gemeinsam genutzten Verkehrsmitteln auf Einzelpersonenoptionen wie Fahrradtaxis umzusteigen. Schließlich zeigt unsere Analyse von Verkehrssystemen in Städten auf der ganzen Welt, dass sich der informelle Verkehr im Vergleich zum formellen Verkehr oft selbst in effizienteren Routenstrukturen organisiert, was darauf hindeutet, dass Lehren aus diesen informellen Systemen zur Verbesserung formeller Verkehrssysteme führen könnten. Unsere Ergebnisse bieten eine Grundlage für die Entwicklung von Interventionsstrategien zur Verbesserung des öffentlichen Verkehrs, indem sie die Lücke zwischen Physik, Graphentheorie, Verkehrsforschung, Datenwissenschaft und öffentlicher Politik schließen. Die Ergebnisse bieten wertvolle Einblicke in die Reduzierung von Staus und Emissionen und tragen so zu einer nachhaltigeren und lebenswerteren urbanen Zukunft bei.