Busca avançada
Ano de início
Entree


Sobre a escolha da relaxação e ordenação das projeções no método de Kaczmarz com ênfase em implementações altamente paralelas e aplicações em reconstrução tomográfica

Texto completo
Autor(es):
Leonardo Bravo Estácio
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Imprenta: São Carlos.
Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
Data de defesa:
Membros da banca:
Elias Salomão Helou Neto; Eduardo Fontoura Costa; Marcos Eduardo Ribeiro do Valle Mesquita
Orientador: Elias Salomão Helou Neto
Resumo

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 (AU)

Processo FAPESP: 12/11207-2 - Sobre a Escolha da Relaxação e Ordenação das Projeções no Método de Kaczmarz com Ênfase em Implementações Altamente Paralelas e Aplicações em Reconstrução Tomográfica
Beneficiário:Leonardo Bravo Estácio
Modalidade de apoio: Bolsas no Brasil - Mestrado