💻 computer science

55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

Este artigo apresenta um novo algoritmo de posto-23 para a multiplicação de matrizes $3\times3$ que reduz o número de adições necessárias para 55 (totalizando 78 operações escalares), melhorando assim o estado da arte anterior de 56 adições enquanto mantém a validade sobre qualquer anel associativo através de uma construção baseada no tensor de Perminov e um circuito linear otimizado.

Autores originais: Samurdhi Karunaratne, Anushka Idamekorala

Publicado 2026-08-03

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Samurdhi Karunaratne, Anushka Idamekorala

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um mestre chef tentando assar um bolo enorme e complexo. A receita exige que você misture dezenas de ingredientes de maneiras muito específicas. No mundo dos computadores, "misturar" ingredientes é como multiplicar números, e "assar o bolo" é como multiplicar duas grades de números (matrizes) para obter um novo resultado. Durante muito tempo, os matemáticos pensaram que a única maneira de fazer isso era seguir a receita padrão, lenta: multiplicar cada número individualmente e depois somá-los. No entanto, na década de 1960, um gênio chamado Strassen descobriu um truque de mágica. Ele percebeu que, se você rearranjasse a ordem da sua mistura, poderia pular parte do trabalho pesado. Você poderia obter o mesmo bolo delicioso usando menos "multiplicações", que são as etapas mais caras e demoradas na cozinha.

No entanto, há uma pegadinha. Embora você possa economizar nas multiplicações caras, muitas vezes tem que fazer mais "adições" (tigelas de mistura) para deixar os ingredientes prontos. Pense nisso como: em vez de apenas despejar farinha em uma tigela, você pode ter que picar, mexer e dobrar os ingredientes em uma dança muito específica antes de combiná-los. O objetivo tem sido encontrar a coreografia perfeita que use o menor número de passos possível. Este artigo que você está prestes a ler é sobre uma equipe que encontrou uma dança ligeiramente mais eficiente para um tipo específico de bolo: uma matriz 3x3. Eles não mudaram o número de levantamentos pesados (multiplicações), mas conseguiram reduzir o número de passos de mistura (adições), poupando uma quantidade pequena, mas significativa de trabalho.

A Nova Dança Recordista

Este artigo, escrito por Samurdhi Karunaratne e Anushka Idamekorala, da Logical AI, anuncia um novo recorde para a multiplicação de duas grades de números 3x3. Eles descobriram uma maneira de fazê-lo usando apenas 55 adições e 23 multiplicações.

Para entender por que isso é importante, imagine a receita campeã anterior. A atual campeã, criada por um pesquisador chamado Sun, exigia 56 adições. Os autores deste artigo não inventaram uma maneira totalmente nova de multiplicar matrizes; em vez disso, eles pegaram uma receita pública existente (criada por Perminov) que usava 58 adições e 59 adições em versões anteriores, e otimizaram as etapas de "preparação". Eles perceberam que, ao rearranjar como os ingredientes eram pré-misturados, poderiam reduzir o número total de passos de adição para 55.

Aqui está como a nova "cozinha" deles funciona, dividida em três estáções simples:

Preparando os Ingredientes da Esquerda: Antes de misturar, eles pegam a primeira grade de números (vamos chamá-la de grade "Esquerda") e realizam 13 etapas simples de adição ou subtração para criar 23 misturas especiais.
Preparando os Ingredientes da Direita: Eles fazem o mesmo para a segunda grade de números (a grade "Direita"), usando 14 etapas para criar suas 23 misturas especiais.
A Grande Mistura e Montagem Final: Eles multiplicam as misturas correspondentes das grades Esquerda e Direita (23 multiplicações no total). Em seguida, pegam esses 23 resultados e realizam mais 28 etapas de adição para montar o resultado final 3x3.

Quando você soma o trabalho de preparação (13 + 14) e a montagem final (28), você obtém exatamente 55 adições. Isso é uma adição a menos do que o melhor anterior, tornando-o o método mais eficiente conhecido para este tipo específico de cálculo.

Por Que Isso Importa (e o Que Não Importa)

Você pode se perguntar: "Este é o melhor jeito absoluto de fazer isso?". Os autores são muito cuidadosos ao dizer: Não, não necessariamente. Eles provaram que, para esta organização específica de ingredientes que escolheram, 55 é o melhor que se pode fazer. Eles usaram uma busca matemática rigorosa para provar que você não consegue realizar menos passos para esta receita específica. No entanto, eles admitem que pode haver uma receita completamente diferente (uma organização diferente de ingredientes) que poderia ser ainda mais rápida. Eles ainda não a encontraram e não estão alegando ter resolvido todo o mistério da multiplicação de matrizes para sempre.

Eles também esclarecem que isso não é apenas um palpite de sorte ou uma simulação de computador que possa estar errada. Eles forneceram um "certificado" de verdade. Eles escreveram toda a receita passo a passo (chamada de "programa de linha reta") e a rodaram através de vários programas de computador independentes (escritos em Python e Node.js) para verificar cada uma das 729 regras matemáticas que devem ser verdadeiras para que a receita funcione. Cada uma das verificações passou. Isso significa que a matemática é sólida e a receita funciona perfeitamente para qualquer tipo de sistema numérico, mesmo aqueles estranhos onde a ordem da multiplicação importa.

A IA Por Trás da Cortina

Uma reviravolta interessante nesta história é como a receita foi encontrada. Os autores revelam que um pesquisador humano guiou um sistema de IA (especificamente, um agente usando o OpenAI GPT-5.6 Sol) para descobrir isso. O humano definiu o objetivo: "Encontre uma maneira de superar o recorde de 56 adições". A IA então explorou o cenário de receitas existentes, encontrou a versão de 58 adições de Perminov e percebeu que, ao ajustar as etapas de preparação, poderia subtrair três movimentos extras. A IA então conferiu seu próprio trabalho, escreveu o código e verificou a matemática. É um exemplo perfeito de humanos e máquinas trabalhando juntos: o humano forneceu a direção e o "porquê", enquanto a IA lidou com o trabalho pesado de pesquisar através de milhões de possibilidades para encontrar o "como".

No fim, este artigo é uma vitória pequena, mas precisa. Ele mostra que, mesmo em um campo tão antigo quanto a multiplicação de matrizes, ainda existem pequenas eficiências ocultas esperando para serem descobertas, se você olhar de perto. É como encontrar um caminho novo, ligeiramente mais curto, através de uma floresta familiar. Você ainda chega ao mesmo lugar, mas chega com apenas um passo a menos.

Resumo Técnico: 55 Adições São Suficientes para a Multiplicação de Matrizes $3 \times 3$ de Posto 23

Enunciado do Problema
O artigo aborda o problema de minimizar a complexidade aditiva (o número de adições e subtrações) necessária para multiplicar duas matrizes $3 \times 3$ arbitrárias sobre um anel associativo, dado um posto multiplicativo fixo de 23. Enquanto o algoritmo de Strassen estabeleceu que a multiplicação de matrizes pode ser acelerada pela redução de produtos bilineares, o posto multiplicativo para matrizes $3 \times 3$ gerais permanece em 23 desde a descoberta de Laderman em 1976. Pesquisas recentes focaram em reduzir o número de adições escalares necessárias para realizar esses esquemas de posto 23. Antes deste trabalho, o estado da arte era de 56 adições, alcançado por Sun.

Metodologia
Os autores constroem um novo algoritmo otimizando as etapas lineares de uma fatoração de tensor pré-existente. A metodologia procede da seguinte forma:

Tensor Base: A construção utiliza a fatoração cr58_cn122 de Perminov, liberada publicamente, que originalmente exigia 58 adições (14 para a entrada à esquerda, 15 para a entrada à direita e 29 para a reconstrução da saída).
Síntese Exata de Mapas de Fator: Os autores realizam uma busca exaustiva de dependência dentro do modelo de programa de linha reta (SLP) binário de adição/subtração para otimizar os três mapas lineares ( $U, V, W$ $U, V, W$ ) que transformam as 9 entradas da matriz nos 23 forms bilineares.
- Eles identificam que, para a orientação fixa do tensor, o número mínimo de portas necessárias para gerar as direções de saída necessárias excede o limite inferior teórico baseado em direções distintas de não-base ( $d(F)$ ).
- Especificamente, eles provam que para o fator à esquerda ( $U$ ), o custo é 13 (um a mais que o piso de 12); para o fator à direita ( $V$ ), o custo é 14 (um a mais que o piso de 13); e para o fator de saída ( $W$ ), o custo é 14 (um a mais que o piso de 13).
Princípio da Transposição: Para obter o circuito de reconstrução de saída (que mapeia 23 produtos de volta para 9 entradas de matriz), os autores transpõem o circuito de 14 adições otimizado para $W$ . Usando o princípio de transposição de circuito linear, um circuito com $L$ portas, $n$ entradas e $m$ saídas transforma-se em um circuito para a transposta com $L + m - n$ portas. Aplicando isso ao circuito $W$ ( $L=14, n=9, m=23$ ), obtém-se um circuito de saída de 28 portas.
Verificação: A correção do algoritmo é verificada checando todas as 729 identidades de Brent sobre os inteiros $\mathbb{Z}$ . Os autores fornecem quatro métodos de verificação independentes, incluindo implementações em Python e Node.js, garantindo que o resultado se mantenha sobre qualquer anel associativo (comutativo ou não), uma vez que o alfabeto de coeficientes é restrito a $\{-1, 0, 1\}$ .

Principais Contribuições

Novo Limite Superior: O artigo apresenta uma realização da multiplicação de matrizes $3 \times 3$ usando 23 multiplicações escalares e 55 adições/subtrações, melhorando o recorde anterior de 56.
Certificado de Otimalidade: Os autores fornecem um circuito linear provadamente ótimo para a orientação específica do tensor utilizada. Eles demonstram que, para o tensor cr58_cn122 fixo, a soma dos custos das etapas lineares não pode ser inferior a 55 no modelo padrão de SLP bilinear de três estágios.
Liberação de Dados Exata: O artigo inclui o programa de linha reta completo, os fatores do tensor e um "certificado congelado" que permite a regeneração byte a byte e a verificação independente das 729 identidades.

Resultos
A anatomia do circuito resultante é a seguinte:

Pré-processamento à Esquerda (A): 13 adições (mapeando 9 entradas para 23 formas).
Pré-processamento à Direita (B): 14 adições (mapeando 9 entradas para 23 formas).
Camada Bilinear: 23 multiplicações.
Reconstrução de Saída: 28 adições (mapeando 23 produtos para 9 saídas).
Trabalho Linear Total: 55 adições.

O artigo confirma que o algoritmo se aplica a qualquer anel associativo porque os coeficientes estão em $\{-1, 0, 1\}$ e a ordem dos produtos bilineares é preservada.

Significância e Alegações
Os autores declaram explicitamente que não alegam que 55 seja o mínimo global entre todas as possíveis decomposições de posto-23, nem que seja ótimo em modelos de circuito que permitem operações primitivas além de adição/subtração. No entanto, dentro do modelo específico de uma orientação de tensor fixa e do padrão de programa de linha reta bilinear de três estágios, 55 é a contagem de adições mais baixa conhecida atualmente.

A significância do trabalho reside em:

Melhoria Incremental: Reduz o limite superior em uma adição, continuando a tendência de otimizar a complexidade aditiva para postos multiplicativos fixos.
Verificação Rigorosa: O resultado é sustentado por aritmética inteira exata e múltiplas implementações independentes, evitando a dependência de testes numéricos ou aleatórios.
Descoberta Assistida por IA: O artigo revela que a descoberta foi impulsionada por uma investigação dirigida por humanos utilizando agentes de IA (OpenAI GPT-5.6 Sol e Codex) para busca, síntese e verificação. O pesquisador humano definiu os objetivos e critérios de aceitação, enquanto os agentes de IA executaram as buscas de circuitos e geraram o certificado. Os autores enfatizam que a validade matemática repousa inteiramente nas 729 identidades exatas e no programa de linha reta impresso, não no envolvimento da IA.

A Nova Dança Recordista

Por Que Isso Importa (e o Que Não Importa)

A IA Por Trás da Cortina

Resumo Técnico: 55 Adições São Suficientes para a Multiplicação de Matrizes 3×33 \times 33×3 de Posto 23

Mais como este

Resumo Técnico: 55 Adições São Suficientes para a Multiplicação de Matrizes $3 \times 3$ de Posto 23