<p>The Stressometer system is a measurement and control system used in cold rolling to improve the flatness of a metal strip. In order to achieve this goal the system employs a multiple input multiple output (MIMO) control system that has a considerable number of sensors and actuators. As a consequence the computational load on the Stressometer control system becomes very high if too advance functions are used. Simultaneously advances in rolling mill mechanical design makes it necessary to implement more complex functions in order for the Stressometer system to stay competitive. Most industrial players in this market considers improved computational power, for measurement, control and modeling applications, to be a key competitive factor. Accordingly there is a need to improve the computational power of the Stressometer system. Several different approaches towards this objective have been identified, e.g. exploiting hardware parallelism in modern general purpose and graphics processors.</p><p>Another approach is to implement different applications in FPGA-based hardware, either tailored to a specific problem or as a part of hardware/software co-design. Through the use of a hardware/software co-design approach the efficiency of the Stressometer system can be increased, lowering overall demand for processing power since the available resources can be exploited more fully. Hardware accelerated platforms can be used to increase the computational power of the Stressometer control system without the need for major changes in the existing hardware. Thus hardware upgrades can be as simple as connecting a cable to an accelerator platform while hardware/software co-design is used to find a suitable hardware/software partition, moving applications between software and hardware.</p><p>In order to determine whether this hardware/software co-design approach is realistic or not, the feasibility of implementing simulator, computational and control applications in FPGAbased hardware needs to be determined. This is accomplished by selecting two specific applications for a closer study, determining the feasibility of implementing a Stressometer measuring roll simulator and a parallel Cholesky algorithm in FPGA-based hardware.</p><p>Based on these studies this work has determined that the FPGA device technology is perfectly suitable for implementing both simulator and computational applications. The Stressometer measuring roll simulator was able to approximate the force and pulse signals of the Stressometer measuring roll at a relative modest resource consumption, only consuming 1747 slices and eight DSP slices. This while the parallel FPGA-based Cholesky component is able to provide performance in the range of GFLOP/s, exceeding the performance of the personal computer used for comparison in several simulations, although at a very high resource consumption. The result of this thesis, based on the two feasibility studies, indicates that it is possible to increase the processing power of the Stressometer control system using the FPGA device technology.</p>

This thesis deals with the development of efficient and reliable algorithms and library software for factorizing matrices and solving matrix equations on high-performance computer systems. The architectures of today's computers consist of multiple processors, each with multiple functional units. The memory systems are hierarchical with several levels, each having different speed and size. The practical peak performance of a system is reached only by considering all of these characteristics. One portable method for achieving good system utilization is to express a linear algebra problem in terms of level 3 BLAS (Basic Linear Algebra Subprogram) transformations. The most important operation is GEMM (GEneral Matrix Multiply), which typically defines the practical peak performance of a computer system. There are efficient GEMM implementations available for almost any platform, thus an algorithm using this operation is highly portable. The dissertation focuses on how recursion can be applied to solve linear algebra problems. Recursive linear algebra algorithms have the potential to automatically match the size of subproblems to the different memory hierarchies, leading to much better utilization of the memory system. Furthermore, recursive algorithms expose level 3 BLAS operations, and reveal task parallelism. The first paper handles the Cholesky factorization for matrices stored in packed format. Our algorithm uses a recursive packed matrix data layout that enables the use of high-performance matrix--matrix multiplication, in contrast to the standard packed format. The resulting library routine requires half the memory of full storage, yet the performance is better than for full storage routines. Paper two and tree introduce recursive blocked algorithms for solving triangular Sylvester-type matrix equations. For these problems, recursion together with superscalar kernels produce new algorithms that give 10-fold speedups compared to existing routines in the SLICOT and LAPACK libraries. We show that our recursive algorithms also have a significant impact on the execution time of solving unreduced problems and when used in condition estimation. By recursively splitting several problem dimensions simultaneously, parallel algorithms for shared memory systems are obtained. The fourth paper introduces a library---RECSY---consisting of a set of routines implemented in Fortran 90 using the ideas presented in paper two and three. Using performance monitoring tools, the last paper evaluates the possible gain in using different matrix blocking layouts and the impact of superscalar kernels in the RECSY library.

The Stressometer system is a measurement and control system used in cold rolling to improve the flatness of a metal strip. In order to achieve this goal the system employs a multiple input multiple output (MIMO) control system that has a considerable number of sensors and actuators. As a consequence the computational load on the Stressometer control system becomes very high if too advance functions are used. Simultaneously advances in rolling mill mechanical design makes it necessary to implement more complex functions in order for the Stressometer system to stay competitive. Most industrial players in this market considers improved computational power, for measurement, control and modeling applications, to be a key competitive factor. Accordingly there is a need to improve the computational power of the Stressometer system. Several different approaches towards this objective have been identified, e.g. exploiting hardware parallelism in modern general purpose and graphics processors. Another approach is to implement different applications in FPGA-based hardware, either tailored to a specific problem or as a part of hardware/software co-design. Through the use of a hardware/software co-design approach the efficiency of the Stressometer system can be increased, lowering overall demand for processing power since the available resources can be exploited more fully. Hardware accelerated platforms can be used to increase the computational power of the Stressometer control system without the need for major changes in the existing hardware. Thus hardware upgrades can be as simple as connecting a cable to an accelerator platform while hardware/software co-design is used to find a suitable hardware/software partition, moving applications between software and hardware. In order to determine whether this hardware/software co-design approach is realistic or not, the feasibility of implementing simulator, computational and control applications in FPGAbased hardware needs to be determined. This is accomplished by selecting two specific applications for a closer study, determining the feasibility of implementing a Stressometer measuring roll simulator and a parallel Cholesky algorithm in FPGA-based hardware. Based on these studies this work has determined that the FPGA device technology is perfectly suitable for implementing both simulator and computational applications. The Stressometer measuring roll simulator was able to approximate the force and pulse signals of the Stressometer measuring roll at a relative modest resource consumption, only consuming 1747 slices and eight DSP slices. This while the parallel FPGA-based Cholesky component is able to provide performance in the range of GFLOP/s, exceeding the performance of the personal computer used for comparison in several simulations, although at a very high resource consumption. The result of this thesis, based on the two feasibility studies, indicates that it is possible to increase the processing power of the Stressometer control system using the FPGA device technology.

金融風暴過後，在預期全球景氣轉佳之下，將帶動原物料市場價格之走揚。故能源及基礎金屬商品等的投資需求增加，近年來也出現不少連結能源及商品的投資工具。加上現今低利率之經濟環境，使得投資人希望尋求有較市場利率高之獲利率的金融商品。 本論文採用市場上銷售的結構型商品來進行評價與分析，其為連結一籃子商品之保本型票券。本文以蒙地卡羅模擬法作產品之評價及分析，讓讀者充分瞭解產品結構、報酬型態與成本以及所面臨的風險；此外也從發行商的角度，並分析其可運用的避險策略。

In a wireless communication system the transmitted information is subjected to a number of impairments, among which inter-symbol interference (ISI), thermal noise and fading are the most prevalent. Owing to the dispersive nature of the communication channel, ISI results from the arrival of multiple delayed copies of the transmitted signal at the receiver. Thermal noise is caused by the random fluctuation on electrons in the receiver hardware, while fading is the result of constructive and destructive interference, as well as absorption during transmission. To protect the source information, error-correction coding (ECC) is performed in the transmitter, after which the coded information is interleaved in order to separate the information to be transmitted temporally. Turbo equalization (TE) is a technique whereby equalization (to correct ISI) and decoding (to correct errors) are iteratively performed by iteratively exchanging extrinsic information formed by optimal posterior probabilistic information produced by each algorithm. The extrinsic information determined from the decoder output is used as prior information by the equalizer, and vice versa, allowing for the bit-error rate (BER) performance to be improved with each iteration. Turbo equalization achieves excellent BER performance, but its computational complexity grows exponentially with an increase in channel memory as well as with encoder memory, and can therefore not be used in dispersive channels where the channel memory is large. A number of low complexity equalizers have consequently been developed to replace the maximum a posteriori probability (MAP) equalizer in order to reduce the complexity. Some of the resulting low complexity turbo equalizers achieve performance comparable to that of a conventional turbo equalizer that uses a MAP equalizer. In other cases the low complexity turbo equalizers perform much worse than the corresponding conventional turbo equalizer (CTE) because of suboptimal equalization and the inability of the low complexity equalizers to utilize the extrinsic information effectively as prior information. In this thesis the author develops two novel iterative low complexity turbo equalizers. The turbo equalization problem is modeled on superstructures, where, in the context of this thesis, a superstructure performs the task of the equalizer and the decoder. The resulting low complexity turbo equalizers process all the available information as a whole, so there is no exchange of extrinsic information between different subunits. The first is modeled on a dynamic Bayesian network (DBN) modeling the Turbo Equalization problem as a quasi-directed acyclic graph, by allowing a dominant connection between the observed variables and their corresponding hidden variables, as well as weak connections between the observed variables and past and future hidden variables. The resulting turbo equalizer is named the dynamic Bayesian network turbo equalizer (DBN-TE). The second low complexity turbo equalizer developed in this thesis is modeled on a Hopfield neural network, and is named the Hopfield neural network turbo equalizer (HNN-TE). The HNN-TE is an amalgamation of the HNN maximum likelihood sequence estimation (MLSE) equalizer, developed previously by this author, and an HNN MLSE decoder derived from a single codeword HNN decoder. Both the low complexity turbo equalizers developed in this thesis are able to jointly and iteratively equalize and decode coded, randomly interleaved information transmitted through highly dispersive multipath channels. The performance of both these low complexity turbo equalizers is comparable to that of the conventional turbo equalizer while their computational complexities are superior for channels with long memory. Their performance is also comparable to that of other low complexity turbo equalizers, but their computational complexities are worse. The computational complexity of both the DBN-TE and the HNN-TE is approximately quadratic at best (and cubic at worst) in the transmitted data block length, exponential in the encoder constraint length and approximately independent of the channel memory length. The approximate quadratic complexity of both the DBN-TE and the HNN-TE is mostly due to interleaver mitigation, requiring matrix multiplication, where the matrices have dimensions equal to the data block length, without which turbo equalization using superstructures is impossible for systems employing random interleavers. / Thesis (PhD)--University of Pretoria, 2013. / gm2013 / Electrical, Electronic and Computer Engineering / unrestricted

Dans cette thèse, nous nous sommes focalisés sur le modèle statistique linéaire à effets mixtes. Nous nous sommes d'abord intéressés à l'estimation consistante des paramètres du modèle dans sa version multidimensionnelle, puis à de la sélection d'effets fixes en dimension un. En ce qui concerne l'estimation des paramètres du modèle linéaire à effets mixtes multidimensionnel, nous avons proposé des estimateurs du maximum de vraisemblance par utilisation de l'algorithme EM, mais avec des expressions plus générales que celles de la littérature classique, permettant d'analyser non seulement des données longitudinales multivariées mais aussi des données multidimensionnelles multi-niveaux. Ici, en s'appuyant sur ces EM-estimateurs, nous avons introduit un test de rapport de vraisemblance permettant de tester la significativité globale des corrélations entre les effets aléatoires de deux dimensions du modèle. Ce qui permettrait de construire un modèle multidimensionnel plus parcimonieux en terme de paramètres de variance des effets aléatoires, par une procédure de selection pas-à-pas ascendante. Cette démarche a été suscitée par le fait que la dimension du vecteur de tous les effets aléatoires du modèle peut très rapidement croitre avec le nombre de variables à analyser, entrainant facilement des problèmes numériques dans l'optimisation du critère choisi (ML ou REML). Nous avons ensuite proposé une procédure d'estimation consistante des paramètres du modèle qui passe par la résolution d'un problème de moindres carrés pénalisés pour fournir une expression explicite de la déviance à minimiser. La procédure de sélection d'effets fixes proposée ici est de type adaptive ridge itérative et permet d'approximer les performances de sélection d'une pénalité de type L0 de la vraisemblance des paramètres du modèle. Nos résultats ont été appuyés par des études de simulation à plusieurs niveaux, mais aussi par l'analyse de plusieurs jeux de données réelles. / This thesis focuses on the statistical linear mixed-effects model, where we have been interested in its multivariate version's parameters estimation but also in the unidimensional selection of fixed effects. Concerning the parameters estimation of the multivariate linear mixed-effects model, we have first introduced more general expressions of the EM algorithm-based estimators which fit the multivariate longitudinal data analysis framework but also the framework of the multivariate multilevel data analysis. Since the dimensionality of the total vector of random effects in the multivariate model can grow with the number of the outcome variables leading often to computational problems in the likelihood optimization, we introduced a likelihood ratio test for testing the global effect of the correlations between the random effects of two dimensions of the model. This bivariate correlation test is intended to help in constructing a more parsimonious model regarding the variance components of the random effects, using a stepwise procedure. Secondly, we have introduced another estimation procedure that yields to consistent estimates for all the model parameters. This procedure is based on the Cholesky factorization of the random effects covariance matrix and the resolution of a preliminary penalized means square problem, and leads to an explicite expression of the profiled deviance of the model. For selecting fixed effects in the one dimensional mixed-effects model, we introduce an iterative adaptive ridge procedure for approximating sL0 penalty selection performances. All the results in this manuscript have been accompanied by extensive simulation studies along with real data analysis examples.

This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDLT factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.

本論文一共分為兩大主題，分別為匯率連結商品之評價與分析，及違約事件相關係數之估計。在結構型金融商品於市場上熱賣之後，金融業者紛紛投入財務工程領域，競相推出類似的產品。然而，自1971年世界各國開始實行浮動匯率制度之後，匯率風險較以往提高不少，因此各種不同設計的外匯衍生性商品開始不斷地問世。有鑑於此，本文希望藉由分析市場上的匯率商品：「新加坡華僑銀行一年期匯率連結結構型存款」，讓發行商和投資人了解結構型商品設計的要點與風險所在。在此商品中，本文利用多變數蒙地卡羅模擬法求出商品的近似價格，除了看發行商是否有利可尋之外，也提供發行商可行之避險策略。同時，本文也透過商品條款分析與情境分析，讓投資人了解其獲利所在與將面臨的風險。 / 由於近年來信用事件層出不窮，顯示出信用風險控管的重要性，信用衍生性商品也因而開始蓬勃發展。目前信用衍生性商品以信用違約交換為最大宗，擔保債權憑證(Collateralized Debt Obligations, CDO)為其次。由於一籃子信用衍生性商品和擔保債權憑證涉及多檔標的資產，在評價時，公司之間的違約相關係數是個重要因子，因此本文在另一個主題上，透過Robert Jarrow與Donald van Deventer(2005)提出的違約相關係數之估計方法，以簡約模型估計違約相關係數，利用台灣公司資料做實證分析，期許對連結多項標的資產之信用衍生性商品之評價有所幫助。

Τα τελευταία χρόνια χαρακτηρίζονται από μια αλματώδη ανάπτυξη των προϊόντων και υπηρεσιών που βασίζονται στα δίκτυα ασύρματης επικοινωνίας, ενώ προκύπτουν σημαντικές ερευνητικές προκλήσεις. Τα συστήματα πολλαπλών κεραιών στον πομπό και στο δέκτη, γνωστά και ως συστήματα MIMO (multi-input multi-output), καθώς και η τεχνολογία πολλαπλής προσπέλασης με χρήση κωδικών (code division multiple access, CDMA) αποτελούν δύο από τα βασικά μέτωπα ανάπτυξης των ασύρματων τηλεπικοινωνιών. Στα πλαίσια της παρούσας διδακτορικής διατριβής, ασχοληθήκαμε με την ανάπτυξη και μελέτη αλγορίθμων επεξεργασίας σήματος για τα δύο παραπάνω συστήματα, όπως περιγράφεται αναλυτικά παρακάτω. Σχετικά με τα συστήματα MIMO, η πρωτοποριακή έρευνα που πραγματοποιήθηκε στα Bell Labs γύρω στα 1996, όπου αναπτύχθηκε η αρχιτεκτονική BLAST (Bell Labs Layered Space-Time), απέδειξε ότι η χρήση πολλαπλών κεραιών μπορεί να οδηγήσει σε σημαντική αύξηση της χωρητικότητας των ασύρματων συστημάτων. Προκειμένου να αξιοποιηθούν οι παραπάνω δυνατότητες, απαιτείται η σχεδίαση σύνθετων δεκτών MIMO. Προς αυτήν την κατεύθυνση, έχει προταθεί ένας μεγάλος αριθμός μεθόδων ισοστάθμισης του καναλιού. Ωστόσο, οι περισσότερες από αυτές υποθέτουν ότι το ασύρματο κανάλι είναι: 1) χρονικά σταθερό, 2) συχνοτικά επίπεδο (δεν εισάγει διασυμβολική παρεμβολή), και κυρίως 3) ότι είναι γνωστό στο δέκτη. Δεδομένου ότι σε ευρυζωνικά συστήματα μονής φέρουσας οι παραπάνω υποθέσεις είναι δύσκολο να ικανοποιηθούν, στραφήκαμε προς τις προσαρμοστικές μεθόδους ισοστάθμισης. Συγκεκριμένα, αναπτύξαμε τρεις βασικούς αλγορίθμους. Ο πρώτος αλγόριθμος αποτελεί έναν προσαρμοστικό ισοσταθμιστή ανάδρασης αποφάσεων (decision feedback equalizer, DFE) για συχνοτικά επίπεδα κανάλια ΜΙΜΟ. Ο προτεινόμενος MIMO DFE ακολουθεί την αρχιτεκτονική BLAST, και ανανεώνεται με βάση τον αλγόριθμο αναδρομικών ελαχίστων τετραγώνων (RLS) τετραγωνικής ρίζας. Ο ισοσταθμιστής μπορεί να παρακολουθήσει ένα χρονικά μεταβαλλόμενο κανάλι, και, από όσο γνωρίζουμε, έχει τη χαμηλότερη πολυπλοκότητα από όλους τους δέκτες BLAST που έχουν προταθεί έως σήμερα. Ο δεύτερος αλγόριθμος αποτελεί την επέκταση του προηγούμενου σε συχνοτικά επιλεκτικά κανάλια. Μέσω κατάλληλης μοντελοποίησης του προβλήματος ισοστάθμισης, οδηγηθήκαμε σε έναν αποδοτικό DFE για ευρυζωνικά κανάλια MIMO. Τότε, η διαδικασία της ισοστάθμισης εμφανίζει προβλήματα αριθμητικής ευστάθειας, που λόγω της υλοποίησης RLS τετραγωνικής ρίζας αντιμετωπίστηκαν επιτυχώς. Κινούμενοι προς την κατεύθυνση περαιτέρω μείωσης της πολυπλοκότητας, προτείναμε έναν προσαρμοστικό MIMO DFE που ανανεώνεται με βάση τον αλγόριθμο ελαχίστων μέσων τετραγώνων (LMS) υλοποιημένο εξ ολοκλήρου στο πεδίο της συχνότητας. Με χρήση του ταχύ μετασχηματισμού Fourier (FFT), μειώνεται η απαιτούμενη πολυπλοκότητα. Παράλληλα, η μετάβαση στο πεδίο των συχνοτήτων έχει ως αποτέλεσμα την προσεγγιστική διαγωνοποίηση του συστήματος, προσφέροντας ανεξάρτητη ανανέωση των φίλτρων ανά συχνοτική συνιστώσα και επιτάχυνση της σύγκλισης του αλγορίθμου. Ο προτεινόμενος ισοσταθμιστής πετυχαίνει μια καλή ανταλλαγή μεταξύ απόδοσης και πολυπλοκότητας. Παράλληλα με τα παραπάνω, ασχοληθήκαμε με την εκτίμηση του ασύρματου καναλιού σε ένα ασύγχρονο σύστημα CDMA. Το βασικό σενάριο είναι ότι ο σταθμός βάσης γνωρίζει ήδη τους ενεργούς χρήστες, και καλείται να εκτιμήσει τις παραμέτρους του καναλιού ανερχόμενης ζεύξης ενός νέου χρήστη που εισέρχεται στο σύστημα. Το πρόβλημα περιγράφεται από μια συνάρτηση ελαχίστων τετραγώνων, η οποία είναι γραμμική ως προς τα κέρδη του καναλιού, και μη γραμμική ως προς τις καθυστερήσεις του. Αποδείξαμε ότι το πρόβλημα έχει μια προσεγγιστικά διαχωρίσιμη μορφή, και προτείναμε μια επαναληπτική μέθοδο υπολογισμού των παραμέτρων. Ο προτεινόμενος αλγόριθμος δεν απαιτεί κάποια ειδική ακολουθία διάχυσης και λειτουργεί αποδοτικά ακόμη και για περιορισμένη ακολουθία εκπαίδευσης. Είναι εύρωστος στην παρεμβολή πολλαπλών χρηστών και περισσότερο ακριβής από μια υπάρχουσα μέθοδο εις βάρος μιας ασήμαντης αύξησης στην υπολογιστική πολυπλοκότητα. / Over the last decades, a dramatic progress in the products and services based on wireless communication networks has been observed, while, at the same time, new research challenges arise. The systems employing multiple antennas at the transmitter and the receiver, known as MIMO (multi-input multi-output) systems, as well as code division multiple access (CDMA) systems, are two of the main technologies employed for the evolution of wireless communications. During this PhD thesis, we worked on the design and analysis of signal processing algorithms for the two above systems, as it is described in detail next. Concerning the MIMO systems, the pioneering work performed at Bell Labs around 1996, where the BLAST (Bell Labs Layered Space-Time) architecture has been developed, proved that by using multiple antennas can lead to a significant increase in wireless systems capacity. To exploit this potential, sophisticated MIMO receivers should be designed. To this end, a large amount of channel equalizers has been proposed. However, most of these methods assume that the wireless channel is: 1) static, 2) frequency flat (no intersymbol interference is introduced), and mainly 3) it is perfectly known at the receiver. Provided that in high rate single carrier systems these assumptions are difficult to be met, we focused our attention on adaptive equalization methods. More specifically, three basic algorithms have been developed. The first algorithm is an adaptive decision feedback equalizer (DFE) for frequency flat MIMO channels. The proposed MIMO DFE implements the BLAST architecture, and it is updated by the recursive least squares (RLS) algorithm in its square root form. The new equalizer can track time varying channels, and, to the best of our knowledge, it has the lowest computational complexity among the BLAST receivers that have been proposed up to now. The second algorithm is an extension of the previous one to the frequency selective channel case. By proper modeling of the equalization problem, we arrived at an efficient DFE for wideband MIMO channels. In this case, the equalization process encounters numerical instability problems, which were successfully treated by the square root RLS implementation employed. To further reduce complexity, we proposed an adaptive MIMO DFE that is updated by the least mean square (LMS) algorithm, fully implemented in the frequency domain. By using the fast Fourier transform (FFT), the complexity required is considerably reduced. Moreover, the frequency domain implementation leads to an approximate decoupling of the equalization problem at each frequency bin. Thus, an independent update of the filters at each frequency bin allows for a faster convergence of the algorithm. The proposed equalizer offers a good performance - complexity tradeoff. Furthermore, we worked on channel estimation for an asynchronous CDMA system. The assumed scenario is that the base station has already acquired all the active users, while the uplink channel parameters of a new user entering the system should be estimated. The problem can be described via a least squares cost function, which is linear with respect to the channel gains, and non linear to its delays. We proved that the problem is approximately decoupled, and a new iterative parameter estimation method has been proposed. The suggested method does not require any specific pilot sequence and performs well even for a short training interval. It is robust to multiple access interference and more accurate compared to an existing method, at the expense of an insignificant increase in computational complexity.

This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDLT factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.:List of Figures xi List of Tables xiii List of Algorithms xv List of Acronyms xvii List of Symbols xix Publications xxi 1 Introduction 1 1.1 Notation 2 1.2 Structure of this Thesis 3 2 Basics 5 2.1 Linear Algebra and Eigenvalues 6 2.1.1 The Eigenvalue Problem 7 2.1.2 Dense Matrix Algorithms 9 2.2 Integral Operators and Integral Equations 14 2.2.1 Definitions 14 2.2.2 Example - BEM 16 2.3 Introduction to Hierarchical Arithmetic 17 2.3.1 Main Idea 17 2.3.2 Definitions 19 2.3.3 Hierarchical Arithmetic 24 2.3.4 Simple Hierarchical Matrices (Hl-Matrices) 30 2.4 Examples 33 2.4.1 FEM Example 33 2.4.2 BEM Example 36 2.4.3 Randomly Generated Examples 37 2.4.4 Application Based Examples 38 2.4.5 One-Dimensional Integral Equation 38 2.5 Related Matrix Formats 39 2.5.1 H2-Matrices 40 2.5.2 Diagonal plus Semiseparable Matrices 40 2.5.3 Hierarchically Semiseparable Matrices 42 2.6 Review of Existing Eigenvalue Algorithms 44 2.6.1 Projection Method 44 2.6.2 Divide-and-Conquer for Hl(1)-Matrices 45 2.6.3 Transforming Hierarchical into Semiseparable Matrices 46 2.7 Compute Cluster Otto 47 3 QR Decomposition of Hierarchical Matrices 49 3.1 Introduction 49 3.2 Review of Known QR Decompositions for H-Matrices 50 3.2.1 Lintner’s H-QR Decomposition 50 3.2.2 Bebendorf’s H-QR Decomposition 52 3.3 A new Method for Computing the H-QR Decomposition 54 3.3.1 Leaf Block-Column 54 3.3.2 Non-Leaf Block Column 56 3.3.3 Complexity 57 3.3.4 Orthogonality 60 3.3.5 Comparison to QR Decompositions for Sparse Matrices 61 3.4 Numerical Results 62 3.4.1 Lintner’s H-QR decomposition 62 3.4.2 Bebendorf’s H-QR decomposition 66 3.4.3 The new H-QR decomposition 66 3.5 Conclusions 67 4 QR-like Algorithms for Hierarchical Matrices 69 4.1 Introduction 70 4.1.1 LR Cholesky Algorithm 70 4.1.2 QR Algorithm 70 4.1.3 Complexity 71 4.2 LR Cholesky Algorithm for Hierarchical Matrices 72 4.2.1 Algorithm 72 4.2.2 Shift Strategy 72 4.2.3 Deflation 73 4.2.4 Numerical Results 73 4.3 LR Cholesky Algorithm for Diagonal plus Semiseparable Matrices 75 4.3.1 Theorem 75 4.3.2 Application to Tridiagonal and Band Matrices 79 4.3.3 Application to Matrices with Rank Structure 79 4.3.4 Application to H-Matrices 80 4.3.5 Application to Hl-Matrices 82 4.3.6 Application to H2-Matrices 83 4.4 Numerical Examples 84 4.5 The Unsymmetric Case 84 4.6 Conclusions 88 5 Slicing the Spectrum of Hierarchical Matrices 89 5.1 Introduction 89 5.2 Slicing the Spectrum by LDLT Factorization 91 5.2.1 The Function nu(M − µI) 91 5.2.2 LDLT Factorization of Hl-Matrices 92 5.2.3 Start-Interval [a, b] 96 5.2.4 Complexity 96 5.3 Numerical Results 97 5.4 Possible Extensions 100 5.4.1 LDLT Slicing Algorithm for HSS Matrices 103 5.4.2 LDLT Slicing Algorithm for H-Matrices 103 5.4.3 Parallelization 105 5.4.4 Eigenvectors 107 5.5 Conclusions 107 6 Computing Eigenvalues by Vector Iterations 109 6.1 Power Iteration 109 6.1.1 Power Iteration for Hierarchical Matrices 110 6.1.2 Inverse Iteration 111 6.2 Preconditioned Inverse Iteration for Hierarchical Matrices 111 6.2.1 Preconditioned Inverse Iteration 113 6.2.2 The Approximate Inverse of an H-Matrix 115 6.2.3 The Approximate Cholesky Decomposition of an H-Matrix 116 6.2.4 PINVIT for H-Matrices 117 6.2.5 The Interior of the Spectrum 120 6.2.6 Numerical Results 123 6.2.7 Conclusions 130 7 Comparison of the Algorithms and Numerical Results 133 7.1 Theoretical Comparison 133 7.2 Numerical Comparison 135 8 Conclusions 141 Theses 143 Bibliography 145 Index 153