Full text
| |
| Author(s): |
Leonardo Bravo Estácio
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Carlos. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2014-05-16 |
| Examining board members: |
Elias Salomão Helou Neto;
Eduardo Fontoura Costa;
Marcos Eduardo Ribeiro do Valle Mesquita
|
| Advisor: | Elias Salomão Helou Neto |
| Abstract | |
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 (AU) | |
| FAPESP's process: | 12/11207-2 - About the Selection of the Relaxation and Ordering of the Projections in Kaczmarz method with Emphasis on Highly Parallel Implementations and Applications in Tomographic Reconstruction |
| Grantee: | Leonardo Bravo Estácio |
| Support Opportunities: | Scholarships in Brazil - Master |