Thesis advisor: John A. Baldwin / We classify genus-two L-space knots in S3 and the Poincare homology sphere.This leads to the first and to-date only detection results in knot Floer homology for knots of genus greater than one. Our proofs interweave Floer-homological properties of L-space knots, the geometry of pseudo-Anosov maps, and the theory of train tracks and folding automata for braids. The crux of our argument is a complete classification of fixed-point-free pseudo-Anosov maps in all but one stratum on the genus-two surface with one boundary component. To facilitate our classification, we exhibit a small family of train tracks carrying all pseudo-Anosov maps in most strata on the marked disk. As a consequence of our proof technique, we almost completely classify genus-two, hyperbolic, fibered knots with knot Floer homology of rank 1 in their next-to-top grading in any 3-manifold. Several corollaries follow, regarding the Floer homology of cyclic branched covers, SU(2)-abelian Dehn surgeries, Khovanov and annular Khovanov homology, and instanton Floer homology. / Thesis (PhD) — Boston College, 2024. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Mathematics.

No description available.

We study isotone self-maps of complete lattices and their fixed point sets, which are complete lattices contained as suborders, but not necessarily as subsemilattices. We develop a representation of such maps by means of relations and show how to navigate their fixed point lattices using a modification of the standard Next closure algorithm. Our approach is inspired by early work of Shmuely and Crapo. We improve and substantially extend our earlier publication.

In this thesis, the design and implementation of a Portable Feedback Active Noise Controller Headphone System, which is based on Texas Instruments TMS320VC5416PGE120 Fixed Point DSP, is described. Problems resulted from fixed-point implementation of LMS algorithm and delays existing in digital ANC implementation are determined. Effective solutions to overcome the aforementioned problems are proposed based on the literature survey. Design of the DSP based control card is explained and crucial points about analog-digital-mixed board design for noise sensitive applications are explained. Filtered input LMS algorithm, filtered input normalized LMS algorithm and filtered input sign-sign LMS algorithm are implemented as adaptation algorithms. The advantages and disadvantages of using modified LMS algorithms are indicated. The selection of the parameters of these algorithms is based on theoretical results and experiments. The real time performances of different adaptation algorithms are compared with each other as well as with a commercial analog ANC headphone under different types of artificial and natural noise signals. Moreover, practical conditions such as put on - put off case and dynamic range overflow case are handled with additional software implementations. It is shown that adaptive ANC systems improve the noise reduction significantly when the noise is within a narrow frequency range and this reduction can be applied to a wider frequency range. It is also shown that the problems of digitally implemented adaptive filters which are based on tracking capability, stability, dynamic range and portability can be fixed to challenge with the analog commercial ANC systems.

The realisation of signal processing algorithms in fixed-point offers substantial performance advantages over floating-point realisations. However, it is widely acknowledged that the task of realising algorithms in fixed-point is a challenging one with limited tool support. This thesis examines various aspects related to the translation of algorithms, given in infinite precision or floating-point, into fixed-point. In particular, this thesis reports on the implementation of a given algorithm, an EDFA (Erbium-Doped Fibre Amplifier) control algorithm, on a FPGA (Field Programmable Gate Array) using fixed-point arithmetic. An analytical approach is proposed that allows the automated realisation of algorithms in fixedpoint. The technique provides fixed-point parameters for a given floating-point model that satisfies a precision constraint imposed on the primary output of the algorithm to be realised. The development of a simulation framework based on this analysis allows fixed-point designs to be generated in a shorter time frame. Albeit being limited to digital algorithms that can be represented as a data flow graph (DFG), the approach developed in the thesis allows for a speed up in the design and development cycle, reduces the possibility of error and eases the overall effort involved in the process. It is shown in this thesis that a fixed-point realisation of an EDFA control algorithm using this technique produces results that satisfy the given constraints.

Thesis (MSc)--University of Stellenbosch, 2005. / ENGLISH ABSTRACT: The majority of tra c on the Internet uses the Transmission Control Protocol (TCP) as a transport layer protocol for the end-to-end control of information transfer. Measurement, simulation and analytical models are the techniques and tools that can be used to understand and investigate the Internet and its performance. Measurements can only be used to explore existing network scenario or otherwise become costly and in exible with the growth and complexity of the Internet. Simulation models do not scale with the growth of network capacities and the number of users. Computationally e cient analytical models are therefore important tools for investigating, designing, dimensioning and planning IP (Internet Protocol) networks. Existing analytical models of TCP performance are either too simple to capture the internal dynamics of TCP or are too complex to be used to analyze realistic network topologies with several bottleneck links. The literature shows that the xed point algorithm (FPA) is a very useful way of solving analytical models of Internet performance. This thesis presents fast and accurate analytical models of TCP performance with the FPA used to solve them. Apart from what is observed in experimental literature, no comprehensive proof of the convergence and uniqueness of the FPA is given. In this thesis we show how the FPA of analytical models of reliable Internet protocols such as TCP converges to a unique xed point. The thesis speci es the conditions necessary in order to use the FPA for solving analytical models of reliable Internet protocols. We also develop a general implementation algorithm of the FPA of analytical models of TCP performance for realistic and arbitrary network topologies involving heterogenous TCP connections crossing many bottleneck links. The models presented in this thesis give Internet performance metrics, assuming that only basic network parameters such as the network topology, the number of TCP connections, link capacity, distance between network nodes and router bu er sizes are known. To obtain the performance metrics, TCP and network sub{models are used. A closed network of :=G=1 queues is used to develop each TCP sub-model where each queue represents a state of a TCP connection. An M=M=1=K queue is used for each network sub{model which represents the output interface of an IP router with a bu er capacity of K 􀀀��������1 packets. The two sub-models are iteratively solved. We also give closed form expressions for important TCP performance values and distributions. We show how the geometric, bounded geometric and truncated geometric distributions can be used to model reliable protocols such as TCP. We give models of the congestion window cwnd size distribution by conditioning on the slow start threshold ssthresh distribution and vice-versa. We also present models of the probabilities of TCP timeout and triple duplicate ACK receptions. Numerical results based on comparisons against ns2 simulations show that our models are more accurate, simpler and computationally more e cient than another well known TCP model. Our models can therefore be used to rapidly analyze network topologies with several bottlenecks and obtain detailed performance metrics. / AFRIKAANSE OPSOMMING: Die meerderheid van die verkeer op die Internet gebruik die Transmission Control Protocol (TCP) as `n vervoer laag protokol vir die einde-tot-einde kontrole van inligting oordrag. Meting, simulasie en analitiese modelle is die tegnieke en gereedskap wat gebruik kan word om die Internet te ondersoek en verstaan. Meting kan slegs gebruik word om bestaande netwerke scenarios te verken. Meting is duur en onbuigsaam met die groei en samegesteldheid van die Internet. Simulasie modelle skaal nie met die groei van netwerk kapasiteit en gebruikers nie. Analitiese modelle wat berekening e ektief is is dus nodige gereedskap vir die ondersoek, ontwerp, afmeting en beplanning van IP (Internet Protocol) netwerke. Bestaande analitiese TCP modelle is of te eenvoudig om die interne dinamiek van die TCP saam te vat of hulle is te ingewikkeld om realistiese netwerk topologie met heelwat bottelnek skakels te analiseer. Literatuur toon dat die xed point algorithm (FPA) baie handig is vir die oplos van analitiese modelle van Internet verrigting. In hierdie tesis word vinnige en akkurate analitiese modelle van TCP verrigting opgelos deur FPA weergegee. Buiten wat deur eksperimentele literatuur aangedui word is daar geen omvattende bewyse van die konvergensie en uniekheid van die FPA nie. In hierdie tesis word aangedui hoe die FPA van analitiese modelle van betroubare Internet protokolle soos die TCP konvergeer na `n unieke vaste punt. Hierdie tesis spesi seer die voorwaardes benodig om die FPA te gebruik vir die oplos van analitiese modelle van realistiese Internet protokolle. `n Algemene uitvoer algoritme van die FPA van analitiese modelle van TCP vir realistiese en arbitr^ere netwerk topogra e insluitende heterogene TCP konneksies oor baie bottelnek skakels is ontwikkel. Die model in hierdie tesis gee Internet verrigting metodes met die aanname dat slegs basiese netwerk parameters soos netwerk topologie, die aantal TCP konneksies, die konneksie kapasiteit, afstand tussen netwerk nodusse en die roete bu er grotes bekend is. Om die verrigting metodes te verkry, word TCP en netwerk sub-modelle gebruik. `n Geslote netwerk van :=G=1 rye is gebruik om elke TCP sub-model, waar elke ry 'n toestand van `n TCP konneksie voorstel, te ontwikkel. `n M=M=1=K ry is gebruik vir elke netwerk sub-model wat die uitset koppelvlak van `n IP roetemaker met `n bu er kapasiteit van K 􀀀������� 1 pakkies voorstel. Die twee submodelle word iteratief opgelos. Geslote vorm uitdrukkings vir belangrike TCP verrigting waardes en verspreidings word gegee. Daar word getoon hoe geometriese, begrensde geometriese en geknotte geometriese verspreidings gebruik kan word om betroubare protokolle soos die TCP te modelleer. Modelle van die kongestie venster cwnd grootte verspreiding word gegee deur die kondisionering van die stadige aanvang drempel ssthresh verspreiding en andersom. Modelle van die voorspelling van TCP tyduit en trippel duplikaat ACK resepsie word weergegee. Numeriese resultate gebaseer op vergelykings met ns2 simulasies wys dat ons modelle meer akkuraat, eenvoudiger en berekeningsgewys meer e ektief is as ander wel bekende TCP modelle. Ons modelle kan dus gebruik word vir vinnig analise van netwerk topologie met verskeie bottelnekke en om gedetailleerde verrigting metodes te bekom.

Pour réduire les coûts des systèmes embarqués, ces derniers sont livrés avec des micro-processeurs peu puissants. Ces processeurs sont dédiés à l'exécution de tâches calculatoires dont certaines, comme la transformée de Fourier rapide, peuvent s'avérer exigeantes en termes de ressources de calcul. Afin que les implémentations de ces algorithmes soient efficaces, les programmeurs utilisent l'arithmétique à virgule fixe qui est plus adaptée aux processeurs dépourvus d'unité flottante. Cependant, ils se retrouvent confrontés à deux difficultés: D'abord, coder en virgule fixe est fastidieux et exige que le programmeur gère tous les détails arithmétiques. Ensuite, et en raison de la faible dynamique des nombres à virgule fixe par rapport aux nombres flottants, les calculs en fixe sont souvent perçus comme intrinsèquement peu précis. La première partie de cette thèse propose une méthodologie pour dépasser ces deux limitations. Elle montre comment concevoir et mettre en œuvre des outils pour générer automatiquement des programmes en virgule fixe. Ensuite, afin de rassurer l'utilisateur quant à la qualité numérique des codes synthétisés, des certificats sont générés qui fournissent des bornes sur les erreurs d'arrondi. La deuxième partie de cette thèse est dédiée à l'étude des compromis lors de la génération de programmes en virgule fixe pour les briques d'algèbre linéaire. Des données expérimentales y sont fournies sur la synthèse de code pour la multiplication et l'inversion matricielles. / To be cost effective, embedded systems are shipped with low-end micro-processors. These processors are dedicated to one or few tasks that are highly demanding on computational resources. Examples of widely deployed tasks include the fast Fourier transform, convolutions, and digital filters. For these tasks to run efficiently, embedded systems programmers favor fixed-point arithmetic over the standardized and costly floating-point arithmetic. However, they are faced with two difficulties: First, writing fixed-point codes is tedious and requires that the programmer must be in charge of every arithmetical detail. Second, because of the low dynamic range of fixed-point numbers compared to floating-point numbers, there is a persistent belief that fixed-point computations are inherently inaccurate. The first part of this thesis addresses these two limitations as follows: It shows how to design and implement tools to automatically synthesize fixed-point programs. Next, to strengthen the user's confidence in the synthesized codes, analytic methods are suggested to generate certificates. These certificates can be checked using a formal verification tool, and assert that the rounding errors of the generated codes are indeed below a given threshold. The second part of the thesis is a study of the trade-offs involved when generating fixed-point code for linear algebra basic blocks. It gives experimental data on fixed-point synthesis for matrix multiplication and matrix inversion through Cholesky decomposition.

Neste trabalho demonstram-se os teoremas de ponto fixo de Brouwer e Kakutani com o objetivo de provar a existência do equilíbrio de Nash em jogos finitos em forma normal. No primeiro capítulo apresentam-se as definições de teoria dos jogos, começando com jogos finitos em forma normal e terminando com o conceito de equilíbrio de Nash. Na primeira seção do capítulo dois desenvolve-se a teoria de simplexes, em Rn, e se demonstra o teorema de Brouwer. Na seção seguinte, são relacionadas as propriedades de semi-continuidade superior e gráfico fechado em set functions, para então provar os teoremas de Celina e von Neumann que, em conjunto com o teorema de Brouwer, resultam no teorema de Kakutani no fim da seção. Como último resultado é demonstrado o teorema de existência do equilíbrio de Nash em jogos finitos em forma normal através do teorema de Kakutani, mostrando que o equilíbrio de Nash é um ponto fixo de uma set function. / In this work, the fixed-point theorems of Kakutani and Brouwer are proved with the intention of showing the existence of Nash equilibrium in finite normal-form games. In the first chapter the needed definitions of game theory are shown, starting with finite normal-form games and ending with the concept of Nash equilibrium. In the first section of chapter two, simplex theory in Rn is developed and then the Brouwer fixer point theorem is proved. In the next section, some relations of upper hemi-continuity and closed graph in set functions are shown, then proving the theorems of Celina and von Neumann that, along with Brouwer theorem, result in Kakutani fixed-point theorem in the end of the section. As the last result, the existence of Nash equilibrium in finite normal-form games is proved through Kakutani’s theorem, relating the Nash equilibrium to the fixed-point of a set function.

No description available.

L’objectif de ce travail de thèse est d’étudier quelques problèmes elliptiques et paraboliques d’écoulement de fluides non Newtoniens incompressibles et non isothermes gouvernés par l’équation aux dérivées partielles de Stokes avec la condition de Tresca sur une partie du bord quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations. Dans le premier chapitre, on a fait une introduction générale. Dans le deuxième chapitre, nous nous intéressons au couplage entre le système de Stokes et l’équation de la chaleur en régime stationnaire. On montre l’existence de la solution de l’inéquation variationnelle décrivant le système de Stokes pour une température donnée quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations en utilisant la méthode de monotonie pour la vitesse et le théorème de De Rham pour la pression. Dans un deuxième temps, on étudie l’existence et l’unicité de la température solution de l’équation de la chaleur avec un terme L1(Ω) au second membre quand la viscosité dépend à la fois de la température, de la vitesse et du module du tenseur des taux de déformations. On montre ensuite l’existence de la solution du problème variationnel couplé avec la viscosité dépend de la température et du module du tenseur des taux de déformations, en utilisant le théorème de point fixe de Schauder. Dans le troisième et le quatrième chapitre, on traite l’existence et l’unicité de la solution du système de Stokes en régime instationnaire quand la viscosité dépend de la température et du module du tenseur des taux de déformations dans les cas p = 2, p > 2 et 6 5 < p < 2 en utilisant la notion des semi-groupes et la méthode de monotonie pour la vitesse et le théorème de De Rham pour la pression. Par contre, lorsque la viscosité dépend de plus de la vitesse on obtient seulement l’existence par le théorème de point fixe de Schauder / The objective of this thesis is to study some elliptic and parabolic problems of the non-Newtonian flow of an incompressible and non isothermal fluid governed by partial differential equation of Stokes with Tresca’s condition on a part of the boundary when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid. In the first chapter, we did a general introduction. In the second chapter, we consider the coupling between the Stokes systemand the heat equation in steady state. We prove the existence of a solution of the variational inequality describing the Stokes system when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid of a given temperature by using the monotony methods for the velocity and De Rham’s theorem for the pressure. We study the existence and uniqueness of the temperature solution of the heat equation with L1 (Ω) term to the second member when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor and the velocity of the fluid. We show the existence of a solution of the coupled variational problem when the fluid viscosity depends on temperature and also on the modulus of strain rate tensor by using Schauder fixed point theorem. In the third and the fourth chapter, we treate the existence and uniqueness of a solution of the Stokes system in unsteady state when the fluid viscosity depends only on temperature and on the modulus of strain rate tensor in the cases p = 2, p > 2 and 6 5 < p < 2 by using the notion of semigroup and monotony methods for the velocity and De Rham’s theorem for the pressure. However, when the fluid viscosity depends also on the velocity of the fluid we obtain only the existence by Schauder fixed point theorem