Google

Aviso: Se está a ler esta mensagem, provavelmente, o browser que utiliza não é compatível com os "standards" recomendados pela W3C. Sugerimos vivamente que actualize o seu browser para ter uma melhor experiência de utilização deste "website". Mais informações em webstandards.org.

Warning: If you are reading this message, probably, your browser is not compliant with the standards recommended by the W3C. We suggest that you upgrade your browser to enjoy a better user experience of this website. More informations on webstandards.org.

Trabalho Final de Mestrado

Ano Lectivo: 2019/2020
Aluno: LEONARDO AUGUSTO LIMA FERREIRA DA SILVA (51869)
Mestrado: Mathematical Finance
Tipo: Estágio
Título do Trabalho Final de Mestrado: The Bandwidth minimisation problem: Applications in finance
Sub Título:
Comentário: -
Instituição: -
Homologação: Dia 10/12/2020 às 20:36 por NUNO JOÃO DE OLIVEIRA VALÉRIO

Resumo

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. (Português)

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. (Inglês)

Palavras-chave

minimização de largura de banda, métodos de diferenças finitas, pico de utilização de memória, tempo de execução (Português)

bandwidth minimization, finite difference scheme, peak memory usage, execution time (Inglês)

Resumo Alargado

O Resumo Alargado ainda não foi submetido.

Data da Prova Pública

Data da Prova Pública: 16-12-2020 14:00
Voltar