Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.

Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.

The presented thesis is focused on the GMRES convergence analysis. The basic principles of CG, MINRES and GMRES are briefly explained. The thesis summarizes some known convergence results of these methods. The known characterizations of the matrices and the right hand sides gen- erating the same Krylov residual spaces are summarized. Connections and the differences between the different points of view on GMRES convergence analysis are shown. We expect that if the convergence curve of GMRES applied to the nonnormal matrix and the right hand side seems to be de- termined by the eigenvalues of the matrix then exists a matrix that is close to normal and has the same spectrum as the matrix and for the right hand side has the same GMRES convergence curve (We assume that the initial approximation 0 = 0). Several numerical experiments are done to examine this assumption. This thesis describes an unpublished result of Gérard Meu- rant which is the formula for the norm of the -th error of GMRES applied to the matrix and right hand side and its derivation. The upper estimate of the -th GMRES error is derived. This estimate is minimized via spectrum.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-06-26T19:40:40Z No. of bitstreams: 1 MarcosSilvaMontelo.pdf: 2980665 bytes, checksum: 3b07ab02be8c6a4e17cda1a61787ffe2 (MD5) / Made available in DSpace on 2017-06-26T19:40:40Z (GMT). No. of bitstreams: 1 MarcosSilvaMontelo.pdf: 2980665 bytes, checksum: 3b07ab02be8c6a4e17cda1a61787ffe2 (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / In this work is investigated the performance of the GMRES Method in studies of power flow extremely loaded, ill-conditioned and including FACTS Controllers, focusing on Jacobian matrix with high numbers of conditioning and real eigenvalue close to zero, in order to consolidate the virtues of GMRES in ill-conditioned problems. From this information you can set operating scenarios that may indicate points of robustness and GMRES efficiency. Consolidating test systems (hypothetical and actual) of difficult convergence associated with extremely high loaded, is also part of research to create s cenarios close to reality, or that may occur in practice. The primary purpose of the inclusion of FACTS is to assess the impact that these devices can cause the Jacobian matrix. These characteristics are informed through eigenvalues and conditioning number. In addition, we propose an iterative solver developed in MATLAB platform for power flow studies and a detailed investigation of the influence of the reordering and the e limination of non-null elements in the quality of the preconditioner of incomplete factors. The proposed methodology was applied to hypothetical and real systems with FACTS controllers, and the results of the experiments showed the greater efficiency of the iterative solver GMRES in most simulations. It was found that the larger the size of the electrical system and the worse their numeric characteristics, the better its performance. / Neste Trabalho é investigado o desempenho do Método GMRES em estudos de Fluxo de potência extremamente carregados, mal condicionados e incluindo Controladores FACTS, enfocando matrizes Jacobianas com elevados números de condicionamento e autovalores reais próximos de zero, a fim de consolidar virtudes do GMRES na solução de problemas mal-condicionados. A apartir destas informações será possível estabelecer cenários de operação que poderão indicar pontos de robustez e eficiência do GMRES. A consolidação de sistemas-teste (hipotéticos e reais) de difícil convergência associados a carregamentos extremamente elevados, também faz parte das investigações para criar cenários próximos da realidade, ou seja, que possam ocorrer na prática. O objetivo primário da inclusão de FACTS está em avaliar o impacto que estes equipamentos podem causar na matriz Jacobiana. Estas características são informadas através de autovalores e número de condicionamento. Além disso, propõe-se um solucionador iterativo desenvolvido na plataforma MATLAB para estudos de fluxo de potência e uma investigação detalhada da influência do reordenamento e da eliminação de elementos não-nulos na qualidade do pré-condicionador de fatores incompletos. A metodologia proposta foi aplicada em sistemas hipotéticos e reais com Controladores FACTS, e os resultados dos experimentos mostraram a maior eficiência do solucionador iterativo GMRES em grande parte das simulações realizadas. Verificou-se que, quanto maior a dimensão do sistema elétrico e quanto pior suas características numéricas, melhor seu desempenho.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-02-13T20:18:37Z No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-02-16T19:30:20Z (GMT) No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) / Made available in DSpace on 2017-02-16T19:30:20Z (GMT). No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) Previous issue date: 2016-07-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / Este trabalho tem por objetivo investigar o comportamento de converg?ncia do m?todo GMRES (Generalized Minimal RESidual) e sua vers?o GMRES(m), sem e com precondicionador ILU(0) aplicado ? sistemas lineares n?o sim?tricos esparsos. Nosso interesse principal ? verificar se o comportamento destes algoritmos pode ser influenciado pela estrutura das matrizes consideradas, em particular, as Z-matrizes e a influ?ncia da escolha do grau de esparsidade. Entre os par?metros observados, concentramos no raio espectral dessas matrizes, tanto como a norma do res?duo relativo obtido por estes algoritmos. / This study aims to investigate the convergence behavior of the GMRES (Generalized Minimal Residual) method and its version GMRES(m), without and with preconditioner ILU(0) applied to sparse non-symmetric linear systems. Our main interest is to see if the behavior of these algorithms can be influenced by the structure of the matrices considered, in particular, the Z-matrices. Furthermore, the influence of the choice of the degree of sparsity. Among the observed parameters, we focus on the spectral radius of these matrices, as well as the relative residual norm obtained by these algorithms.

Made available in DSpace on 2015-03-03T15:32:44Z (GMT). No. of bitstreams: 1 ElvisNM_DISSERT.pdf: 1325328 bytes, checksum: 26a5738f48a900e63cafc3f1e0b1d776 (MD5) Previous issue date: 2014-04-22 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Neste trabalho estudamos o problema n?o linear F(X) = 0, onde F ? continuamente diferenci?vel com F : Rn-> Rn. Para solucion?-lo empregamos o m?todo de Newton Inexato obtendo um sistema linearizado J(xk)sk =-F(xk), onde J(xk) representa a matriz Jacobiana no ponto xk e o passo iterativo sk ? calculado por meio do m?todo do Res?duo M?nimo Generalizado (GMRES), que pertence ? fam?lia dos m?todos de proje??o em subespa?os de Krylov. Afim de evitar de evitar o acr?scimo no custo computacional devido ao aumento a cada itera??o na dimens?o do subespa?o de Krylov utilizamos o GMRES com recome?os ou GMRES(m), o qual pode apresentar problemas de estagna??o (duas solu??es consecutivas iguais ou quase iguais). Uma das maneiras de contornar essa estagna??o est? no uso de precondicionadores no sistema inicial Ax = b, passando a um sistema equivalente do tipo M-1Ax = M-1b onde a matriz M ? chamada de precondicionador e tem o papel de facilitar a solu??o do sistema inicial. A escolha de precondicionadores ? uma ?rea de pesquisa que remete ao conhecimento espec?fico a priori do problema a ser resolvido e/ou da estrutura da matriz dos coeficientes A. Neste trabalho buscamos estudar o precondicionamento pela esquerda no m?todo do Newton Inexato - GMRES(m). Apresentamos tamb?m uma estrat?gia que permite a mudan?a entre 3 tipos de precondicionadores (Jacobi, ILU e SSOR) dependendo de informa??es advindas da aplica??o do GMRES(m) a cada itera??o do Newton Inexato, ou seja, a cada vez que se resolve o sistema linearizado precondicionado. Assim fazemos ao final uma compara??o entre nossas estrat?gias e o uso de precondicionadores fixos na resolu??o de problemas teste por meio do NI-GMRES

[pt] O desenvolvimento e/ou a adaptação de métodos numéricos para aplicação em análises computacionais de estabilidade de sistemas elétricos no domínio do tempo costumam despertar interesse em função das dificuldades de solução das equações diferenciais e algébricas (EDAs) que representam a rede e seus componentes. Condições de operações muito carregadas e compensadas dificultam a solução, devido, p.ex., ao mau condicionamento da matriz Jacobiana, instabilidade numérica e singularidade. Uma dessas dificuldades pode surgir durante a solução de equações não lineares, especificamente no problema linear do tipo Ax = b. Para contornar estas e outras dificuldades, a presente tese procurou contribuir no aspecto numérico do problema destacando a aplicação do método iterativo Resíduo Mínimo Generalizado - GMRES na solução do problema. Optou-se por trabalhar na qualidade do pré-condicionador construído com base na matriz Jacobiana calculada no início do processo de solução. Verificou-se que, se esta matriz estiver bem condicionada, a qualidade do pré-condicionador resultante dela é boa para o GMRES atingir a convergência em poucas iterações. Comprovou-se através de experimentos numéricos com diferentes sistemas-teste e diferentes condições de operação, que o condicionamento da matriz Jacobiana é melhorado se escalonada, normalizada e reordenada antes da construção do pré-condicionador, resultando, de fato, num pré-condicionador de boa qualidade, agindo positivamente no desempenho do GMRES e consequentemente no processo global de solução. / [en] The development and/or adaptation of numerical methods when applied to power systems stability computer simulations in time domain are of interest due to the difficulties related to the solution of the algebraic differential equations (ADEs) which represent the network and its components. The solution of networks operating under heavy load conditions and extremely compensated is difficult due to the ill-conditioning of the Jacobian matrix, numerical instability and singularity. It can happen, for instance, when solving linear problems of type Ax = b. In order to overcome this and other difficulties, this thesis aims to contribute in the numerical aspect of the problem applying the Generalized Minimal Residual method – GMRES to solve the problem. The idea is to work over the preconditioner quality constructed based on the Jacobian matrix. It is shown that, if this matrix is well conditioned, the quality of the resulting preconditioner is good enough to the GMRES reaches convergence in few iterations. It is seen through numerical experiments using different test-systems and different operating conditions as well, that the Jacobian matrix conditioning is improved if scaled, normalized and reordered before the preconditioner construction, resulting, in fact, in a high quality preconditioner, improving the GMRES performance.

No description available.

NITSOL: A Newton Iterative Solver for Nonlinear Systems describes an algorithm for solving nonlinear systems. Michael Pernice and Homer F. Walker, the authors of the paper NITSOL [3], implemented this algorithm in FORTRAN. The goal of the project has been to use the modern and robust language MATLAB to implement the NITSOL algorithm. In this paper, the main mathematical and algorithmic background for understanding NITSOL are described, and a user guide is included outlining how to use the MATLAB implementation of NITSOL. A nonlinear system example problem, the 2D Bratu problem, and the solution obtained by MATLAB NITSOL's are also included.

This thesis deals with the numerical solution of ordinary differential equations (ODEs) using finite difference (FD) methods. In particular, boundary summation equation (BSE) preconditioning for FD approximations for ODEs with constant coefficients on locally refined meshes is studied. Firstly, the BSE for FD approximations of ODEs with constant coefficients is derived on a locally refined mesh. Secondly, the obtained linear system of equations are solved by the iterative method GMRES. Then, the arithmetic complexity and convergence rate of the iterative solution of the BSE formulation are discussed. Finally, numerical experiments are performed to compare the new approach with the FD approach. The results show that the BSE formulation has low arithmetic complexity and the convergence rate of the iterative solvers is fast and independent of the number of grid points.