Neste trabalho demos continuidade ao estudo desenvolvido por Colla (2007) que utilizou-se do arcabouço de álgebra linear com técnicas de fatoração de matrizes esparsas aplicadas à inferência em redes Bayesianas. Com isso, a biblioteca computacional resultante possui uma separação clara entre a fase simbólica e numérica da inferência, o que permite aproveitar os resultados obtidos na primeira etapa para variar apenas os valores numéricos. Aplicamos técnicas de paralelização para melhorar o desempenho computacional, adicionamos inferência para Redes Credais e novos algoritmos para inferência em Redes Bayesianas para melhor eciência dependendo da estrutura do grafo relacionado à rede e buscamos tornar ainda mais independentes as etapas simbólica e numérica. / In this work we continued the study by Colla (2007), who used the framework of linear algebra techniques with sparse matrix factorization applied to inference in Bayesian networks. Thus, the resulting computational library has a clear separation between the symbolic and numerical phase of inference, which allows you to use the results obtained in the rst step to vary only numeric values. We applied parallelization techniques to improve computational performance, we add inference to Credal Networks and new algorithms for inference in Bayesian networks for better eciency depending on the structure of the graph related to network and seek to become more independent symbolic and numerical steps.

Neste trabalho demos continuidade ao estudo desenvolvido por Colla (2007) que utilizou-se do arcabouço de álgebra linear com técnicas de fatoração de matrizes esparsas aplicadas à inferência em redes Bayesianas. Com isso, a biblioteca computacional resultante possui uma separação clara entre a fase simbólica e numérica da inferência, o que permite aproveitar os resultados obtidos na primeira etapa para variar apenas os valores numéricos. Aplicamos técnicas de paralelização para melhorar o desempenho computacional, adicionamos inferência para Redes Credais e novos algoritmos para inferência em Redes Bayesianas para melhor eciência dependendo da estrutura do grafo relacionado à rede e buscamos tornar ainda mais independentes as etapas simbólica e numérica. / In this work we continued the study by Colla (2007), who used the framework of linear algebra techniques with sparse matrix factorization applied to inference in Bayesian networks. Thus, the resulting computational library has a clear separation between the symbolic and numerical phase of inference, which allows you to use the results obtained in the rst step to vary only numeric values. We applied parallelization techniques to improve computational performance, we add inference to Credal Networks and new algorithms for inference in Bayesian networks for better eciency depending on the structure of the graph related to network and seek to become more independent symbolic and numerical steps.

Este estudo tem como objetivo melhorar o desempenho computacional dos algoritmos de inferência em redes credais, aplicando técnicas de computação paralela e sistemas distribuídos em algoritmos de fatoração de matrizes esparsas. Grosso modo, técnicas de computação paralela são técnicas para transformar um sistema em um sistema com algoritmos que possam ser executados concorrentemente. E a fatoração de matrizes são técnicas da matemática para decompor uma matriz em um produto de duas ou mais matrizes. As matrizes esparsas são matrizes que possuem a maioria de seus valores iguais a zero. E as redes credais são semelhantes as redes bayesianas, que são grafos acíclicos que representam uma probabilidade conjunta através de probabilidades condicionais e suas relações de independência. As redes credais podem ser consideradas como uma extensão das redes bayesianas para lidar com incertezas ou a má qualidade dos dados. Para aplicar a técnica de paralelização de fatoração de matrizes esparsas na inferência de redes credais, a inferência utiliza-se da técnica de eliminação de variáveis onde o grafo acíclico da rede credal é associado a uma matriz esparsa e cada variável eliminada é análoga a eliminação de uma coluna. / This study\'s objective is the computational performance improvement of credal network inference algorithms by applying computational parallel and distributed system techniques of sparse matrix factorization algorithms. Roughly, computational parallel techniques are used to transform systems in systems with algorithms that can be executed concurrently. And the matrix factorization is a group of mathematical techniques to decompose a matrix in a product of two or more matrixes. The sparse matrixes are matrixes which have most of their values equal to zero. And credal networks are similar to Bayesian networks, which are acyclic graphs representing a joint probability through conditional probabilities and their independence relations. Credal networks can be considered as a Bayesian network extension because of their manner of leading to uncertainty and the poor data quality. To apply parallel techniques of sparse matrix factorization in credal network inference the variable elimination method was used, where the credal network acyclic graph is associated to a sparse matrix and every eliminated variable is analogous to an eliminated column.

Este estudo tem como objetivo melhorar o desempenho computacional dos algoritmos de inferência em redes credais, aplicando técnicas de computação paralela e sistemas distribuídos em algoritmos de fatoração de matrizes esparsas. Grosso modo, técnicas de computação paralela são técnicas para transformar um sistema em um sistema com algoritmos que possam ser executados concorrentemente. E a fatoração de matrizes são técnicas da matemática para decompor uma matriz em um produto de duas ou mais matrizes. As matrizes esparsas são matrizes que possuem a maioria de seus valores iguais a zero. E as redes credais são semelhantes as redes bayesianas, que são grafos acíclicos que representam uma probabilidade conjunta através de probabilidades condicionais e suas relações de independência. As redes credais podem ser consideradas como uma extensão das redes bayesianas para lidar com incertezas ou a má qualidade dos dados. Para aplicar a técnica de paralelização de fatoração de matrizes esparsas na inferência de redes credais, a inferência utiliza-se da técnica de eliminação de variáveis onde o grafo acíclico da rede credal é associado a uma matriz esparsa e cada variável eliminada é análoga a eliminação de uma coluna. / This study\'s objective is the computational performance improvement of credal network inference algorithms by applying computational parallel and distributed system techniques of sparse matrix factorization algorithms. Roughly, computational parallel techniques are used to transform systems in systems with algorithms that can be executed concurrently. And the matrix factorization is a group of mathematical techniques to decompose a matrix in a product of two or more matrixes. The sparse matrixes are matrixes which have most of their values equal to zero. And credal networks are similar to Bayesian networks, which are acyclic graphs representing a joint probability through conditional probabilities and their independence relations. Credal networks can be considered as a Bayesian network extension because of their manner of leading to uncertainty and the poor data quality. To apply parallel techniques of sparse matrix factorization in credal network inference the variable elimination method was used, where the credal network acyclic graph is associated to a sparse matrix and every eliminated variable is analogous to an eliminated column.

Este trabalho propõe uma nova abordagem, baseada em wavelets, para o método Multigrid Algébrico (WAMG). Nesta nova abordagem, a Transformada Discreta Wavelet é aplicada na matriz de coeficientes do sistema linear gerando uma aproximação dessa matriz em cada nível do processo de multiresolução. As vantagens da nova abordagem, que incluem maior facilidade de paralelização e menor tempo de montagem, são apresentadas com detalhes e uma análise quantitativa de convergência do método WAMG é realizada a partir da sua aplicação em problemas testes. O WAMG também é testado como pré- condicionador para métodos iterativos no subespaço de Krylov na análise magnetostática e magnetodinâmica (regime permanente senoidal) pelo Método dos Elementos Finitos, e em matrizes esparsas extraidas das coleções Matrix Market e da Universidade da Flórida. São apresentados resultados numéricos comparando o WAMG com o Multigrid Algébrico tradicional e com os pré-condicionadores baseados em decomposições incompletas de Cholesky e LU. / In this work we propose a wavelet-based algebraic multigrid method (WAMG) as a linear system solver as well as a prediconditioner for Krylov subspace methods. It is a new approach for the Algebraic Multigrid method (AMG), which considers the use of Discrete Wavelet Transform (DWT) in the construction of a hierarchy of matrices. The two-dimensional DWT is applied to produce an approximation of the matrix in each level of the wavelets multiresolution decomposition process. The main advantages of this new approach are presented and a quantitative analysis of its convergence is shown after its application in some test problems. The WAMG also is tested as a preconditioner for Krylov subspace methods in problems with sparse matrices, in nonlinear magnetic field problems and in 3D time-harmonic Electromagnetic Edge-based Finite Element Analysis. Numerical results are presented comparing the WAMG with the standard Algebraic Multigrid method and with the preconditioners based on the incomplete Cholesky and LU decompositions.

Este trabalho propõe uma nova abordagem, baseada em wavelets, para o método Multigrid Algébrico (WAMG). Nesta nova abordagem, a Transformada Discreta Wavelet é aplicada na matriz de coeficientes do sistema linear gerando uma aproximação dessa matriz em cada nível do processo de multiresolução. As vantagens da nova abordagem, que incluem maior facilidade de paralelização e menor tempo de montagem, são apresentadas com detalhes e uma análise quantitativa de convergência do método WAMG é realizada a partir da sua aplicação em problemas testes. O WAMG também é testado como pré- condicionador para métodos iterativos no subespaço de Krylov na análise magnetostática e magnetodinâmica (regime permanente senoidal) pelo Método dos Elementos Finitos, e em matrizes esparsas extraidas das coleções Matrix Market e da Universidade da Flórida. São apresentados resultados numéricos comparando o WAMG com o Multigrid Algébrico tradicional e com os pré-condicionadores baseados em decomposições incompletas de Cholesky e LU. / In this work we propose a wavelet-based algebraic multigrid method (WAMG) as a linear system solver as well as a prediconditioner for Krylov subspace methods. It is a new approach for the Algebraic Multigrid method (AMG), which considers the use of Discrete Wavelet Transform (DWT) in the construction of a hierarchy of matrices. The two-dimensional DWT is applied to produce an approximation of the matrix in each level of the wavelets multiresolution decomposition process. The main advantages of this new approach are presented and a quantitative analysis of its convergence is shown after its application in some test problems. The WAMG also is tested as a preconditioner for Krylov subspace methods in problems with sparse matrices, in nonlinear magnetic field problems and in 3D time-harmonic Electromagnetic Edge-based Finite Element Analysis. Numerical results are presented comparing the WAMG with the standard Algebraic Multigrid method and with the preconditioners based on the incomplete Cholesky and LU decompositions.

[pt] Este trabalho apresenta técnicas de reordenação para minimização de banda, perfil e frente de malhas de elementos finitos. Um conceito unificado relacionando as malhas de elementos finitos, os grafos associados e as matrizes correspondentes é proposto. As informações geométricas, disponíveis nos programans de elemnetos finitos, são utilizadas para aumentar a eficiência dos algoritmos heurísticos. Com base nestas idéias, os algoritmos são classificados em topológicos, geométricos, híbridos e espectrais. Um Grafo de Elementos Finitos - Finite Element Graph (FEG)- é definido coo um grafo nodal(G), um garfo dual(G) ou um grafo de comunicação(G.), associado a uma dada malha de elementos finitos. Os algoritmos topológicos mais utilizados na literatura técnica, tais como, Reverse- CuthiiMcKee (RCM), Collins, Gibbs-Poole-Stockmeyer(GPS), Gibbs-King (GK), Snay e Sloan, são inventigados detalhadamente. Em particular, o algoritmo de Collins é estendido para consideração de componentes não conexos nos grafos associados e a numeração é invertida para uma posterior redução do perfil das matrizer correspondentes. Essa nova versão é denominada Modified Reverse Collins (MRCollins). Um algoritmo puramente geométrico, denominado Coordinate Based Bandwidth and Profile Reduction (CBBPR), é apresentado. Um novo algoritmo híbrido (HybWP) para redução de frente e perfil é proposto. A matriz Laplaciana [L(G), L(G) ou L (G.)], utilizada no estudo de propriedades espectrais de grafos, é construída a partir das relações usuais de adjacências entre vértices e arestas. Um algoritmo automático, baseado em propriedades espectrais de FEGs, é proposto para reordenação de nós e/ou elementos das malhas associadas. Este algoritmo, denominado Spectral FEG Resequencing (SFR), utiliza informações globais do grafo; não depende da escolha de um vértice pseudo- periférico; e não utiliza o conceito de estrutura de níveis. Um novo algoritmo espectral para determinação de vértices pseudo-periféricos em grafos também é proposto. Os algoritmos apresentados neste trabalho são implementados computacionalmente e testados utilizando- se diversos exemplos numéricos. Finalmente, conclusões são apresentadas e algumas sugestões para trabalhos futuros são propostas. / [en] This work presents resequencing techniques for minimizing bandwidth, profile and wavefront of finite element meshes. A unified approach relating a finite element mesh, its associated graphs, and the corresponding matrices is proposed. The geometrical information available from conventional finite element program is also used in order to improve heuristic algorithms. Following these ideas, the algorithms are classified here as a nodal graph (G), a dual graph (G) or a communication graph (G.) associated with a generic finie element mesh. The most widely used topological algorithms, such as Reverse-Cuthill-McKee (RCM), Collins, Gibbs-Poole-Stockmeyer (GPS), Gibbs-King (GK), Snay, and Sloan, are investigated in detail. In particular, the Collins algorithm is extended to consider nonconnected components in associated graph and the ordering provide by this algorithm is reverted for improved profile. This new version is called Modified Reverse Collins (MRCollins). A purely geometrical algorithm, called Coordinate Based Bandwidth and Profile Reduction (CBBPR), is presented. A new hybrid reordering algorithm (HybWP) for wavefront and profile reduction is proposed. The Laplacian matrix [L(G), L(G) or L(G.)], used for the study of spectral properties of an FEG, is constructed from usual vertex and edge conectivities of a graph. An automatic algorithm, based on spectral properties of an FEG, is proposed to reorder the nodes and/or elements of the associated finite element meshes. The new algorithm, called Spectral FEG Resequencing (SFR), uses global information in the graph; it does not depende on a pseudoperipheral vertex in the resequencing process; and it does not use any kind of level structure of the graph. A new spectral algorithm for finding pseudoperipheral vertices in graphs is also proposed. The algorithmpresented herein are computationally implemented and tested against several numerical examples. Finally, conclusions are drawn and directions for futue work are given.