Algoritmos para Multiplicação Matricial
share
The goal of this article is to study algorithms that compute the product between two matrixes, specifically using the ingenuous methods of Strassen and Strassen-Winograd, which will be presented in Section 2. At present, the cited methods are not the most optimal considering the arithmetic complexity of these algorithms (see Table 1). However, changes to the Strassen and Strassen-Winograd methods will be exposed which will result in a reduction in their memory allocation and/or execution time. The algorithms in this study were implemented using the Julia programming language, version 1.9.1, with the aid of the packages Pluto (notebooks), Plots (graphic visualization of the results) and BenchmarkTools (measurement of memory allocation and execution time of the algorithms). – O objetivo deste artigo é estudar algoritmos que computam o produto entre duas matrizes, mais especificamente utilizando os métodos ingênuo, de Strassen e de Strassen-Winograd, que serão apresentados na Seção 2. Atualmente, os métodos citados não são os mais otimizados considerando a complexidade aritmética de seus algoritmos (vide Tabela 1). No entanto, serão expostas modificações dos métodos de Strassen e Strassen-Winograd que conseguem reduzir sua alocação de memória e/ou tempo de execução. Os algoritmos do problema em estudo foram implementados utilizando a linguagem de programação Julia, na versão 1.9.1, com o auxílio dos pacotes Pluto (notebooks), Plots (visualização gráfica dos resultados) e BenchmarkTools (medição de alocação de memória e tempo de execução dos algoritmos).
READ FULL TEXT