TY  - THES
A1  - Wichitsa-nguan, Korakot
T1  - Modifications and extensions of the logistic regression and Cox model
T1  - Modifikationen und Erweiterungen des logistischen Regressionsmodells und des Cox-Modells
N2  - In many statistical applications, the aim is to model the relationship between covariates and some outcomes. A choice of the appropriate model depends on the outcome and the research objectives, such as linear models for continuous outcomes, logistic models for binary outcomes and the Cox model for time-to-event data. In epidemiological, medical, biological, societal and economic studies, the logistic regression is widely used to describe the relationship between a response variable as binary outcome and explanatory variables as a set of covariates. However, epidemiologic cohort studies are quite expensive regarding data management since following up a large number of individuals takes long time. Therefore, the case-cohort design is applied to reduce cost and time for data collection. The case-cohort sampling collects a small random sample from the entire cohort, which is called subcohort. The advantage of this design is that the covariate and follow-up data are recorded only on the subcohort and all cases (all members of the cohort who develop the event of interest during the follow-up process).
In this thesis, we investigate the estimation in the logistic model for case-cohort design. First, a model with a binary response and a binary covariate is considered. The maximum likelihood estimator (MLE) is described and its asymptotic properties are established. An estimator for the asymptotic variance of the estimator based on the maximum likelihood approach is proposed; this estimator differs slightly from the estimator introduced by Prentice (1986). Simulation results for several proportions of the subcohort show that the proposed estimator gives lower empirical bias and empirical variance than Prentice's estimator.
Then the MLE in the logistic regression with discrete covariate under case-cohort design is studied. Here the approach of the binary covariate model is extended. Proving asymptotic normality of estimators, standard errors for the estimators can be derived. The simulation study demonstrates the estimation procedure of the logistic regression model with a one-dimensional discrete covariate. Simulation results for several proportions of the subcohort and different choices of the underlying parameters indicate that the estimator developed here performs reasonably well. Moreover, the comparison between theoretical values and simulation results of the asymptotic variance of estimator is presented.
Clearly, the logistic regression is sufficient for the binary outcome refers to be available for all subjects and for a fixed time interval. Nevertheless, in practice, the observations in clinical trials are frequently collected for different time periods and subjects may drop out or relapse from other causes during follow-up. Hence, the logistic regression is not appropriate for incomplete follow-up data; for example, an individual drops out of the study before the end of data collection or an individual has not occurred the event of interest for the duration of the study. These observations are called censored observations. The survival analysis is necessary to solve these problems. Moreover, the time to the occurence of the event of interest is taken into account. The Cox model has been widely used in survival analysis, which can effectively handle the censored data. Cox (1972) proposed the model which is focused on the hazard function. The Cox model is assumed to be
λ(t|x) = λ0(t) exp(β^Tx)
where λ0(t) is an unspecified baseline hazard at time t and X is the vector of covariates, β is a p-dimensional vector of coefficient.
In this thesis, the Cox model is considered under the view point of experimental design. The estimability of the parameter β0 in the Cox model, where β0 denotes the true value of β, and the choice of optimal covariates are investigated. We give new representations of the observed information matrix In(β) and extend results for the Cox model of Andersen and Gill (1982). In this way conditions for the estimability of β0 are formulated. Under some regularity conditions, ∑ is the inverse of the asymptotic variance matrix of the MPLE of β0 in the Cox model and then some properties of the asymptotic variance matrix of the MPLE are highlighted. Based on the results of asymptotic estimability, the calculation of local optimal covariates is considered and shown in examples. In a sensitivity analysis, the efficiency of given covariates is calculated. For neighborhoods of the exponential models, the efficiencies have then been found. It is appeared that for fixed parameters β0, the efficiencies do not change very much for different baseline hazard functions. Some proposals for applicable optimal covariates and a calculation procedure for finding optimal covariates are discussed.
Furthermore, the extension of the Cox model where time-dependent coefficient are allowed, is investigated. In this situation, the maximum local partial likelihood estimator for estimating the coefficient function β(·) is described. Based on this estimator, we formulate a new test procedure for testing, whether a one-dimensional coefficient function β(·) has a prespecified parametric form, say β(·; ϑ). The score function derived from the local constant partial likelihood function at d distinct grid points is considered. It is shown that the distribution of the properly standardized quadratic form of this d-dimensional vector under the null hypothesis tends to a Chi-squared distribution. Moreover, the limit statement remains true when replacing the unknown ϑ0 by the MPLE in the hypothetical model and an asymptotic α-test is given by the quantiles or p-values of the limiting Chi-squared distribution. Finally, we propose a bootstrap version of this test. The bootstrap test is only defined for the special case of testing whether the coefficient function is constant. A simulation study illustrates the behavior of the bootstrap test under the null hypothesis and a special alternative. It gives quite good results for the chosen underlying model.

References
P. K. Andersen and R. D. Gill. Cox's regression model for counting processes: a large samplestudy. Ann. Statist., 10(4):1100{1120, 1982.

D. R. Cox. Regression models and life-tables. J. Roy. Statist. Soc. Ser. B, 34:187{220, 1972.

R. L. Prentice. A case-cohort design for epidemiologic cohort studies and disease prevention trials. Biometrika, 73(1):1{11, 1986.
N2  - In vielen statistischen Anwendungen besteht die Aufgabe darin, die Beziehung zwischen Einflussgrößen und einer Zielgröße zu modellieren. Die Wahl eines geeigneten Modells hängt vom Typ der Zielgröße und vom Ziel der Untersuchung ab - während lineare Modelle für die Beschreibung des Zusammenhanges stetiger Outputs und Einflussgrößen genutzt werden, dienen logistische Regressionsmodelle zur Modellierung binärer Zielgrößen und das Cox-Modell zur Modellierung von Lebendauer-Daten.
In epidemiologischen, medizinischen, biologischen, sozialen und ökonomischen Studien wird oftmals die logistische Regression angewendet, um den Zusammenhang zwischen einer binären Zielgröße und den erklärenden Variablen, den Kovariaten, zu modellieren. In epidemiologischen Studien muss häufig eine große Anzahl von Individuen für eine lange Zeit beobachtet werden. Um hierbei Kosten zu reduzieren, wird ein "Case-Cohort-Design" angewendet. Hierbei werden die Einflussgrößen nur für die Individuen erfasst, für die das interessierende Ereignis eintritt, und für eine zufällig gewählte kleine Teilmenge von Individuen, die Subkohorte.
In der vorliegenden Arbeit wird das Schätzen im logistischen Regressionsmodell unter Case-Cohort-Design betrachtet. Für den Fall, dass auch die Kovariate binär ist, wurde bereits von Prentice (1986) die asymptotische Normalität des Maximum-Likelihood-Schätzers für den Logarithmus des "odds ratio", einen Parameter, der den Effekt der Kovariate charakterisiert, angegeben. In dieser Arbeit wird über einen Maximum-Likelihood-Zugang ein Schätzer für die Varianz der Grenzverteilung hergeleitet, für den durch empirische Untersuchungen gezeigt wird, dass er dem von Prentice überlegen ist.
Ausgehend von dem binärem Kovariate-Modell werden Maximum-Likelihood-Schätzer für logistische Regressionsmodelle mit diskreten Kovariaten unter Case-Cohort-Design hergeleitet. Die asymptotische Normalität wird gezeigt; darauf aufbauend können Formeln für die Standardfehler angegeben werden. Simulationsstudien ergänzen diesen Abschnitt. Sie zeigen den Einfluss des Umfanges der Subkohorte auf die Varianz der Schätzer.
Logistische Regression ist geeignet, wenn man das interessierende Ereignis für alle Individuen beobachten kann und wenn man ein festes Zeitintervall betrachtet. Will man die Zeit bis zum Eintreten eines Ereignisses bei der Untersuchung der Wirkung der Kovariate berücksichtigen, so sind Lebensdauermodelle angemessen. Hierbei können auch zensierte Daten behandelt werden. Ein sehr häufig angewendetes Regressionsmodell ist das von Cox (1972) vorgeschlagene, bei dem die Hazardrate durch
λ(t|x) = λ0(t) exp(β^Tx)
definiert ist. Hierbei ist λ0(t) eine unspezifizierte Baseline-Hazardrate und X ist ein Kovariat-Vektor, β ist ein p-dimensionaler Koeffizientenvektor.
Nachdem ein Überblick über das Schätzen und Testen im Cox-Modell und seinen Erweiterungen gegeben wird, werden Aussagen zur Schätzbarkeit des Parameters β durch die "partiallikelihood"- Methode hergeleitet. Grundlage hierzu sind neue Darstellungen der beobachteten Fisher-Information, die die Ergebnisse von Andersen and Gill (1982) erweitern. Unter Regularitätsbedingungen ist der Schätzer asymptotisch normal; die Inverse der Grenzmatrix der Fisher-Information ist die Varianzmatrix der Grenzverteilung. Bedingungen für die Nichtsingularität dieser Grenzmatrix führen zum Begriff der asymptotischen Schätzbarkeit, der in der vorliegenden Arbeit ausführlich untersucht wird. Darüber hinaus ist diese Matrix Grundlage für die Herleitung lokal optimaler Kovariate. In einer Sensitivitätsanalyse wird die Effizienz gewählter Kovariate berechnet. Die Berechnungen zeigen, dass die Baseline-Verteilung nur wenig Einfluss auf die Effizienz hat. Entscheidend ist die Wahl der Kovariate. Es werden einige Vorschläge für anwendbare optimale Kovariate und Berechnungsverfahren für das Auffinden optimaler Kovariate diskutiert.
Eine Erweiterung des Cox-Modells besteht darin, zeitabhängige Koeffizienten zuzulassen. Da diese Koeffizientenfunktionen nicht näher spezifiziert sind, werden sie nichtparametrisch geschätzt. Eine mögliche Methode ist die "local-linear-partial-likelihood"-Methode, deren Eigenschaften beispielsweise in der Arbeit von Cai and Sun (2003) untersucht wurden. In der vorliegenden Arbeit werden Simulationen zu dieser Methode durchgeführt.
Hauptaspekt ist das Testen der Koeffizientenfunktion. Getestet wird, ob diese Funktion eine bestimmte parametrische Form besitzt. Betrachtet wird der Score-Vektor, der von der "localconstant-partial-likelihood"-Funktion abgeleitet wird. Ausgehend von der asymptotischen Normalität dieses Vektors an verschiedenen Gitterpunkten kann gezeigt werden, dass die Verteilung der geeignet standardisierten quadratischen Form unter der Nullhypothese gegen eine Chi-Quadrat-Verteilung konvergiert.
Die Eigenschaften des auf dieser Grenzverteilungsaussage aufbauenden Tests hängen nicht nur vom Stichprobenumfang, sondern auch vom verwendeten Glättungsparameter ab. Deshalb ist es sinnvoll, auch einen Bootstrap-Test zu betrachten. In der vorliegenden Arbeit wird ein Bootstrap-Test zum Testen der Hypothese, dass die Koeffizienten-Funktion konstant ist, d.h. dass das klassische Cox-Modell vorliegt, vorgeschlagen. Der Algorithmus wird angegeben. Simulationen zum Verhalten dieses Tests unter der Nullhypothese und einer speziellen Alternative werden durchgeführt.

Literatur
P. K. Andersen and R. D. Gill. Cox's regression model for counting processes: a large sample study. Ann. Statist., 10(4):1100{1120, 1982.

Z. Cai and Y. Sun. Local linear estimation for time-dependent coefficients in Cox's regression models. Scand. J. Statist., 30(1):93-111, 2003.

D. R. Cox. Regression models and life-tables. J. Roy. Statist. Soc. Ser. B, 34:187-220, 1972.

R. L. Prentice. A case-cohort design for epidemiologic cohort studies and disease prevention trials. Biometrika, 73(1):1-11, 1986.
KW  - survival analysis
KW  - Cox model
KW  - logistic regression analysis
KW  - logistische Regression
KW  - Case-Cohort-Design
KW  - Cox-Modell
Y1  - 2016
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-90033
ER  - 
TY  - THES
A1  - Zhelavskaya, Irina
T1  - Modeling of the Plasmasphere Dynamics
T1  - Modellierung der Plasmasphärendynamik
N2  - The plasmasphere is a dynamic region of cold, dense plasma surrounding the Earth. Its shape and size are highly susceptible to variations in solar and geomagnetic conditions. Having an accurate model of plasma density in the plasmasphere is important for GNSS navigation and for predicting hazardous effects of radiation in space on spacecraft. The distribution of cold plasma and its dynamic dependence on solar wind and geomagnetic conditions remain, however, poorly quantified. Existing empirical models of plasma density tend to be oversimplified as they are based on statistical averages over static parameters. Understanding the global dynamics of the plasmasphere using observations from space remains a challenge, as existing density measurements are sparse and limited to locations where satellites can provide in-situ observations. In this dissertation, we demonstrate how such sparse electron density measurements can be used to reconstruct the global electron density distribution in the plasmasphere and capture its dynamic dependence on solar wind and geomagnetic conditions. 

First, we develop an automated algorithm to determine the electron density from in-situ measurements of the electric field on the Van Allen Probes spacecraft. In particular, we design a neural network to infer the upper hybrid resonance frequency from the dynamic spectrograms obtained with the Electric and Magnetic Field Instrument Suite and Integrated Science (EMFISIS) instrumentation suite, which is then used to calculate the electron number density. The developed Neural-network-based Upper hybrid Resonance Determination (NURD) algorithm is applied to more than four years of EMFISIS measurements to produce the publicly available electron density data set.

We utilize the obtained electron density data set to develop a new global model of plasma density by employing a neural network-based modeling approach. In addition to the location, the model takes the time history of geomagnetic indices and location as inputs, and produces electron density in the equatorial plane as an output. It is extensively validated using in-situ density measurements from the Van Allen Probes mission, and also by comparing the predicted global evolution of the plasmasphere with the global IMAGE EUV images of He+ distribution. The model successfully reproduces erosion of the plasmasphere on the night side as well as plume formation and evolution, and agrees well with data.

The performance of neural networks strongly depends on the availability of training data, which is limited during intervals of high geomagnetic activity. In order to provide reliable density predictions during such intervals, we can employ physics-based modeling. We develop a new approach for optimally combining the neural network- and physics-based models of the plasmasphere by means of data assimilation. The developed approach utilizes advantages of both neural network- and physics-based modeling and produces reliable global plasma density reconstructions for quiet, disturbed, and extreme geomagnetic conditions. 

Finally, we extend the developed machine learning-based tools and apply them to another important problem in the field of space weather, the prediction of the geomagnetic index Kp. The Kp index is one of the most widely used indicators for space weather alerts and serves as input to various models, such as for the thermosphere, the radiation belts and the plasmasphere. It is therefore crucial to predict the Kp index accurately. Previous work in this area has mostly employed artificial neural networks to nowcast and make short-term predictions of Kp, basing their inferences on the recent history of Kp and solar wind measurements at L1. We analyze how the performance of neural networks compares to other machine learning algorithms for nowcasting and forecasting Kp for up to 12 hours ahead. Additionally, we investigate several machine learning and information theory methods for selecting the optimal inputs to a predictive model of Kp. The developed tools for feature selection can also be applied to other problems in space physics in order to reduce the input dimensionality and identify the most important drivers.

Research outlined in this dissertation clearly demonstrates that machine learning tools can be used to develop empirical models from sparse data and also can be used to understand the underlying physical processes. Combining machine learning, physics-based modeling and data assimilation allows us to develop novel methods benefiting from these different approaches.
N2  - Die Plasmasphäre ist eine die Erde umgebende dynamische Region aus kaltem, dichtem Plasma. Ihre Form und Größe sind sehr anfällig für Schwankungen der solaren und geomagnetischen Bedingungen. Ein präzises Modell der Plasmadichte in der Plasmasphäre ist wichtig für die GNSS-Navigation und für die Vorhersage gefährlicher Auswirkungen der kosmischen Strahlung auf Raumfahrzeuge. Die Verteilung des kalten Plasmas und seine dynamische Abhängigkeit vom Sonnenwind und den geomagnetischen Bedingungen sind jedoch nach wie vor nur unzureichend quantifiziert. Bestehende empirische Modelle der Plasmadichte sind in der Regel zu stark vereinfacht, da sie auf statistischen Durchschnittswerten statischer Parameter basieren. Das Verständnis der globalen Dynamik der Plasmasphäre anhand von Beobachtungen aus dem Weltraum bleibt eine Herausforderung, da vorhandene Dichtemessungen spärlich sind und sich auf Orte beschränken, an denen Satelliten In-situ-Beobachtungen liefern können. In dieser Dissertation zeigen wir, wie solche spärlichen Elektronendichtemessungen verwendet werden können, um die globale Elektronendichteverteilung in der Plasmasphäre zu rekonstruieren und ihre dynamische Abhängigkeit vom Sonnenwind und den geomagnetischen Bedingungen zu erfassen.

Zunächst entwickeln wir einen automatisierten Algorithmus zur Bestimmung der Elektronendichte aus In-situ-Messungen des elektrischen Feldes der Van Allen Probes Raumsonden. Insbesondere entwerfen wir ein neuronales Netzwerk, um die obere Hybridresonanzfrequenz aus den dynamischen Spektrogrammen abzuleiten, die wir durch die Instrumentensuite „Electric and Magnetic Field Instrument Suite“ (EMFISIS) erhielten, welche dann zur Berechnung der Elektronenzahldichte verwendet wird. Der entwickelte „Neural-network-based Upper Hybrid Resonance Determination“ (NURD)-Algorithmus wird auf mehr als vier Jahre der EMFISIS-Messungen angewendet, um den öffentlich verfügbaren Elektronendichte-Datensatz zu erstellen.

Wir verwenden den erhaltenen Elektronendichte-Datensatz, um ein neues globales Modell der Plasmadichte zu entwickeln, indem wir einen auf einem neuronalen Netzwerk basierenden Modellierungsansatz verwenden. Zusätzlich zum Ort nimmt das Modell den zeitlichen Verlauf der geomagnetischen Indizes und des Ortes als Eingabe und erzeugt als Ausgabe die Elektronendichte in der äquatorialebene. Dies wird ausführlich anhand von In-situ-Dichtemessungen der Van Allen Probes-Mission und durch den Vergleich der vom Modell vorhergesagten globalen Entwicklung der Plasmasphäre mit den globalen IMAGE EUV-Bildern der He+ -Verteilung validiert. Das Modell reproduziert erfolgreich die Erosion der Plasmasphäre auf der Nachtseite sowie die Bildung und Entwicklung von Fahnen und stimmt gut mit den Daten überein.

Die Leistung neuronaler Netze hängt stark von der Verfügbarkeit von Trainingsdaten ab, die für Intervalle hoher geomagnetischer Aktivität nur spärlich vorhanden sind. Um zuverlässige Dichtevorhersagen während solcher Intervalle zu liefern, können wir eine physikalische Modellierung verwenden. Wir entwickeln einen neuen Ansatz zur optimalen Kombination der neuronalen Netzwerk- und physikbasierenden Modelle der Plasmasphäre mittels Datenassimilation. Der entwickelte Ansatz nutzt sowohl die Vorteile neuronaler Netze als auch die physikalischen Modellierung und liefert zuverlässige Rekonstruktionen der globalen Plasmadichte für ruhige, gestörte und extreme geomagnetische Bedingungen.

Schließlich erweitern wir die entwickelten auf maschinellem Lernen basierten Werkzeuge und wenden sie auf ein weiteres wichtiges Problem im Bereich des Weltraumwetters an, die Vorhersage des geomagnetischen Index Kp. Der Kp-Index ist einer der am häufigsten verwendeten Indikatoren für Weltraumwetterwarnungen und dient als Eingabe für verschiedene Modelle, z.B. für die Thermosphäre, die Strahlungsgürtel und die Plasmasphäre. Es ist daher wichtig, den Kp-Index genau vorherzusagen. Frühere Arbeiten in diesem Bereich verwendeten hauptsächlich künstliche neuronale Netze, um Kurzzeit-Kp-Vorhersagen zu treffen, wobei deren Schlussfolgerungen auf der jüngsten Vergangenheit von Kp- und Sonnenwindmessungen am L1-Punkt beruhten. Wir analysieren, wie sich die Leistung neuronaler Netze im Vergleich zu anderen Algorithmen für maschinelles Lernen verhält, um kurz- und längerfristige Kp-Voraussagen von bis zu 12 Stunden treffen zu können. Zusätzlich untersuchen wir verschiedene Methoden des maschinellen Lernens und der Informationstheorie zur Auswahl der optimalen Eingaben für ein Vorhersagemodell von Kp. Die entwickelten Werkzeuge zur Merkmalsauswahl können auch auf andere Probleme in der Weltraumphysik angewendet werden, um die Eingabedimensionalität zu reduzieren und die wichtigsten Treiber zu identifizieren.

Die in dieser Dissertation skizzierten Untersuchungen zeigen deutlich, dass Werkzeuge für maschinelles Lernen sowohl zur Entwicklung empirischer Modelle aus spärlichen Daten als auch zum Verstehen zugrunde liegender physikalischer Prozesse genutzt werden können. Die Kombination von maschinellem Lernen, physikbasierter Modellierung und Datenassimilation ermöglicht es uns, kombinierte Methoden zu entwickeln, die von unterschiedlichen Ansätzen profitieren.
KW  - Plasmasphere
KW  - Inner magnetosphere
KW  - Neural networks
KW  - Machine learning
KW  - Modeling
KW  - Kp index
KW  - Geomagnetic activity
KW  - Data assimilation
KW  - Validation
KW  - IMAGE EUV
KW  - Kalman filter
KW  - Plasmasphäre
KW  - Innere Magnetosphäre
KW  - Neuronale Netze
KW  - Maschinelles Lernen
KW  - Modellieren
KW  - Forecasting
KW  - Kp-Index
KW  - Geomagnetische Aktivität
KW  - Datenassimilation
KW  - Validierung
KW  - Kalman Filter
KW  - Prognose
Y1  - 2020
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-482433
ER  - 
TY  - THES
A1  - Perera, Upeksha
T1  - Solutions of direct and inverse Sturm–Liouville problems
T1  - Lösungen von direkten und inversen Sturm-Liouville-Problemen
N2  - Lie group method in combination with Magnus expansion is utilized to develop a universal method applicable to solving a Sturm–Liouville Problem (SLP) of any order with arbitrary boundary conditions. It is shown that the method has ability to solve direct regular and some singular SLPs of even orders (tested up to order eight), with a mix of boundary conditions (including non-separable and finite singular endpoints), accurately and efficiently.

The present technique is successfully applied to overcome the difficulties in finding suitable sets of eigenvalues so that the inverse SLP problem can be effectively solved.

Next, a concrete implementation to the inverse Sturm–Liouville problem
algorithm proposed by Barcilon (1974) is provided. Furthermore, computational feasibility and applicability of this algorithm to solve inverse Sturm–Liouville problems of order n=2,4 is verified successfully. It is observed that the method is successful even in the presence of significant noise, provided that the assumptions of the algorithm are satisfied.

In conclusion, this work provides methods that can be adapted successfully for solving a direct (regular/singular) or inverse SLP of an arbitrary order with arbitrary boundary conditions.
N2  - Die Lie-Gruppen-Methode in Kombination mit der Magnus-Expansion wird
verwendet, um eine universelle Methode zu entwickeln, die zur Lösung eines Sturm-Liouville-Problems (SLP) beliebiger Ordnung mit beliebigen Randbedingungen anwendbar ist. Es wird gezeigt, dass die Methode in der Lage ist, direkte reguläre und einige singuläre SLPs gerader Ordnung (getestet bis zur 8. Ordnung) mit einer Mischung von Randbedingungen (einschließlich nicht trennbarer und endlicher singulärer Endpunkte) genau und effizient zu lösen.

Die vorliegende Technik wird erfolgreich angewendet, um die Schwierigkeiten beim Finden geeigneter Sätze von Eigenwerten zu überwinden, so dass das inverse SLP-Problem effektiv gelöst werden kann.

Als nächstes wird eine konkrete Implementierung des von Barcilon (1974) vorgeschlagenen inversen Sturm-Liouville-Problemalgorithmus bereitgestellt. Weiterhin wird die rechnerische Durchführbarkeit und Anwendbarkeit dieses Algorithmus zur Lösung inverser Sturm-Liouville-Probleme der Ordnung n=2,4 erfolgreich verifiziert. Es wird beobachtet, dass das Verfahren selbst bei Vorhandensein von signifikantem Rauschen erfolgreich ist, vorausgesetzt, dass
die Annahmen des Algorithmus erfüllt sind.

Zusammenfassend stellt diese Arbeit Methoden zur Verfügung, die erfolgreich zur Lösung eines direkten (regulär/singulären) oder inversen SLP beliebiger Ordnung mit beliebigen Randbedingungen angepasst werden können.
KW  - Sturm-Liouville problem
KW  - Inverse Sturm-Liouville problem
KW  - Higher-order Sturm-Liouville problem
KW  - Sturm-Liouville-Problem höherer Ordnung
KW  - Inverses Sturm-Liouville-Problem
KW  - Sturm-Liouville-Problem
Y1  - 2021
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-530064
ER  - 
TY  - THES
A1  - Lagodzinski, Julius Albert Gregor
T1  - Counting homomorphisms over fields of prime order
T1  - Zählen von Homomorphismen über Körper mit Primzahlordnung
N2  - Homomorphisms are a fundamental concept in mathematics expressing the similarity of structures. They provide a framework that captures many of the central problems of computer science with close ties to various other fields of science. Thus, many studies over the last four decades have been devoted to the algorithmic complexity of homomorphism problems. Despite their generality, it has been found that non-uniform homomorphism problems, where the target structure is fixed, frequently feature complexity dichotomies. Exploring the limits of these dichotomies represents the common goal of this line of research.

We investigate the problem of counting homomorphisms to a fixed structure over a finite field of prime order and its algorithmic complexity. Our emphasis is on graph homomorphisms and the resulting problem #_{p}Hom[H] for a graph H and a prime p. The main research question is how counting over a finite field of prime order affects the complexity. 

In the first part of this thesis, we tackle the research question in its generality and develop a framework for studying the complexity of counting problems based on category theory. In the absence of problem-specific details, results in the language of category theory provide a clear picture of the properties needed and highlight common ground between different branches of science. The proposed problem #Mor^{C}[B] of counting the number of morphisms to a fixed object B of C is abstract in nature and encompasses important problems like constraint satisfaction problems, which serve as a leading example for all our results. We find explanations and generalizations for a plethora of results in counting complexity. Our main technical result is that specific matrices of morphism counts are non-singular. The strength of this result lies in its algebraic nature. First, our proofs rely on carefully constructed systems of linear equations, which we know to be uniquely solvable. Second, by exchanging the field that the matrix is defined by to a finite field of order p, we obtain analogous results for modular counting. For the latter, cancellations are implied by automorphisms of order p, but intriguingly we find that these present the only obstacle to translating our results from exact counting to modular counting. If we restrict our attention to reduced objects without automorphisms of order p, we obtain results analogue to those for exact counting. This is underscored by a confluent reduction that allows this restriction by constructing a reduced object for any given object. We emphasize the strength of the categorial perspective by applying the duality principle, which yields immediate consequences for the dual problem of counting the number of morphisms from a fixed object.

In the second part of this thesis, we focus on graphs and the problem #_{p}Hom[H]. We conjecture that automorphisms of order p capture all possible cancellations and that, for a reduced graph H, the problem #_{p}Hom[H] features the complexity dichotomy analogue to the one given for exact counting by Dyer and Greenhill. This serves as a generalization of the conjecture by Faben and Jerrum for the modulus 2. The criterion for tractability is that H is a collection of complete bipartite and reflexive complete graphs. From the findings of part one, we show that the conjectured dichotomy implies dichotomies for all quantum homomorphism problems, in particular counting vertex surjective homomorphisms and compactions modulo p. Since the tractable cases in the dichotomy are solved by trivial computations, the study of the intractable cases remains. As an initial problem in a series of reductions capable of implying hardness, we employ the problem of counting weighted independent sets in a bipartite graph modulo prime p. A dichotomy for this problem is shown, stating that the trivial cases occurring when a weight is congruent modulo p to 0 are the only tractable cases. We reduce the possible structure of H to the bipartite case by a reduction to the restricted homomorphism problem #_{p}Hom^{bip}[H] of counting modulo p the number of homomorphisms between bipartite graphs that maintain a given order of bipartition. This reduction does not have an impact on the accessibility of the technical results, thanks to the generality of the findings of part one. In order to prove the conjecture, it suffices to show that for a connected bipartite graph that is not complete, #_{p}Hom^{bip}[H] is #_{p}P-hard. Through a rigorous structural study of bipartite graphs, we establish this result for the rich class of bipartite graphs that are (K_{3,3}\{e}, domino)-free. This overcomes in particular the substantial hurdle imposed by squares, which leads us to explore the global structure of H and prove the existence of explicit structures that imply hardness.
N2  - Homomorphismen sind ein grundlegendes Konzept der Mathematik, das die Ähnlichkeit von Strukturen ausdrückt. Sie bieten einen Rahmen, der viele der zentralen Probleme der Informatik umfasst und enge Verbindungen zu verschiedenen Wissenschaftsbereichen aufweist. Aus diesem Grund haben sich in den letzten vier Jahrzehnten viele Studien mit der algorithmischen Komplexität von Homomorphismusproblemen beschäftigt. Trotz ihrer Allgemeingültigkeit wurden Komplexitätsdichotomien häufig für nicht-uniforme Homomorphismusprobleme nachgewiesen, bei denen die Zielstruktur fixiert ist. Die Grenzen dieser Dichotomien zu erforschen, ist das gemeinsame Ziel dieses Forschungskalküls.

Wir untersuchen das Problem und seine algorithmische Komplexität, Homomorphismen zu einer festen Struktur über einem endlichen Körper mit Primzahlordnung zu zählen. Wir konzentrieren uns auf Graphenhomomorphismen und das daraus resultierende Problem #_{p}Hom[H] für einen Graphen H und eine Primzahl p. Die Hauptforschungsfrage ist, wie das Zählen über einem endlichen Körper mit Primzahlordnung die Komplexität beeinflusst. 

Im ersten Teil wird die Forschungsfrage in ihrer Allgemeinheit behandelt und ein Rahmen für die Untersuchung der Komplexität von Zählproblemen auf der Grundlage der Kategorientheorie entwickelt. Losgelöst von problemspezifischen Details liefern die Ergebnisse in der Sprache der Kategorientheorie ein klares Bild der benötigten Eigenschaften und zeigen Gemeinsamkeiten zwischen verschiedenen Wissenschaftsgebieten auf. Das vorgeschlagene Problem #Mor^{C}[B] des Zählens der Anzahl von Morphismen zu einem festen Objekt B von C ist abstrakter Natur und umfasst wichtige Probleme wie Constraint Satisfaction Problems, die als leitendes Beispiel für alle unsere Ergebnisse dienen. Wir finden Erklärungen und Verallgemeinerungen für eine Vielzahl von Ergebnissen in der Komplexitätstheorie von Zählproblemen. Unser wichtigstes technisches Ergebnis ist, dass bestimmte Matrizen von Morphismenzahlen nicht singulär sind. Die Stärke dieses Ergebnisses liegt in seiner algebraischen Natur. Erstens basieren unsere Beweise auf sorgfältig konstruierten linearen Gleichungssystemen, von denen wir wissen, dass sie eindeutig lösbar sind. Zweitens, indem wir den Körper, über dem die Matrix definiert ist, durch einen endlichen Körper der Ordnung p ersetzen, erhalten wir analoge Ergebnisse für das modulare Zählen. Für letztere sind Annullierungen durch Automorphismen der Ordnung p impliziert, aber faszinierenderweise stellen diese das einzige Hindernis für die Übertragung unserer Ergebnisse von der exakten auf die modulare Zählung dar. Wenn wir unsere Aufmerksamkeit auf reduzierte Objekte ohne Automorphismen der Ordnung p beschränken, erhalten wir Ergebnisse, die zu denen des exakten Zählens analog sind. Dies wird durch eine konfluente Reduktion unterstrichen, die für jedes beliebige Objekt ein reduziertes Objekt konstruiert. Wir heben die Stärke der kategorialen Perspektive durch die Anwendung des Dualitätsprinzips hervor, das direkte Konsequenzen für das duale Problem des Zählens der Anzahl der Morphismen von einem fixen Objekts aus liefert.

Im zweiten Teil konzentrieren wir uns auf Graphen und das Problem #_{p}Hom[H]. Wir stellen die Vermutung auf, dass Automorphismen der Ordnung p alle möglichen Annullierungen erklären und dass das Problem #_{p}Hom[H] für einen reduzierten Graphen H eine Komplexitätsdichotomie analog zu der aufweist, die von Dyer und Greenhill für das exakte Zählen bewiesen wurde. Dies stellt eine Verallgemeinerung der Vermutung von Faben und Jerrum für den Modulus 2 dar. Das Kriterium für die effiziente Lösbarkeit ist, dass H lediglich aus vollständigen bipartiten und reflexiven vollständigen Graphen besteht. Basierend auf den Ergebnisse des ersten Teils zeigen wir, dass die Vermutung Dichotomien für alle Quantenhomomorphismenprobleme impliziert, insbesondere für das Zählen modulo p von Homomorphismen surjektiv auf Knoten und von Verdichtungen. Da die effizient lösbaren Fälle in der Dichotomie durch triviale Berechnungen gelöst werden, bleibt es, die unlösbaren Fälle zu untersuchen. Als erstes Problem in einer Reihe von Reduktionen, deren Ziel es ist, Härte zu implizieren, verwenden wir das Problem des Zählens gewichteter unabhängiger Mengen in einem bipartiten Graphen modulo p. Für dieses Problem beweisen wir eine Dichotomie, die besagt, dass nur die trivialen Fälle effizient lösbar sind. Diese treten auf, wenn ein Gewicht kongruent modulo p zu 0 ist. Durch eine Reduktion auf das eingeschränkte Homomorphismusproblem #_{p}Hom^{bip}[H] reduzieren wir die mögliche Struktur von H auf den bipartiten Fall. Hierbei handelt es sich um das Problem des Zählens modulo p der Homomorphismen zwischen bipartiten Graphen, die eine gegebene Ordnung der Bipartition erhalten. Dank der Allgemeingültigkeit der Ergebnisse des ersten Teils hat diese Reduktion keinen Einfluss auf die Verfügbarkeit der technischen Ergebnisse. Für einen Beweis der Vermutung genügt es zu zeigen, dass #_{p}Hom^{bip}[H] für einen zusammenhängenden und nicht vollständigen bipartiten Graphen #_{p}P-schwer ist. Durch eine rigorose Untersuchung der Struktur von bipartiten Graphen beweisen wir dieses Ergebnis für die umfangreiche Klasse von bipartiten Graphen, die (K_{3,3}\{e}, domino)-frei sind. Dies überwindet insbesondere die substantielle Hürde, die durch Quadrate gegeben ist und uns dazu veranlasst, die globale Struktur von H zu untersuchen und die Existenz expliziter Strukturen zu beweisen, die Härte implizieren.
KW  - complexity theory
KW  - (modular) counting
KW  - relational structures
KW  - categories
KW  - homomorphisms
KW  - Zählen
KW  - Kategorien
KW  - Komplexitätstheorie
KW  - Homomorphismen
KW  - relationale Strukturen
Y1  - 2024
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-646037
ER  -