No description available.

In many digital signal processing applications, we often need some special function units that can compute complicated arithmetic functions such as reciprocal, square-root, base-2 logarithm, power of 2, trigonometric functions, etc. The most popular design approaches to compute these single-value functions are based on look-up tables (LUT) with interpolation. In general, there are two different types of LUT-based method: piecewise and multipartite. As the required bit accuracy increases, the size of LUT increases exponentially. In this thesis, we will develop a generator that can automatically synthesize suitable hardware to compute these special arithmetic functions given the required bit accuracy. In particular, higher-order piecewise method will be supported to reduce the table size for high-accuracy applications. The synthesized arithmetic units are used in the design of a vertex shader for 3D graphics application.

The notion of asymptotic structure of an infinite dimensional Banach space was introduced by Maurey, Milman and Tomczak-Jaegermann. The asymptotic structure consists of those finite dimensional spaces which can be found everywhere `at infinity'. These are defined as the spaces for which there is a winning strategy in a certain vector game. The above authors introduced the class of asymptotic $\ell_p$ spaces, which are the spaces having simplest possible asymptotic structure. Key examples of such spaces are Tsirelson's space and James' space. We prove some new properties of general asymptotic $\ell_p$ spaces and also compare the notion of asymptotic $\ell_2$ with other notions of asymptotic Hilbert space behaviour such as weak Hilbert and asymptotically Hilbertian. We study some properties of smooth functions defined on subsets of asymptotic $\ell_\infty$ spaces. Using these results we show that that an asymptotic $\ell_\infty$ space which has a suitably smooth norm is isomorphically polyhedral, and therefore admits an equivalent analytic norm. We give a sufficient condition for a generalized Orlicz space to be a stabilized asymptotic $\ell_\infty$ space, and hence obtain some new examples of asymptotic $\ell_\infty$ spaces. We also show that every generalized Orlicz space which is stabilized asymptotic $\ell_\infty$ is isomorphically polyhedral. In 1991 Gowers and Maurey constructed the first example of a space which did not contain an unconditional basic sequence. In fact their example had a stronger property, namely that it was hereditarily indecomposable. The space they constructed was `$\ell_1$-like' in the sense that for any $n$ successive vectors $x_1 < \ldots < x_n$, $\frac{1}{f(n)} \sum_{i=1}^n \| x_i \| \leq \| \sum_{i=1}^n x_i \| \leq \sum_{i=1}^n \| x_i \|,$ where $ f(n) = \log_2 (n+1) $. We present an adaptation of this construction to obtain, for each $ p \in (1, \infty)$, an hereditarily indecomposable Banach space, which is `$\ell_p$-like' in the sense described above. We give some sufficient conditions on the set of types, $\mathscr{T}(X)$, for a Banach space $X$ to contain almost isometric copies of $\ell_p$ (for some $p \in [1, \infty)$) or of $c_0$. These conditions involve compactness of certain subsets of $\mathscr{T}(X)$ in the strong topology. The proof of these results relies heavily on spreading model techniques. We give two examples of classes of spaces which satisfy these conditions. The first class of examples were introduced by Kalton, and have a structural property known as Property (M). The second class of examples are certain generalized Tsirelson spaces. We introduce the class of stopping time Banach spaces which generalize a space introduced by Rosenthal and first studied by Bang and Odell. We look at subspaces of these spaces which are generated by sequences of independent random variables and we show that they are isomorphic to (generalized) Orlicz spaces. We deduce also that every Orlicz space, $h_\phi$, embeds isomorphically in the stopping time Banach space of Rosenthal. We show also, by using a suitable independence condition, that stopping time Banach spaces also contain subspaces isomorphic to mixtures of Orlicz spaces.

This thesis aims to resolve some open questions about sonic boom, and particularly secondary sonic boom, which arises from long-range propagation in a non-uniform atmosphere. We begin with an introduction to sonic boom modelling and outline the current state of research. We then proceed to review standard results of gas dynamics and we prove a new theorem, similar to Kelvin's circulation theorem, but valid in the presence of shocks. We then present the definitions used in sonic boom theory, in the framework of linear acoustics for stationary and for moving non-uniform media. We present the wavefront patterns and ray patterns for a series of analytical examples for propagation from steadily moving supersonic point sources in stratified media. These examples elucidate many aspects of the long-range propagation of sound and in particular of secondary sonic boom. The formation of `fold caustics' of boomrays is a key feature. The focusing of linear waves and weak shock waves is compared. Next, in order to address the consistent approximation of sonic boom amplitudes, we consider steady motion of supersonic thin aerofoils and slender axisymmetric bodies in a uniform medium, and we use the method of matched asymptotic expansions (MAE) to give a consistent derivation of Whitham's model for nonlinear effects in primary boom analysis. Since for secondary boom, as for primary, the inclusion of nonlinearities is essential for a correct estimation of the amplitudes, we then study the paradigm problem of a thin aerofoil moving steadily in a weakly stratified medium with a horizontal wind. We again use MAE to calculate approximations of the Euler equations; this results in an inhomogeneous kinematic wave equation. Returning to the linear acoustics framework, for a point source that accelerates and decelerates through the sound speed in a uniform medium we calculate the wavefield in the `time-domain'. Certain other motions of interest are also illustrated. In the accelerating and in the manoeuvring motions fold caustics that are essentially the same as those from steady motions in stratified atmospheres again arise. We also manage to pinpoint a scenario where a `cusp caustic' of boomrays forms instead. For the accelerating motions the asymptotic analysis of the wavefield reveals the formation of singularities which are incompatible with linear theory; this suggests the re-introduction of nonlinear effects. However, it is a formidable task to solve such a nonlinear problem in two or three dimensions, so we solve a related one-dimensional problem instead. Its solution possesses an unexpectedly rich structure that changes as the strength of nonlinearity varies. In all cases however we find that the singularities of the linear problem are regularised by the nonlinearity.

Delay differential equations (DDEs) are often used to model systems with time-delayed effects, and they have found applications in fields such as climate dynamics, biosciences, engineering, and control theory. In contrast to ordinary differential equations (ODEs), the phase space associated even with a scalar DDE is infinite-dimensional. Oftentimes, it is desirable to have low-dimensional ODE systems that capture qualitative features as well as approximate certain quantitative aspects of the DDE dynamics. In this thesis, we present a Galerkin scheme for a broad class of DDEs and derive convergence results for this scheme. In contrast to other Galerkin schemes devised in the DDE literature, the main new ingredient here is the use of the so called Koornwinder polynomials, which are orthogonal polynomials under an inner product with a point mass. A main advantage of using such polynomials is that they live in the domain of the underlying linear operator, which arguably simplifies the related numerical treatments. The obtained results generalize a previous work to the case of DDEs with multiply delays in the linear terms, either discrete or distributed, or both. We also consider the more challenging case of discrete delays in the nonlinearity and obtain a convergence result by assuming additional assumptions about the Galerkin approximations of the linearized systems. / Master of Science

Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous déterminons le temps moyen de sortie vers le haut de la marche. / This thesis deals with several problems in probability, mostly motivated by theoretical computer science. In the first part, we study of a probabilistic algorithm that counts the number of different words in a given sequence, by boiling it down to a statistical problem. We show that slightly improved, it achieves an optimal bound. The second and main part is devoted to different asymptotic problems concerning finite particle systems, for which we consider different kinds of infinite limits. We first deal with cellular automata. In dimension one, it appears random walks for which we entirely describe the asymptotic behaviors. In dimension two, on a square grid, we study some caracteristic rules for which we estimate the converge time. Lastly, we study a family of urn models. The third part focuses on two random walks problems. These questions where motivated by the study of cellular automata, but presented here in a self-contained way. The first problem is the study of a family of self-reflected random walks on a circle, for which we show a ``brownian limit''. The latter is a combinatorial description of a family of biased random walks on an interval.

In the work we estimate the rate of convergence of the Wong-Zakai type of approximations for SDEs and SPDEs. Two cases are studied: SDEs in finite dimensional settings and evolution stochastic systems (SDEs in the infinite dimensional case). The latter result is applied to the second order SPDEs of parabolic type and the filtering problem. Roughly, the result is the following. Let Wn be a sequence of continuous stochastic processes of finite variation on an interval [0, T]. Assume that for some a > 0 the processes Wn converge almost surely in the supremum norm in [0, T] to W with the rate n-k for each k < a. Then the solutions Un of the differential equations with Wn converge almost surely in the supremum norm in [0, T] to the solution u of the "Stratonovich" SDE with W with the same rate of convergence, n-k for each k < a, in the case of SDEs and with the rate of convergence n-k/2 for each k < a, in the case of evolution systems and SPDEs. In the final chapter we verify that the two most common approximations of the Wiener process, smoothing and polygonal approximation, satisfy the assumptions made in the previous chapters.

This thesis aims to model the uniaxial deformation of a class of materials consisting of microscopic spherical shells embedded in a rubber matrix. These shells are assumed to buckle as the stress on the material increases. To motivate the analysis we consider the paradigm problem of the debonding of a distribution of cylindrical inclusions in an elastic material undergoing antiplane shear, with bonded and debonded inclusions playing the role of unbuckled and buckled shells respectively. We begin the modelling of the microsphere-containing material by considering the buckling of an isolated embedded shell inclusion with a uniaxial stress field at infinity, using Koiter's theory of shallow shells. The resulting energy functional is solved as an eigenvalue problem by the Rayleigh-Ritz method. Subsequently, we analyse the buckling criterion asymptotically in the limit as the thickness ratio tends to zero by analogy with the WKB analysis of a beam on a variable-stiffness substrate. To model the shell after buckling we consider the simplified case of an embedded shell with a crack around its equator. The system is solved by expressing the displacements in the shell and matrix as series of Love stress functions, with the resulting infinite system of equations solved numerically with the aid of a convergence acceleration method. Finally we consider a composite material consisting of a homogenised dilute distribution of buckled and unbuckled shells, with the proportion of each type of shell dependent on the stress applied to the material, according to an asymptotic formula relating the size of the inclusions and the critical buckling stress that was obtained previously.

Consider n players whose "scores" are independent and identically distributed values {Xi}i=1n from some discrete distribution F. We pay special attention to the cases where (i) F is geometric with parameter p{combining right arrow above}0 and (ii) F is uniform on {1,2,. . . ,N}; the latter case clearly corresponds to the classical occupancy problem. The quantities of interest to us are, first, the U-statistic W which counts the number of "ties" between pairs i, j; second, the univariate statistic Yr, which counts the number of strict r-way ties between contestants, i.e., episodes of the form Xi1=Xi2=. . .=Xir; Xj≠Xi1;j≠i1,i2,. . . ,ir; and, last but not least, the multivariate vector ZAB=(YA, YA+1,. . . ,YB). We provide Poisson approximations for the distributions of W, Yr and ZAB under some general conditions. New results on the joint distribution of cell counts in the occupancy problem are derived as a corollary.

In this thesis, we present three projects. First, we investigate the numerical approximation of Hamilton-Jacobi equations with the Caputo time-fractional derivative. We introduce an explicit in time discretization of the Caputo derivative and a finite-difference scheme for the approximation of the Hamiltonian. We show that the approximation scheme so obtained is stable under an appropriate condition on the discretization parameters and converges to the unique viscosity solution of the Hamilton-Jacobi equation. Also, we study the numerical approximation of a system of PDEs which arises from an optimal control problem for the time-fractional Fokker-Planck equation with time-dependent drift. The system is composed of a backward time-fractional Hamilton-Jacobi-Bellman equation and a forward time-fractional Fokker-Planck equation. We approximate Caputo derivatives in the system by means of L1 schemes and the Hamiltonian by finite differences. The scheme for the Fokker-Planck equation is constructed in such a way that the duality structure of the PDE system is preserved on the discrete level. We prove the well-posedness of the scheme and the convergence to the solution of the continuous problem. Finally, we study a particle approximation for one-dimensional first-order Mean-Field-Games with local interactions with planning conditions. Our problem comprises a system of a Hamilton-Jacobi equation coupled with a transport equation. As we are dealing with the planning problem, we prescribe initial and terminal distributions for the transport equation. The particle approximation builds on a semi-discrete variational problem. First, we address the existence and uniqueness of the semi-discrete variational problem. Next, we show that our discretization preserves some conserved quantities. Finally, we prove that the approximation by particle systems preserves displacement convexity. We use this last property to establish uniform estimates for the discrete problem. All results for the discrete problem are illustrated with numerical examples.