Based on the geometric analysis of Gaussian elimination (GE) found in Neal and Poole (Linear Algebra Appl. 173 (1992) 239-264) and Poole and Neal (Linear Algebra Appl. 149 (1991) 249-272; 162-164 (1992) 309-324), a new pivoting strategy, Rook's pivoting (RP), was introduced in Neal and Poole (Linear Algebra Appl. 173 (1992) 239-264) which encourages stability in the back-substitution phase of GE while controlling the growth of round-off error during the sweep-out. In fact, Foster (J. Comput. Appl. Math. 86 (1997) 177-194) has previously shown that RP, as with complete pivoting, cannot have exponential growth error. Empirical evidence presented in Neal and Poole (Linear Algebra Appl. 173 (1992) 239-264) showed that RP produces computed solutions with consistently greater accuracy than partial pivoting. That is, Rook's pivoting is, on average, more accurate than partial pivoting, with comparable costs. Moreover, the overhead to implement Rook's pivoting in a scalar or serial environment is only about three times the overhead to implement partial pivoting. The theoretical proof establishing this fact is presented here, and is empirically confirmed in this paper and supported in Foster (J. Comput. Appl. Math. 86 (1997) 177-194).

No description available.

Digital communications have now become a fundamental part of modern society. In communications, channel coding is an effective way to reduce the information rate down to channel capacity so that the information can be transmitted reliably through the channel. This thesis is devoted to studying the mathematical theory and analysis of channel codes that possess a useful diagonal structure in the parity-check and generator matrices. The first aspect of these codes that is studied is the ability to describe the parity-check matrix of a code with sliding diagonal structure using polynomials. Using this framework, an efficient new method is proposed to obtain a generator matrix G from certain types of parity-check matrices with a so-called defective cyclic block structure. By the nature of this method, G can also be completely described by a polynomial, which leads to efficient encoder design using shift registers. In addition, there is no need for the matrices to be in systematic form, thus avoiding the need for Gaussian elimination. Following this work, we proceed to explore some of the properties of diagonally structured lowdensity parity-check (LDPC) convolutional codes. LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. The first crucial property studied is the minimum free distance of LDPC convolutional code ensembles, an important parameter contributing to the error-correcting capability of the code. Here, asymptotic methods are used to form lower bounds on the ratio of the free distance to constraint length for several ensembles of asymptotically good, protograph-based LDPC convolutional codes. Further, it is shown that this ratio of free distance to constraint length for such LDPC convolutional codes exceeds the ratio of minimum distance to block length for corresponding LDPC block codes. Another interesting property of these codes is the way in which the structure affects the performance in the infamous error floor (which occurs at high signal to noise ratio) of the bit error rate curve. It has been suggested that “near-codewords” may be a significant factor affecting decoding failures of LDPC codes over an additive white Gaussian noise (AWGN) channel. A near-codeword is a sequence that satisfies almost all of the check equations. These nearcodewords can be associated with so-called ‘trapping sets’ that exist in the Tanner graph of a code. In the final major contribution of the thesis, trapping sets of protograph-based LDPC convolutional codes are analysed. Here, asymptotic methods are used to calculate a lower bound for the trapping set growth rates for several ensembles of asymptotically good protograph-based LDPC convolutional codes. This value can be used to predict where the error floor will occur for these codes under iterative message-passing decoding.

The aim of this thesis is to conduct a general investigation in the field of sparse matrices, to investigate and compare various techniques for handling sparse systems suggested in the literature, to develop some new techniques, and to discuss the feasibility of using sparsity techniques in the solution of overdetermined equations and the eigenvalue problem.

Orientador: Fabio Violaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T10:44:21Z (GMT). No. of bitstreams: 1 Yared_GlaucoFerreiraGazel_D.pdf: 5774867 bytes, checksum: 49a79d9495ce25c8a69ca34858a956ee (MD5) Previous issue date: 2006 / Resumo: Atualmente os sistemas de reconhecimento de fala baseados em HMMs são utilizados em diversas aplicações em tempo real, desde telefones celulares até automóveis. Nesse contexto, um aspecto importante que deve ser considerado é a complexidade dos HMMs, a qual está diretamente relacionada com o custo computacional. Assim, no intuito de permitir a aplicação prática do sistema, é interessante otimizar a complexidade dos HMMs, impondo-se restrições em relação ao desempenho no reconhecimento. Além disso, a otimização da topologia é importante para uma estimação confiável dos parâmetros dos HMMs. Os trabalhos anteriores nesta área utilizam medidas de verossimilhança para a obtenção de sistemas que apresentem um melhor compromisso entre resolução acústica e robustez. Este trabalho apresenta o novo Algoritmo para Eliminação de Gaussianas (GEA), o qual é baseado em uma análise discriminativa e em uma análise interna, para a determinação da complexidade mais apropriada para os HMMs. O novo método é comparado com o Critério de Informação Bayesiano (BIC), com um método baseado em medidas de entropia, com um método discriminativo para o aumento da resolução acústica dos modelos e com os sistemas contendo um número fixo de Gaussianas por estado / Abstract: Nowadays, HMM-based speech recognition systems are used in many real time processing applications, from cell phones to auto mobile automation. In this context, one important aspect to be considered is the HMM complexity, which directly determines the system computational load. So, in order to make the system feasible for practical purposes, it is interesting to optimize the HMM size constrained to a minimum acceptable recognition performance. Furthermore, topology optimization is also important for reliable parameter estimation. Previous works in this area have used likelihood measures in order to obtain models with a better compromise between acoustic resolution and robustness. This work presents the new Gaussian Elimination Algorithm (GEA), which is based on a discriminative analysis and on an internal analysis, for determining the more suitable HMM complexity. The new approach is compared to the classical Bayesian Information Criterion (BIC), to an entropy based method, to a discriminative-based method for increasing the acoustic resolution of the HMMs and also to systems containing a fixed number of Gaussians per state / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Neste trabalho foi realizado um grande levantamento de técnicas de esparsidade relacionadas a sistemas estáticos de energia elétrica. Tais técnicas visam, do ponto de vista computacional, ao aumento da eficiência na solução de rede elétrica objetivando, além da resolução em si, a redução dos requisitos de memória, armazenamento e tempo de processamento. Para tanto, uma extensa revisão bibliográfica foi compilada, apresentando um posicionamento histórico e uma ampla visão do desenvolvimento teórico. Os testes comparativos realizados para sistemas de 14, 30, 57 e 118 barras, sobre a implantação de três das técnicas mais empregadas, apontou a Bi-fatoração como tendo o melhor desempenho médio. Para sistemas pequenos, a Eliminação Esparsa e Sintética de Gauss apresentou melhores resultados. Este trabalho fornecerá subsídios conceituais e metodológicos a técnicos e pesquisadores da área. / In this work a great survey of sparsity techniques related to static systems of electric power was accomplished. Such techniques seek, for of the computational point of view, the increase of the efficiency in the solution of the electric net aiming, besides the resolution of itself, the reduction of memory requirements, the storage and time processing. For that, an extensive bibliographic review was compiled providing a historic positioning and a broad view of theoretic development. The comparative tests accomplished for systems of 14,30, 57 and 118 buses, on the implementation of three of the most employed techniques, it pointed out an bi-factorisation as best medium performance. For small systems, the sparse symmetric Gaussian elimination showed the best results. This work will supply conceptual and methodological subsidies to technicians and researchers of the area.

Neste trabalho foi realizado um grande levantamento de técnicas de esparsidade relacionadas a sistemas estáticos de energia elétrica. Tais técnicas visam, do ponto de vista computacional, ao aumento da eficiência na solução de rede elétrica objetivando, além da resolução em si, a redução dos requisitos de memória, armazenamento e tempo de processamento. Para tanto, uma extensa revisão bibliográfica foi compilada, apresentando um posicionamento histórico e uma ampla visão do desenvolvimento teórico. Os testes comparativos realizados para sistemas de 14, 30, 57 e 118 barras, sobre a implantação de três das técnicas mais empregadas, apontou a Bi-fatoração como tendo o melhor desempenho médio. Para sistemas pequenos, a Eliminação Esparsa e Sintética de Gauss apresentou melhores resultados. Este trabalho fornecerá subsídios conceituais e metodológicos a técnicos e pesquisadores da área. / In this work a great survey of sparsity techniques related to static systems of electric power was accomplished. Such techniques seek, for of the computational point of view, the increase of the efficiency in the solution of the electric net aiming, besides the resolution of itself, the reduction of memory requirements, the storage and time processing. For that, an extensive bibliographic review was compiled providing a historic positioning and a broad view of theoretic development. The comparative tests accomplished for systems of 14,30, 57 and 118 buses, on the implementation of three of the most employed techniques, it pointed out an bi-factorisation as best medium performance. For small systems, the sparse symmetric Gaussian elimination showed the best results. This work will supply conceptual and methodological subsidies to technicians and researchers of the area.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-07T13:34:15Z No. of bitstreams: 2 Dissertação - Carmencita Ferreira Silva Assis - 2014.pdf: 1032992 bytes, checksum: dcfbc22b53a2352c6e65a7615ffb72b5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-05-07T13:40:12Z (GMT) No. of bitstreams: 2 Dissertação - Carmencita Ferreira Silva Assis - 2014.pdf: 1032992 bytes, checksum: dcfbc22b53a2352c6e65a7615ffb72b5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-05-07T13:40:12Z (GMT). No. of bitstreams: 2 Dissertação - Carmencita Ferreira Silva Assis - 2014.pdf: 1032992 bytes, checksum: dcfbc22b53a2352c6e65a7615ffb72b5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-03-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to present te hniques for solving systems of linear equations, in its traditional formulation, where it sought to explore the referen es ommonly used in ourses in linear algebra and numeri al omputation, fo using on the dire t methods of Gauss elimination and LU fa torization. Troubleshooters established in the literature are ondu ted, in order to illustrate the operation and appli ation of su h methods to real problems, thus highlighting the possibility of inserting them in high s hool. The ontents were treated and exposed so that exemplify the diversity of areas in luding linear systems, su h as engineering, e onomi s and biology, showing the gains that an be a hieved by students if they have onta t with the methods as soon as possible. At the end we suggest the use of omputational resour es in math lasses, sin e the redu tion of time spent in algebrai manipulation will allow the tea her to deepen the on epts and to address larger systems, to enhan e the resolution perspe tive, and motivate the student in the learning pro ess. / Este trabalho tem por objetivo apresentar té ni as de resolução de sistemas de equações lineares, em sua formulação tradi ional, onde se bus ou explorar as referên ias usualmente utilizadas em ursos de álgebra linear e ál ulo numéri o, enfo ando os métodos diretos de Eliminação de Gauss e Fatoração LU. Resoluções de problemas onsolidados na literatura são realizadas, om a nalidade de ilustrar o fun ionamento e apli ação de tais métodos em problemas reais, desta ando assim a possibilidade de inserção dos mesmos no Ensino Médio. Os onteúdos foram tratados e expostos de modo que exempli quem a diversidade de áreas que abrangem os sistemas lineares, tais omo engenharia, e onomia e biologia, mostrando os ganhos que podem ser al ançados pelos alunos, se tiverem ontato om os métodos o quanto antes. Ao nal sugere- se a utilização de re ursos omputa ionais nas aulas de matemáti a, uma vez que a redução do tempo empregado na manipulação algébri a permitirá que o professor possa aprofundar os on eitos e abordar sistemas de maior porte, que ampliem a perspe tiva de resolução, além de motivar o aluno no pro esso de aprendizagem.

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille par des méthodes directes de factorisation. Dans ce contexte, la taille de la matrice des facteurs constitue un des facteurs limitants principaux pour l'utilisation de méthodes directes de résolution. Nous supposons donc que la matrice des facteurs est de trop grande taille pour être rangée dans la mémoire principale du multiprocesseur et qu'elle a donc été écrite sur les disques locaux (hors-mémoire : OOC) d'une machine multiprocesseurs durant l'étape de factorisation. Nous nous intéressons à l'étude et au développement de techniques efficaces pour la phase de résolution après une factorization multifrontale creuse. La phase de résolution, souvent négligée dans les travaux sur les méthodes directes de résolution directe creuse, constitue alors un point critique de la performance de nombreuses applications scientifiques, souvent même plus critique que l'étape de factorisation. Cette thèse se compose de deux parties. Dans la première partie nous nous proposons des algorithmes pour améliorer la performance de la résolution hors-mémoire. Dans la deuxième partie nous pousuivons ce travail en montrant comment exploiter la nature creuse des seconds membres pour réduire le volume de données accédées en mémoire. Dans la première partie de cette thèse nous introduisons deux approches de lecture des données sur le disque dur. Nous montrons ensuite que dans un environnement parallèle le séquencement des tâches peut fortement influencer la performance. Nous prouvons qu'un ordonnancement contraint des tâches peut être introduit; qu'il n'introduit pas d'interblocage entre processus et qu'il permet d'améliorer les performances. Nous conduisons nos expériences sur des problèmes industriels de grande taille (plus de 8 Millions d'inconnues) et utilisons une version hors-mémoire d'un code multifrontal creux appelé MUMPS (solveur multifrontal parallèle). Dans la deuxième partie de ce travail nous nous intéressons au cas de seconds membres creux multiples. Ce problème apparaît dans des applications en electromagnétisme et en assimilation de données et résulte du besoin de calculer l'espace propre d'une matrice fortement déficiente, du calcul d'éléments de l'inverse de la matrice associée aux équations normales pour les moindres carrés linéaires ou encore du traitement de matrices fortement réductibles en programmation linéaire. Nous décrivons un algorithme efficace de réduction du volume d'Entrées/Sorties sur le disque lors d'une résolution hors-mémoire. Plus généralement nous montrons comment le caractère creux des seconds -membres peut être exploité pour réduire le nombre d'opérations et le nombre d'accès à la mémoire lors de l'étape de résolution. Le travail présenté dans cette thèse a été partiellement financé par le projet SOLSTICE de l'ANR (ANR-06-CIS6-010). / We consider the solution of very large systems of linear equations with direct multifrontal methods. In this context the size of the factors is an important limitation for the use of sparse direct solvers. We will thus assume that the factors have been written on the local disks of our target multiprocessor machine during parallel factorization. Our main focus is the study and the design of efficient approaches for the forward and backward substitution phases after a sparse multifrontal factorization. These phases involve sparse triangular solution and have often been neglected in previous works on sparse direct factorization. In many applications, however, the time for the solution can be the main bottleneck for the performance. This thesis consists of two parts. The focus of the first part is on optimizing the out-of-core performance of the solution phase. The focus of the second part is to further improve the performance by exploiting the sparsity of the right-hand side vectors. In the first part, we describe and compare two approaches to access data from the hard disk. We then show that in a parallel environment the task scheduling can strongly influence the performance. We prove that a constraint ordering of the tasks is possible; it does not introduce any deadlock and it improves the performance. Experiments on large real test problems (more than 8 million unknowns) using an out-of-core version of a sparse multifrontal code called MUMPS (MUltifrontal Massively Parallel Solver) are used to analyse the behaviour of our algorithms. In the second part, we are interested in applications with sparse multiple right-hand sides, particularly those with single nonzero entries. The motivating applications arise in electromagnetism and data assimilation. In such applications, we need either to compute the null space of a highly rank deficient matrix or to compute entries in the inverse of a matrix associated with the normal equations of linear least-squares problems. We cast both of these problems as linear systems with multiple right-hand side vectors, each containing a single nonzero entry. We describe, implement and comment on efficient algorithms to reduce the input-output cost during an outof- core execution. We show how the sparsity of the right-hand side can be exploited to limit both the number of operations and the amount of data accessed. The work presented in this thesis has been partially supported by SOLSTICE ANR project (ANR-06-CIS6-010).

Cette thèse traite d’une routine d’algèbre linéaire largement utilisée pour la résolution des systèmes li- néaires, il s’agit de la factorisation LU. Habituellement, pour calculer une telle décomposition, on utilise l’élimination de Gauss avec pivotage partiel (GEPP). La stabilité numérique de l’élimination de Gauss avec pivotage partiel est caractérisée par un facteur de croissance qui est reste assez petit en pratique. Toutefois, la version parallèle de cet algorithme ne permet pas d’atteindre les bornes inférieures qui ca- ractérisent le coût de communication pour un algorithme donné. En effet, la factorisation d’un bloc de colonnes constitue un goulot d’étranglement en termes de communication. Pour remédier à ce problème, Grigori et al [60] ont développé une factorisation LU qui minimise la communication(CALU) au prix de quelques calculs redondants. En théorie la borne supérieure du facteur de croissance de CALU est plus grande que celle de l’élimination de Gauss avec pivotage partiel, cependant CALU est stable en pratique. Pour améliorer la borne supérieure du facteur de croissance, nous étudions une nouvelle stra- tégie de pivotage utilisant la factorisation QR avec forte révélation de rang. Ainsi nous développons un nouvel algorithme pour la factorisation LU par blocs. La borne supérieure du facteur de croissance de cet algorithme est plus petite que celle de l’élimination de Gauss avec pivotage partiel. Cette stratégie de pivotage est ensuite combinée avec le pivotage basé sur un tournoi pour produire une factorisation LU qui minimise la communication et qui est plus stable que CALU. Pour les systèmes hiérarchiques, plusieurs niveaux de parallélisme sont disponibles. Cependant, aucune des méthodes précédemment ci- tées n’exploite pleinement ces ressources. Nous proposons et étudions alors deux algorithmes récursifs qui utilisent les mêmes principes que CALU mais qui sont plus appropriés pour des architectures à plu- sieurs niveaux de parallélisme. Pour analyser d’une façon précise et réaliste / This dissertation focuses on a widely used linear algebra kernel to solve linear systems, that is the LU decomposition. Usually, to perform such a computation one uses the Gaussian elimination with partial pivoting (GEPP). The backward stability of GEPP depends on a quantity which is referred to as the growth factor, it is known that in general GEPP leads to modest element growth in practice. However its parallel version does not attain the communication lower bounds. Indeed the panel factorization rep- resents a bottleneck in terms of communication. To overcome this communication bottleneck, Grigori et al [60] have developed a communication avoiding LU factorization (CALU), which is asymptotically optimal in terms of communication cost at the cost of some redundant computation. In theory, the upper bound of the growth factor is larger than that of Gaussian elimination with partial pivoting, however CALU is stable in practice. To improve the upper bound of the growth factor, we study a new pivoting strategy based on strong rank revealing QR factorization. Thus we develop a new block algorithm for the LU factorization. This algorithm has a smaller growth factor upper bound compared to Gaussian elimination with partial pivoting. The strong rank revealing pivoting is then combined with tournament pivoting strategy to produce a communication avoiding LU factorization that is more stable than CALU. For hierarchical systems, multiple levels of parallelism are available. However, none of the previously cited methods fully exploit these hierarchical systems. We propose and study two recursive algorithms based on the communication avoiding LU algorithm, which are more suitable for architectures with multiple levels of parallelism. For an accurate and realistic cost analysis of these hierarchical algo- rithms, we introduce a hierarchical parallel performance model that takes into account processor and network hierarchies. This analysis enables us to accurately predict the performance of the hierarchical LU factorization on an exascale platform.