The Bandwidth minimisation problem: Applications in finance

O problema de minimização de largura de banda em matrizes consiste em encontrar uma permutação de linhas e colunas de forma que os elementos não nulos sejam mantidos em uma banda o mais próximo possível da diagonal principal. Este problema é conhecido por ser NP-completo, e também pode ser formulado como um problema de rotulagem de vértices em um grafo. Além disso, a reordenação de instruções em programas de computador pode reduzir o pico de utilização de memória, desalocando recursos em pontos ideais. Isso resulta no problema de minimização do pico de memória, que é uma extensão do problema de minimização de largura de banda, uma vez que também pode ser formulado como um problema de rotulagem de vértices, onde instruções e a dependência de entrada/saída são traduzidas em vértices e arestas, respectivamente. Para esses grafos, baixa largura de banda implica em baixo pico de utilização de memória. Neste relatório, o impacto da redução da largura de banda é analisado ao resolver numericamente a equação do calor e ao reduzir o pico de utilização de memória em programas. Os problemas são cuidadosamente descritos e uma variedade de algoritmos são implementados em C++, com o objetivo de aproveitar ao máximo a redução da largura de banda.