Dissertação
Parallelization of the Kaczmarz Algorithm EVALUATED
O algoritmo de Kaczmarz é um método iterativo que resolve sistemas lineares de equações. Destaca-se de outros algoritmos iterativos ao resolver sistemas com grandes dimensões por duas razões. Em primeiro lugar, em cada iteração, o algoritmo de Kaczmarz utiliza uma equação, resultando em trabalho computacional reduzido. Em segundo lugar, pode ser apenas necessário um pequeno subconjunto de equações do sistema para o resolver. Estas características têm atraído atenção para o algoritmo de Kaczmarz. Investigadores observaram que escolher as equações aleatoriamente pode melhorar a velocidade de convergência do algoritmo, o que levou ao desenvolvimento do algoritmo aleatório de Kaczmarz que, consequentemente, causou o aparecimento de variações do mesmo. Nesta tese, analisamos o comportamento do método de Kaczmarz e das suas variações sequenciais. Descobrimos que a versão aleatória do algoritmo que escolhe equações sem reposição pode superar tanto o método original como a versão aleatória. Além disso, exploramos abordagens para paralelizar o método de Kaczmarz. Em particular, implementamos o método aleatório de Kaczmarz com média que, para sistemas com ruído, reduz o erro da solução. Embora não seja possível obter uma parallelização eficiente deste algoritmo, apresentamos uma versão por blocos do método anterior que apresenta diminuições significativos nos tempos de execução em relação à sua contraparte sequencial. Finalmente, aplicamos o método de Kaczmarz para resolver problemas reais que envolvem sistemas com ruído derivados de tomografias computadorizadas. O objetivo é obter imagens que minimizem o erro de reconstrução. Mostramos que, incorporando restrições que sabemos ser verificadas pela imagem, o erro da solução reduz-se.
junho 21, 2023, 14:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
José Carlos Alves Pereira Monteiro
Departamento de Engenharia Informática (DEI)
Professor Catedrático