Complexidade de Algoritmos

Multiplica¸ao de Matrizes e Complexidade de c˜ Algoritmos
Andr´ Eleuterio, Leonardo Pereira e Universidade Tecnol´gica Federal do Paran´, Curitiba - Paran´, Brazil o a a 29 de Novembro de 2013

1

Resumo
Imagens s˜o armazenadas em um computador como matrizes. Pora tanto as opera¸˜es que envolvem gera¸˜o e atualiza¸˜o de imagens co ca ca necessitam de algoritmos eficientes para a multiplica¸˜o de matrica zes. Al´m disso, matrizes s˜o importantes para a ´rea de hardware, e a a como chips DSP, que est˜o presentes na grande maioria dos aparelhos a eletrˆnicos. Esta monografia apresenta um detalhamento e impleo menta¸˜o do algoritmo de Strassen, que ´ o mais utilizado na atualica e dade. Como extens˜o, ser˜o apresentados algoritmos mais modernos a a e a raz˜o pela qual estes n˜o s˜o t˜o utilizados quanto o algoritmo de a a a a
Strassen.

Palavras-chave: Multiplica¸ao de matrizes, complexidade de algoritc˜ mos, algoritmo de Strassen, nota¸ao O-Grande c˜ Abstract
Images are stored in a computer as matrices. Therefore, the operations that regard the displaying and refreshing of images require efficient algorithms for matrix multiplication. Furthermore, matrices are important for hardware, where DSP chips are used in the majority of electronic devices, such as cameras and cell phones. This scientific article presents a detailed explanation and implementation of the Strassen algorithm, the most commonly used algorithm of such kind today. Also, it will present more modern algorithms and the reason why they aren’t utilized as much as the Strassen algorithm.

Keywords: Matrix multiplication, algorithm complexity, Strassen algorithm, Big-O notation

2

1

Introdu¸˜o ca Matrizes representam um importante papel, tanto na matem´tica quanto na a computa¸ao. Na matem´tica sistemas lineares de diversas vari´veis podem c˜ a a ser resolvidos atrav´s de opera¸˜es com matrizes. No escopo da computa¸ao, e co c˜ foco deste