Estudo comparativo de Métodos de Resolução de Sistemas Lineares para Matrizes Cheias e Esparsas

Exportar este item:

Use este identificador para citar ou linkar para este item: http://www.bdtd.uerj.br/handle/1/17604

Tipo do documento:	Dissertação
Título:	Estudo comparativo de Métodos de Resolução de Sistemas Lineares para Matrizes Cheias e Esparsas
Título(s) alternativo(s):	Comparative study of Methods for Solving Full and Sparse Linear Systems
Autor:	Brum, Rafaela Correia
Primeiro orientador:	Castro, Maria Clicia Stelling de
Segundo orientador:	Faria, Cristiane Oliveira de
Primeiro membro da banca:	Carvalho Filho, Luiz Mariano Paes de
Segundo membro da banca:	Brandão, Diego Nunes
Resumo:	Sistemas lineares são modelos recorrentes na resolução de problemas em diversas áreas de conhecimento como simulação de fluidos, design de componentes eletrônicos, e até em áreas recentes como, Deep Learning e análise de dados de redes sociais. Quanto mais precisa a descrição do problema for, mais variáveis devemos conhecer para resolver os sistemas lineares, chegando a sistemas que passam dos terabytes de armazenamento. Por isso, é importante entendermos os métodos de resolução para propormos melhorias em seus algoritmos, como por exemplo, otimizações de memória e pontos de paralelismo. O objetivo principal dessa dissertação é realizar estudos comparativos entre métodos de resolução de sistemas lineares, para aprofundar o entendimento de cada método, além de observar se existe alguma predisposição de paralelismo nos métodos abordados. O primeiro estudo considerou métodos diretos de resolução de sistemas lineares com matrizes cheias. Resultados comparando precisão de variáveis, tempo de execução e a influência de parâmetros de compilação são apresentados. No segundo estudo, métodos iterativos foram aplicados em matrizes cheias. Resultados comparando um método recente, o método chamado de Delayed Over Relaxation (DOR) (ANTUONO; COLICCHIO, 2016) e um método distribuído, o Gauss-Seidel distribuído (SHANG, 2009) também são apresentados. Este último método teve um speedup de 1,15. Por fim, o último estudo focou nos métodos iterativos de projeção para matrizes esparsas. Neste estudo comparamos métodos clássicos como o GMRES(m) (SAAD; SCHULTZ, 1986) com métodos recentes, como o _GMRES (BAKER; JESSUP; KOLEV, 2009) e o Heavy Ball GMRES (IMAKURA; LI; ZHANG, 2016). Além disso, apresentamos um estudo inicial de paralelização do método Heavy Ball GMRES, que apresentou um speedup de 2,11.
Abstract:	Linear systems are recurrent models to solve problems in many areas as dynamic fluids, electronic computer design and even recent areas as Deep Learning and social media data analysis. As the linear system gets more precise to describe the real problem, more variables are needed to correctly solve the system, easily needing terabytes of storage. Having said that, it is important to understand the resolution methods to propose better algorithms, as memory optimizations and parallelism points. The objective of this work is do many comparative studies between resolution methods of linear systems to better understand each one and observe if there is any paralellism spot in the given methods. The first study was with direct methods to solve full matrices linear systems. In this study, we compare variable precision, execution time and compilation flags. The second study evaluated iterative methods to solve full matrices linear systems. In this study, we compare a recent method, named DOR (ANTUONO; COLICCHIO, 2016), and a distributed method, the Distributed Gauss-Seidel (SHANG, 2009). Our reproduction of this last method obtained 1,15 of speedup. Finally, the last study focused on iterative projective methods to solve sparse matrices linear systems. In this last study, we compare classical methods like GMRES(m) (SAAD; SCHULTZ, 1986) with recent methods as _GMRES (BAKER; JESSUP; KOLEV, 2009) and the Heavy Ball GMRES (IMAKURA; LI; ZHANG, 2016). Besides, we show an initial study of parallel points in the Heavy Ball GMRES method, which obtained an speedup of 2.11.
Palavras-chave:	Linear systems Direct and Iterative Methods Projection Methods Full and Sparse Matrices Memory optimization Parallelism Sistemas Lineares Métodos Diretos e Iterativos Métodos de Projeção Matrizes Cheias e Esparsas Otimização de memória Paralelização
Área(s) do CNPq:	CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	Brasil
Instituição:	Universidade do Estado do Rio de Janeiro
Sigla da instituição:	UERJ
Departamento:	Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística
Programa:	Programa de Pós-Graduação em Ciências Computacionais
Citação:	BRUM, Rafaela Correia. Estudo comparativo de Métodos de Resolução de Sistemas Lineares para Matrizes Cheias e Esparsas. 2019. 105 f. Dissertação (Mestrado em Ciências Computacionais) - Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2019.
Tipo de acesso:	Acesso Aberto
URI:	http://www.bdtd.uerj.br/handle/1/17604
Data de defesa:	6-Ago-2019
Aparece nas coleções:	Mestrado em Ciências Computacionais

Arquivos associados a este item:

Arquivo	Descrição	Tamanho	Formato
Dissertação - Rafaela Correia Brum - 2019 - Completa.pdf.pdf		1,09 MB	Adobe PDF	Baixar/Abrir Pré-Visualizar ×

Mostrar registro completo do item Recomendar este item Visualizar estatísticas