Em um trabalho recente, um novo recorde de velocidade foi estabelecido para a multiplicação de duas matrizes . Também marca o fim de uma era para o método que os cientistas têm usado para pesquisas por décadas.
Os matemáticos se esforçam para atingir um objetivo mítico - o segundo grau (expoente dois), ou seja, multiplicar um par de matrizes n x n em apenas n 2 etapas. Os pesquisadores estão se aproximando de seu objetivo, mas será que algum dia conseguirão alcançá-lo?
Para cientistas da computação e matemáticos, a própria ideia do "segundo grau" está associada à ideia de um mundo perfeito.
“É difícil distinguir entre pensamento científico e devaneio sem fundamento”, admite Chris Umans, do California Institute of Technology. "Eu quero que o diploma seja dois porque é lindo."
Do ponto de vista do número necessário de etapas, "segundo grau" é a velocidade de execução idealuma das operações matemáticas mais fundamentais é a multiplicação de matrizes. Se o segundo grau for alcançável, a multiplicação da matriz pode ser realizada o mais rápido fisicamente possível. Se não for esse o caso, estaremos presos em um mundo que não corresponde aos nossos sonhos.
Matrizes são arranjos de números. Quando as duas matrizes concordam (o número de colunas no primeiro fator é igual ao número de linhas no segundo), elas podem ser multiplicadas para obter o terceiro. Por exemplo, se você começar com um par de matrizes 2 x 2, seu produto também será uma matriz 2 x 2 contendo quatro elementos. Mais geralmente, o produto de um par de matrizes n x n é outra matriz n x n com n 2 elementos.
Portanto, o menor número possível de passos para multiplicar pares de matrizes é n 2 , ou seja, o número de passos necessários apenas para escrever a resposta. Daí o nome "segundo grau".
E embora ninguém saiba ao certo se isso pode ser alcançado, os pesquisadores continuam a se mover nessa direção.
O artigo, publicado em outubro, chega ainda mais perto da meta e descreve o método mais rápido de multiplicação de duas matrizes até o momento. O resultado foi recebido por Josh Alman , estudante de doutorado na Universidade de Harvard, e Virginia Wasilewska Williamsdo Massachusetts Institute of Technology, diminui o grau do melhor anterior em cerca de cem milésimos. Esta é realmente uma grande conquista nesta área, alcançada através de um trabalho árduo.
Para obter uma melhor compreensão deste processo e como ele pode ser melhorado, vamos começar com um par de matrizes 2 x 2, A e B. Ao calcular cada elemento de seu produto, você usa a linha correspondente de A e a coluna correspondente de B. Para obter o elemento superior direito, multiplique o primeiro número na primeira linha A pelo primeiro número na segunda coluna B, em seguida, multiplique o segundo número na primeira linha A pelo segundo número na segunda coluna B e adicione os dois produtos.
Samuel Velasco / Revista Quanta
Esta operação é conhecida como obter um "produto escalar" de uma linha com uma coluna (às vezes chamado de "produto interno"). Para calcular outros elementos no produto da matriz, repita o procedimento com as linhas e colunas correspondentes.
Em geral, o método clássico de multiplicação de matrizes 2 x 2 consiste em oito multiplicações e várias adições. Normalmente, esse método de multiplicação de duas matrizes n x n requer n 3 multiplicações.
À medida que o tamanho das matrizes aumenta, o número de multiplicações necessárias para encontrar seu produto cresce muito mais rápido do que o número de adições. Para encontrar o produto de matrizes 2 x 2, são necessárias apenas oito multiplicações intermediárias e, para encontrar o produto de matrizes 4 x 4, já existem 64. No entanto, o número de adições necessárias para obter a soma dessas matrizes é não muito diferente. Normalmente, o número de adições é igual ao número de elementos na matriz, ou seja, quatro para matrizes 2 x 2 e 16 para matrizes 4 x 4. Essa diferença entre adição e multiplicação deixa claro por que os pesquisadores medem a velocidade de multiplicação da matriz apenas em termos do número de multiplicações necessárias.
“Multiplicações são tudo”, diz Umans. “O expoente no final depende inteiramente do número de multiplicações. As adições desaparecem em certo sentido. "
Por séculos, as pessoas acreditaram que n 3 era a maneira mais rápida de multiplicar matrizes . Em 1969, Volker Strassen supostamente tentou provar que é impossível multiplicar matrizes 2 x 2 usando menos de oito multiplicações. Aparentemente, ele ainda não conseguiu encontrar a prova, e depois de um tempo entendeu o porquê: na verdade, existe uma maneira de fazer isso usando sete multiplicações!
Strassen criou um conjunto complexo de relações que lhe permitiu substituir uma dessas oito multiplicações por 14 adições adicionais. A diferença pode parecer uma diferença sutil, mas vale a pena porque a multiplicação contribui mais do que a adição. Encontrando uma maneira de se livrar de uma multiplicação para matrizes 2 x 2 pequenas, Strassen descobriu uma possibilidade que ele poderia usar ao multiplicar matrizes maiores.
“Essa pequena mudança se traduz em grandes melhorias no manuseio de grandes matrizes”, diz Williams.
Virginia Wasilewska Williams do Massachusetts Institute of Technology e Josh Alman da Harvard University descobriram a maneira mais rápida de multiplicar duas matrizes em n 2,3728596 etapas. Jared Charney; Richard T.K. Falcão
Suponha que você queira multiplicar um par de matrizes 8 x 8. Uma maneira de fazer isso é dividir cada matriz grande em quatro matrizes 4 x 4, de modo que cada uma tenha quatro elementos. Uma vez que os elementos de uma matriz também podem ser matrizes, você pode pensar nas matrizes originais como um par de matrizes 2 x 2, cada um dos quatro elementos sendo uma matriz 4 x 4. Com alguma manipulação, cada um desses 4 x 4 matrizes podem ser divididas em quatro matrizes de tamanho 2 x 2.
A ideia por trás dessa divisão múltipla de matrizes grandes em matrizes menores é que você pode aplicar o algoritmo de Strassen a matrizes menores repetidamente e usar seu método para reduzir o número de etapas em cada etapa. Em geral, o algoritmo de Strassen aumentou a velocidade da multiplicação da matriz com n 3 a n 2,81 etapas multiplicativas.
O próximo passo importante no desenvolvimento da ideia ocorreu no final dos anos 1970, quando uma abordagem fundamentalmente nova para resolver esse problema apareceu. Envolve traduzir a multiplicação de matrizes em outro problema de álgebra linear computacional usando objetos chamados tensores. Os tensores usados neste problema são arranjos tridimensionais de números compostos de muitas partes diferentes, cada uma das quais se parece com um pequeno problema de multiplicação de matrizes.
A multiplicação de matrizes e este problema de tensor são em certo sentido equivalentes um ao outro, mas os pesquisadores já tinham procedimentos mais rápidos para resolver o último. Assim, eles se depararam com a tarefa de determinar a "taxa de câmbio" entre eles: quais matrizes de tamanho podem ser multiplicadas com os mesmos custos computacionais necessários para resolver o problema do tensor?
“Este é um conceito muito comum na ciência da computação teórica: transformar tarefas e fazer analogias entre elas para mostrar que são igualmente simples ou complexas”, disse Alman.
Em 1981, Arnold Schönhage usou essa abordagem para provar que a multiplicação da matriz pode ser feita em 2.522 etapas. Strassen mais tarde chamou essa abordagem de "método laser" .
Nas últimas décadas, todo aprimoramento na multiplicação da matriz veio de melhorias no método do laser, à medida que os pesquisadores descobriram maneiras mais eficientes de transformar o problema. Em sua nova prova, Alman e Williams confundem a distinção entre os dois problemas e mostram que é possível reduzir o número de multiplicações. “No geral, Josh e Virginia encontraram uma maneira de aplicar a computação de máquina no método do laser e obtiveram os melhores resultados até o momento”, disse Henry Cohn.da Microsoft Research.
Em seu artigo, o limite teórico na velocidade de multiplicação da matriz é melhorado para n 2,3728596 .
Também graças a esta pesquisa, Williams pode recuperar a coroa no campo da multiplicação de matrizes, que ela recebeu por direito em 2012 (n 2.372873 ), e depois perdeu em 2014 para François Le Gall (n 2.3728639 ).
Mas, apesar de todas essas corridas e vitórias, fica claro que, no caso dessa abordagem, a lei dos rendimentos decrescentes, ou rendimentos decrescentes, opera. Muito provavelmente, o aprimoramento de Alman e Williams esgotou quase por completo as possibilidades do método a laser, mas não permitiu atingir o objetivo teórico final.
“É improvável que você possa chegar perto do segundo grau usando esta família de métodos”, disse Umans.
Isso exigirá a descoberta de novos métodos e uma forte crença de que isso é possível.
Williams relembra uma de suas conversas com Strassen sobre isso: “Eu perguntei se ele achava que era possível obter o segundo grau para multiplicação de matrizes, e ele respondeu:“ Não, não, não, nunca! ”.