In this thesis, the multi-carrier (MC) code division multiple access (CDMA) system is considered in Rayleigh fading channel. The main concern of this thesis is to devise a new direct linearly constrained constant modulus (LCCM) inverse QRD-RLS algorithm for multiple access interference (MAI) cancellation and the problem due to the mismatch of the channel estimator. In the conventional approach, two significant detectors are applied to the system for multiuser interference suppression, one is the blind adaptation algorithm and the other is adaptive linearly constrained PLIC approach. However, the mirror effect may occur when the blind adaptation algorithm is employed. It might affect the performance in terms of bit error rate (BER), although the desired signal to interference (due to other users) improvement is still acceptable. Moreover, in case that the channel coefficients could not be estimated perfectly, the mismatch problem may occur to degrade the performance of the adaptive linearly constrained PLIC approach with the LMS or RLS algorithm. To overcome the mismatch problem, the conventional approach is to use the LCCM criterion with gradient algorithm. However, the convergence rate of the gradient algorithm is too slow to be implemented in real-time wireless communication system. In this thesis, to have fast convergence rate and to circumvent the mismatch problem, the robust LCCM-IQRD algorithm is devised and applied to the MC-CDMA system in Rayleigh fading channel. The proposed robust LCCM-IQRD algorithm has shown to be more effective in terms of MAI cancellation and the mismatch due to imperfect channel estimator. The performance, in terms of BER, of the proposed algorithm is superior to that of the conventional PLIC based algorithms, the blind adaptation algorithm, and the conventional LCCM gradient algorithm.

The convergence speed using the conventional approaches, viz., time-domain adaptive constrained and unconstrained LMS algorithms, becomes slowly, when dealing with the correlated source signals. In consequence, the performance of time delay estimation (TDE) will be degraded, dramatically. To improve this problem, the so-called transform-domain adaptive constrained filtering scheme, i.e., the adaptive constrained discrete-cosine-transform (DCT) LMS algorithm, has been proposed in [15]. However, the use of any one orthogonal transform will not result in a completely diagonal the input signal auto-correlation matrix for all types of input signals. In fact, the significant non-diagonal entries in the transform-domain auto-correlation matrix, will deteriorate the convergence performance of the algorithm. To further overcome the problem described above, in this thesis, a modified approach, referred as the adaptive constrained modified DCT-LMS (CMDCT-LMS) algorithm, is devised for TDE under a wide class of input processes. In addition, based on the orthogonal discrete wavelet transform (DWT), an adaptive constrained modified DMT-LMS (CMDWT-LMS) algorithm is also devised and applied to the problem of TDE. We show that the proposed two modified constrained approaches for TDE does perform well than the unmodified approaches under different source signal models. Moreover, the adaptive CMDCT-LMS filtering algorithm does perform slightly better than the adaptive CMDWT-LMS filtering algorithm as observed from the simulation results.

In this thesis, the problem of multiple access interference (MAI) suppression for the multi-carrier (MC) code division multiple access (CDMA) system, based on the wavelet-based (WB) multi-carrier modulation, associated with the combining process is investigated for Rayleigh fading channel. The main concern of this thesis is to derive a new scheme, based on the linearly constrained constant modulus (LCCM) criterion with the robust inverse QR decomposition (IQRD) recursive least squares (RLS) algorithm to improve the performance of the conventional MC-CDMA system with combining process. To verify the merits of the new algorithm, the effect due to imperfect channel parameters estimation and frequency offset are investigated. We show that the proposed robust LCCM IQRD-RLS algorithm outperforms the conventional LCCM-gradient algorithm [6], in terms of output SINR, improvement percentage index (IPI), and bit error rate (BER) for MAI suppression under channel mismatch environment. Also, the performance of the WB MC-CDMA system is superior to the one with conventional MC-CDMA system. It is more robust to the channel mismatch and frequency offset. Moreover, the WB MC-CDMA system with robust LCCM IQRD-RLS algorithm does have better performance over other conventional approaches, such as the LCCM-gradient algorithm, maximum ratio combining (MRC), blind adaptation algorithm and partitioned linear interference canceller (PLIC) approach with LMS algorithm, in terms of the capability of MAI suppression and bit error rate (BER).

The technique of direct sequence spread spectrum (DS/SS) has been widely used in commercial mobile communication systems. The efficiency of DS/SS system is highly dependent on the accurate and fast synchronization between the incoming and locally generated PN (pseudo-noise) codes. The code synchronization is processed in two steps, acquisition (coarse alignment) and tracking (fine alignment), to bring the delay offset between the two codes. Conventionally, for code synchronization, most of techniques were proposed based on the correlation property of PN codes. Recently, the different approach, by using the adaptive LMS filtering scheme, has been proposed to reduce the hardware complexity and to improve the performance of code synchronization, especially for a long PN code. In this thesis, a new coherent adaptive code synchronization scheme is proposed, where the adaptive constrained LMS (CLMS) algorithm with the maximum tap-weight (MTW) test method is devised for code acquisition. The statistics of weight vector of the proposed CLMS scheme are derived to evaluate the performance, in terms of mean acquisition time (MAT). Analytical and simulation results verify that the proposed scheme for code acquisition outperforms the one using the conventional LMS filtering schemes, under the integer and non-integer time delay cases. Moreover, the setting of threshold value is derived for code acquisition, which is independent of the values of signal-to-noise ratio (SNR) and time delay. Next, the CLMS scheme is proposed associated with the direct delay estimation (DDE) formula for code tracking. This approach does achieve a good delay-tracking performance, which is verified via computer simulation. Simultaneously, the hardware complexity can further be reduced due to that a code-tracking loop implemented by the interpolation method is not required.

The conventional temporal filtering approach cannot be used to separate signal from interference which occupies the same temporal frequency band as signal. Using a spatial filtering at the receiver can separate signals from interference that originates from different spatial location. Many adaptive array beamforming algorithms, based on linear constraints, have been proposed for suppressing undesired interference and being applied to wireless communication systems for multiuser detection. The adaptive array system can be employed to automatically adjust its directional to achieve the purpose that nulls the interferences or jammers and thus, enhances the reception of the desired signal. Inverse QR Decomposition Recursive Least-square (IQRD-RLS) algorithm has many advantages such as where the LS weight vector be computed without back substitution, a well known numerical stable algorithm and offering better convergence rate, steady-state means-square error, and parameter tracking capability over the adaptive least mean square (LMS) based algorithms. In this thesis, a new application, GSC-IQRD-RLS combining Generalized Sidelobe Canceller (GSC) and IQRD-RLS algorithm, is developed. It preserves the advantages of GSC such as simple structure, less computations, and converts a linearly constrained optimization problem into a standard optimum filtering problem. But the performance is equivalent between GSC-IQRD-RLS and LC-IQRD-RLS algorithms.

In this dissertation, we study the single machine scheduling problem with an objective of minimizing the total completion time subject to release dates. The problem, denoted 1|rj £UCj ,was known to be strongly NP-hard and both theoretically and practically important. The focus of the research in this dissertation is to develop the efficient algorithms for solving the 1|rj|£UCj problem. This thesis contains two parts. In the first part, the theme concerns the approximation approach. We derive a necessary and sufficient condition for local optimality, which can be implemented as a priority rule and be used to construct three heuristic algorithms with running times of O(n log n). By ¡¨local optimality¡¨, we mean the optimality of all candidates whenever a job is selected in a schedule, without considering the other jobs preceding or following. This is the most broadly considered concepts of locally optimal rule. We also identify a dominant subset which is strictly contained in each of all known dominant subsets, where a dominant subset is a set of solutions containing all optimal schedules. In the second part, we develop our optimality algorithms for the 1|rj |£UCj problem. First, we present a lemma for estimating the sum of delay times of the rest jobs, if the starting time is delayed a period of time in a schedule. Then, using the lemma, partially, we proceed to develop a new partition property and three dominance theorems, that will be used and have improved the branch-and-bound algorithms for our optimization approach. By exploiting the insights gained from our heuristics as a branching scheme and by exploiting our heuristics as an upper bounding procedure, we propose three branch-and-bound algorithms. Our algorithms can optimally solve the problem up to 120 jobs, which is known to be the best till now.

This dissertation maps various kernels and applications to a spectrum of programming models and architectures and also presents architecture-aware algorithms for different systems. The kernels and applications discussed in this dissertation have widely varying computational characteristics. For example, we consider both dense numerical computations and sparse graph algorithms. This dissertation also covers emerging applications from image processing, complex network analysis, and computational biology. We map these problems to diverse multicore processors and manycore accelerators. We also use new programming models (such as Transactional Memory, MapReduce, and Intel TBB) to address the performance and productivity challenges in the problems. Our experiences highlight the importance of mapping applications to appropriate programming models and architectures. We also find several limitations of current system software and architectures and directions to improve those. The discussion focuses on system software and architectural support for nested irregular parallelism, Transactional Memory, and hybrid data transfer mechanisms. We believe that the complexity of parallel programming can be significantly reduced via collaborative efforts among researchers and practitioners from different domains. This dissertation participates in the efforts by providing benchmarks and suggestions to improve system software and architectures.

This thesis describes improvements of the periodic QZ algorithm and several variants of the Schur algorithm for block Toeplitz matrices. Documentation of the available software is included.

The paper "Parallel Genetic Algorithms" discusses the theoretical basics of Evolutionary Algorithms concentrating on Genetic Algorithms. Possibilities for a parallelization of these algorithms are examined and explained on the basis of concepts of parallel programming. A concrete suggestion for a practical realization of a parallel Genetic Algorithm at different levels of complexity is presented. / Die Studienarbeit zum Thema "Parallele Genetische Algorithmen" befasst sich mit den theoretischen Grundlagen Evolutionärer Algorithmen, wobei die Konzentration bei Genetischen Algorithmen liegt, und untersucht die Möglichkeiten einer parallelen Realisierung dieser Algorithmen. Des weiteren werden Konzepte der Parallelen Programmierung diskutiert sowie ein konkreter Vorschlag zur praktischen Realisierung eines parallelen Genetischen Algorithmus' auf verschiedenen Komplexitätsebenen vorgestellt.

The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the shortest distances and paths between vertices with any given single failure in constant time without reconstructing the oracle. Using their paper as a guideline, we have implemented their algorithm in C++ and recorded each step in this thesis. Each step has its own pseudo-code and its own analysis to prove that the entire oracle construction stays within the stated running time and total space bounds, from the authors. The effciency of the algorithm is compared against that of the brute-force methods total running time and total space needed. Using multiple test cases with an increasing number of vertices and edges, we have experimentally validated that their algorithm holds true to their statements of space, running time, and query time.