[pt] Foi desenvolvido pelos grupos MPEG (Moving Picture Expert Group) e VCEG (Video Coding Expert Group) um novo padrão de codificação de vídeo denominado AVC (Advanced Vídeo Coding). Este padrão fornece uma capacidade de compressão maior de vídeo se comparado com os padrões anteriores. A estimação de movimento é a fase da codificação de vídeo que demanda maior tempo de processamento. Estimação de movimento é computacionalmente custosa para H.264/AVC se o método Full Search [1] é usado. A fim de reduzir o tempo de codificação, o software de referência JM 9.8 adota um rápido método de estimação de movimento para pixel inteiro chamado UMHexagonS e um método para pixel fracionário chamado CBFPS. Um método proposto por Xiaoquan Yi, Jun Zhang, Nam Ling e Weijia Shang [2] chamado aqui, por simplicidade, de P021 apresenta, em comparação com o software de referência JM, uma melhor e simplificada forma de estimação de movimento para aumentar a velocidade do processo de codificação e manter a qualidade visual do vídeo. Visando diminuir ainda mais o tempo de processamento e o custo computacional apresentada pelos métodos citados anteriormente, o que é necessário principalmente para aplicações de codificação de vídeo móveis, como celulares e palm tops e aplicações de tempo real, como videoconferência, este trabalho propõe um método de estimação de movimento que consiste em evitar o processamento de blocos que não se beneficiam da pesquisa de metade de pixel. Após a execução dos testes, pode-se constatar que com uma qualidade de vídeo semelhante, o método proposto reduz o tempo de processamento em 76,17%, 75,95% e 11,74% em média quando comparado com os métodos Full Search, JM 98 e P021. Além disso, este método praticamente preserva a taxa de bits, apresentando um pequeno aumento de 8,72% , 8,06% e 8,02% em média quando comparado com os mesmos métodos. Isto representa, em nossa opinião, um pequeno preço a ser pago, considerando os benefícios em termos de tempo de processamento. / [en] The MPEG (Moving Picture Experts Group) and the VCEG (Video Coding Experts Group) have developed a new video compression standard entitled AVC (Advanced Video Coding). This standard offers the capacity of video compression greater than the previous standards.The motion estimation which is a phase of the video compression is extremely computer-intensive and therefore demands most of the processing time. When Full Search [1] method is used for H.264/AVC, this process is extremely expensive. In order to reduce encoding time, the reference software JM (throughout this work, JM98 is the version used) has respectively adopted a fast motion estimation method for the integer pixel called UMHexagonS and a method for the sub- pixel called CBFPS. A method proposed by Xiaoquan Yi, Jun Zhang, Nam Ling e Weijia Shang [2] called here P021 (as referenced by the Joint Video Team) has shown, when compared to the reference software JM, a simple way of motion estimation that increases the speed of coding process while maintaining the video visual quality. In order to decrease the processing time and computational cost of these methods, which are: i) particularly needed in mobile video coding applications such as mobile phones and palmtops; ii) in real time applications such as videoconference, this work proposes a motion estimation method that eliminates the processing of blocks that does not produce benefits for the half-pixel search. The simulation results show that the proposed method reduces the processing time in 76,17%, 75,95% and 11,74% in average when respectively compared with Full Search, JM98 and P021 methods, without relevant impact in video quality. Besides, this method produces a bits rate increase of 8,72% , 8,06% e 8,02% in average when compared with the same methods. This is in our opinion, an inexpensive price to be paid when the time benefits are considered.

The transformed rejection method, a combination of the inversion and the rejection method, which is used to generate non-uniform random numbers from a variety of continuous distributions can be applied to discrete distributions as well. For the Poisson distribution a short and simple algorithm is obtained which is well suited for large values of the Poisson parameter $\mu$, even when $\mu$ may vary from call to call. The average number of uniform deviates required is lower than for any of the known uniformly fast algorithms. Timings for a C implementation show that the algorithm needs only half of the code but is - for $\mu$ not too small - at least as fast as the current state-of-the-art algorithms. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

Doctor of Philosophy / Department of Mathematics / Alexander G. Ramm / In this thesis, the author presents several numerical methods for solving scalar and electromagnetic wave scattering problems. These methods are taken from the papers of Professor Alexander Ramm and the author, see [1] and [2]. In Chapter 1, scalar wave scattering by many small particles of arbitrary shapes with impedance boundary condition is studied. The problem is solved asymptotically and numerically under the assumptions a << d << λ, where k = 2π/λ is the wave number, λ is the wave length, a is the characteristic size of the particles, and d is the smallest distance between neighboring particles. A fast algorithm for solving this wave scattering problem by billions of particles is presented. The algorithm comprises the derivation of the (ORI) linear system and makes use of Conjugate Orthogonal Conjugate Gradient method and Fast Fourier Transform. Numerical solutions of the scalar wave scattering problem with 1, 4, 7, and 10 billions of small impedance particles are achieved for the first time. In these numerical examples, the problem of creating a material with negative refraction coefficient is also described and a recipe for creating materials with a desired refraction coefficient is tested. In Chapter 2, electromagnetic (EM) wave scattering problem by one and many small perfectly conducting bodies is studied. A numerical method for solving this problem is presented. For the case of one body, the problem is solved for a body of arbitrary shape, using the corresponding boundary integral equation. For the case of many bodies, the problem is solved asymptotically under the physical assumptions a << d << λ, where a is the characteristic size of the bodies, d is the minimal distance between neighboring bodies, λ = 2π/k is the wave length and k is the wave number. Numerical results for the cases of one and many small bodies are presented. Error analysis for the numerical method are also provided.

No / Information security has been a critical issue in the design and development of reliable distributed communication systems and has attracted significant research efforts. A challenging task is how to maintain information security at a high level for multiple-destination video applications with the huge volume of data and dynamic property of clients. This paper proposes a novel Content-Aware Secure Multicast (CASM) protocol for video distribution that seamlessly integrates three important modules: 1) a scalable light-weight algorithm for group key management; 2) a content-aware key embedding algorithm that can make video quality distortion imperceptible and is reliable for clients to detect embedded keys; and 3) a smart two-level video encryption algorithm that can selectively encrypt a small set of video data only, and yet ensure the video as well as the embedded keys unrecognizable without a genuine key. The implementation of the CASM protocol is independent of the underlying multicast mechanism and is fully compatible with existing coding standards. Performance evaluation studies built upon a CASM prototype have demonstrated that CASM is highly robust and scalable in dynamic multicast environments. Moreover, it ensures secure distribution of key and video data with minimized communication and computation overheads. The proposed content-aware key embedding and encryption algorithms are fast enough to support real-time video multicasting.

J.-P. Serre a conjecturé à la fin des années 60 et P. Deligne a prouvé au début des années 70 que pour toute newform f = q + ∑ n⩾2 a n q n 2 S k (N; "), k ⩾ 2, et tout premier l du corps de nombres Kf = Q(a n ; n ⩾ 2), il existe une représentation galoisienne l-adique pf;l : Gal(Q=Q) ! GL2 (ZKf;l) qui est non-ramifiée en dehors de ℓN et telle que le polynôme caractéristique du Frobenius en p ∤ ℓN est X2 a pX + "(p)p k 1 .Après réduction modulo l et semi-simplification, on obtient une représentation galoisienne pf;l : Gal(Q=Q) ! GL2 (Fl) modulo l, non-ramifiée en dehors de ℓN et telle que lepolynôme caractéristique du Frobenius en p ∤ ℓN est X 2 a pX + "(p)p k 1mod l, d'où un moyen de calcul rapide de ap mod l pour p gigantesque.L'objet de cette thèse est l'étude et l'implémentation d'un algorithme reposant sur cette idée (initialement due à J.-M. Couveignes and B. Edixhoven), qui calcule les coefficients ap modulo l en calculant d'abord cette représentation modulo l, en s'appuyant sur le fait que pour k < ℓ, cette représentation est réalisée dans la ℓ-torsion de la jacobienne de la courbe modulaire X1 (ℓN ).Grâce à plusieurs améliorations, telles que l'utilisation des méthodes de K. KhuriMakdisi pour calculer dans la jacobienne modulaire J1(ℓN ) ou la construction d'une fonction a 2 Q (J1(ℓN )) au bon comportement arithmétique, cet algorithme est très efficace, ainsi qu'illustré par des tables de coefficients. Cette thèse se conclut par la présentation d'une méthode permettant de prouver formellement que les résultats de ces calculs sont corrects. / It was conjectured in the late 60's by J.-P. Serre and proved in the early 70's by P.Deligne that to each newform f = q +Σn ⩾2 anqn 2 Sk(N; "), k ⩾2, and each primel of the number field Kf = Q(an; n ⩾ 2), is attached an l-adic Galois representationPf;l : Gal(Q=Q) ! GL2(ZKf;l ), which is unrami fied outside ℓN and such the characteristicpolynomial of the Frobenius element at p ∤ ℓN is X2 apX +"(p)pk1. Reducing modulo land semi-simplifying, one gets a mod l Galois representation Pf;l : Gal(Q=Q) ! GL2(Fl),which is unrami filed outside ℓN and such that the characteristic polynomial of the Frobeniuselement at p ℓN is X2 apX +"(p)pk1 mod l. In particular, its trace is ap mod l, whichgives a quick way to compute ap mod l for huge p.The goal of this thesis is to study and implement an algorithm based on this idea(originally due to J.-M. Couveignes and B. Edixhoven) which computes the coefficients apmodulo l by computing the mod l Galois representation first, relying on the fact that ifk < ℓ, this representation shows up in the ℓ-torsion of the jacobian of the modular curveX1(ℓN).Thanks to several improvements, such as the use of K. Khuri-Makdisi's methods tocompute in the modular Jacobian J1(ℓN) or the construction of an arithmetically well-behaved function alph 2 Q(J1(ℓN)), this algorithm performs very well, as illustrated bytables of coefficients. This thesis ends by the presentation of a method to formally provethat the output of the algorithm is correct.

<div>The design of advanced integrated circuits (ICs) and systems calls for multiphysics and large-scale modeling and simulation methods. On the one hand, novel devices and materials are emerging in next-generation IC technology, which requires multiphysics modeling and simulation. On the other hand, the ever-increasing complexity of ICs requires more efficient numerical solvers.</div><div><br></div><div>In this work, we propose a multiphysics modeling and simulation algorithm to co-simulate Maxwell's equations, dispersion relation of materials, and Boltzmann equation to characterize emerging new devices in IC technology such as Cu-Graphene (Cu-G) hybrid nano-interconnects. We also develop an unconditionally stable time marching scheme to remove the dependence of time step on space step for an efficient simulation of the multiscaled and multiphysics system. Extensive numerical experiments and comparisons with measurements have validated the accuracy and efficiency of the proposed algorithm. Compared to simplified steady-state-models based analysis, a significant difference is observed when the frequency is high or/and the dimension of the Cu-G structure is small, which necessitates our proposed multiphysics modeling and simulation for the design of advanced Cu-G interconnects. </div><div><br></div><div>To address the large-scale simulation challenge, we develop a new split-field domain-decomposition algorithm amenable for parallelization for solving Maxwell’s equations, which minimizes the communication between subdomains, while having a fast convergence of the global solution. Meanwhile, the algorithm is unconditionally stable in time domain. In this algorithm, unlike prevailing domain decomposition methods that treat the interface unknown as a whole and let it be shared across subdomains, we partition the interface unknown into multiple components, and solve each of them from one subdomain. In this way, we transform the original coupled system to fully decoupled subsystems to solve. Only one addition (communication) of the interface unknown needs to be performed after the computation in each subdomain is finished at each time step. More importantly, the algorithm has a fast convergence and permits the use of a large time step irrespective of space step. Numerical experiments on large-scale on-chip and package layout analysis have demonstrated the capability of the new domain decomposition algorithm. </div><div><br></div><div>To tackle the challenge of efficient simulation of irregular structures, in the last part of the thesis, we develop a method for the stability analysis of unsymmetrical numerical systems in time domain. An unsymmetrical system is traditionally avoided in numerical formulation since a traditional explicit simulation is absolutely unstable, and how to control the stability is unknown. However, an unsymmetrical system is frequently encountered in modeling and simulating of unstructured meshes and nonreciprocal electromagnetic and circuit devices. In our method, we reduce stability analysis of a large system into the analysis of dissembled single element, therefore provides a feasible way to control the stability of large-scale systems regardless of whether the system is symmetrical or unsymmetrical. We then apply the proposed method to prove and control the stability of an unsymmetrical matrix-free method that solves Maxwell’s equations in general unstructured meshes while not requiring a matrix solution.<br></div><div><br></div>

Les algèbres centrales simples ont de nombreuses applications en théorie des nombres, mais leur algorithmique est encore peu développée. Dans cette thèse, j’apporte une contribution dans deux directions. Premièrement, je présente des algorithmes de complexité prouvée, ce qui est nouveau dans la plupart des cas. D’autre part, je développe des algorithmes heuristiques mais très efficaces dans la pratique pour les exemples qui nous intéressent le plus, comme en témoignent mes implantations. Les algorithmes sont à la fois plus rapides et plus généraux que les algorithmes existants. Plus spécifiquement, je m’intéresse aux problèmes suivants : calcul du groupe des unités d’un ordre et problème de l’idéal principal. Je commence par étudier le diamètre du domaine fondamental de certains groupes d’unités grâce à la théorie des représentations. Je décris ensuite un algorithme prouvé pour calculer des générateurs et une présentation du groupe des unités d’un ordre maximal dans une algèbre à division, puis un algorithme efficace qui calcule également un domaine fondamental dans le cas où le groupe des unités est un groupe kleinéen. Je donne en outre un algorithme de complexité prouvée qui détermine si un idéal d’un tel ordre est principal, et qui en calcule un générateur le cas échéant, puis je décris un algorithme heuristiquement sous-exponentiel pour résoudre le même problème dans le cas d’une algèbre de quaternions indéfinie. / Central simple algebras have many applications in number theory, but their algorithmic theory is not yet fully developed. I present algorithms to compute effectively with central simple algebras that are both faster and more general than existing ones. Some of these algorithms have proven complexity estimates, a new contribution in this area; others rely on heuristic assumptions but perform very efficiently in practice.Precisely, I consider the following problems: computation of the unit group of an order and principal ideal problem. I start by studying the diameter of fundamental domains of some unit groups using representation theory. Then I describe an algorithm with proved complexity for computing generators and a presentation of the unit group of a maximal order in a division algebra, and then an efficient algorithm that also computes a fundamental domain in the case where the unit group is a Kleinian group. Similarly, I present an algorithm with proved complexity that decides whether an ideal of such an order is principal and that computes a generator when it is. Then I describe a heuristically subexponential algorithm that solves the same problem in indefinite quaternion algebras.

Supraglacial lakes in the ablation zone of the Greenland Ice Sheet (GrIS) often drain rapidly (in hours to days) by hydraulically-driven fracture (“hydrofracture”) in the summer. Hydrofracture can deliver large meltwater volumes to the ice-bed interface and open-up surface-to-bed connections, thereby routing surface meltwater to the subglacial system, altering basal water pressures and, consequently, the velocity profile of the GrIS. The study of rapidly draining lakes is thus important for developing coupled hydrology and ice-dynamics models, which can help predict the GrIS’s future mass balance. Remote sensing is commonly used to identify the location, timing and magnitude of rapid lake-drainage events for different regions of the GrIS and, with the increased availability of high-quality satellite data, may be able to offer additional insights into the GrIS’s surface hydrology. This study uses new remote-sensing datasets and develops novel analytical techniques to produce improved knowledge of rapidly draining lake behaviour in west Greenland over recent years. While many studies use 250 m MODerate-resolution Imaging Spectroradiometer (MODIS) imagery to monitor intra- and inter-annual changes to lakes on the GrIS, no existing research with MODIS calculates changes to individual and total lake volume using a physically-based method. The first aim of this research is to overcome this shortfall by developing a fully-automated lake area and volume tracking method (“the FAST algorithm”). For this, various methods for automatically calculating lake areas and volumes with MODIS are tested, and the best techniques are incorporated into the FAST algorithm. The FAST algorithm is applied to the land-terminating Paakitsoq and marine-terminating Store Glacier regions of west Greenland to investigate the incidence of rapid lake drainage in summer 2014. The validation and application of the FAST algorithm show that lake areas and volumes (using a physically-based method) can be calculated accurately using MODIS, that the new algorithm can identify rapidly draining lakes reliably, and that it therefore has the potential to be used widely across the GrIS to generate novel insights into rapidly draining lakes. The controls on rapid lake drainage remain unclear, making it difficult to incorporate lake drainage into models of GrIS hydrology. The second aspect of this study therefore investigates whether various hydrological, morphological, glaciological and surface-mass-balance controls can explain the incidence of rapid lake drainage on the GrIS. These potential controlling factors are examined within an Exploratory Data Analysis statistical technique to elicit statistical similarities and differences between the rapidly and non-rapidly draining lake types. The results show that the lake types are statistically indistinguishable for almost all factors, except lake area. It is impossible, therefore, to elicit an empirically-supported, deterministic method for predicting hydrofracture in models of GrIS hydrology. A frequent problem in remote sensing is the need to trade-off high spatial resolution for low temporal resolution, or vice versa. The final element of this thesis overcomes this problem in the context of monitoring lakes on the GrIS by adapting the FAST algorithm (to become “the FASTER algorithm”) to use with a combined Landsat 8 and Sentinel-2 satellite dataset. The FASTER algorithm is applied to a large, predominantly land-terminating region of west Greenland in summers 2016 and 2017 to track changes to lakes, identify rapidly draining lakes, and ascertain the extra quantity of information that can be generated by using the two satellites simultaneously rather than individually. The FASTER algorithm can monitor changes to lakes at both high spatial (10 to 30 m) and temporal (~3 days) resolution, overcoming the limitation of low spatial or temporal resolution associated with previous remote sensing of lakes on the GrIS. The combined dataset identifies many additional rapid lake-drainage events than would be possible with Landsat 8 or Sentinel-2 alone, due to their low temporal resolutions, or with MODIS, due to its inferior spatial resolution.