O método de Kaczmarz é um algoritmo iterativo que soluciona sistemas lineares do tipo Ax = b através de projeções sobre hiperplanos bastante usado em aplicações que envolvem a Tomografia Computadorizada. Recentemente voltou a ser destaque após a publicação de uma versão aleatória apresentada por Strohmer e Vershynin em 2009 a qual foi provada possuir taxa de convergência esperada exponencial. Posteriormente, Eldar e Needell em 2011 sugeriram uma versão modificada do algoritmo de Strohmer e Vershynin, na qual a cada iteração é selecionada a projeção ótima a partir de um conjunto aleatório, utilizando para isto o lema de Johnson-Lindenstrauss. Nenhum dos artigos mencionados apresenta uma técnica para a escolha do parâmetro de relaxação, entretanto, a seleção apropriada deste parâmetro pode ter uma influência substancial na velocidade do método. Neste trabalho apresentamos uma metodologia para a escolha do parâmetro de relaxação, bem como implementações paralelas do algoritmo de Kaczmarz utilizando as ideias de Eldar e Needell. Nossa metodologia para seleção do parâmetro utiliza uma nova generalização dos resultados de Strohmer e Vershynin que agora leva em consideração o parâmetro λ de relaxação e, a partir daí, obtemos uma estimativa da taxa de convergência como função de λ. Escolhemos então, para uso no algoritmo, aquele que otimiza esta estimativa. A paralelização dos métodos foi realizada através da plataforma CUDA e se mostrou muito promissora, pois conseguimos, através dela, um ganho significativo na velocidade de convergência / The Kaczmarz method is an iterative algorithm for finding the solution of a system of linear equations Ax = b by projecting onto the hyperplanes widely used in applications involving Computerized Tomography. It has been recently highlighted after the publication of a random version presented by Strohmer and Vershynin in 2009 that yields probably exponential convergence in expectation. Thereafter, Eldar and Needell in 2011 suggested a modified version of Strohmer and Vershynin algorithm, which at each iteration selects the optimal projection from a random set making use of the Johnson-Lindenstrauss lemma. None of the mentioned articles presents a technique for choosing the relaxation parameter, however, the proper selection of this parameter can achieve a substantial gain on the speed of the method. In this project we present a methodology for finding the relaxation parameter, as well as parallel implementations of Kacmarzs Algorithm using the ideas of Eldar and Needell. Our methodology for parameter selection uses a new generalization on Strohmer and Vershynins results which now regards the relaxation parameter λ. Thenceforward, we obtain an estimate of the convergence rate as a function of λ. Then we use this estimate in the algorithm the optimizer of this estimate. The parallelization of the methods has been implemented through the CUDA platform and appears to be very promising, since it delivers substantial gain in the convergence speed

O método de Kaczmarz é um algoritmo iterativo que soluciona sistemas lineares do tipo Ax = b através de projeções sobre hiperplanos bastante usado em aplicações que envolvem a Tomografia Computadorizada. Recentemente voltou a ser destaque após a publicação de uma versão aleatória apresentada por Strohmer e Vershynin em 2009 a qual foi provada possuir taxa de convergência esperada exponencial. Posteriormente, Eldar e Needell em 2011 sugeriram uma versão modificada do algoritmo de Strohmer e Vershynin, na qual a cada iteração é selecionada a projeção ótima a partir de um conjunto aleatório, utilizando para isto o lema de Johnson-Lindenstrauss. Nenhum dos artigos mencionados apresenta uma técnica para a escolha do parâmetro de relaxação, entretanto, a seleção apropriada deste parâmetro pode ter uma influência substancial na velocidade do método. Neste trabalho apresentamos uma metodologia para a escolha do parâmetro de relaxação, bem como implementações paralelas do algoritmo de Kaczmarz utilizando as ideias de Eldar e Needell. Nossa metodologia para seleção do parâmetro utiliza uma nova generalização dos resultados de Strohmer e Vershynin que agora leva em consideração o parâmetro λ de relaxação e, a partir daí, obtemos uma estimativa da taxa de convergência como função de λ. Escolhemos então, para uso no algoritmo, aquele que otimiza esta estimativa. A paralelização dos métodos foi realizada através da plataforma CUDA e se mostrou muito promissora, pois conseguimos, através dela, um ganho significativo na velocidade de convergência / The Kaczmarz method is an iterative algorithm for finding the solution of a system of linear equations Ax = b by projecting onto the hyperplanes widely used in applications involving Computerized Tomography. It has been recently highlighted after the publication of a random version presented by Strohmer and Vershynin in 2009 that yields probably exponential convergence in expectation. Thereafter, Eldar and Needell in 2011 suggested a modified version of Strohmer and Vershynin algorithm, which at each iteration selects the optimal projection from a random set making use of the Johnson-Lindenstrauss lemma. None of the mentioned articles presents a technique for choosing the relaxation parameter, however, the proper selection of this parameter can achieve a substantial gain on the speed of the method. In this project we present a methodology for finding the relaxation parameter, as well as parallel implementations of Kacmarzs Algorithm using the ideas of Eldar and Needell. Our methodology for parameter selection uses a new generalization on Strohmer and Vershynins results which now regards the relaxation parameter λ. Thenceforward, we obtain an estimate of the convergence rate as a function of λ. Then we use this estimate in the algorithm the optimizer of this estimate. The parallelization of the methods has been implemented through the CUDA platform and appears to be very promising, since it delivers substantial gain in the convergence speed

Submitted by Edisangela Bastos (edisangela@ufpa.br) on 2018-03-21T16:46:59Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MetodosProjecaoConvergencia.pdf: 3858869 bytes, checksum: 6d1d5430b45704ff15ac44b85f148097 (MD5) / Made available in DSpace on 2018-03-21T16:46:59Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MetodosProjecaoConvergencia.pdf: 3858869 bytes, checksum: 6d1d5430b45704ff15ac44b85f148097 (MD5) Previous issue date: 1987-03-20 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, mostramos de forma mais geral que é possível obtermos métodos de projeção com a mesma propriedade dos métodos propostos por Bjorck e Elfving. Em particular, estabelecemos versões modificadas dos métodos de Kaczmarz, Cimmino [ 5] e Garza que apresentam a propriedade anteriormente citada. Isto é mostrado como segue. Os capítulos 1 e 2 são dedicados a resolução numérica de sistemas algébricos de equações lineares consistentes. No capítulo 1, apresentamos uma versão bloco acelerada do método de Kaczmarz e outra, também bloco acelerada, do método de Cimmino que serão úteis para o desenvolvimento dos capítulos posteriores. Nõ capítulo 2, estabelecemos de forma geral, um algoritmo do tipo projeção e demonstramos que a convergência é atingida em um número finito e conhecido de passos mostrado que as versões dos métodos de Kaczxnarz e Ciinmino, apresentadas no capítulo 1, convenientemente modificadas, são do tipo do algoritmo estabelecido. O capítulo 3 é dedicado a resolução numérica do problema de Quadrados Mínimos Lineares. De forma similar ao capítulo 2, são estabelecidas as versões aceleradas dos métodos de Garza e Cimmino para a resolução desse problema. No capítulo 4, mostramos uma aplicação desses tipos de algoritmos, através da resolução de um problema de Engenharia Hidráulica.