O ALGORITMO DE STRASSEN E A COMPLEXIDADE DE FORMAS BILINEARES

Resumo

Este estudo investigou a complexidade de formas bilineares, em especial o produto de matrizes, com foco nos avanços iniciais advindos de alguns dos primeiros resultados obtidos nesta área, começando com o algoritmo subcúbico descoberto por Strassen em 1969.
A análise aprofundada do trabalho posterior de Winograd permitiu a compreensão de qual é a cota inferior para o caso 2 × 2, independentemente do tipo de algoritmo utilizado. A interpretação dos resultados de Winograd revelou-se especialmente desafiadora, devido à concisão da demonstração original, que omite algumas justificativas essenciais. Isso exigiu um esforço adicional para compreender as ideias subjacentes e conectar as diferentes passagens matemáticas.
Por fim, o exame do algoritmo de Laderman mostrou que pode-se estender a busca pela otimização para matrizes de dimensão maior. No entanto, observou-se que o algoritmo de Strassen continua sendo o mais eficiente, do ponto de vista assintótico.
A pesquisa proporcionou uma visão abrangente sobre como a otimização da multiplicação matricial está intrinsecamente ligada à decomposição de tensores e ao estudo da complexidade computacional. Isso reforça a importância de desenvolver algoritmos mais eficientes, que desempenham um papel crucial em diversas aplicações científicas e tecnológicas.