Um artigo recente estabeleceu o recorde mais rápido para a multiplicação de duas matrizes. Mas também marca o fim da linha de um método no qual os pesquisadores confiaram durante décadas para fazer melhorias.
Para cientistas da computação e matemáticos, as opiniões sobre o “expoente dois” se resumem a uma noção de como o mundo deveria ser.
“É difícil distinguir o pensamento científico do pensamento positivo”, disse Chris Umans, do California Institute of Technology. “Quero que o expoente seja dois porque é lindo.”
“Expoente dois” refere-se à velocidade ideal – em termos de número de etapas necessárias – de realizar uma das operações mais fundamentais em matemática: a multiplicação de matrizes. Se o expoente dois for alcançável, então é possível realizar a multiplicação da matriz o mais rápido possível fisicamente. Se não for, então estamos presos em um mundo desajustado para nossos sonhos.
Matrizes são arranjos de números. Quando você tem duas matrizes de tamanhos compatíveis, é possível multiplicá-las para produzir uma terceira matriz. Por exemplo, se você começar com um par de matrizes dois por dois, seu produto também será uma matriz dois por dois, contendo quatro entradas. Mais geralmente, o produto de um par de matrizes n por n é outra matriz n por n com entradas n2.
Por esse motivo, o mais rápido que se poderia esperar para multiplicar pares de matrizes é em n2 etapas – ou seja, no número de etapas necessárias apenas para escrever a resposta. É daí que vem o “expoente dois”.
E embora ninguém saiba ao certo se ele pode ser alcançado, os pesquisadores continuam a fazer progressos nessa direção.
Um artigo publicado em outubro é o que mais se aproxima, descrevendo o método mais rápido de todos os tempos para multiplicar duas matrizes. O resultado, de Josh Alman, pesquisador de pós-doutorado da Universidade de Harvard, e Virginia Vassilevska Williams do Instituto de Tecnologia de Massachusetts, reduz em cerca de cem milésimos o expoente da melhor marca anterior. É típico dos recentes ganhos meticulosos no campo.
Para ter uma noção desse processo e como ele pode ser melhorado, vamos começar com um par de matrizes dois por dois, A e B. Ao calcular cada entrada de seu produto, você usa a linha correspondente de A e a coluna correspondente de B. Portanto, para obter a entrada superior direita, multiplique o primeiro número na primeira linha de A pelo primeiro número na segunda coluna de B e, em seguida, multiplique o segundo número na primeira linha de A pelo segundo número na segunda coluna de B e some esses dois produtos.
Essa operação é conhecida como obter o “produto interno” de uma linha com uma coluna. Para calcular as outras entradas na matriz do produto, repita o procedimento com as linhas e colunas correspondentes.
Ao todo, o método de livro para multiplicar matrizes dois por dois requer oito multiplicações, mais algumas adições. Geralmente, essa maneira de multiplicar duas matrizes n por n requer n3 multiplicações ao longo do caminho.
À medida que as matrizes crescem, o número de multiplicações necessárias para encontrar seu produto aumenta muito mais rápido do que o número de adições. Embora sejam necessárias oito multiplicações intermediárias para encontrar o produto de matrizes dois por dois, são necessárias 64 para encontrar o produto de matrizes quatro por quatro. No entanto, o número de adições necessárias para adicionar esses conjuntos de matrizes é muito mais próximo. Geralmente, o número de adições é igual ao número de entradas na matriz, portanto, quatro para as matrizes dois por dois e 16 para as matrizes quatro por quatro. Essa diferença entre adição e multiplicação começa a entender por que os pesquisadores medem a velocidade da multiplicação da matriz puramente em termos do número de multiplicações necessárias.
“Multiplicações são tudo”, disse Umans. “O expoente no tempo de execução eventual depende totalmente apenas do número de multiplicações. As adições meio que desaparecem.”
Durante séculos, as pessoas pensaram que n3 era simplesmente o mais rápido que a multiplicação de matrizes poderia ser feita. Em 1969, Volker Strassen supostamente tentou provar que não havia como multiplicar matrizes dois por dois usando menos de oito multiplicações. Aparentemente, ele não conseguiu encontrar a prova e, depois de um tempo, percebeu o porquê: na verdade, há uma maneira de fazer isso com sete!
Strassen criou um conjunto complicado de relações que tornou possível substituir uma dessas oito multiplicações por 14 adições extras. Isso pode não parecer uma grande diferença, mas vale a pena graças à importância da multiplicação sobre a adição. E ao encontrar uma maneira de salvar uma única multiplicação para pequenas matrizes dois por dois, Strassen encontrou uma abertura que poderia explorar ao multiplicar matrizes maiores.
“Essa pequena melhoria leva a grandes melhorias com grandes matrizes”, disse Vassilevska Williams.
Jared Charney; Richard TK Hawke
Digamos, por exemplo, que você queira multiplicar um par de matrizes oito por oito. Uma maneira de fazer isso é dividir cada matriz grande em quatro matrizes quatro por quatro, de modo que cada uma tenha quatro entradas. Como uma matriz também pode ter entradas que são matrizes, você pode pensar nas matrizes originais como um par de matrizes dois por dois, cada uma das quatro entradas sendo, ela própria, uma matriz quatro por quatro. Por meio de alguma manipulação, essas matrizes quatro por quatro podem ser divididas cada uma em quatro matrizes dois por dois.
O objetivo dessa redução – de quebrar repetidamente matrizes maiores em matrizes menores – é que é possível aplicar o algoritmo de Strassen repetidamente às matrizes menores, colhendo as economias de seu método a cada etapa. Ao todo, o algoritmo de Strassen melhorou a velocidade da multiplicação da matriz de n3 para n2.81 etapas multiplicativas.
A próxima grande melhoria ocorreu no final dos anos 1970, com uma maneira fundamentalmente nova de abordar o problema. Envolve traduzir a multiplicação de matrizes em um problema computacional diferente em álgebra linear envolvendo objetos chamados tensores. Os tensores específicos usados neste problema são matrizes 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 envolvendo tensores são equivalentes entre si em certo sentido, mas os pesquisadores já tinham procedimentos mais rápidos para resolver o último. Isso os deixou com a tarefa de determinar a taxa de câmbio entre os dois: Qual o tamanho das matrizes que você pode multiplicar pelo mesmo custo computacional necessário para resolver o problema do tensor?
“Este é um paradigma muito comum na ciência da computação teórica, de reduzir problemas para mostrar que são tão fáceis ou tão difíceis quanto uns aos outros”, disse Alman.
Em 1981, Arnold Schönhage usou essa abordagem para provar que é possível realizar a multiplicação da matriz em n2.522 etapas. Strassen mais tarde chamou essa abordagem de “método a laser”.
Nas últimas décadas, cada melhoria na multiplicação da matriz veio de melhorias no método do laser, à medida que os pesquisadores descobriram maneiras cada vez mais eficientes de traduzir entre os dois problemas. Em sua nova prova, Alman e Vassilevska Williams reduzem o atrito entre os dois problemas e mostram que é possível “comprar” mais multiplicação de matriz do que anteriormente realizado para resolver um problema de tensor de um determinado tamanho.
“Josh e Virginia basicamente encontraram uma maneira de pegar a máquina dentro do método a laser e ajustá-la para obter resultados ainda melhores”, disse Henry Cohn, da Microsoft Research.
O artigo melhora o limite de velocidade teórica na multiplicação da matriz para n2.3728596.
Também permite que Vassilevska Williams recupere a coroa de multiplicação da matriz, que ela tinha anteriormente em 2012 (n2.372873), depois perdeu em 2014 para François Le Gall (n2.3728639).
Mesmo assim, apesar de todas as manobras, também está claro que essa abordagem está proporcionando retornos decrescentes. Na verdade, a melhoria de Alman e Vassilevska Williams pode ter quase maximizado o método do laser – permanecendo muito aquém do objetivo teórico final.
“Não é provável que haja um salto para o expoente dois usando esta família particular de métodos”, disse Umans.
Para chegar lá, será necessário descobrir novos métodos e manter a crença de que isso é até possível.
Vassilevska Williams se lembra de uma conversa que teve uma vez com Strassen sobre isso: “Eu perguntei a ele se ele acha que você pode obter [expoente 2] para multiplicação de matriz e ele disse,- não, não, não, não, não.'”
Publicado em 28/03/2021 00h51
Artigo original: