We show that equitable partitions, which are generalizations of graph symmetries, and Fourier transforms are fundamentally related. For a partition of a graph's vertices we define a Fourier similarity transform of the graph's adjacency matrix built from the matrices used to carryout discrete Fourier transformations. We show that the matrix (graph) decomposes into a number of smaller matrices (graphs) under this transformation if and only if the partition is an equitable partition. To extend this result to directed graphs we define two new types of equitable partitions, equitable receiving and equitable transmitting partitions, and show that if a partition of a directed graph is both, then the graph's adjacency matrix will similarly decomposes under this transformation. Since the transformation we use is a similarity transform the collective eigenvalues of the resulting matrices (graphs) is the same as the eigenvalues of the original untransformed matrix (graph).

While Monte Carlo methods for bootstrapping are typically easy to implement, they can be quite time intensive. This work aims to extend an established convolutional method of bootstrapping to work when convolutions in two or more dimensions are required. The convolutional method relies on efficient computational tools rather than Monte Carlo simulation which can greatly reduce the computation time. The proposed method is particularly well suited for the analysis of degradation data when the data are not collected on time intervals of equal length. The convolutional bootstrapping method is typically much faster than the Monte Carlo bootstrap and can be used to produce exact results in some simple cases. Even in more complicated applications, where it is not feasible to find exact results, mathematical bounds can be placed on the resulting distribution. With these benefits of the convolutional method, this bootstrapping approach has been shown to be a useful alternative to the traditional Monte Carlo bootstrap.

Discrete Fourier Transforms (DFTs) are used in a wide variety of dif-ferent scientific areas. In addition, there is an ever increasing demand on fast and effective ways of computing DFT problems with large data sets. The FFTW library is one of the most common used libraries when computing DFTs. It adapts to the system architecture and predicts the most effective way of solving the input problem. Previous studies have proved the FFTW library to be superior to other DFT solving libraries. However, not many have specifically examined the cache memory performance, which is a key factor for overall performance. In this study, we examined the cache memory utilization when computing 1-D complex DFTs using the FFTW library. Testing was done using bench FFT, Linux Perf and testing scripts. The results from this study show that cache miss ratio increases with problem size when the input size is smaller than the theoretical input size matching the cache capacity. This is also verified by the results from the L2 prefetcher miss ratio. However, the study show that cache miss ratio stabilizes when exceeding the cache capacity. In conclusion, it is possible to use bench FFT and Linux Perf to measure cache memory utilization. Also, the analysis shows that cache memory performance is good when computing 1-D complex DFTS using the FFTW library, since the miss ratios stabilizes at low values. However, we suggest further examination ofthe memory behaviour for DFT computations using FFTW with larger input sizes and a more in-depth testing method. / Diskret Fouriertransform (DFT) används inom många olika vetenskapliga områden. Det finns en ökande efterfrågan på snabba och effektiva sätt att beräkna DFT-problem med stora mängder data. FFTW-biblioteket är ett av de mest använda biblioteken vid beräkning av DFT-problem. FFTW-biblioteket anpassar sig till systemarkitekturen och försöker generera det mest effektiva sättet att lösa ett givet DFT-problem. Tidigare studier har visat att FFTW-biblioteket är effektivare än andra bibliotek som kan användas för att lösa DFT-problem. Däremot har studierna inte fokuserat på minneshanteringen, vilket är en nyckelfaktor för den generella prestandan. I den här studien undersökte vi FFTW-bibliotekets cache-minneshanteringen vid beräkning av 1-D komplexa DFT-problem. Tester utfördes med hjälp av bench FFT, Linux Perf och testskript. Resultaten från denna studie visar att cache-missförhållandet ökar med problemstorleken när problemstorleken ärmindre än den teoretiska problemstorleken som matchar cachekapaciteten. Detta bekräftas av resultat från L2-prefetcher-missförhållandet. Studien visar samtidigt att cache-missförhållandet stabiliseras när problemstorleken överskrider cachekapaciteten. Sammanfattningsvis går det att argumentera för att det är möjligt att använda bench FFT och Linux Perf för att mäta cache-minneshanteringen. Analysen visar också att cache-minneshanteringen är bra vid beräkning av 1-D komplexa DFTs med hjälp av FFTW-biblioteket eftersom missförhållandena stabiliseras vid låga värden. Vi föreslår dock ytterligare undersökning av minnesbeteendet för DFT-beräkningar med hjälp av FFTW där problemstorlekarna är större och en mer genomgående testmetod används.

Recent developments in smart grid technology have spawned interest in the use of phasor measurement units to help create a reliable power system transmission and distribution infrastructure. Wide-area monitoring systems (WAMSs) utilizing synchrophasor measurements can help with understanding, forecasting, or even controlling the status of power grid stability in real-time. A power system Frequency Monitoring Network (FNET) was first proposed in 2001 and was established in 2004. As a pioneering WAMS, it serves the entire North American power grid through advanced situational awareness techniques, such as real-time event alerts, accurate event location estimation, animated event visualization, and post event analysis. Traditionally, Phasor Measurement Units (PMUs) have utilized signals obtained from current transformers (CTs) to compute current phasors. Unfortunately, this requires that CTs must be directly connected with buses, transformers or power lines. Chapters 2, 3 will introduce an innovative phasor measurement instrument, the Non-contact Frequency Disturbance Recorder (NFDR), which uses the magnetic and electric fields generated by power transmission lines to obtain current phasor measurements. The NFDR is developed on the same hardware platform as the Frequency Disturbance Recorder (FDR), which is actually a single phase PMU. Prototype testing of the NFDR in both the laboratory and the field environments were performed. Testing results show that measurement accuracy of the NFDR satisfies the requirements for power system dynamics observation. Researchers have been developing various techniques in power system phasor measurement and frequency estimation, due to their importance in reflecting system health. Each method has its own pros and cons regarding accuracy and speed. The DFT (Discrete Fourier Transform) based algorithm that is adopted by the FDR device is particularly suitable for tracking system dynamic changes and is immune to harmonic distortions, but it has not proven to be very robust when the input signal is polluted by random noise. Chapter 4 will discuss the Least Mean Squares-based methods for power system frequency tracking, compared with a DFT-based algorithm. Wide-area monitoring systems based on real time PMU measurements can provide great visibility to the angle instability conditions. Chapter 5 focuses on developing an early warning algorithm on the FNET platform. / Ph. D.

No / We analyze the possibility and efficiency of nonholonomic control over quantum devices with exponentially large number of Hilbert space dimensions. We show that completely controllable devices of this type can be assembled from elementary units of arbitrary physical nature, and can be employed efficiently for universal quantum computations and simulation of quantum-field dynamics. As an example we describe a toy device that can perform Toffoli-gate transformations and discrete Fourier transform on 9 qubits.

In today's highly competitive and deregulated electricity market, companies in the generation, transmission and distribution sectors can all benefit from collecting, analyzing and deep-understanding their customers' load profiles. This strategic information is vital in load forecasting, demand-side management planning and long-term resource and capital planning. With the proliferation of Advanced Metering Infrastructure (AMI) in recent years, the amount of load profile data collected by utilities has grown exponentially. Such high-resolution datasets are difficult to model and analyze due to the large size, diverse usage patterns, and the embedded noisy or erroneous data points. In order to overcome these challenges and to make the load data useful in system analysis, this dissertation introduces a frequency domain load profile modeling framework. This framework can be used a complementary technology alongside of the conventional time domain load profile modeling techniques. There are three main components in this framework: 1) the frequency domain load profile descriptor, which is a compact, modular and extendable representation of the original load profile. A methodology was introduced to demonstrate the construction of the frequency domain load profile descriptor. 2) The load profile Characteristic Attributes in the Frequency Domain (CAFD). Which is developed for load profile characterization and classification. 3) The frequency domain load profile statistics and forecasting models. Two different models were introduced in this dissertation: the first one is the wavelet load forecast model and the other one is a stochastic model that incorporates local weather condition and frequency domain load profile statistics to perform medium term load profile forecast. 7 different utilities load profile data were used in this research to demonstrate the viability of modeling load in the frequency domain. The data comes from various customer classes and geographical regions. The results have shown that the proposed framework is capable to model the load efficiently and accurately. / Ph. D. / In today’s highly competitive and deregulated electricity market, companies in the electricity power generation, transmission and distribution sectors can all benefit from collecting, analyzing and deep-understanding their customers’ electricity consumption behavior. This strategic information is vital in forecasting and managing the future electricity demand. This information is also very important in utility company’s long-term resource and capital planning. With the proliferation of Advanced Metering Infrastructure (AMI) in recent years, the amount of electric load profile data collected by utilities has grown exponentially. Such high-resolution datasets are difficult to model and analyze due to the large size, diverse usage patterns, and the embedded noisy or erroneous data points. In order to overcome these challenges and to make the load data useful in system analysis, this dissertation introduces a frequency domain load profile modeling framework. This framework can be used a complementary technology alongside of the conventional time domain load profile modeling techniques. There are three main components in this framework: I) the frequency domain load profile descriptor, which is a compact, modular and extendable representation of the original load profile. A methodology was introduced to demonstrate the construction of the frequency domain load profile descriptor. II) The load profile Characteristic Attributes in the Frequency Domain (CAFD). Which is developed for categorizing the load profile data. III) The frequency domain load profile statistics and forecasting models. 7 different utilities load profile data were used in this research to demonstrate the viability of modeling load in the frequency domain. The data comes from various customer classes and geographical regions. The results have shown that the proposed framework is capable to model the load efficiently and accurately.

In large antenna systems, traditional channel estimation is costly and infeasible in some situations. Compressive sensing was proposed to estimate the channel with fewer measurements. Most of the previous work uses a predefined discrete Fourier transform matrix or overcomplete Fourier transform matrix to approximate the channel. Then, a learned dictionary trained by K-singular value decomposition (K-SVD) was proposed and was proved superiority using orthogonal matching pursuit (OMP) to reconstruct the sparse channel. However, with the development of compressive sensing, there are plenty of dictionary learning algorithms and sparse recovery algorithms. It is important to identify the effect and the performance of different algorithms when transforming the high dimensional channel vectors to low dimensional representations. In this thesis, we use a spatial channel model to generate channel vectors. Dictionaries are trained by K-SVD and method of optimal directions (MOD). Several sparse recovery algorithms are used to find the sparse approximation of the channel like OMP and gradient descent with sparsification (GraDeS). We present simulation results and discuss the performance of the various algorithms in terms of accuracy, sparsity, and complexity. We find that predefined dictionaries works with most of the algorithms in sparse recovery but learned dictionaries only work with pursuit algorithms, and only show superiority when the algorithm coincides with the algorithm in the sparse coding stage. / I stora antennsystem är traditionell kanaluppskattning kostsam och omöjlig i vissa situationer. Kompressionsavkänning föreslogs för att uppskatta kanalen med färre mätningar. Det mesta av det tidigare arbetet använder en fördefinierad diskret Fourier transformmatris eller överkompletterad Fourier -transformmatris för att approximera kanalen. Därefter föreslogs en inlärd ordbok som utbildats av K-SVD och bevisades överlägsen med hjälp av OMP för att rekonstruera den glesa kanalen. Men med utvecklingen av komprimerad avkänning finns det gott om algoritmer för inlärning av ordlistor och glesa återställningsalgoritmer. Det är viktigt att identifiera effekten och prestandan hos olika algoritmer när de högdimensionella kanalvektorerna omvandlas till lågdimensionella representationer. I denna avhandling använder vi en rumslig kanalmodell för att generera kanalvektorer. Ordböcker tränas av K-SVD och MOD. Flera glesa återställningsalgoritmer används för att hitta den glesa approximationen av kanalen som OMP och GraDeS. Vi presenterar simuleringsresultat och diskuterar prestanda för de olika algoritmerna när det gäller noggrannhet, sparsamhet och komplexitet. Vi finner att fördefinierade ordböcker fungerar med de flesta algoritmerna i gles återhämtning, men inlärda ordböcker fungerar bara med jaktalgoritmer och visar bara överlägsenhet när algoritmen sammanfaller med algoritmen i det glesa kodningsstadiet.

No description available.

Au cours de cette thèse nous nous intéressons à des orthogonalités asymptotiques (au sens ou le produit scalaire dans le tore discret de taille N tend vers 0 lorsque N tend vers l’infini) entre certaines fonctions liées aux blocs des chiffres des entiers et la fonction de Möbius (ainsi qu’avec la fonction de von Mangoldt). Ces travaux prolongent ceux de Mauduit et Rivat et répondent partiellement à une question de Kalai posée en 2012. Au cours du Chapitre 1 nous établissons ces estimations asymptotiques dans le cas où la fonction étudiée est une fonction exponentielle d’une fonction qui compte les blocs de chiffres consécutifs ou espacés de taille k fixé dans l’écriture de n en base q. Nous donnons aussi une grande classe de polynômes agissant sur les blocs de chiffres qui nous fournissent un théorème des nombres premiers et une orthogonalité asymptotique avec la fonction de Möbius. Dans le Chapitre 2, nous obtenons un principe d’aléa de Möbius avec dans le cas où notre fonction est une fonction exponentielle d’une fonction qui compte les blocs de ‘1’ consécutifs dans l’écriture de n en base 2, où la taille du bloc est une application croissante tendant vers l’infini, mais avec une certaine restriction de croissance. Dans le cas extrémal, que nous ne pouvons pas traiter, ce problème est lié à l’estimation du nombre de nombres premiers dans la suite des nombres de Mersenne. Dans le Chapitre 3, nous donnons des estimations dans le cas où la fonction est l’exponentielle d’une fonction qui compte les blocs de k ‘1’ dans l’écriture de n en base 2 où k est grand par rapport à log N. Une conséquence du Chapitre 3 est que les résultats du Chapitre 1 sont quasi optimaux. / Throughout this thesis, we are interested in asymptotic orthogonality (in the sense that the scale product of the discrete torus of length N tends to zero as N tend to infinity) between some functions related to the blocks of digits of integers and the Möbius function (and also the von Mangoldt function). Our work extends previous results of Mauduit and Rivat, and gives a partial answer to a question posed by Kalai in 2012. Chapter 1 provides estimates in the case of the function is the exponential of a function taking values on the blocks (with and without wildcards) of length k (k fixed) in the digital expansion of n in base q. We also give a large class of polynomials acting on the digital blocks that allow to get a prime number theorem and asymptotic orthogonality with the Möbius function. In Chapter 2, we get an asymptotic formula in the case of our function is the exponential of the function which counts blocks of consecutive ‘1’s in the expansion of n in base 2, where the length of the block is an increasing function that tends (slowly) to infinity. In the extremal case, which we cannot handle, this problem is connected to estimating the number of primes in the sequences of Mersenne numbers. In Chapter 3, we provides estimates on the case of the function is the exponential of a function which count the blocks of k ‘1’s in the expansion of n in base 2 where k is large with respect to log N. A consequence of Chapter 3 is that the results of Chapter 1 are quasi-optimal.

Efficient implementation of the number theoretic transform(NTT), also known as the discrete Fourier transform(DFT) over a finite field, has been studied actively for decades and found many applications in digital signal processing. In 1971 Schonhage and Strassen proposed an NTT based asymptotically fast multiplication method with the asymptotic complexity O(m log m log log m) for multiplication of $m$-bit integers or (m-1)st degree polynomials. Schonhage and Strassen's algorithm was known to be the asymptotically fastest multiplication algorithm until Furer improved upon it in 2007. However, unfortunately, both algorithms bear significant overhead due to the conversions between the time and frequency domains which makes them impractical for small operands, e.g. less than 1000 bits in length as used in many applications. With this work we investigate for the first time the practical application of the NTT, which found applications in digital signal processing, to finite field multiplication with an emphasis on elliptic curve cryptography(ECC). We present efficient parameters for practical application of NTT based finite field multiplication to ECC which requires key and operand sizes as short as 160 bits in length. With this work, for the first time, the use of NTT based finite field arithmetic is proposed for ECC and shown to be efficient. We introduce an efficient algorithm, named DFT modular multiplication, for computing Montgomery products of polynomials in the frequency domain which facilitates efficient multiplication in GF(p^m). Our algorithm performs the entire modular multiplication, including modular reduction, in the frequency domain, and thus eliminates costly back and forth conversions between the frequency and time domains. We show that, especially in computationally constrained platforms, multiplication of finite field elements may be achieved more efficiently in the frequency domain than in the time domain for operand sizes relevant to ECC. This work presents the first hardware implementation of a frequency domain multiplier suitable for ECC and the first hardware implementation of ECC in the frequency domain. We introduce a novel area/time efficient ECC processor architecture which performs all finite field arithmetic operations in the frequency domain utilizing DFT modular multiplication over a class of Optimal Extension Fields(OEF). The proposed architecture achieves extension field modular multiplication in the frequency domain with only a linear number of base field GF(p) multiplications in addition to a quadratic number of simpler operations such as addition and bitwise rotation. With its low area and high speed, the proposed architecture is well suited for ECC in small device environments such as smart cards and wireless sensor networks nodes. Finally, we propose an adaptation of the Itoh-Tsujii algorithm to the frequency domain which can achieve efficient inversion in a class of OEFs relevant to ECC. This is the first time a frequency domain finite field inversion algorithm is proposed for ECC and we believe our algorithm will be well suited for efficient constrained hardware implementations of ECC in affine coordinates.