Busca avançada
Ano de início
Entree

Algoritmos randomizados para a decomposição em valores singulares

Processo: 15/18552-5
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de outubro de 2015
Vigência (Término): 30 de setembro de 2016
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
Pesquisador responsável:Renato da Rocha Lopes
Beneficiário:Antonio Pedro de Sousa Vieira
Instituição-sede: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Algoritmos   Métodos de decomposição   Matrizes   Processamento de dados

Resumo

A decomposição em valores singulares (SVD, do inglês singular value decomposition) é a fatoração de uma matriz real ou complexa na forma A = UV*, onde as matrizes U e V são unitárias e a matriz é diagonal. A SVD existe para qualquer matriz A. Tal decomposição é útil em diversas áreas, como o cálculo de soluções de quadrados mínimos e a aproximação de A por matrizes de baixo posto. Esta última aplicação é amplamente utilizada no processamento de grandes matrizes. Métodos clássicos para o cálculo de SVDs enfrentam barreiras relacionadas ao tamanho das matrizes de dados encontradas: o custo temporal de acesso a memória e o custo computacional associado às muitas operações necessárias para o cálculo da decomposição. O tempo de processamento pode ser reduzido com algoritmos randomizados, que minimizam o acesso à memória por meio de uma redução preliminar do posto, e por meio da paralelização do processamento. Neste trabalho, será realizado um estudo de implementações de SVD, partindo da abordagem clássica para incluir métodos randomizados, métodos que utilizem GPU e, posteriormente, uma implementação que acople as duas modificações. A análise comparativa dos resultados será conduzida com base no desempenho de implementações padrão em Python e MATLAB. Este estudo objetiva a formação do candidato no âmbito do processamento de dados e a criação de opções de código aberto para uso em decomposições de matrizes de grandes dimensões.