We propose using overlapping, tapered windows to process seismic data in parallel. This method consists of numerically tight linear operators and adjoints that are suitable for use in iterative algorithms. This method is also highly scalable and makes parallel processing of large seismic data sets feasible. We use this scheme to define the Parallel Windowed Fast Discrete Curvelet Transform (PWFDCT), which we apply to a seismic data interpolation algorithm. The successful performance of our parallel processing scheme and algorithm on a two-dimensional synthetic data is shown.

This thesis develops a generic framework based on the Fourier transform for pricing and hedging of various options in equity, commodity, currency, and insurance markets. The pricing problem can be reduced to solving a partial integro-differential equation (PIDE). The Fourier Space Time-stepping (FST) framework developed in this thesis circumvents the problems associated with the existing finite difference methods by utilizing the Fourier transform to solve the PIDE. The FST framework-based methods are generic, highly efficient and rapidly convergent. The Fourier transform can be applied to the pricing PIDE to obtain a linear system of ordinary differential equations that can be solved explicitly. Solving the PIDE in Fourier space allows for the integral term to be handled efficiently and avoids the asymmetrical treatment of diffusion and integral terms, common in the finite difference schemes found in the literature. For path-independent options, prices can be obtained for a range of stock prices in one iteration of the algorithm. For exotic, path-dependent options, a time-stepping methodology is developed to handle barriers, free boundaries, and exercise policies. The thesis includes applications of the FST framework-based methods to a wide range of option pricing problems. Pricing of single- and multi-asset, European and path-dependent options under independent-increment exponential Levy stock price models, common in equity and insurance markets, can be done efficiently via the cornerstone FST method. Mean-reverting Levy spot price models, common in commodity markets, are handled by introducing a frequency transformation, which can be readily computed via scaling of the option value function. Generating stochastic volatility, to match the long-term equity options market data, and stochastic skew, observed in currency markets, is addressed by introducing a non-stationary extension of multi-dimensional Levy processes using regime-switching. Finally, codependent jumps in multi-asset models are introduced through copulas. The FST methods are computationally efficient, running in O(MN^d log_2 N) time with M time steps and N space points in each dimension on a d-dimensional grid. The methods achieve second-order convergence in space; for American options, a penalty method is used to attain second-order convergence in time. Furthermore, graphics processing units are utilized to further reduce the computational time of FST methods.

This thesis presents a method for dynamic characterization of MEMS structures and discuses parameters that affect its measurements and techniques to improve them. Current methods of non-contact, laser based vibration measurement require special and expensive instruments. The method used in this thesis on the other hand, relies on Fast Fourier Transform analysis of blurred images captured using conventional cameras. The Fourier series analysis and transformation are introduced. Basic concepts of blur image analysis and associated technical terms are described. Step by step data extraction process for Fourier analysis of blurred images and results such as amplitude, attenuation, signal to noise ratio and Bessel curve are explained. Macro and micro scale experiments are designed and used to determine the effect and significance of different parameters on signal-to-noise ratio of extracted results. For this purpose geometrical parameters of macro scale combs such as length, width and duty cycle are varied across a considerable range and tests results are examined. In addition to the experiments, MATLAB code is used to model environmental effects such as addition of noise or changes of brightness. In micro scale experiments, extra patterns are created using Focused Ion Beam and etching process. Test and comparison of modified micro structures with unpatterned structures show improvement in signal to noise ratio especially in environments with high level of noise.

This thesis develops a generic framework based on the Fourier transform for pricing and hedging of various options in equity, commodity, currency, and insurance markets. The pricing problem can be reduced to solving a partial integro-differential equation (PIDE). The Fourier Space Time-stepping (FST) framework developed in this thesis circumvents the problems associated with the existing finite difference methods by utilizing the Fourier transform to solve the PIDE. The FST framework-based methods are generic, highly efficient and rapidly convergent. The Fourier transform can be applied to the pricing PIDE to obtain a linear system of ordinary differential equations that can be solved explicitly. Solving the PIDE in Fourier space allows for the integral term to be handled efficiently and avoids the asymmetrical treatment of diffusion and integral terms, common in the finite difference schemes found in the literature. For path-independent options, prices can be obtained for a range of stock prices in one iteration of the algorithm. For exotic, path-dependent options, a time-stepping methodology is developed to handle barriers, free boundaries, and exercise policies. The thesis includes applications of the FST framework-based methods to a wide range of option pricing problems. Pricing of single- and multi-asset, European and path-dependent options under independent-increment exponential Levy stock price models, common in equity and insurance markets, can be done efficiently via the cornerstone FST method. Mean-reverting Levy spot price models, common in commodity markets, are handled by introducing a frequency transformation, which can be readily computed via scaling of the option value function. Generating stochastic volatility, to match the long-term equity options market data, and stochastic skew, observed in currency markets, is addressed by introducing a non-stationary extension of multi-dimensional Levy processes using regime-switching. Finally, codependent jumps in multi-asset models are introduced through copulas. The FST methods are computationally efficient, running in O(MN^d log_2 N) time with M time steps and N space points in each dimension on a d-dimensional grid. The methods achieve second-order convergence in space; for American options, a penalty method is used to attain second-order convergence in time. Furthermore, graphics processing units are utilized to further reduce the computational time of FST methods.

Nonlinear mesoscopic elastic (NME) materials present ananomalous nonlinear elastic behavior, which could not beexplained by classical theories. New physical mechanismsshould be individuated to explain NMEs response.Dislocations in damaged metals, fluids in rocks andadhesion (in composites) could be plausible. In this thesisI have searched for differences in the macroscopic elasticresponse of materials which could be ascribed to differentphysical processes. I have found that the nonlinearindicators follow a power law behavior as a function of theexcitation energy, with exponent ranging from 1 to 3 (thisis not completely new). This allowed to classify materialsinto well-defined classes, each characterized by a value ofthe exponent and specific microstructural properties. Tolink the measured power law exponent to plausiblephysical mechanisms, I have extended thePreisach-Mayergoyz formalism for hysteresis to multi-statemodels. Specific multi-state discrete models have beenderived from continuous microscopic physical processes,such as adhesion-clapping, adhesion-capillary forces,dislocations motion and hysteresis. In each model, themicroscopic behavior is described by a multistate equationof state, with parameters which are statisticallydistributed. Averaging over many microscopic elements theso-called mesoscopic equation of state is derived and, fromwave propagation simulations in a sample composed bymany mesoscopic elements, the experimental results couldbe reproduced. In the work of the thesis, I have shownthat model predictions of the exponent b ( the exponent bhas not been introduced before) are linked in a 'a priori'predictable way to the number of states and the propertiesof the statistical distribution adopted. We have classifiedmodels into classes defined by a different exponent b andcomparing with experimental results we have suggestedplausible mechanisms for the nonlinearity generation.

The Fast Fourier Transform (FFT) has been used in many scientific and engineering applications. The use of FFT for financial derivatives has been gaining momentum in the recent past. In this thesis, i) we have improved a recently proposed model of FFT for pricing financial derivatives to help design an efficient parallel algorithm. The improved mathematical model put forth in our research bridges a gap between quantitative approaches for the option pricing problem and practical implementation of such approaches on modern computer architectures. The thesis goes further by proving that the improved model of fast Fourier transform for option pricing produces accurate option values. ii) We have developed a parallel algorithm for the FFT using the classical Cooley-Tukey algorithm and improved this algorithm by introducing a data swapping technique that brings data closer to the respective processors and hence reduces the communication overhead to a large extent leading to better performance of the parallel algorithm. We have tested the new algorithm on a 20 node SunFire 6800 high performance computing system and compared the new algorithm with the traditional Cooley-Tukey algorithm. Option values are calculated for various strike prices with a proper selection of strike-price spacing to ensure fine-grid integration for FFT computation as well as to maximize the number of strikes lying in the desired region of the stock price. Compared to the traditional Cooley-Tukey algorithm, the current algorithm with data swapping performs better by more than 15% for large data sizes. In the rapidly changing market place, these improvements could mean a lot for an investor or financial institution because obtaining faster results offers a competitive advantages.

Three different algorithms for the generation of stationary Gaussian time series with given autocorrelation function are presented in this paper. The algorithms have already been suggested in the literature but are not well known and have never been compared before. Interrelations between the different methods, advantages and disadvantages with respect to speed and memory requirements and the range of autocorrelation functions for which the different methods are stable are discussed. The time-complexity of the algorithms and the comparisons of their implementations show that the method twice using the Fourier transform is by far the most efficient if time series of moderate or large length are generated. A tested C-code of the latter algorithm is included as this method is tricky to implement and very difficult to find in the literature. (We know only one reference, that gives a correct algorithm, but there the description is very short and no proof is included.) (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

The Fast Fourier Transform (FFT) has been used in many scientific and engineering applications. The use of FFT for financial derivatives has been gaining momentum in the recent past. In this thesis, i) we have improved a recently proposed model of FFT for pricing financial derivatives to help design an efficient parallel algorithm. The improved mathematical model put forth in our research bridges a gap between quantitative approaches for the option pricing problem and practical implementation of such approaches on modern computer architectures. The thesis goes further by proving that the improved model of fast Fourier transform for option pricing produces accurate option values. ii) We have developed a parallel algorithm for the FFT using the classical Cooley-Tukey algorithm and improved this algorithm by introducing a data swapping technique that brings data closer to the respective processors and hence reduces the communication overhead to a large extent leading to better performance of the parallel algorithm. We have tested the new algorithm on a 20 node SunFire 6800 high performance computing system and compared the new algorithm with the traditional Cooley-Tukey algorithm. Option values are calculated for various strike prices with a proper selection of strike-price spacing to ensure fine-grid integration for FFT computation as well as to maximize the number of strikes lying in the desired region of the stock price. Compared to the traditional Cooley-Tukey algorithm, the current algorithm with data swapping performs better by more than 15% for large data sizes. In the rapidly changing market place, these improvements could mean a lot for an investor or financial institution because obtaining faster results offers a competitive advantages.

We present the application of the boundary integral equation method for solving the motion of biological cell or particle under Stokes flow in the presence of electrostatic field. The huge dense matrix-vector product from the boundary integral method poses a computationally challenging problem for solving the large system of equations generated. In our work, we used the precorrected-FFT (pFFT) method to reduce the computational time and memory usage drastically, so that large scale simulations can be performed quickly on a personal computer. Results on the force field acting on the particle, as well as the behavior of the particle through cell trap are presented. / Singapore-MIT Alliance (SMA)

Modern embedded systems complexity, performance and energy efficiency has been increasing steeply the last few years. An explosive growth in demand for wireless communication is observed as well and modern wireless links are expected to deliver bit rates of several gigabits while consuming even less energy. In order to satisfy these needs new technologies emerge and novel design approaches are put into practice. Communication at 60 GHz is such a technology that is able to deliver high bit rates in short range wireless links. A major motivation to use the 60 GHz spectrum is the worldwide availability which makes exploitation economically viable. Moreover, small wavelength of only 5 mm promises high integration due to small antenna component size which is one of the main bottlenecks for reducing the dimensions. However, increased frequency comes with many disadvantages as well. To increase the market potential of such a new technology the chip design needs to be cheap and energy-efficient. Such cost and energy constrains heavily impact the performance and the quality of both the analog and the digital components of the chip. In the current thesis the design possibilities of a component in the digital baseband of the receiver of such a chip are explored. The component under investigation is a Fast Fourier Transform (FFT) that is used for frequency domain equalization. This part of the receiver is used to reduce the effects of multipath in a non line-ofsight communication environment and as this is a common case in wireless communication the FFT block has been identified as one of the 2 most computational intensive components of the receiver in 60 GHz. This is the main reason why we explore possibilities to further decrease the power consumption of the block while maintaining the performance and the quality of service. To achieve this reduction the possibilities of a new design concept are explored. System Scenarios is a new design concept for embedded systems operating in dynamic environments. Wireless communication systems exhibit high dynamism during their operation on highly varying data streams, providing the System Scenarios huge xvi capabilities. The essential idea behind system scenarios is the classification of the application under investigation from a cost perspective during design time. Then, the classification is exploited during run time resulting to an overall improved implementation of the application. To achieve this the application is broken down to run-time situations (RTS) which are distinguishable operation modes of the application. Then RTSs with similar costs are clustered to form system scenarios. Finally for each scenario a different mapping and scheduling of the application is generated. In the case of the current thesis the application is the FFT and the cost perspective is the power consumption of the component. To exploit the RTS clustering in run time different quantization schemes have been produced. These schemes have been generated based on various properties of the data waveforms in the input of the FFT. The thesis explores the potential of the System Scenarios as well as the application of a quantization methodology for the FFT. Different options of the RTS clustering and the quantization of the FFT block are evaluated in order to come up with a more efficient implementation. / Τα σύγχρονα ηλεκτρονικά συστήματα παρέχουν στους χρήστες έναν καθημερινά αυξανόμενο αριθμό υπηρεσιών και λειτουργιών. Η ζήτηση τς αγοράς για ϕθηνές, αξιόπιστες και ϕορητές ηλεκτρονικές συ- σκευές ωθεί τα όρια του σχεδιασμού των ενσωματωμένων συστημάτων σε νέες ανεξερεύνητες περιοχές. Η ϕορητότητα απαιτεί την αϕαίρεση όλων των καλωδίων είτε για μετάδοση δεδομένων είτε για ενέργεια. Για να επιτευχθεί αυτό, η ασύρματη επικοινωνία σε υψηλό ρυθμό μετάδοσης είναι επιθυμητή χωρίς να θυσιαστεί η υψηλή ενεργειακή απο- δοτικότητα που καθιστά την συσκευή αυτόνομη από το ενεργειακό δίκτυο για μεγάλες χρονικές περιόδους. Η συνεχής αύξηση στις προδιαγραϕές των σύγχρονων ενσωματομένων συστημάτων έχει οδηγήσει στην χρήση καινοτόμων ιδεών, προσεγγίσεων και τεχνολογιών. Μια νέα τεχνολογία που υπόσχεται υψηλή ολοκλήρωση και υψηλό ρυθμό μετάδοσης δεδομένων στις ασύρματες ζεύξεις είναι η επικοινωνία στα 60 GHz. Μια νέα προσέγγιση σχεδιασμού για ενσωματομένα συστήματα υπόσχεται αποτελεσματική εκμετάλευση του δυναμισμού που μπορεί να παρουσιάζει ένα σύστημα. Τα ασύρματα συστήματα επικοινωνίας λειτουργούν τυπικά σε πολύ δυναμικά περιβάλλοντα. Τα Σενάρια συστήματος έχουν μεγάλες δυνατότητες για να βελτιώσουν την αποτελεσματικότητα της υλοποίησης των ψηϕιακών βάσεων τέτοιων συστημάτων. Στην παρούσα διπλωματική εξερευνούμε της δυνατότητες της αρχιτεκτονικής του FFT που βρίσκεται στην πλευρά του δέκτη ενός πομποδέκτη στα 60 GHz. Ο FFT είναι μέρος της εξίσωσης στο πεδίο της συχνότητας που χρησιμοποιείται για να μειώσει της επιδράσεις του ϕαινομένου multipath. Χρησιμοποιώντας Σενάρια Συστήματος προσπαθούμε να καταλήξουμε με μια πιο προσαρμοστική και συνεπώς πιο ενεργειακά αποδοτική υλοποίηση του μετασχηματισμού. Η εϕαρμογή των Σεναρίων Συστήματος χρησιμοποιώντας δεδομένα ως παράμετρο είναι μια καινοτόμα προσέγγιση και σε αυτή την διπλωματική εργασία ελέγχουμε την επιτευξιμότητα της. Για να επιτύχουμε κάτι τέτοιο πρέπει να μπορούμε να παράγουμε πολλαπλά διαϕορετικά σχέδια κβαντοποίησης του μετασχηματισμού σε αποδεκτά χρονικά διαστήματα. Οι παρούσες μέθοδοι κβαντοποίησης δεν μπορούν ακόμα να παρέχουν τέτοια δυνατότητα. Έτσι βασιζόμενοι στην επέκταση μια υπάρχουσας μεθοδολογίας προτείνουμε μια ολοκληρωμένη μεθοδολογία που μπορεί να παράγει σχέδια κβαντοποίησης μεγάλων στοιχείων υλικού όπως ο FFT.