Data: 07/05/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Matrizes simétricas: diagonalização e treewidth
Palestrante: Carlos Hoppen (UFRGS)


Resumo: Encontrar uma matriz diagonal D que é congruente a uma matriz simétrica M tem diversas aplicações, como classificar formas quadráticas ou determinar o número de autovalores de uma matriz em um determinado intervalo. Nessa palestra, discutiremos esse problema de forma mais geral e apresentaremos um algoritmo de programação dinâmica que encontra uma matriz diagonal com essa propriedade, dada a matriz M e uma decomposição em árvore de um grafo associado a M. Esse algoritmo se insere em uma gama de resultados do tipo  "FPT within P", que investigam problemas fundamentais que podem ser resolvidos em tempo polinomial, mas para os quais um expoente melhor pode ser obtido por um algoritmo FPT que também é polinomial no parâmetro k. No nosso caso, k é a largura de árvore (treewidth) do grafo.