The purpose of this paper is to present two proofs of Helly's Theorem and to use it in the proofs of several theorems classified in a group called Helly-type theorems.

The invariant theory of finite reflection groups has rich connections to geometry, topology, representation theory, and combinatorics. We consider finite reflection groups acting on vector spaces over fields of arbitrary characteristic, where many arguments of classical invariant theory break down. When the characteristic of the underlying field is positive, reflections may be nondiagonalizable. A group containing these so-called transvections has order which is divisible by the characteristic of the underlying field, so is in the modular setting. In this thesis, we examine the action on differential derivations, which include products of differential forms and derivations, and identify the structure of the set of invariants under the action of groups fixing a single hyperplane, groups with maximal transvection root spaces acting on vector spaces over prime fields, as well as special linear groups and general linear groups over finite fields.

The results from this dissertation are a computation of ultrapowers by supercompactness measures and concepts related to such measures. The second chapter gives an overview of the basic ideas required to carry out the computations. Included are preliminary ideas connected to measures, and the supercompactness measures. Order type results are also considered in this chapter. In chapter III we give an alternate characterization of 2 using the notion of iterated ordinal measures. Basic facts related to this characterization are also considered here. The remaining chapters are devoted to finding bounds fwith arguments taking place both inside and outside the ultrapowers. Conditions related to the upper bound are given in chapter VI.

The purpose of this thesis is to construct the homology groups of a complex over an R-module. The thesis begins with hyperplanes in Euclidean n-space. Simplexes and complexes are defined, and orientations are given to each simplex of a complex. The chains of a complex are defined, and each chain is assigned a boundary. The function which assigns to each chain a boundary defines the set of r-dimensional cycles and the set of r—dimensional bounding cycles. The quotient of those two submodules is the r-dimensional homology group.

Made available in DSpace on 2016-06-02T20:06:03Z (GMT). No. of bitstreams: 1 2717.pdf: 1036198 bytes, checksum: 1ebaa6889e2e06b8855d55db6f41cfc0 (MD5) Previous issue date: 2009-11-27 / Financiadora de Estudos e Projetos / In this work we present a bayesian approach for the survival model with cure rate in the presence of covariates. In this perspective, the modelling is a direct extension of the long-term model of (Chen et al., 1999). This model is considered flexible in the sense that the effects of the covariates are measured locally using the bayesian partition model developed by Holmes et al. (1999). The bayesian partition model is a generic approach to problems of classification and regression where the space of covariates is divided in disjoint regions defined by a structure of tessellation. The extension to modelling local maintains the structure of the proportional hazards model that it is intrinsic of the long-term model(promotion time) (Rodrigues et al., 2009a). Application of this theory appears in several areas, for example in finance, biology, engineering, economics and medicine. We present a simulation study and apply the methodology to a set of data on the clinical studies. / Neste trabalho apresentamos uma abordagem bayesiana para modelos de sobrevivência com fração de cura na presença de covariáveis. Nesta perspectiva, a modelagem é uma extensão direta do modelo de longa duração (Chen et al., 1999). Este modelo é considerado flexível no sentido de que os efeitos das covariáveis são medidos localmente, utilizando o modelo de partição bayesiana desenvolvido por Holmes et al. (1999). O modelo de partição bayesiana é uma abordagem genérica para problemas de classificação e regressão, em que o espaço das covariáveis é dividido em regiões disjuntas definidas por uma estrutura de tesselação. A extensão para modelagem local mantém a estrutura de riscos proporcionais, que é intrínseca ao modelo de longa duração (tempo de promoção) (Rodrigues et al., 2009a). Aplicações desta teoria aparecem em várias áreas, como por exemplo, em Finanças, Biologia, Engenharia, Economia e Medicina. Neste trabalho, apresentamos um estudo de simulação e aplicamos a metodologia a um conjunto de dados na área de estudos clínicos.

A range space (P, S) consists of a set P of n elements and a collection S = {S1,...,Sm} of subsets of P , referred to as ranges. A hitting set for this range space refers to a subset H of P such that every Si in S contains at least one element of H. The hitting set problem is studied for many geometric range spaces where P is a set of n points in Rd and the ranges are defined by the intersection of geometric objects with P . The algorithmic question of finding the minimum-sized hitting set for a given range space is well studied and is NP-Complete even for geometric range spaces defined by unit disks. The dual of the hitting set problem is the equally well studied set cover problem. A set cover is a sub-collection C⊆S such that every element in P is contained in at least one range in C. A classic problem which is related to the minimum set cover problem is the maximum coverage problem. In this problem, given a range space (P, S) and an integer k, we have to find k ranges from S such that the number of elements in P that are covered by these k ranges are maximized. In this thesis, we study combinatorial questions on a similar variant of hitting set problem for specific geometric range spaces where the size of the hitting set is fixed as a small constant. We study the small hitting set problem mainly for two broad classes of range spaces. We first consider the Dense range space (P, S) where P is a set of n points in Rd and S is defined by “dense” geometric objects i.e, geometric objects that contain more than a constant fraction, say �, of points from P . We fix the size of the hitting set as a small constant k and investigate bounds on the value of � such that all ranges that contain more than �n points from P are hit. Next we consider the Induced range space (P, I) where P isa setof n points in R2 and the ranges are all geometric objects that are induced(spanned) by P i.e., the ranges are defined by geometric objects that have a distinct tuple of points from P on its boundary. For Induced range spaces, we prove bounds on the maximum number of ranges that can be hit using a single point. We also prove combinatorial bounds on the size of the hitting set for various families of induced objects. Now, we describe the problems that we study in this thesis and summarize the results obtained. 1. Strong centerpoints: Here we study the small hitting set question for dense range spaces when the size of hitting set is one. This is related to a classic result in geometry called Centerpoint Theorem. A point x ∈ Rd is said to be the centerpoint of P if x is contained in all convex objects that contain more than dn points from P . Centerpoint Theorem states d+1 that a centerpoint always exists for any point set P . A centerpoint need not be an input point. A natural question to ask is the following: Does there exist a strong centerpoint? i.e., is it true that for any given point set P there exists a point p ∈ P such that p is contained in every convex object that contains more than a constant fraction, say �, of points of P ? It can be easily seen that a strong centerpoint does not exist even for geometric range spaces defined by half spaces. We study the existence and the corresponding bounds for strong centerpoints for some range spaces. In particular, we prove the existence of strong centerpoint and show tight bounds for the following range spaces. Convex polytopes defined by a fixed set of orientations : Geometric range spaces like those induced by axis-parallel boxes, skylines and downward facing equilateral triangles belong to this family of convex polytopes. Hyperplanes in Rd Range spaces with discrete intersection 2. Small Strong Epsilon Nets: This can be considered as an extension of strong centerpoints. This question is related to a well studied area called �-nets. N ⊂ P is called a (strong) �-net of P with respect to S if N ∩ S =�∅ for all objects S ∈S that contain more than �n points of P . We study the following question. Let �S∈ [0, 1] represent the smallest real number such that, for any given point set P , there exists Q ⊂ P of size i which is an �S-net with respect to S. Thus a strong centerpoint will be an �S1 -net. We prove bounds on �Si for small values of i where S is the family of axis-parallel rectangles, halfspaces and disks. 3. Strong First Selection Lemma: Here we consider the hitting question for induced range spaces when the size of the hitting set is one. In other words, given an induced range space, we prove bounds on the maximum number of ranges that can be hit using a single input point. Such questions are referred to as First Selection Lemma and are well studied. We consider the strong version of the First Selection Lemma where the “heavily covered” point is required to be an input point. We study the strong first selection lemma for induced rectangles, induced special rectangles and induced disks. We prove an exact result for the strong variant of the first selection lemma for axis-parallel rectangles. We also prove exact results for the strong variant of the first selection lemma for some subclasses of axis-parallel rectangles like orthants and slabs. We prove strong first selection lemma with almost tight bounds for skylines, another sub-class of axis-parallel rectangles. We prove bounds for first selection lemma for disks in the plane and exact results for a special case when the discs are induced by a centrally symmetric point set. 2 Hitting all Induced Objects: Here we discuss and prove combinatorial bounds on the size of the minimum hitting set for induced range spaces. We prove tight bounds on the hitting set size when induced objects are special rectangles, disks and downward facing equilateral triangles.

La géométrie symplectique et la géométrie complexe sont intimement liées, en particulier par les techniques asymptotiquement holomorphes de Donaldson et Auroux d'une part et par les travaux d’Eliashberget et Cieliebak sur la pseudoconvexité d'autre part. Les travaux présentés dans cette thèse sont motivés par ces deux liens. On donne d’abord la caractérisation symplectique suivante des constantes de Seshadri. Dans une variété complexe, la constante de Seshadri d’une classe de Kähler entière en un point est la borne supérieure des capacités de boules standard admettant, pour une certaine forme de Kähler dans cette classe, un plongement holomorphe et iso-Kähler de codimension 0 centré en ce point. Ce critère était connu de Eckl en 2014 ; on en donne une preuve différente. La deuxième partie est motivée par la question suivante de Donaldson : <<Toute sphère lagrangienne d'une variété projective complexe est-elle un cycle évanescent d'une déformation complexe vers une variété à singularité conique ?>> D'une part, on présente toute sous-variété lagrangienne close d’une variété symplectique/kählérienne close dont les périodes relatives sont entières comme lieu des minima d’une exhaustion <<convexe>> définie sur le complémentaire d'une section hyperplane symplectique/complexe. Dans le cadre kählérien, <<convexe>> signifie strictement plurisousharmonique tandis que dans le cadre symplectique, cela signifie de Lyapounov pour un champ de Liouville. D'autre part, on montre que toute sphère lagrangienne d'un domaine de Stein qui est le lieu des minima d’une fonction <<convexe>> est un cycle évanescent d'une déformation complexe sur le disque vers un domaine à singularité conique. / Symplectic geometry and complex geometry are closely related, in particular by Donaldson and Auroux’s asymptotically holomorphic techniques and by Eliashberg and Cieliebak’s work on pseudoconvexity. The work presented in this thesis is motivated by these two connections. We first give the following symplectic characterisation of Seshadri constants. In a complex manifold, the Seshadri constant of an integral Kähler class at a point is the upper bound on the capacities of standard balls admitting, for some Kähler form in this class, a codimension 0 holomorphic and iso-Kähler embedding centered at this point. This criterion was known by Eckl in 2014; we give a different proof of it. The second part is motivated by Donaldon’s following question: ‘Is every Lagrangian sphere of a complex projective manifold a vanishing cycle of a complex deformation to a variety with a conical singularity?’ On the one hand, we present every closed Lagrangian submanifold of a closed symplectic/Kähler manifold whose relative periods are integers as the lowest level set of a ‘convex’ exhaustion defined on the complement of a symplectic/complex hyperplane section. In the Kähler setting ‘complex’ means strictly plurisubharmonic while in the symplectic setting it refers to the existence of a Liouville pseudogradient. On the other hand, we prove that any Lagrangian sphere of a Stein domain which is the lowest level-set of a ‘convex’ function is a vanishing cycle of some complex deformation over the disc to a variety with a conical singularity.

The thesis unifies the most important author's results in the field of algorithms concerning zonotopes and their applications in optimization and statistics. The computational-geometric results consist of a new compact output-sensitive algorithm for enumerating vertices of a zonotope, which outperforms the rival algorithm with the same complexity-theoretic properties both theoretically and empirically, and a polynomial algorithm for arbitrarily precise approximation of a zonotope with the Löwner-John ellipsoid. In the application area, the thesis presents a result, which connects linear regression model with interval outputs with the zonotope matters. The usage of presented geometric algorithms for solving a nonconvex optimisation problem is also discussed.

Scientific applications that operate on large data sets require huge amount of computation power and memory. These applications are typically run on High Performance Computing (HPC) systems that consist of multiple compute nodes, connected over an network interconnect such as InfiniBand. Each compute node has its own memory and does not share the address space with other nodes. A significant amount of work has been done in past two decades on parallelizing for distributed-memory architectures. A majority of this work was done in developing compiler technologies such as high performance Fortran (HPF) and partitioned global address space (PGAS). However, several steps involved in achieving good performance remained manual. Hence, the approach currently used to obtain the best performance is to rely on highly tuned libraries such as ScaLAPACK. The objective of this work is to improve automatic compiler and runtime support for distributed-memory clusters for regular programs. Regular programs typically use arrays as their main data structure and array accesses are affine functions of outer loop indices and program parameters. A lot of scientific applications such as linear-algebra kernels, stencils, partial differential equation solvers, data-mining applications and dynamic programming codes fall in this category. In this work, we propose techniques for finding computation mapping and data allocation when compiling regular programs for distributed-memory clusters. Techniques for transformation and detection of parallelism, relying on the polyhedral framework already exist. We propose automatic techniques to determine computation placements for identified parallelism and allocation of data. We model the problem of finding good computation placement as a graph partitioning problem with the constraints to minimize both communication volume and load imbalance for entire program. We show that our approach for computation mapping is more effective than those that can be developed using vendor-supplied libraries. Our approach for data allocation is driven by tiling of data spaces along with a compiler assisted runtime scheme to allocate and deallocate tiles on-demand and reuse them. Experimental results on some sequences of BLAS calls demonstrate a mean speedup of 1.82× over versions written with ScaLAPACK. Besides enabling weak scaling for distributed memory, data tiling also improves locality for shared-memory parallelization. Experimental results on a 32-core shared-memory SMP system shows a mean speedup of 2.67× over code that is not data tiled.

Stencil computations are iterative kernels often used to simulate the change in a discretized spatial domain overtime (e.g., computational fluid dynamics) or to solve for unknowns in a discretized space by converging to a steady state (i.e., partial differential equations).They are commonly found in many scientific and engineering applications. Most stencil computations allow tile-wise concurrent start ,i.e., there exists a face of the iteration space and a set of tiling hyper planes such that all tiles along that face can be started concurrently. This provides load balance and maximizes parallelism. Loop tiling is a key transformation used to exploit both data locality and parallelism from stencils simultaneously. Numerous works exist that target improving locality, controlling frequency of synchronization, and volume of communication wherever applicable. But, concurrent start-up of tiles that evidently translates into perfect load balance and often reduction in frequency of synchronization is completely ignored. Existing automatic tiling frameworks often choose hyperplanes that lead to pipelined start-up and load imbalance. We address this issue with a new tiling technique that ensures concurrent start-up as well as perfect load balance whenever possible. We first provide necessary and sufficient conditions on tiling hyperplanes to enable concurrent start for programs with affine data accesses. We then discuss an iterative approach to find such hyperplanes. It is not possible to directly apply automatic tiling techniques to periodic stencils because of the wrap-around dependences in them. To overcome this, we use iteration space folding techniques as a pre-processing stage after which our technique can be applied without any further change. We have implemented our techniques on top of Pluto-a source-level automatic parallelizer. Experimental evaluation on a 12-core Intel Westmere shows that our code is able to outperform a tuned domain-specific stencil code generator by 4% to2 x, and previous compiler techniques by a factor of 1.5x to 15x. For the swim benchmark from SPECFP2000, we achieve an .improvement of 5.12 x on a 12-core Intel Westmere and 2.5x on a 16-core AMD Magny-Cours machines, over the auto-parallelizer of Intel C Compiler.