Dissertations / Theses on the topic 'Computational algebraic geometry'

Commutative algebra finds its roots in invariant theory and the connection is drawn from a modern standpoint. The Hilbert Basis Theorem and the Nullstellenstatz were considered lemmas for classical invariant theory. The Groebner basis is a modern tool used and is implemented with the computer algebra system Mathematica. Number 14 of Hilbert\'s 23 problems is discussed along with the notion of invariance under a group action of GLn(C). Computational difficulties are also discussed in reference to Groebner bases and Invariant theory.The straitening law is presented from a Groebner basis point of view and is motivated as being a key piece of machinery in proving First Fundamental Theorem of Invariant Theory.
Master of Science

This thesis consists of two parts, a first part on computations in algebraic geometry, and a second part on deformation quantization. More specifically, it is a collection of four papers. In the papers I, II and III, we present algorithms and an implementation for the computation of degrees of characteristic classes in algebraic geometry. Paper IV is a contribution to the field of deformation quantization and actions of the Grothendieck-Teichmüller group. In Paper I, we present an algorithm for the computation of degrees of Segre classes of closed subschemes of complex projective space. The algorithm is based on the residual intersection theorem and can be implemented both symbolically and numerically. In Paper II, we describe an algorithm for the computation of the degrees of Chern-Schwartz-MacPherson classes and the topological Euler characteristic of closed subschemes of complex projective space, provided an algorithm for the computation of degrees of Segre classes. We also explain in detail how the algorithm in Paper I can be implemented numerically. Together this yields a symbolical and a numerical version of the algorithm. Paper III describes the Macaulay2 package CharacteristicClasses. It implements the algorithms from papers I and II, as well as an algorithm for the computation of degrees of Chern classes. In Paper IV, we show that L-infinity-automorphisms of the Schouten algebra T_poly(R^d) of polyvector fields on affine space R^d which satisfy certain conditions can be globalized. This means that from a given L-infinity-automorphism of T_poly(R^d) an L-infinity-automorphism of T_poly(M) can be constructed, for a general smooth manifold M. It follows that Willwacher's action of the Grothendieck-Teichmüller group on T_poly(R^d) can be globalized, i.e., the Grothendieck-Teichmüller group acts on the Schouten algebra T_poly(M) of polyvector fields on a general manifold M.

At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 2: Manuscript. Paper 3: Manuscript. Paper 4: Accepted.

We develop the necessary theory in algebraic geometry to place Bayesian networks into the realm of algebraic statistics. This allows us to create an algebraic geometry--statistics dictionary. In particular, we study the algebraic varieties defined by the conditional independence statements of Bayesian networks. A complete algebraic classification, in terms of primary decomposition of polynomial ideals, is given for Bayesian networks on at most five random variables. Hidden variables are related to the geometry of higher secant varieties. Moreover, a complete algebraic classification, in terms of generating sets of polynomial ideals, is given for Bayesian networks on at most three random variables and one hidden variable. The relevance of these results for model selection is discussed.
Ph. D.

We investigate the action of the Atkin operator on spaces of overconvergent p-adic modular forms. Our contributions are both computational and geometric. We present several algorithms to compute the spectrum of the Atkin operator, as well as its p-adic variation as a function of the weight. As an application, we explicitly construct Heegner-type points on elliptic curves. We then make a geometric study of the Atkin operator, and prove a potential semi-stability theorem for correspondences. We explicitly determine the stable models of various Hecke operators on quaternionic Shimura curves, and make a purely geometric study of canonical subgroups.

This thesis concerns computation and algebraic geometry. On the computational side we have focused on numerical homotopy methods. These procedures may be used to numerically solve systems of polynomial equations. The thesis contains four papers. In Paper I and Paper II we apply continuation techniques, as well as symbolic algorithms, to formulate methods to compute Chern classes of smooth algebraic varieties. More specifically, in Paper I we give an algorithm to compute the degrees of the Chern classes of smooth projective varieties and in Paper II we extend these ideas to cover also the degrees of intersections of Chern classes. In Paper III we formulate a numerical homotopy to compute the intersection of two complementary dimensional subvarieties of a smooth quadric hypersurface in projective space. If the two subvarieties intersect transversely, then the number of homotopy paths is optimal. As an application we give a new solution to the inverse kinematics problem of a six-revolute serial-link mechanism. Paper IV is a study of curves on certain special quartic surfaces in projective 3-space. The surfaces are invariant under the action of a finite group called the level (2,2) Heisenberg group. In the paper, we determine the Picard group of a very general member of this family of quartics. We have found that the general Heisenberg invariant quartic contains 320 smooth conics and we prove that in the very general case, this collection of conics generates the Picard group.
QC 20101115

Diss. (sammanfattning) Stockholm : Stockholms universitet, 2009.
At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: Manuscript. Härtill 6 uppsatser.

Cette thèse traite de certains aspects particuliers de la résolution des systèmes algébriques. Dans un premier temps, nous présentons une façon de minimiser le nombres de variables additives apparaissant dans un système algébrique. Nous utilisons pour cela deux invariants de variété introduits par Hironaka : le faîte et la directrice. Dans un second temps, nous proposons une arithmétique rapide, dite détendue, pour les entiers p-adiques. Cette arithmétique nous permet ensuite de résoudre efficacement un système algébrique à coefficients rationnels localement, c'est-à-dire sur les entiers p-adiques. En quatrième partie, nous nous intéressons à la factorisation d'un polynôme à deux variables qui est une brique élémentaire pour la décomposition en composantes irréductibles des hypersurfaces. Nous proposons un algorithme réduisant la factorisation du polynôme donné en entrée à celle d'un polynôme dont la taille dense est essentiellement équivalente à la taille convexe-dense de celui donné en entrée. Dans la dernière partie, nous considérons la résolution en moyenne des systèmes algébriques réels. Nous proposons un algorithme probabiliste calculant un zéro approché complexe du système algébrique réel donné en entrée.

We study admissible transformations and solve group classification problems for various classes of linear and nonlinear Schrödinger equations with an arbitrary number n of space variables. The aim of the thesis is twofold. The first is the construction of the new theory of uniform seminormalized classes of differential equations and its application to solving group classification problems for these classes. Point transformations connecting two equations (source and target) from the class under study may have special properties of semi-normalization. This makes the group classification of that class using the algebraic method more involved. To extend this method we introduce the new notion of uniformly semi-normalized classes. Various types of uniform semi-normalization are studied: with respect to the corresponding equivalence group, with respect to a proper subgroup of the equivalence group as well as the corresponding types of weak uniform semi-normalization. An important kind of uniform semi-normalization is given by classes of homogeneous linear differential equations, which we call uniform semi-normalization with respect to linear superposition of solutions. The class of linear Schrödinger equations with complex potentials is of this type and its group classification can be effectively carried out within the framework of the uniform semi-normalization. Computing the equivalence groupoid and the equivalence group of this class, we show that it is uniformly seminormalized with respect to linear superposition of solutions. This allow us to apply the version of the algebraic method for uniformly semi-normalized classes and to reduce the group classification of this class to the classification of appropriate subalgebras of its equivalence algebra. To single out the classification cases, integers that are invariant under equivalence transformations are introduced. The complete group classification of linear Schrödinger equations is carried out for the cases n = 1 and n = 2. The second aim is to study group classification problem for classes of generalized nonlinear Schrödinger equations which are not uniformly semi-normalized. We find their equivalence groupoids and their equivalence groups and then conclude whether these classes are normalized or not. The most appealing classes are the class of nonlinear Schrödinger equations with potentials and modular nonlinearities and the class of generalized Schrödinger equations with complex-valued and, in general, coefficients of Laplacian term. Both these classes are not normalized. The first is partitioned into an infinite number of disjoint normalized subclasses of three kinds: logarithmic nonlinearity, power nonlinearity and general modular nonlinearity. The properties of the Lie invariance algebras of equations from each subclass are studied for arbitrary space dimension n, and the complete group classification is carried out for each subclass in dimension (1+2). The second class is successively reduced into subclasses until we reach the subclass of (1+1)-dimensional linear Schrödinger equations with variable mass, which also turns out to be non-normalized. We prove that this class is mapped by a family of point transformations to the class of (1+1)-dimensional linear Schrödinger equations with unique constant mass.

This dissertation has two topics. The rst one is about rotating a supporting hyperplane on the convex hull of a nite point set to arrive at one of its facets. We present three procedures for these rotations in multiple dimensions. The rst two procedures rotate a supporting hyperplane for the polytope starting at a lower dimensional face until the support set is a facet. These two procedures keep current points in the support set and accumulate new points after the rotations. The rst procedure uses only algebraic operations. The second procedure uses LP. In the third procedure we rotate a hyperplane on a facet of the polytope to a dierent adjacent facet. Similarly to the rst procedure, this procedure uses only algebraic operations. Some applications to these procedures include data envelopment analysis (DEA) and integer programming. The second topic is in the eld of containment problems for polyhedral sets. We present three procedures to nd a circumscribing simplex that contains a point set in any dimension. The rst two procedures are based on the supporting hyperplane rotation ideas from the rst topic. The third circumscribing simplex procedure uses polar cones and other geometrical properties to nd facets of a circumscribing simplex. One application of the second topic discussed in this dissertation is in hyperspectral unmixing.

Proteins are an important component of living organisms, composed of one or more polypeptide chains, each containing hundreds or even thousands of amino acids of 20 standard types. The structure of a protein from the sequence determines crucial functions of proteins such as initiating metabolic reactions, DNA replication, cell signaling, and transporting molecules. In the past, proteins were considered to always have a well-defined stable shape (structured proteins), however, it has recently been shown that there exist intrinsically disordered proteins (IDPs), which lack a fixed or ordered 3D structure, have dynamic characteristics and therefore, exist in multiple states. Based on this, we extend the mapping of protein sequence not only to a fixed stable structure but also to an ensemble of protein conformations, which help us explain the complex interaction within a cell that was otherwise obscured. The objective of this dissertation is to develop effective ab initio methods and tools for protein un/structure prediction by developing effective statistical energy function, conformational search method, and disulfide connectivity patterns predictor. The key outcomes of this dissertation research are: i) a sequence and structure-based energy function for structured proteins that includes energetic terms extracted from hydrophobic-hydrophilic properties, accessible surface area, torsion angles, and ubiquitously computed dihedral angles uPhi and uPsi, ii) an ab initio protein structure predictor that combines optimal energy function derived from sequence and structure-based properties of proteins and an effective conformational search method which includes angular rotation and segment translation strategies, iii) an SVM with RBF kernel-based framework to predict disulfide connectivity pattern, iv) a hydrophobic-hydrophilic property based energy function for unstructured proteins, and v) an ab initio conformational ensemble generator that combines energy function and conformational search method for unstructured proteins which can help understand the biological systems involving IDPs and assist in rational drugs design to cure critical diseases such as cancer or cardiovascular diseases caused by challenging states of IDPs.

Orientador: Carlile Campos Lavor
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-17T14:47:27Z (GMT). No. of bitstreams: 1 Melo_Nolmar_D.pdf: 2834013 bytes, checksum: 5639deabb953aa019e4e1c9c905e856d (MD5) Previous issue date: 2011
Resumo: Este trabalho apresenta uma linguagem algébrica para dois elementos básicos da teoria da informação quântica (os bits quânticos e os operadores densidade), baseada nas propriedades de uma álgebra de Clifford de assinatura (n,3n). Demonstramos que a nova descrição desses elementos preserva as mesmas propriedades matemáticas obtidas com a descrição clássica. Com isso, estendemos alguns resultados apresentados na literatura que relaciona Álgebra de Clifford e Informação Quântica.
Abstract: This work presents an algebraic language for two basic elements of quantum information theory (the quantum bits and density operators), based in the properties of a Clifford algebra of signature (n,3n). We prove that the new description of these elements preserves the same mathematical properties obtained with the classical description. We also extend some results presented in the literature that relate Clifford algebra and quantum information.
Doutorado
Matematica Aplicada
Doutor em Matemática

La première partie concerne un problème de théorie des nombres, pour laquel nous développons une approche géométrique basé sur des outils provenant de la géométrie algébrique et de la géométrique combinatoire. Introduites par M. Kontsevich et D. Zagier en 2001, les périodes sont des nombres complexes obtenus comme valeurs des intégrales d'une forme particulier, où le domaine et l'intégrande s'expriment par des polynômes avec coefficients rationnels. La conjecture de périodes de Kontsevich-Zagier affirme que n'importe quelle relation polynomiale entre périodes peut s'obtenir par des relations linéaires entre différentes représentations intégrales, exprimées par des règles classiques du calcul intégrale. En utilisant des résolutions de singularités, on introduit une réduction semi-canonique de périodes en se concentrant sur le fait d'obtenir une méthode algorithmique et constructive respectant les règles classiques de transformation intégrale: nous prouvons que n'importe quelle période non nulle, représentée par une certaine intégrale, peut être exprimée sauf signe comme le volume d'un ensemble semi-algébrique compact. La réduction semi-canonique permet une reformulation de la conjecture de périodes de Kontsevich-Zagier en termes de changement de variables préservant le volume entre ensembles semi-algébriques compacts. Via des triangulations et méthodes de la géométrie-PL, nous étudions les obstructions de cette approche comme la généralisation du 3ème Problème de Hilbert. Nous complétons les travaux de J. Wan dans le développement d'une théorie du degré pour les périodes, basée sur la dimension minimale de l'espace ambiance nécessaire pour obtenir une telle réduction compacte, en donnant une première notion géométrique sur la transcendance de périodes. Nous étendons cet étude en introduisant des notions de complexité géométrique et arithmétique pour le périodes basées sur la complexité polynomiale minimale parmi les réductions semi-canoniques d'une période. La seconde partie s'occupe de la compréhension d'objets provenant de la géométrie algébrique avec une forte connexion avec la géométrique combinatoire, pour lesquels nous avons développé une approche dynamique. Les champs de vecteurs logarithmiques sont un outils algébro-analytique utilisés dans l'étude des sous-variétés et des germes dans des variétés analytiques. Nous nous sommes concentré sur le cas des arrangements de droites dans des espaces affines ou projectifs. On s'est plus particulièrement intéressé à comprendre comment la combinatoire d'un arrangement détermine les relations entre les champs de vecteurs logarithmiques associés: ce problème est connu sous le nom de conjecture de Terao. Nous étudions le module des champs de vecteurs logarithmiques d'un arrangement de droites affin en utilisant la filtration induite par le degré des composantes polynomiales. Nous déterminons qu'il n'existent que deux types de champs de vecteurs polynomiaux qui fixent une infinité de droites. Ensuite, nous décrivons l'influence de la combinatoire de l'arrangement de droites sur le degré minimal attendu pour ce type de champs de vecteurs. Nous prouvons que la combinatoire ne détermine pas le degré minimal des champs de vecteurs logarithmiques d'un arrangement de droites affin, en présentant deux pairs de contre-exemples, chaque qu'un d'eux correspondant à une notion différente de combinatoire. Nous déterminons que la dimension des espaces de filtration suit une croissance quadratique à partir d'un certain degré, en dépendant uniquement de la combinatoire de l'arrangement. A fin d'étudier de façon calculatoire une telle filtration, nous développons une librairie de fonctions sur le software de calcul formel Sage
The first part concerns a problem of number theory, for which we develop a geometrical approach based on tools coming from algebraic geometry and combinatorial geometry. Introduced by M. Kontsevich and D. Zagier in 2001, periods are complex numbers expressed as values of integrals of a special form, where both the domain and the integrand are expressed using polynomials with rational coefficients. The Kontsevich-Zagier period conjecture affirms that any polynomial relation between periods can be obtained by linear relations between their integral representations, expressed by classical rules of integral calculus. Using resolution of singularities, we introduce a semi-canonical reduction for periods focusing on give constructible and algorithmic methods respecting the classical rules of integral transformations: we prove that any non-zero real period, represented by an integral, can be expressed up to sign as the volume of a compact semi-algebraic set. The semi-canonical reduction permit a reformulation of the Kontsevich-Zagier conjecture in terms of volume-preserving change of variables between compact semi-algebraic sets. Via triangulations and methods of PL–geometry, we study the obstructions of this approach as a generalization of the Third Hilbert Problem. We complete the works of J. Wan to develop a degree theory for periods based on the minimality of the ambient space needed to obtain such a compact reduction, this gives a first geometric notion of transcendence of periods. We extend this study introducing notions of geometric and arithmetic complexities for periods based in the minimal polynomial complexity among the semi-canonical reductions of a period. The second part deals with the understanding of particular objects coming from algebraic geometry with a strong background in combinatorial geometry, for which we develop a dynamical approach. The logarithmic vector fields are an algebraic-analytic tool used to study sub-varieties and germs of analytic manifolds. We are concerned with the case of line arrangements in the affine or projective space. One is interested to study how the combinatorial data of the arrangement determines relations between its associated logarithmic vector fields: this problem is known as the Terao conjecture. We study the module of logarithmic vector fields of an affine line arrangement by the filtration induced by the degree of the polynomial components. We determine that there exist only two types of non-trivial polynomial vector fields fixing an infinitely many lines. Then, we describe the influence of the combinatorics of the arrangement on the expected minimal degree for these kind of vector fields. We prove that the combinatorics do not determine the minimal degree of the logarithmic vector fields of an affine line arrangement, giving two pair of counter-examples, each pair corresponding to a different notion of combinatorics. We determine that the dimension of the filtered spaces follows a quadratic growth from a certain degree, depending only on the combinatorics of the arrangements. We illustrate these formula by computations over some examples. In order to study computationally these filtration, we develop a library of functions in the mathematical software Sage

Cette thèse porte sur la commande H∞ par loop-shaping pour les systèmes linéaires à temps invariant d'ordre faible avec ou sans retard et dépendant de paramètres inconnus. L'objectif est d'obtenir des correcteurs H∞ paramétriques, c'est-à-dire dépendant explicitement des paramètres inconnus, pour application à des viseurs gyrostabilisés.L'existence de ces paramètres inconnus ne permet plus l'utilisation des techniques numériques classiques pour la résolution du problème H∞ par loop-shaping. Nous avons alors développé une nouvelle méthodologie permettant de traiter les systèmes linéaires de dimension finie grâce à l'utilissation de techniques modernes de calcul formel dédiées à la résolution des systèmes polynomiaux (bases de Gröbner, variétés discriminantes, etc.).Une telle approche présente de multiples avantages: étude de sensibilités du critère H∞ par rapport aux paramètres, identification de valeurs de paramètres singulières ou remarquables, conception de correcteurs explicites optimaux/robustes, certification numérique des calculs, etc. De plus, nous montrons que cette approche peut s'étendre à une classe de systèmes à retard.Plus généralement, cette thèse s'appuie sur une étude symbolique des équations de Riccati algébriques. Les méthodologies génériques développées ici peuvent s'étendre à de nombreux problèmes de l'automatique, notamment la commande LQG, le filtrage de Kalman ou invariant
This PhD thesis deals with the H∞ loop-shaping design for low order linear time invariant systems depending on unknown parameters. The objective of the PhD thesis is to obtain parametric H∞ controllers, i.e. controllers which depend explicitly on the unknown model parameters, and to apply them to the stabilization of gyrostabilized sights.Due to the unknown parameters, no numerical algorithm can solve the robust control problem. Using modern symbolic techniques dedicated to the solving of polynomial systems (Gröbner bases, discriminant varieties, etc.), we develop a new methodology to solve this problem for finite-dimensional linear systems.This approach shows several advantages : we can study the sensibilities of the H∞ criterion to the parameter variations, identify singular or remarquable values of the parameters, compute controllers which depend explicitly on the parameters, certify the numerical computations, etc. Furthermore, we show that this approach can be extended to a class of linear time-delay systems.More generally, this PhD thesis develops an algebraic approach for the study of algebraic Riccati equations. Thus, the methodology obtained can be extended to many different problems such as LQG control and Kalman or invariant filtering

The Mukhin-Tarasov-Varchenko Theorem (previously the Shapiro Conjecture) asserts that a Schubert problem has all solutions distinct and real if the Schubert varieties involved osculate a rational normal curve at real points. When conjectured, it sparked interest in real osculating Schubert calculus, and computations played a large role in developing the surrounding theory. Our purpose is to uncover generalizations of the Mukhin-Tarasov-Varchenko Theorem, proving them when possible. We also improve the state of the art of computationally solving Schubert problems, allowing us to more effectively study ill-understood phenomena in Schubert calculus. We use supercomputers to methodically solve real osculating instances of Schubert problems. By studying over 300 million instances of over 700 Schubert problems, we amass data significant enough to reveal generalizations of the Mukhin-Tarasov- Varchenko Theorem and compelling enough to support our conjectures. Combining algebraic geometry and combinatorics, we prove some of these conjectures. To improve the efficiency of solving Schubert problems, we reformulate an instance of a Schubert problem as the solution set to a square system of equations in a higher- dimensional space. During our investigation, we found the number of real solutions to an instance of a symmetrically defined Schubert problem is congruent modulo four to the number of complex solutions. We proved this congruence, giving a generalization of the Mukhin-Tarasov-Varchenko Theorem and a new invariant in enumerative real algebraic geometry. We also discovered a family of Schubert problems whose number of real solutions to a real osculating instance has a lower bound depending only on the number of defining flags with real osculation points. We conclude that our method of computational investigation is effective for uncovering phenomena in enumerative real algebraic geometry. Furthermore, we point out that our square formulation for instances of Schubert problems may facilitate future experimentation by allowing one to solve instances using certifiable numerical methods in lieu of more computationally complex symbolic methods. Additionally, the methods we use for proving the congruence modulo four and for producing an

The major part of this thesis revolves around the real algebraic geometry of curves, especially curves of degree six. We use the topological and rigid isotopy classifications of plane sextics to explore the reality of several features associated to each class, such as the bitangents, inflection points, and tensor eigenvectors. We also study the real tensor rank of plane sextics, the construction of quartic surfaces with prescribed topology, and the avoidance locus, which is the locus of all real lines that do not meet a given plane curve. In the case of space sextics, a classical construction relates an important family of these genus 4 curves to the del Pezzo surfaces of degree one. We show that this construction simplifies several problems related to space sextics over the field of real numbers. In particular, we find an example of a space sextic with 120 totally real tritangent planes, which answers a historical problem originating from Arnold Emch in 1928. The last part of this thesis is an algebraic study of a real optimization problem known as Weber problem. We give an explanation and a partial proof for a conjecture on the algebraic degree of the Fermat-Weber point over the field of rational numbers.

Tropical geometry is an area of mathematics that interfaces algebraic geometry and combinatorics. The main object of study in tropical geometry is the tropical variety, which is the combinatorial counterpart of a classical variety. A classical variety is converted into a tropical variety by a process called tropicalization, thus reducing the problems of algebraic geometry to problems of combinatorics. This new tropical variety encodes several useful information about the original variety, for example an algebraic variety and its tropical counterpart have the same dimension. In this thesis, we look at the some of the computational aspects of tropical algebraic geometry. We study a generalization of Grobner basis theory of modules which unlike the standard Grobner basis also takes the valuation of coefficients into account. This was rst introduced in (Maclagan & Sturmfels, 2009) in the settings of polynomial rings and its computational aspects were first studied in (Chan & Maclagan, 2013) for the polynomial ring case. The motivation for this comes from tropical geometry as it can be used to compute tropicalization of varieties. We further generalize this to the case of modules. But apart from that it has many other computational advantages. For example, in the standard case the size of the initial submodule generally grows with the increase in degree of the generators. But in this case, we give an example of a family of submodules where the size of the initial submodule remains constant. We also develop an algorithm for computation of Grobner basis of submodules of modules over Z=p`Z[x1; : : : ; xn] that works for any weight vector. We also look at some of the important applications of this new theory. We show how this can be useful in efficiently solving the submodule membership problem. We also study the computation of Hilbert polynomials, syzygies and free resolutions.

Studying properties of random polynomials has marked a shift in algebraic geometry. Instead of worst-case analysis, which often leads to overly pessimistic perspectives, randomness helps perform average-case analysis, and thus obtain a more realistic view. Also, via Erdos' astonishing 'probabilistic method', one can potentially obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness.

In this thesis, we study topological questions in real algebraic geometry, o-minimal geometry and random algebraic geometry, with motivation from incidence combinatorics. Specifically, we prove results along two different threads:

1. Topology of semi-algebraic and definable (over any o-minimal structure over R) sets, in both deterministic and random settings.

2. Topology of random hypersurface arrangements. In this case, we also prove a result that could be of independent interest in random graph theory.

Towards the first thread, motivated by applications in o-minimal incidence combinatorics, we prove bounds (both deterministic and random) on the topological complexity (as measured by the Betti numbers) of general definable hypersurfaces restricted to algebraic sets. Given any sequence of hypersurfaces, we show that there exists a definable hypersurface G, and a sequence of polynomials, such that each manifold in the sequence of hypersurfaces appears as a component of G restricted to the zero set of some polynomial in the sequence of polynomials. This shows that the topology of the intersection of a definable hypersurface and an algebraic set can be made arbitrarily pathological. On the other hand, we show that for random polynomials, the Betti numbers of the restriction of the zero set of a random polynomial to any definable set deviates from a Bezout-type bound with bounded probability.

Progress in o-minimal incidence combinatorics has lagged behind the developments in incidence combinatorics in the algebraic case due to the absence of an o-minimal version of the Guth-Katz polynomial partitioning theorem, and the first part of our work explains why this is so difficult. However, our average result shows that if we can prove that the measure of the set of polynomials which satisfy a certain property necessary for polynomial partitioning is suitably bounded from below, by the probabilistic method, we get an o-minimal polynomial partitioning theorem. This would be a tremendous breakthrough and would enable progress on multiple fronts in model theoretic combinatorics.

Along the second thread, we have studied the average Betti numbers of random hypersurface arrangements. Specifically, we study how the average Betti numbers of a finite arrangement of random hypersurfaces grows in terms of the degrees of the polynomials in the arrangement, as well as the number of polynomials. This is proved using a random Mayer-Vietoris spectral sequence argument. We supplement this result with a better bound on the average Betti numbers when one considers an arrangement of quadrics. This question turns out to be equivalent to studying the expected number of connected components of a certain random graph model, which has not been studied before, and thus could be of independent interest. While our motivation once again was incidence combinatorics, we obtained the first bounds on the topology of arrangements of random hypersurfaces, with an unexpected bonus of a result in random graphs.

This thesis studies problems in computational topology through the lens of semi-algebraic geometry. We first give an algorithm for computing a semi-algebraic basis for the first homology group, H1(S,F), with coefficients in a field F, of any given semi-algebraic set S⊂Rk defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (sd)^kO(1).This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. We then turn our attention to the Reeb graph, a tool from Morse theory which has recently found use in applied topology due to its ability to track the changes in connectivity of level sets of a function. The roadmap of a set, a construction that arises in semi-algebraic geometry, is a one-dimensional set that encodes information about the connected components of a set. In this thesis, we show that the Reeb graph and, more generally, the Reeb space, of a semi-algebraic set is homeomorphic to a semi-algebraic set, which opens up the algorithmic problem of computing a semi-algebraic description of the Reeb graph. We present an algorithm with singly-exponential complexity that realizes the Reeb graph of a function f:X→Y as a semi-algebraic quotient using the roadmap of X with respect to f.

This thesis presents the development towards a system that can capture and quantify motion for applications in biomechanical and medical fields demanding precision motion tracking using the lighthouse technology. Commercially known as SteamVR tracking, the lighthouse technology is a motion tracking system developed for virtual reality applications that makes use of patterned infrared light sources to highlight trackers (objects embedded with photodiodes) to obtain their pose or spatial position and orientation. Current motion capture systems such as the camera-based motion capture are expensive and not readily available outside of research labs. This thesis provides a case for low-cost motion capture systems. The technology is applied to quantify motion to draw inferences about biomechanics capture and analysis, quantification of gait, and prosthetic alignment. Possible shortcomings for data acquisition using this system for the stated applications have been addressed. The repeatability of the system has been established by determining the standard deviation error for multiple trials based on a motion trajectory using a seven degree-of-freedom robot arm. The accuracy testing for the system is based on cross-validation between the lighthouse technology data and transformations derived using joint angles by developing a forward kinematics model for the robot’s end-effector pose. The underlying principle for motion capture using this system is that multiple trackers placed on limb segments allow to record the position and orientation of the segments in relation to a set global frame. Joint angles between the segments can then be calculated from the recorded positions and orientations of each tracker using inverse kinematics. In this work, inverse kinematics for rigid bodies was based on calculating homogeneous transforms to the individual trackers in the model’s reference frame to find the respective Euler angles as well as using the analytical approach to solve for joint variables in terms of known geometric parameters. This work was carried out on a phantom prosthetic limb. A custom application-specific motion tracker was also developed using a hardware development kit which would be further optimized for subsequent studies involving biomechanics motion capture.