Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once. This thesis is concerned with the bounds on the size and with the construction of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant. Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1. Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions. Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most once in any N×t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to optimal PARLs with w=3.

Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once. This thesis is concerned with the bounds on the size and with the construction of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant. Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1. Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions. Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most once in any N×t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to optimal PARLs with w=3.

Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once. This thesis is concerned with the bounds on the size and with the construction of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant. Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1. Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions. Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most once in any N×t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to optimal PARLs with w=3.

Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once. This thesis is concerned with the bounds on the size and with the construction of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant. Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1. Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions. Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most once in any N×t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to optimal PARLs with w=3.

Let k be a perfect field of characteristic p > 2 and K a totally ramified extension of K₀ = Frac W(k) with uniformizer π. Let F ⊆ K be a subfield with ϖ, ring of integers O, and residue field k(F) ⊆ k with |k(F)| = q. Let W(F) = O⊗(W(k(F))) W(k) and consider the ring 𝔖 = W(F)⟦u⟧ with an endomorphism φ that lifts the q-power Frobenius of k on W(F) and satisfies φ(u) ≡ u^q mod ϖ and φ(u) ≡ 0 mod u. In this dissertation, we use O-divided powers to define the analogue of Breuil-Kisin modules over the rings 𝔖 and S, where S is an O-divided power envelope of the surjection 𝔖 ↠ O(K) sending u to π. We prove that these two module categories are equivalent, generalizing the case when F = Q(p) and ϖ - p. As an application of our theory, we generalize the results of Kisin [17] and Cais-Lau [8] to relate the Faltings Dieudonné crystal of a ϖ-divisible O-module, which gives a Breuil module over S in our sense, to the modules of Kisin-Ren, providing a geometric interpretation to the latter.

High performance parallel and distributed computing systems are used to solve large, complex, and data parallel scientific applications that require enormous computational power. Data parallel workloads which require performing similar operations on different data objects, are present in a large number of scientific applications, such as N-body simulations and Monte Carlo simulations, and are expressed in the form of loops. Data parallel workloads that lack precedence constraints are called arbitrarily divisible workloads, and are amenable to easy parallelization. Load imbalance that arise from various sources such as application, algorithmic, and systemic characteristics during the execution of scientific applications degrades performance. Scheduling of arbitrarily divisible workloads to address load imbalance in order to obtain better utilization of computing resources is a major area of research. Divisible load theory (DLT) and dynamic loop scheduling (DLS) algorithms are two algorithmic approaches employed in the scheduling of arbitrarily divisible workloads. Despite sharing the same goal of achieving load balancing, the two approaches are fundamentally different. Divisible load theory algorithms are linear, deterministic and platform dependent, whereas dynamic loop scheduling algorithms are probabilistic and platform agnostic. Divisible load theory algorithms have been traditionally used for performance prediction in environments characterized by known or expected variation in the system characteristics at runtime. Dynamic loop scheduling algorithms are designed to simultaneously address all the sources of load imbalance that stochastically arise at runtime from application, algorithmic, and systemic characteristics. In this dissertation, an analysis and performance evaluation of DLT and DLS algorithms are presented in the form of a scalability study and a robustness investigation. The effect of network topology on their performance is studied. A hybrid scheduling approach is also proposed that integrates DLT and DLS algorithms. The hybrid approach combines the strength of DLT and DLS algorithms and improves the performance of the scientific applications running in large scale parallel and distributed computing environments, and delivers performance superior to that which can be obtained by applying DLT algorithms in isolation. The range of conditions for which the hybrid approach is useful is also identified and discussed.

Soit \M un espace de modules de groupes p-divisibles introduit par Rapoport et Zink. Supposons que cet espace \M soit non-ramifié de type EL ou PEL unitaire ou symplectique. Soit \Mrig la fibre générique de Berthelot de \M. C'est un espace rigide analytique au-dessus duquel il existe une tour de revêtements étales finis (\M_K)_K qui classifient les structures de niveau. On définit un morphisme déterminant \det_K de la tour (\M_K)_K vers une tour d'espaces rigides analytiques étales de dimension 0 associée au cocentre du groupe réductif relié à cet espace. C'est un analogue local en des places non-archimédiennes du morphisme déterminant pour les variétés de Shimura défini par Deligne. Comme pour les variétés de Shimura, on montre que les fibres géométriques du morphisme déterminant \det_K sont les composantes connexes géométriques de \M_K. On définit aussi les morphismes puissances extérieures qui généralisent le morphisme déterminant sur la tour d'espaces rigides analytiques associée à un espace de Lubin-Tate. / Let \M be a moduli space of p-divisible groups introduced by Rapoport and Zink. Assume that \M is unramified of EL or PEL type which is unitary or symplectic. Let \Mrig be the generic fiber of Berthelot of \M. This is a rigid analytic space over which there exist a tower of finite etale coverings (\M_K)_K classifing the level structures. We define a determinant morphism \det_K from the tower (\M_K)_K to a tower of rigid analytic spaces of dimension 0 associated to the cocenter of the reductive group related to the space \M. This is a local analogue on the nonarchimedean places of the determinant morphism for Shimura varieties defined by Deligne. As for Shimura varieties, we prove that the geometric fibers of the determinant morphism \det_K are the geometrically connected components of \M_K. We define also the exterior power morphisms which generalize the determinant morphism on the tower of rigid analytic spaces associated to a Lubin-Tate space.

Cette thèse contient quatre travaux sur le modèle d'Agrégation Limitée par Diffusion Interne (iDLA), qui est un modèle de croissance pour la construction récursive d'ensembles aléatoires. Le premier travail concerne la dimension 1 et étudie le cas où les marches aléatoires formant l'agrégat évoluent dans un milieu aléatoire. L'agrégat normalisé converge alors non pas vers une forme limite déterministe comme dans le cas de marches aléatoires simples mais converge en loi vers un segment contenant l'origine dont les extrémités suivent la loi de l'Arcsinus. Dans le deuxième travail, on considère le cas où l'agrégat est formé par des marches aléatoires simples en dimension d > 1. On donne alors des résultats de convergence et de fluctuations sur la fonction odomètre introduite par Levine et Peres, qui compte en chaque point le nombre de passages des marches ayant formé l'agrégat. Dans le troisième travail, on s'intéresse au cas où l'agrégat est formé par des marches aléatoires multidimensionnelles qui ne sont pas centrées. On montre que sous une normalisation appropriée, l'agrégat converge vers une forme limite qui s'identifie à une vraie boule de chaleur. Nous répondons ainsi à une question ouverte en analyse concernant l'existence d'une telle boule bornée. Le quatrième travail concerne le cas particulier où une borne intérieure est connue pour l'agrégat. On donne alors des conditions suffisantes sur le graphe ainsi que sur la nature de cette borne pour qu'elle implique une borne extérieure. Ce résultat est appliqué au cas de marches évoluant sur un amas de percolation par arêtes surcritique, complétant ainsi un résultat de Shellef. / This thesis contains four works on the Internal Diffusion Limited Aggregation model (iDLA), which is a growth model that recursively builds random sets. The first work is set in dimension 1 and studies the case where the random walks that build the aggregate evolve in a random environment. The normalised aggregate then does not converges towards a deterministic limiting shape as it is the case for simple random walks, but converges in law towards a segment that contains the origin and which extremal points follow the Arcsine law. In the second work, we consider the case where the aggregate is built by simple random walks in dimension d > 1. We give convergence and fluctuation results on the odometer function introduced by Levine and Peres, which counts at each point the number of visits of walkers throughout the construction of the aggregate. In the third work, we examine the case where the aggregate is built using multidimensional drifted random walks. We show that under a suitable normalisation, the aggregate converges towards a limiting shape which is identified as a true heat ball. We thus give an answer to an open question in analysis concerning the existence of such a bounded shape. The last work deals with the special case where an interior bound is known for the aggregate. We give a set of conditions on the graph and on the nature of this interior bound that are sufficient to imply an outer bound. This result is applied to the case of random walks on the supercritical bond percolation cluster, thus completing a result by Shellef.

No description available.

This thesis consists of three papers, all treating various aspects of the operation partial balayage from potential theory. The first paper concerns the equilibrium measure in the setting of two dimensional weighted potential theory, an important measure arising in various mathematical areas, e.g. random matrix theory and the theory of orthogonal polynomials. In this paper we show that the equilibrium measure satisfies a complementary relation with a partial balayage measure if the weight function is of a certain type. The second paper treats the connection between partial balayage measures and measures arising from scaling limits of a generalisation of the so-called divisible sandpile model on lattices. The standard divisible sandpile can, in a natural way, be considered a discrete version of the partial balayage operation with respect to the Lebesgue measure. The generalisation that is developed in this paper is essentially a discrete version of the partial balayage operation with respect to more general measures than the Lebesgue measure. In the third paper we develop a version of partial balayage on Riemannian manifolds, using the theory of currents. Several known properties of partial balayage measures are shown to have corresponding results in the Riemannian manifold setting, one of which being the main result of the first paper. Moreover, we utilize the developed framework to show that for manifolds of dimension two, harmonic and geodesic balls are locally equivalent if and only if the manifold locally has constant curvature. / Denna avhandling består av tre artiklar som alla behandlar olika aspekter av den potentialteoretiska operationen partiell balayage. Den första artikeln betraktar jämviktsmåttet i tvådimensionell viktad potentialteori, ett viktigt mått inom flertalet matematiska inriktningar såsom slumpmatristeori och teorin om ortogonalpolynom. I denna artikel visas att jämviktsmåttet uppfyller en komplementaritetsrelation med ett partiell balayage-mått om viktfunktionen är av en viss typ. Den andra artikeln behandlar relationen mellan partiell balayage-mått och mått som uppstår från skalningsgränser av en generalisering av den så kallade "delbara sandhögen", en diskret modell för partikelaggregation på gitter. Den vanliga delbara sandhögen kan på ett naturligt sätt betraktas som en diskret version av partiell balayage-operatorn med avseende på Lebesguemåttet. Generaliseringen som utarbetas i denna artikel är väsentligen en diskret version av partiell balayage-operatorn med avseende på mer allmänna mått än Lebesguemåttet. I den tredje artikeln formuleras en version av partiell balayage på riemannska mångfalder utifrån teorin om strömmar. Åtskilliga tidigare kända egenskaper om partiella balayage-mått visas ha motsvarande formuleringar i formuleringen på riemannska mångfalder, bland annat huvudresultatet från den första artikeln. Vidare så utnyttjas det utarbetade ramverket för att visa att tvådimensionella riemannska mångfalder har egenskapen att harmoniska och geodetiska bollar lokalt är ekvivalenta om och endast om mångfalden lokalt har konstant krökning. / <p>QC 20160524</p>