Algoritmos randomizados para a decomposição em valores singulares

• Processo: 15/18552-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2015
• Data de Término da vigência: 30 de setembro de 2016
• Área de 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
• Palavra(s)-Chave do Pesquisador: algoritmos randomizados | decomposição em valores singulares | processamento de matrizes | Técnicas de Processamento de Matrizes de Grandes Dimensões

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.