In this paper we study the error behavior of the well known fast Fourier transform for nonequispaced data (NFFT) with respect to the L2-norm. We compare the arising errors for different window functions and show that the accuracy of the algorithm can be significantly improved by modifying the shape of the window function. Based on the considered error estimates for different window functions we are able to state an easy and efficient method to tune the involved parameters automatically. The numerical examples show that the optimal parameters depend on the given Fourier coefficients, which are assumed not to be of a random structure or roughly of the same magnitude but rather subject to a certain decrease.

The Discrete Fourier Transform (DFT) and its improved formulations, the Fast Fourier Transforms (FFTs), are vital for scientists and engineers in a range of domains from signal processing to the solution of partial differential equations.  A growing trend in Scientific Computing is heterogeneous computing, where accelerators are used instead or together with CPUs. This has led to problems for developers in unifying portability, performance, and productivity.  This thesis first motivates this work by showing the importance of having efficient DFT calculations, describes the DFT algorithm and a formulation based on matrix-factorizations which has been developed to formulate FFT algorithms and express their parallelism to exploit modern computer architectures, such as accelerators. The first paper is a motivating study of the breakdown of the performance and scalability of the high-performance Molecular Dynamics code GROMACS where DFT calculations are a main performance bottleneck. In particular, the long-range interactions are solved with the Particle-Mesh Ewald algorithm which uses a three-dimensional Fast Fourier Transform.  The two following papers present two approaches to leverage factorization with the help of two different frameworks using Intermediate Representation and compiler technology, for the development of fast and portable code. The second paper presents a front-end and a pipeline for code generation in a domain-specific language based on Multi-Level Intermediate Representation (MLIR) for developing Fast Fourier Transform libraries. The last paper investigates and optimizes an implementation of an important kernel within the matrix-factorization framework: the batched DFT. It is implemented with data-centric programming and a data-centric intermediate representation called Stateful Dataflow multi-graphs (SDFG). The paper evaluates strategies for complex-valued data layout for performance and portability and we show that there is a trade-off between portability and maintainability in using the native complex data type and that an SDFG-level abstraction could be beneficial for developing higher-level applications. / Den diskreta Fouriertransformen och dess snabba implementeringar är viktiga för vetenskap och ingenjörskonst. Den har tillämningar i ämnen som singnal behnadling, lösning av partiella diffrentialekvationer och många andra ämnen inom vetenskapliga beräkningar. En växande trend inom ämnet är heterogena datorer där acceleratorer som är specialicerade till vissa beräkningar kan användas som stöd för traditionella processorer. Detta leder till problem med portabilitet, prestanda och produktivitet.  Avhandligen inleds med att beskriva diskret Fouriertransform och ett ramverk för faktorisering till glesa strukturerade matriser som tillsammans representerar snabb Fouriertransform (FFT, Eng.) och som kan användas för att uttrycka parallelism i algorithmerna. För att motivera arbete med FFT i vetenskapliga beräkningar så utväreras den parallela prestandan av GROMACS: en kod för simulering av Molekyldynmik. GROMACS använder en tredimensionell diskret Fouriertransform för att finna den elektrostatiska potentialen med hjälp av Particle-Mesh Ewald-tekniken.  De följande två artiklarna presenterar två olika ramverk för att utnyttja mellankod (IR Eng.) och kompilatorteknik, för utvecklandet av  snabb och portabel kod. Den andra artikeln beskriver arbetet att utveckla ett domänspecifikt språk baserat på Multi-Level Intermediate Representation för design av snabba Fouriertransformer baserat på matrisfaktorisering. Den sista artikeln undersöker och optimerar en viktig komponent för matrisfaktorisering av diskreta Fouriertransformen: att beräkna flera små diskreta Fouriertransformer parallelt. Detta är gjort med DaCe som är ramverk för data-centrisk programmering som använder en mellankod kallad SDFG. I artikeln utvärderas strategier för data format av komplexa tal för prestanda och portabilitet, och visar att en abstraktion med hjälp av SDFG kan motiveras. / <p>QC 20230522</p>

This thesis concerns the mathematics and application of various methods for approximating matrices, with a particular eye towards the role that such methods play in image compression. An image is stored as a matrix of values with each entry containing a value recording the intensity of a corresponding pixel, so image compression is essentially equivalent to matrix approximation. First, we look at the singular value decomposition, one of the central tools for analyzing a matrix. We show that, in a sense, the singular value decomposition is the best low-rank approximation of any matrix. However, the singular value decomposition has some serious shortcomings as an approximation method in the context of digital images. The second method we consider is the discrete Fourier transform, which does not require the storage of basis vectors (unlike the SVD). We describe the fast Fourier transform, which is a remarkably efficient method for computing the discrete cosine transform, and how we can use this method to reduce the information in a matrix. Finally, we look at the discrete cosine transform, which reduces the complexity of the calculation further by restricting to a real basis. We also look at how we can apply a filter to adjust the relative importance of the data encoded by the discrete cosine transform prior to compression. In addition, we developed code implementing the ideas explored in the thesis and demonstrating examples.

No description available.

This thesis focuses on the simulation of the gyroscopic effect using the software MSC Adams. A simple shaft-disk system was created and parameter of the sys-tem were changed in order to study the influence of the gyroscopic effect. It was shown that an increasing bearing stiffness reduces the precession motion. Fur-thermore, it was shown that the gyroscopic effect vanishes if the disk of system is placed symmetrically on the shaft, which reduces the system to a Jeffcott-Ro-tor. The second objective of this study was to analyze different defects in a simple fixed axis gear set. In particular, a cracked shaft, a cracked pinion and a chipped pinion as well as a healthy gear system were created and tested in Adams. The contact force between the two gears was monitored and the 2D and 3D frequency spectrum, as well as the Wavelet Transform, were plotted in order to compare the individual defects. It was shown that the Wavelet Transform is a powerful tool, capable of identifying a cracked gear with a non-constant speed. The last part of this study included fault detection with statistical methods as well as with the Sideband Energy Ratio (SER). The time domain signal of the individual faults were used to compare the mean, the standard deviation and the root mean square. Furthermore, the noise profile in the frequency spectrum was tracked with statistical methods using the mean and the standard deviation. It was demonstrated that it is possible to identify a cracked gear, as well as a chipped gear, with statistical methods. However, a cracked shaft could not be identified. The results also show that SER was only capable to identify major defects in a gear system such as a chipped tooth.

The aim of this bachelor's thesis is to use three variants of the discrete Fourier transform (DFT) and compare their computational cost. The transformation will be used to numerically solve partial differential equations (PDE). In its simplest form, the DFT can be regarded as a matrix multiplication. It turns out that this matrix has some nice properties that we can exploit. Namely that it is well-conditioned and the inverse of the matrix elements is similar to the original matrix element, which will simplifies the implementation. Also, the matrix can be rewritten using different properties of complex numbers to reduce computational cost. It turns out that each transformation method has its own benefits and drawbacks. One of the methods makes the cost lower but can only use data of a fixed size. Another method needs a specific library to work but is way faster than the other two methods. The type of PDE that will be solved in this thesis are advection and diffusion, which aided by the Fourier transform, can be rewritten as a set of ordinary differential equations (ODE). These ODEs can then be integrated in time with a Runge-Kutta method. / Detta kandidatarbete går ut på att betrakta tre olika diskreta fouriertransformer och jämföra deras beräkningstid. Fouriertransformen används sedan också för att lösa partiella differentialekvationer (PDE). Fouriertransformerna som betraktas kan ses som en matrismultiplikation. Denna matrismultiplikation visar sig har trevliga egenskaper. Nämligen att matrisen är välkonditionerad och att matrisinversen element liknar ursprungsmatrisens element, vilket kommer underlätta implementationen. Matrisen kan dessutom skrivas om genom diverse samband hos komplexa tal för att få snabbare beräkningstid. PDE:na som betraktas i detta kandiatarbete är advektions och diffusions, vilket med speciella antaganden kan skrivas om till en ordinär differentialekvation som löses med en Runge-Kutta metod. Fouriertransformen används för att derivera, då det motsvarar en multiplikation. Det visar sig att alla metoder har fördelar och nackdelar. Ena metoden gör beräkningen snabbare men kan endast använda sig av datamängder av viss storlek. Andra metoden kräver ett specifikt bibliotek för att fungera men är mycket snabbare än de andra två.

To a large extent mathematical transforms are applied on a signal to uncover information that is concealed, and the capability of such transforms is valuable for signal processing. One such transforms widely used in this area, is the conventional Fourier Transform (FT), which decomposes a stationary signal into different frequency components. However, a major drawback of the conventional transform is that it does not easily render itself to the analysis of non-stationary signals such as a frequency modulated (FM) or amplitude modulated (AM) signal. The different frequency components of complex signals cannot be easily distinguished and separated from one another using the conventional FT. So in this thesis an innovative mathematical transform, Fractional Fourier Transform (FRFT), has been considered, which is more suitable to process non-stationary signals such as FM signals and has the capability not only of distinguishing different frequency components of a multi-component signal but also separating them in a proper domain, different than the traditional time or frequency domain. The discrete-time FRFT (DFRFT) developed along with its derivatives, such as Multi-angle-DFRFT (MA-DFRFT), Slanted Spectrum and Spectrogram Based on Slanted Spectrum (SBSS) are tools belonging to the same FRFT family, and they could provide an effective approach to identify unknown signals and distinguish the different frequency components contained therein. Both artificial stationary and FM signals have been researched using the DFRFT and some derivative tools from the same family. Moreover, to accomplish a contrast with the traditional tools such as FFT and STFT, performance comparisons are shown to support the DFRFT as an effective tool in multi-component chirp signal analysis. The DFRFT taken at the optimum transform order on a single-component FM signal has provided higher degree of signal energy concentration compared to FFT results; and the Slanted Spectrum taken along the slant line obtained from the MA-DFRFT demonstration has shown much better discrimination between different frequency components of a multi-component FM signal. As a practical application of these tools, the motor current signal has been analyzed using the DFRFT and other tools from FRFT family to detect the presence of a motor bearing fault and obtain the fault signature frequency. The conclusion drawn about the applicability of DFRFT and other derivative tools on AM signals with very slowly varying FM phenomena was not encouraging. Tools from the FRFT family appear more effective on FM signals, whereas AM signals are more effectively analyzed using traditional methods like spectrogram or its derivatives. Such methods are able to identify the signature frequency of faults while using less computational time and memory.

No description available.

<p>There is a lot of applications for DSPs (Digital Signal Processor) in the most rapidly growing areas in the industry right now as wireless communication along with audio and video products are getting more and more popular. In this report, a DSP, developed at the division of Computer Engineering at the University of Linköping, is optimized and verified.</p><p>Register Forwarding was implemented on a general architecture level to avoiddata hazards that may arise when implementing instruction pipelining in a processor.</p><p>The very common FFT algorithm is also optimized but on instruction setlevel. That means the algorithm is carefully analyzed to find operations that mayexecute in parallel and then create new instructions for these parallel operations.The optimization is concentrated on the butterfly operation as it is such a majorpart of the FFT computation. Comparing the accelerated butterfly with the unaccelerated gives an improvement of 30% in terms of clock cycles needed for thecomputation.</p><p>In the report there are also some discussions about the benefits and drawbacksof changing from a hardware to a software stack, mostly in terms of interrupts andthe return instruction.</p><p>Another important property of the processor is scalability. That is, it is possibleto attach extra peripherals to the core, which accelerates certain tasks. Aninterface towards these peripherals is developed along with two template designsthat may be used to develop other peripherals.</p><p>After all these modifications, a new test bench is developed to verify the functionality.</p>

In flexible fitting, the high-resolution crystal structure of a molecule is deformed to optimize its position with respect to a low-resolution density map. Solving the flexible fitting problem entails answering the following questions: (A) How can the crystal structure be deformed? (B) How can the term "optimum" be defined? and (C) How can the optimization problem be solved? In this dissertation, we answer the above questions in reverse order. (C) We develop PFCorr, a non-uniform SO(3)-Fourier-based tool to efficiently conduct rigid-body correlations over arbitrary subsets of the space of rigid-body motions. (B) We develop PF2Fit, a rigid-body fitting tool that provides several useful definitions of the optimal fit between the crystal structure and the density map while using PFCorr to search over the space of rigid-body motions (A) We develop PF3Fit, a flexible fitting tool that deforms the crystal structure with a hierarchical domain-based flexibility model while using PF2Fit to optimize the fit with the density map. Our contributions help us solve the rigid-body and flexible fitting problems in unique and advantageous ways. They also allow us to develop a generalized framework that extends, breadth-wise, to other problems in computational structural biology, including rigid-body and flexible docking, and depth-wise, to the question of interpreting the motions inherent to the crystal structure. Publicly-available implementations of each of the above tools additionally provide a window into the technically diverse fields of applied mathematics, structural biology, and 3D image processing, fields that we attempt, in this dissertation, to span. / text