Um algoritmo espectral para redução de envelope de matrizes esparsas

Um novo algoritmo para reduzir o envelope de uma matriz esparsa é apresentado. Este algoritmo é baseado no cálculo de autovetores da matriz laplaciana associada ao grafo da matriz esparsa. Uma reordenação da matriz esparsa é determinada com base nos valores numéricos das entradas de um autovetor da matriz laplaciana. Resultados numéricos mostram que o novo algoritmo de reordenação pode, em alguns casos, reduzir o envelope em mais de um fator de dois em relação aos algoritmos padrão atuais, como Gibbs-Poole-Stockmeyer (GPS) ou SPA RSPAK'S reverse Guthil!-McKee (RCM).