An analysis of bandwidth reduction

Mestrado em Mathematical FinanceO 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.The matrix bandwidth minimization problem consists in finding a permutation of rows and columns such that non-zero elements are kept in a band as close as possible to the main diagonal. This is a long-established NP-complete problem, that can also be formulated as a vertex labeling problem in a graph. Moreover, reordering instructions in computer programs may reduce peak memory usage by deallocating resources at optimal points of execution. This leads to the peak memory minimization problem, an extension of the bandwidth minimization problem, since it can also be formulated as a vertex labeling problem, where instructions and input/output dependency are translated into vertices and edges, respectively. Fortunately, for these graphs, low bandwidth implies low peak memory usage. In this report, the impact of bandwidth reduction is analyzed when numerically solving the heat equation and reducing peak memory usage of computer programs. The problems are carefully described and a variety of algorithms are implemented in C++, aiming to fully take advantage of bandwidth reduction.