Abstract Conventional versions of linear multiuser detectors (MUD) are not feasible in the wideband code division multiple access (WCDMA) downlink due to the use of long scrambling sequences. As an alternative, linear channel equalizers restore the orthogonality of the spreading sequences lost in frequency-selective channels, thus, suppressing multiple access interference (MAI) in the WCDMA downlink. In this thesis, linear channel equalizers in WCDMA terminals are studied. The purpose of the thesis is to develop novel receivers that provide performance enhancement over conventional rake receivers with an acceptable increase in complexity, and to validate their performance under WCDMA downlink conditions. Although the WCDMA standard is emphasized as the candidate system, the receivers presented are suitable for any synchronous direct sequence code division multiple access downlink employing coherent data detection and orthogonal user or channel separation. Two adaptive channel equalizers are developed based on the constrained minimum output energy (MOE) criterion and sample matrix inversion method. An existing equalizer based on the matrix inversion lemma is also developed further to become a prefilter-rake equalizer. Performance analysis is carried out for equalizers trained using a common pilot channel and for the channel response constrained MOE (CR-MOE) and sample matrix inversion (SMI) based equalizers developed in the thesis. The linear minimum mean square error (LMMSE) channel equalizer, which assumes a random scrambling sequence, is shown to approximate the performance of the LMMSE MUD. The adaptive CR-MOE, SMI-based, and prefilter-rake equalizers are observed to attain performance close to that of an approximate LMMSE channel equalizer. The equalizers considered are also shown to be suitable for implementation with fixed-point arithmetic. The SMI-based equalizer is shown to provide good performance and to require an acceptable increase in complexity. It is also well suited for symbol rate equalization after despreading, which allows for computationally efficient receiver designs for low data rate terminals. Hence, the SMI-based equalizer is a suitable receiver candidate for both high and low data rate terminals. Adaptive equalizers are considered in conjunction with forward error correction (FEC) coding, soft handover, transmit diversity and high speed downlink packet access (HSDPA). The adaptive equalizers are shown to provide significant performance gains over the rake receiver in frequency selective channels. The performance gains provided by one antenna equalizers are noted to decrease near the edges of a cell, whereas the equalizers with two receive antennas achieve significant performance improvements also with soft handover. The performance gains of one or two antenna equalizers are shown to be marginal in conjunction with transmit antenna diversity. Otherwise the equalizers are observed to attain good signal-to-noise-plus-interference ratio performance. Therefore, they are also suitable receiver candidates for HSDPA.

The wavelet Galerkin scheme for the fast solution of boundary integral equations produces approximate solutions within discretization error accuracy offered by the underlying Galerkin method at a computational expense that stays proportional to the number of unknowns. In this paper we present an adaptive version of the scheme which preserves the super-convergence of the Galerkin method.

This paper presents a wavelet Galerkin scheme for the fast solution of boundary integral equations. Wavelet Galerkin schemes employ appropriate wavelet bases for the discretization of boundary integral operators which yields quasi-sparse system matrices. These matrices can be compressed such that the complexity for solving a boundary integral equation scales linearly with the number of unknowns without compromising the accuracy of the underlying Galerkin scheme. Based on the wavelet Galerkin scheme we present also an adaptive algorithm. By numerical experiments we provide results which demonstrate the performance of our algorithm.

A new preconditioner for the quick solution of a crack growth problem in 2D adaptive finite element analysis is proposed. Numerical experiments demonstrate the power of the method.

A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral. No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora / The theory of formal languages is widely used to solve problems of different natures as it can deal with artificial and natural languages. The grammars, formalisms able to synthesize languages, can also be used in pattern recognition problems due to the ability to model the language components hierarchies, decomposing patterns in substructures. Based on this idea, the framework GrammarLab was designed to facilitate the work involved in implementing, generating and testing different grammar based sequence classifiers, providing regular and context free grammar in the prior version. However, some problems need a formalism that can be found only in higher classes of grammars in the Chomsky hierarchy. The problem of using a higher class of grammar is the high computational time complexity for parsing. While the problem of recognizing sequences using regular and context free grammars is solved at polynomial time, the same problem in general case is NP-Complete for context sensitive grammars and undecidable for unrestricted grammars. Nevertheless, the use of adaptive methods allows a grammar to alter the set of production rules during sentences generation, including context sensitivity even to grammars that were designed to be context free, without increasing the polynomial parsing complexity. This work was focused in improving the GrammarLab framework by including the ability to deal with adaptive methods and in the creation of an adaptive version of Earleys algorithm. To test the solution in real world problems, it was conducted a preliminary study of the use of the framework in characterizing RNA functional families with conserved secondary structure, including pseudoknots. The pseudoknot pattern, represented by crossing dependences among RNA sequence nucleotides, is an example of context dependence, so it is a good test case for the use of a model that consider adaptability in the constitution. The obtained results with two families of RNAs with pseudoknots show that the approach is promising

A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral. No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora / The theory of formal languages is widely used to solve problems of different natures as it can deal with artificial and natural languages. The grammars, formalisms able to synthesize languages, can also be used in pattern recognition problems due to the ability to model the language components hierarchies, decomposing patterns in substructures. Based on this idea, the framework GrammarLab was designed to facilitate the work involved in implementing, generating and testing different grammar based sequence classifiers, providing regular and context free grammar in the prior version. However, some problems need a formalism that can be found only in higher classes of grammars in the Chomsky hierarchy. The problem of using a higher class of grammar is the high computational time complexity for parsing. While the problem of recognizing sequences using regular and context free grammars is solved at polynomial time, the same problem in general case is NP-Complete for context sensitive grammars and undecidable for unrestricted grammars. Nevertheless, the use of adaptive methods allows a grammar to alter the set of production rules during sentences generation, including context sensitivity even to grammars that were designed to be context free, without increasing the polynomial parsing complexity. This work was focused in improving the GrammarLab framework by including the ability to deal with adaptive methods and in the creation of an adaptive version of Earleys algorithm. To test the solution in real world problems, it was conducted a preliminary study of the use of the framework in characterizing RNA functional families with conserved secondary structure, including pseudoknots. The pseudoknot pattern, represented by crossing dependences among RNA sequence nucleotides, is an example of context dependence, so it is a good test case for the use of a model that consider adaptability in the constitution. The obtained results with two families of RNAs with pseudoknots show that the approach is promising

Cette thèse porte sur la généralisation de la méthode NXFEM proposée par A. et P. Hansbo pour le problème d’interface elliptique. La modélisation et simulation numérique d’écoulements dans des domaines fracturés sont au coeur de nombreuses applications, telles que le milieu pétrolier (modélisation de réservoirs, présence de failles, propagation d’un signal, repérage de couches), l’aérospatiale (problème de chocs, de rupture), en génie civil (fissuration du béton), mais également dans la biologie cellulaire (déformation des globules rouges). En outre, de nombreux projets de recherche nécessitent le développement des méthodes robustes pour la prise en compte de singularités, ce qui fait partie des motivations et des objectifs de l'équipe Concha, ainsi que de cette thèse. Une modification de cette méthode a tout d’abord été proposée afin d’obtenir la robustesse à la fois par rapport à la géométrie du maillage coupé par l’interface et par rapport aux paramètres de diffusion. Nous nous sommes ensuite intéressés à sa généralisation à tout type de maillages 2D-3D (triangles, quadrilatères, tétraèdres, hexaèdres), et pour tout type d’éléments finis (conformes, non conformes, Galerkin discontinus) pour des interfaces planes et courbes. Les applications ont été orientées vers des problèmes d’écoulements en milieux poreux fracturés : adaptation de la méthode NXFEM à la résolution d’un modèle asymptotique de failles, à des problèmes instationnaires, de transports, ou encore à des domaines multi-fracturés. / This thesis focuses on the generalization of the NXFEM method proposed by A. and P. Hansbo for elliptic interface problem. Numerical modeling and simulation of flow in fractured media are at the heart of many applications, such as petroleum and porous media (reservoir modeling, presence of faults, signal propagation, identification of layers ...), aerospace (problems of shock, rupture), civil engineering (concrete cracking), but also in cell biology (deformation of red blood cells). In addition, many research projects require the development of robust methods for the consideration of singularities, which is one of the motivations and objectives of the Concha team and of this thesis. First a modification of this method was proposed to obtain a robust method not only with respect to the mesh-interface geometry, but also with respect to the diffusion parameters. We then looked to its generalization to any type of 2D-3D meshes (triangles, quadrilaterals, tetrahedra, hexahedra), and for any type of finites elements (conforming, nonconforming, Galerkin discontinuous) for plane and curved interfaces. The applications have been referred to the flow problems in fractured porous media : adaptation of NXFEM method to solve an asymptotic model of faults, to unsteady problems, transport problems, or to multi-fractured domains.

The thesis deals with the construction of an adaptive 1D and 2D mesh in the framework of the cell- centered finite volume scheme. The adaptive strategy is applied to the numerical solution of problems governed by the Euler equations, which is a hyperbolic system of PDE's. The used algorithm is applicable to nonstationary problems and consists of three independent parts, which are cyclically repeated. These steps are PDE evolution, then mesh adaptation and recovery of numerical solution from the old mesh to the newly adapted mesh. Owing to this the algorithm can be used also for other hyperbolic systems. The thesis is focused on the development of our mesh adaptation strategy, based on the anisotropic mesh adaptation, which preserves the geometric mass conservation law in each computational step. The proposed method is suitable to solve problems with moving discontinuities. Several test problems with moving discontinuity are computed to compare our algorithm with Moving Mesh algorithms.

Median in some statistical methods Abstract: This work is focused on utilization of robust properties of median. We propose variety of algorithms with respect to their breakdown point. In addition, other properties are studied such as consistency (strong or weak), equivariance and computational complexity. From practical point of view we are looking for methods balancing good robust properties and computational complexity, be- cause these two properties do not usually correspond to each other. The disser- tation is divided to two parts. In the first part, robust methods similar to the exponential smoothing are suggested. Firstly, the previous results for the exponential smoothing with ab- solute norm are generalized using the regression quantiles. Further, the method based on the classical sign test is introduced, which deals not only with outliers but also detects change points. In the second part we propose new estimators of location. These estimators select a robust set around the geometric median, enlarge it and compute the (iterative) weighted mean from it. In this way we obtain a robust estimator in the sense of the breakdown point which exploits more information from observations than standard estimators. We apply our approach on the concepts of boxplot and bagplot. We work in a general normed vector...

In the adaptive finite element method, the solution of a p.d.e. is approximated from finer and finer meshes, which are controlled by error estimators. So, starting from a given coarse mesh, some elements are subdivided a couple of times. We investigate the question of avoiding instabilities which limit this process from the fact that nodal coordinates of one element coincide in more and more leading digits. In a previous paper the stable calculation of the Jacobian matrices of the element mapping was given for straight line triangles, quadrilaterals and hexahedrons. Here, we generalize this ideas to linear and quadratic triangles on curved boundaries.