Semi-algebraic methods for symbolic analysis of complex reaction networks

The identification of chemical mechanism that can exhibit oscillatory phenomena in reaction networks are currently of intense interest. In particular, the parametric question of the existence of Hopf bifurcations has gained increasing popularity due to its relation to the oscillatory behavior around the fixed points. However, the detection of oscillations in high-dimensional systems and systems with constraints by the available symbolic methods has proven to be difficult. The development of new efficient methods are therefore required to tackle the complexity caused by the high-dimensionality and non-linearity of these systems. In this thesis, we mainly present efficient algorithmic methods to detect Hopf bifurcation fixed points in (bio)-chemical reaction networks with symbolic rate constants, thereby yielding information about their oscillatory behavior of the networks. The methods use the representations of the systems on convex coordinates that arise from stoichiometric network analysis. One of the methods called HoCoQ reduces the problem of determining the existence of Hopf bifurcation fixed points to a first-order formula over the ordered field of the reals that can then be solved using computational-logic packages. The second method called HoCaT uses ideas from tropical geometry to formulate a more efficient method that is incomplete in theory but worked very well for the attempted high-dimensional models involving more than 20 chemical species. The instability of reaction networks may lead to the oscillatory behaviour. Therefore, we investigate some criterions for their stability using convex coordinates and quantifier elimination techniques. We also study Muldowney's extension of the classical Bendixson-Dulac criterion for excluding periodic orbits to higher dimensions for polynomial vector fields and we discuss the use of simple conservation constraints and the use of parametric constraints for describing simple convex polytopes on which periodic orbits can be excluded by Muldowney's criteria. All developed algorithms have been integrated into a common software framework called PoCaB (platform to explore bio- chemical reaction networks by algebraic methods) allowing for automated computation workflows from the problem descriptions. PoCaB also contains a database for the algebraic entities computed from the models of chemical reaction networks.

Modellbildung in der algebraischen Kryptoanalyse

In der algebraischen Kryptoanalyse werden moderne Kryptosysteme als polynomielle, nichtlineare Gleichungssysteme dargestellt. Das Lösen solcher Gleichungssysteme ist NP-hart. Es gibt also keinen Algorithmus, der in polynomieller Zeit ein beliebiges nichtlineares Gleichungssystem löst. Dennoch kann man aus modernen Kryptosystemen Gleichungssysteme mit viel Struktur generieren. So sind diese Gleichungssysteme bei geeigneter Modellierung quadratisch und dünn besetzt, damit nicht beliebig. Dafür gibt es spezielle Algorithmen, die eine Lösung solcher Gleichungssysteme finden. Ein Beispiel dafür ist der ElimLin-Algorithmus, der mit Hilfe von linearen Gleichungen das Gleichungssystem iterativ vereinfacht. In der Dissertation wird auf Basis dieses Algorithmus ein neuer Solver für quadratische, dünn besetzte Gleichungssysteme vorgestellt und damit zwei symmetrische Kryptosysteme angegriffen. Dabei sind die Techniken zur Modellierung der Chiffren von entscheidender Bedeutung, so das neue Techniken entwickelt werden, um Kryptosysteme darzustellen. Die Idee für das Modell kommt von Cube-Angriffen. Diese Angriffe sind besonders wirksam gegen Stromchiffren. In der Arbeit werden unterschiedliche Varianten klassifiziert und mögliche Erweiterungen vorgestellt. Das entstandene Modell hingegen, lässt sich auch erfolgreich auf Blockchiffren und auch auf andere Szenarien erweitern. Bei diesen Änderungen muss das Modell nur geringfügig geändert werden.

Identifikation spezieller Funktionen, die durch Rodriguesformeln gegeben sind

Es ist allgemein bekannt, dass sich zwei gegebene Systeme spezieller Funktionen durch Angabe einer Rekursionsgleichung und entsprechend vieler Anfangswerte identifizieren lassen, denn computeralgebraisch betrachtet hat man damit eine Normalform vorliegen. Daher hat sich die interessante Forschungsfrage ergeben, Funktionensysteme zu identifizieren, die über ihre Rodriguesformel gegeben sind. Zieht man den in den 1990er Jahren gefundenen Zeilberger-Algorithmus für holonome Funktionenfamilien hinzu, kann die Rodriguesformel algorithmisch in eine Rekursionsgleichung überführt werden. Falls die Funktionenfamilie überdies hypergeometrisch ist, sogar laufzeiteffizient. Um den Zeilberger-Algorithmus überhaupt anwenden zu können, muss es gelingen, die Rodriguesformel in eine Summe umzuwandeln. Die vorliegende Arbeit beschreibt die Umwandlung einer Rodriguesformel in die genannte Normalform für den kontinuierlichen, den diskreten sowie den q-diskreten Fall vollständig. Das in Almkvist und Zeilberger (1990) angegebene Vorgehen im kontinuierlichen Fall, wo die in der Rodriguesformel auftauchende n-te Ableitung über die Cauchysche Integralformel in ein komplexes Integral überführt wird, zeigt sich im diskreten Fall nun dergestalt, dass die n-te Potenz des Vorwärtsdifferenzenoperators in eine Summenschreibweise überführt wird. Die Rekursionsgleichung aus dieser Summe zu generieren, ist dann mit dem diskreten Zeilberger-Algorithmus einfach. Im q-Fall wird dargestellt, wie Rekursionsgleichungen aus vier verschiedenen q-Rodriguesformeln gewonnen werden können, wobei zunächst die n-te Potenz der jeweiligen q-Operatoren in eine Summe überführt wird. Drei der vier Summenformeln waren bislang unbekannt. Sie wurden experimentell gefunden und per vollständiger Induktion bewiesen. Der q-Zeilberger-Algorithmus erzeugt anschließend aus diesen Summen die gewünschte Rekursionsgleichung. In der Praxis ist es sinnvoll, den schnellen Zeilberger-Algorithmus anzuwenden, der Rekursionsgleichungen für bestimmte Summen über hypergeometrische Terme ausgibt. Auf dieser Fassung des Algorithmus basierend wurden die Überlegungen in Maple realisiert. Es ist daher sinnvoll, dass alle hier aufgeführten Prozeduren, die aus kontinuierlichen, diskreten sowie q-diskreten Rodriguesformeln jeweils Rekursionsgleichungen erzeugen, an den hypergeometrischen Funktionenfamilien der klassischen orthogonalen Polynome, der klassischen diskreten orthogonalen Polynome und an der q-Hahn-Klasse des Askey-Wilson-Schemas vollständig getestet werden. Die Testergebnisse liegen tabellarisch vor. Ein bedeutendes Forschungsergebnis ist, dass mit der im q-Fall implementierten Prozedur zur Erzeugung einer Rekursionsgleichung aus der Rodriguesformel bewiesen werden konnte, dass die im Standardwerk von Koekoek/Lesky/Swarttouw(2010) angegebene Rodriguesformel der Stieltjes-Wigert-Polynome nicht korrekt ist. Die richtige Rodriguesformel wurde experimentell gefunden und mit den bereitgestellten Methoden bewiesen. Hervorzuheben bleibt, dass an Stelle von Rekursionsgleichungen analog Differential- bzw. Differenzengleichungen für die Identifikation erzeugt wurden. Wie gesagt gehört zu einer Normalform für eine holonome Funktionenfamilie die Angabe der Anfangswerte. Für den kontinuierlichen Fall wurden umfangreiche, in dieser Gestalt in der Literatur noch nie aufgeführte Anfangswertberechnungen vorgenommen. Im diskreten Fall musste für die Anfangswertberechnung zur Differenzengleichung der Petkovsek-van-Hoeij-Algorithmus hinzugezogen werden, um die hypergeometrischen Lösungen der resultierenden Rekursionsgleichungen zu bestimmen. Die Arbeit stellt zu Beginn den schnellen Zeilberger-Algorithmus in seiner kontinuierlichen, diskreten und q-diskreten Variante vor, der das Fundament für die weiteren Betrachtungen bildet. Dabei wird gebührend auf die Unterschiede zwischen q-Zeilberger-Algorithmus und diskretem Zeilberger-Algorithmus eingegangen. Bei der praktischen Umsetzung wird Bezug auf die in Maple umgesetzten Zeilberger-Implementationen aus Koepf(1998/2014) genommen. Die meisten der umgesetzten Prozeduren werden im Text dokumentiert. Somit wird ein vollständiges Paket an Algorithmen bereitgestellt, mit denen beispielsweise Formelsammlungen für hypergeometrische Funktionenfamilien überprüft werden können, deren Rodriguesformeln bekannt sind. Gleichzeitig kann in Zukunft für noch nicht erforschte hypergeometrische Funktionenklassen die beschreibende Rekursionsgleichung erzeugt werden, wenn die Rodriguesformel bekannt ist.

Comparing Support Vector Machines with Gaussian Kernels to Radial Basis Function Classifiers

The Support Vector (SV) machine is a novel type of learning machine, based on statistical learning theory, which contains polynomial classifiers, neural networks, and radial basis function (RBF) networks as special cases. In the RBF case, the SV algorithm automatically determines centers, weights and threshold such as to minimize an upper bound on the expected test error. The present study is devoted to an experimental comparison of these machines with a classical approach, where the centers are determined by $k$--means clustering and the weights are found using error backpropagation. We consider three machines, namely a classical RBF machine, an SV machine with Gaussian kernel, and a hybrid system with the centers determined by the SV method and the weights trained by error backpropagation. Our results show that on the US postal service database of handwritten digits, the SV machine achieves the highest test accuracy, followed by the hybrid approach. The SV approach is thus not only theoretically well--founded, but also superior in a practical application.

An Empirical Comparison of SNoW and SVMs for Face Detection

Impressive claims have been made for the performance of the SNoW algorithm on face detection tasks by Yang et. al. [7]. In particular, by looking at both their results and those of Heisele et. al. [3], one could infer that the SNoW system performed substantially better than an SVM-based system, even when the SVM used a polynomial kernel and the SNoW system used a particularly simplistic 'primitive' linear representation. We evaluated the two approaches in a controlled experiment, looking directly at performance on a simple, fixed-sized test set, isolating out 'infrastructure' issues related to detecting faces at various scales in large images. We found that SNoW performed about as well as linear SVMs, and substantially worse than polynomial SVMs.

Support Vector Machines: Training and Applications

The Support Vector Machine (SVM) is a new and very promising classification technique developed by Vapnik and his group at AT&T Bell Labs. This new learning algorithm can be seen as an alternative training technique for Polynomial, Radial Basis Function and Multi-Layer Perceptron classifiers. An interesting property of this approach is that it is an approximate implementation of the Structural Risk Minimization (SRM) induction principle. The derivation of Support Vector Machines, its relationship with SRM, and its geometrical insight, are discussed in this paper. Training a SVM is equivalent to solve a quadratic programming problem with linear and box constraints in a number of variables equal to the number of data points. When the number of data points exceeds few thousands the problem is very challenging, because the quadratic form is completely dense, so the memory needed to store the problem grows with the square of the number of data points. Therefore, training problems arising in some real applications with large data sets are impossible to load into memory, and cannot be solved using standard non-linear constrained optimization algorithms. We present a decomposition algorithm that can be used to train SVM's over large data sets. The main idea behind the decomposition is the iterative solution of sub-problems and the evaluation of, and also establish the stopping criteria for the algorithm. We present previous approaches, as well as results and important details of our implementation of the algorithm using a second-order variant of the Reduced Gradient Method as the solver of the sub-problems. As an application of SVM's, we present preliminary results we obtained applying SVM to the problem of detecting frontal human faces in real images.

The Complexity of Safety Stock Placement in General-Network Supply Chains

We consider the optimization problem of safety stock placement in a supply chain, as formulated in [1]. We prove that this problem is NP-Hard for supply chains modeled as general acyclic networks. Thus, we do not expect to find a polynomial-time algorithm for safety stock placement for a general-network supply chain.

Statistical treatment of grain-size curves and empirical distributions: densities as compositions?

The preceding two editions of CoDaWork included talks on the possible consideration of densities as infinite compositions: Egozcue and D´ıaz-Barrero (2003) extended the Euclidean structure of the simplex to a Hilbert space structure of the set of densities within a bounded interval, and van den Boogaart (2005) generalized this to the set of densities bounded by an arbitrary reference density. From the many variations of the Hilbert structures available, we work with three cases. For bounded variables, a basis derived from Legendre polynomials is used. For variables with a lower bound, we standardize them with respect to an exponential distribution and express their densities as coordinates in a basis derived from Laguerre polynomials. Finally, for unbounded variables, a normal distribution is used as reference, and coordinates are obtained with respect to a Hermite-polynomials-based basis. To get the coordinates, several approaches can be considered. A numerical accuracy problem occurs if one estimates the coordinates directly by using discretized scalar products. Thus we propose to use a weighted linear regression approach, where all k- order polynomials are used as predictand variables and weights are proportional to the reference density. Finally, for the case of 2-order Hermite polinomials (normal reference) and 1-order Laguerre polinomials (exponential), one can also derive the coordinates from their relationships to the classical mean and variance. Apart of these theoretical issues, this contribution focuses on the application of this theory to two main problems in sedimentary geology: the comparison of several grain size distributions, and the comparison among different rocks of the empirical distribution of a property measured on a batch of individual grains from the same rock or sediment, like their composition

Experimental design on the simplex

Optimum experimental designs depend on the design criterion, the model and the design region. The talk will consider the design of experiments for regression models in which there is a single response with the explanatory variables lying in a simplex. One example is experiments on various compositions of glass such as those considered by Martin, Bursnall, and Stillman (2001). Because of the highly symmetric nature of the simplex, the class of models that are of interest, typically Scheff´e polynomials (Scheff´e 1958) are rather different from those of standard regression analysis. The optimum designs are also rather different, inheriting a high degree of symmetry from the models. In the talk I will hope to discuss a variety of modes for such experiments. Then I will discuss constrained mixture experiments, when not all the simplex is available for experimentation. Other important aspects include mixture experiments with extra non-mixture factors and the blocking of mixture experiments. Much of the material is in Chapter 16 of Atkinson, Donev, and Tobias (2007). If time and my research allows, I would hope to finish with a few comments on design when the responses, rather than the explanatory variables, lie in a simplex. References Atkinson, A. C., A. N. Donev, and R. D. Tobias (2007). Optimum Experimental Designs, with SAS. Oxford: Oxford University Press. Martin, R. J., M. C. Bursnall, and E. C. Stillman (2001). Further results on optimal and efficient designs for constrained mixture experiments. In A. C. Atkinson, B. Bogacka, and A. Zhigljavsky (Eds.), Optimal Design 2000, pp. 225–239. Dordrecht: Kluwer. Scheff´e, H. (1958). Experiments with mixtures. Journal of the Royal Statistical Society, Ser. B 20, 344–360. 1

G+: Enhanced Traffic Grooming in WDM Mesh Networks using Lighttours

In this article, a new technique for grooming low-speed traffic demands into high-speed optical routes is proposed. This enhancement allows a transparent wavelength-routing switch (WRS) to aggregate traffic en route over existing optical routes without incurring expensive optical-electrical-optical (OEO) conversions. This implies that: a) an optical route may be considered as having more than one ingress node (all inline) and, b) traffic demands can partially use optical routes to reach their destination. The proposed optical routes are named "lighttours" since the traffic originating from different sources can be forwarded together in a single optical route, i.e., as taking a "tour" over different sources towards the same destination. The possibility of creating lighttours is the consequence of a novel WRS architecture proposed in this article, named "enhanced grooming" (G+). The ability to groom more traffic in the middle of a lighttour is achieved with the support of a simple optical device named lambda-monitor (previously introduced in the RingO project). In this article, we present the new WRS architecture and its advantages. To compare the advantages of lighttours with respect to classical lightpaths, an integer linear programming (ILP) model is proposed for the well-known multilayer problem: traffic grooming, routing and wavelength assignment The ILP model may be used for several objectives. However, this article focuses on two objectives: maximizing the network throughput, and minimizing the number of optical-electro-optical conversions used. Experiments show that G+ can route all the traffic using only half of the total OEO conversions needed by classical grooming. An heuristic is also proposed, aiming at achieving near optimal results in polynomial time

On optimal computation of MPLS label binding for multipoint-to-point connections

Most network operators have considered reducing Label Switched Routers (LSR) label spaces (i.e. the number of labels that can be used) as a means of simplifying management of underlaying Virtual Private Networks (VPNs) and, hence, reducing operational expenditure (OPEX). This letter discusses the problem of reducing the label spaces in Multiprotocol Label Switched (MPLS) networks using label merging - better known as MultiPoint-to-Point (MP2P) connections. Because of its origins in IP, MP2P connections have been considered to have tree- shapes with Label Switched Paths (LSP) as branches. Due to this fact, previous works by many authors affirm that the problem of minimizing the label space using MP2P in MPLS - the Merging Problem - cannot be solved optimally with a polynomial algorithm (NP-complete), since it involves a hard- decision problem. However, in this letter, the Merging Problem is analyzed, from the perspective of MPLS, and it is deduced that tree-shapes in MP2P connections are irrelevant. By overriding this tree-shape consideration, it is possible to perform label merging in polynomial time. Based on how MPLS signaling works, this letter proposes an algorithm to compute the minimum number of labels using label merging: the Full Label Merging algorithm. As conclusion, we reclassify the Merging Problem as Polynomial-solvable, instead of NP-complete. In addition, simulation experiments confirm that without the tree-branch selection problem, more labels can be reduced

All-Optical Label Stacking: Easing the Trade-offs Between Routing and Architecture Cost in All-Optical Packet Switching

All-optical label swapping (AOLS) forms a key technology towards the implementation of all-optical packet switching nodes (AOPS) for the future optical Internet. The capital expenditures of the deployment of AOLS increases with the size of the label spaces (i.e. the number of used labels), since a special optical device is needed for each recognized label on every node. Label space sizes are affected by the way in which demands are routed. For instance, while shortest-path routing leads to the usage of fewer labels but high link utilization, minimum interference routing leads to the opposite. This paper studies all-optical label stacking (AOLStack), which is an extension of the AOLS architecture. AOLStack aims at reducing label spaces while easing the compromise with link utilization. In this paper, an integer lineal program is proposed with the objective of analyzing the softening of the aforementioned trade-off due to AOLStack. Furthermore, a heuristic aiming at finding good solutions in polynomial-time is proposed as well. Simulation results show that AOLStack either a) reduces the label spaces with a low increase in the link utilization or, similarly, b) uses better the residual bandwidth to decrease the number of labels even more

MA167exam00pdf

Exam questions and solutions in PDF

MA167exam00

Exam questions and solutions in LaTex. Diagrams for the questions are all together in the support.zip file, as .eps files

Exercise sheet 2 pdf

Exercises and solutions in PDF