15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY
Refine
Document Type
- Doctoral Thesis (5)
Has Fulltext
- yes (5)
Keywords
- Data Analysis (1)
- Entscheidung (1)
- Entscheidungstheorie (1)
- Entscheidungsunterstützung (1)
- Gyroscopic (1)
- Hypergraph (1)
- Invariante (1)
- Mustererkennung (1)
- Optimierung (1)
- Planung (1)
Faculty / Organisational entity
Linear algebra, together with polynomial arithmetic, is the foundation of computer algebra. The algorithms have improved over the last 20 years, and the current state of the art algorithms for matrix inverse, solution of a linear system and determinants have a theoretical sub-cubic complexity. This thesis presents fast and practical algorithms for some classical problems in linear algebra over number fields and polynomial rings. Here, a number field is a finite extension of the field of rational numbers, and the polynomial rings we considered in this thesis are over finite fields.
One of the key problems of symbolic computation is intermediate coefficient swell: the bit length of intermediate results can grow during the computation compared to those in the input and output. The standard strategy to overcome this is not to compute the number directly but to compute it modulo some other numbers, using either the Chinese remainder theorem (CRT) or a variation of Newton-Hensel lifting. Often, the final step of these algorithms is combined with reconstruction methods such as rational reconstruction to convert the integral result into the rational solution. Here, we present reconstruction methods over number fields with a fast and simple vector-reconstruction algorithm.
The state of the art method for computing the determinant over integers is due to Storjohann. When generalizing his method over number field, we encountered the problem that modules generated by the rows of a matrix over number fields are in general not free, thus Strojohann's method cannot be used directly. Therefore, we have used the theory of pseudo-matrices to overcome this problem. As a sub-problem of this application, we generalized a unimodular certification method for pseudo-matrices: similar to the integer case, we check whether the determinant of the given pseudo matrix is a unit by testing the integrality of the corresponding dual module using higher-order lifting.
One of the main algorithms in linear algebra is the Dixon solver for linear system solving due to Dixon. Traditionally this algorithm is used only for square systems having a unique solution. Here we generalized Dixon algorithm for non-square linear system solving. As the solution is not unique, we have used a basis of the kernel to normalize the solution. The implementation is accompanied by a fast kernel computation algorithm that also extends to compute the reduced-row-echelon form of a matrix over integers and number fields.
The fast implementations for computing the characteristic polynomial and minimal polynomial over number fields use the CRT-based modular approach. Finally, we extended Storjohann's determinant computation algorithm over polynomial ring over finite fields, with its sub-algorithms for reconstructions and unimodular certification. In this case, we face the problem of intermediate degree swell. To avoid this phenomenon, we used higher-order lifting techniques in the unimodular certification algorithm. We have successfully used the half-gcd approach to optimize the rational polynomial reconstruction.
Robuste Optimierung wird zur Entscheidungsunterstützung eines komplexen Beschaffungs- und Transportmodells genutzt, um die Risikoeinstellung der Entscheidenden abzubilden und gleichzeitig ein robustes Ergebnis zu erzielen. Die Modellierung des Problems ist umfassend dargestellt und Ergebnisse der nicht-deterministischen Planung bei verschiedenen Parametern und Risikoeinstellungen gegenübergestellt. Die Datenunsicherheit wird an einem Praxisfall erläutert und Methoden und -empfehlungen zum Umgang mit dieser dargestellt.
In the recent years small towns have experienced several negative developments. Especially in rural areas there are demographic problems and in the sector of retailing. Reforms in state administration resulted in the reduction of county administration seats. Also professional health care services are being reduced.
The thesis explores the effectiveness of three middle order centres (which in two cases are formed by more than one town) to fulfil their respective functions for their regions (complementary regions).
The spatial dominance of these towns in the sectors of jobs and services (retailing, secondary education – up to college level – health and entertainment) is surveyed.
The analysis is done with statistical material already collected by various institutions and by several own surveys. Interviews were done with experts.
Thus each middle order center and its complementary region is evaluated.
Haslach/Hausach/Wolfach performs best, albeit their demographic development is not dynamic. Bad Krozingen/Staufen has some shortcomings in its performance by the most dynamic demographic development of the three entities. Titisee-Neustadt's performance can be ranked second.
In a final chapter further research topics are listed.
This PhD-Thesis deals with the calculation and application of a new class of invariants, that can be used to recognize patterns in tensor fields (i.e. scalar fields, vector fields und matrix fields), and by the composition of scalar fields with delta-functions also to point-clouds.
In the first chapter an overview over already existing invariants is given.
In the second chapter the general definition of the new invariants is given:
starting with a tensor field a set of moment tensor is created via folding in tensor-product manner with different orders of the tensor product of the positional vector. From these, rotational invariant values are calculated via contraction of tensor products. An algorithm to get a complete and independent set of invariants from a given moment tensor set is described. Furthermore methods to make these sets of invariants invariant against translation, rotation, scaling, and affine transformation.
In the third chapter, a method to optimize the calculation of these sets of invariants is described: every invariant can be modeled as undirected graph comprising multiple sub-graphs representing partially contracted tensor products of the moment tensors.
The composition of the sets of invariants is optimized by a clever choice of the decomposition into sub-graphs, all paths creating a hyper-graph of sub-graphs where each node describes a composition step. Finally, C++-source-code is created, which optimized using the symmetry of the different tensors and tensor-products, and a comparison of the effort to other calculation methods of invariants is given.
The fourth chapter describes the application of the invariants to object recognition in point-clouds from 3D-scans. To do this, the invariants of sub-sets of point-clouds are stored for every known object. Afterwards, invariants are calculated from an unknown point-cloud and tried to find them in the database to assign it to one of the known objects. Benchmarks using three 3D-object databases are made testing time and recognition rate.
On Gyroscopic Stabilization
(2012)
This thesis deals with systems of the form
\(
M\ddot x+D\dot x+Kx=0\;, \; x \in \mathbb R^n\;,
\)
with a positive definite mass matrix \(M\), a symmetric damping matrix \(D\) and a positive definite stiffness
matrix \(K\).
If the equilibrium in the system is unstable, a small disturbance is enough to set the system in motion again. The motion of the system sustains itself, an effect which is called self-excitation or self-induced vibration. The reason behind this effect is the presence of negative damping, which results for example from dry friction.
Negative damping implies that the damping matrix \(D\) is indefinite or negative definite. Throughout our work, we assume \(D\) to be indefinite, and that the system possesses both stable and unstable modes and thus is unstable.
It is now the idea of gyroscopic stabilization to mix the modes of a system with indefinite damping such
that the system is stabilized without introducing further
dissipation. This is done by adding gyroscopic forces \(G\dot x\) with a suitable
skew-symmetric matrix \(G\) to the left-hand side. We call \(G=-G^T\in\mathbb R^{n\times n}\) a gyroscopic stabilizer for
the unstable system, if
\(
M\ddot x+(D+ G)\dot x+Kx=0
\)
is asymptotically stable. We show the existence of \(G\) in space dimensions three and four.