Uma das ferramentas mais fundamentais da matemática fora da aritmética diária viu a sua primeira melhoria em 24 anos.
Embora o novo método de multiplicação de matrizes, uma ferramenta essencial para a resolução de problemas em física, economia e na maior parte das áreas da ciência, não seja prático para o uso nos computadores atuais, é um salto teórico surpreendente que poderá um dia ter múltiplas aplicações. E está a criar uma agitação significativa na blogosfera matemática.
"Tudo isto é extremamente excitante, e é um dos melhores resultados obtidos na teoria nos últimos anos", escreveu Richard Lipton, um cientista de computação no Instituto de Tecnologia da Geórgia, em Atlanta, no seu blog.
"Na verdade, eu sabia há um mês que isto ia acontecer – foi muito difícil manter o segredo", escreveu Scott Aaronson, outro cientista de computação e bloguer, do Massachusetts Institute of Technology.
Reduzindo o valor de ómega
A matriz é um conjunto de números, e a multiplicação de matrizes é uma maneira de combinar duas matrizes para produzir uma terceira. A maneira mais simples de se multiplicar duas matrizes n × n - aquelas com n linhas e n colunas - requer mais ou menos n^3 passos, mas em 1969, Volker Strassen descobriu um algoritmo que fez isso em n^2.807 passos.
A multiplicação de matrizes é geralmente realizada utilizando o método simples n^3 ou usando o algoritmo de Strassen, que é mais complexo mas também mais eficiente para grandes matrizes, mas os teóricos têm tentado muitas outras maneiras de reduzir o número de passos, através da redução do valor do expoente, conhecida como ómega.
Em 1987, esta busca culminou com o mais rápido algoritmo conhecido há 24 anos. Foi desenvolvido por Don Coppersmith e Winograd Shmuel e colocou o valor de ómega em 2,376.
Solução enterrada
Agora, Virginia Vassilevska-Williams, que divide o seu tempo entre a Universidade da Califórnia, em Berkeley, e a Universidade de Stanford, mostrou que este pressuposto estava errado - ajustando o algoritmo para produzir um ómega de 2,373.
A ideia por trás da melhoria estava presente no método original de Coppersmith Winograd, que envolve essencialmente a aplicação de um algoritmo de partida duas vezes seguidas. O problema era que a aplicação do algoritmo de uma terceira vez aparentemente não produziu melhorias. "Isso levou a acreditar que níveis mais elevados de recursão não produziriam melhorias", diz Vassilevska-Williams, por isso eles desistiram. Cada aplicação do algoritmo envolveu a resolução de um número crescente de equações difíceis, e sem retorno no final não parecia valer a pena o trabalho duro.
Então, em 2010, Andrew Stothers da Universidade de Edinburgh, Reino Unido, aplicou o algoritmo quatro vezes como parte de sua tese de doutoramento, mas o resultado ficou “enterrado na tese”, o que fez com que passasse despercebido pela maioria comunidade matemática. Ele então deixou a sua pesquisa para trabalhar na indústria de serviços financeiros. "Não foi intencional o facto de eu não a ter divulgado", diz ele.
Caixa de ferramentas matemáticas
Quando Vassilevska-Williams, que estava a trabalhar de forma independente, deparou com a tese de Stothers, percebeu que poderia usar parte do seu trabalho. Ela aplicou o algoritmo de partida oito vezes para descobrir o valor ómega final de 2,373.
Vale a pena ficar animado sobre uma melhoria tão pequena? "Sim, porque tem resistido por tanto tempo e muitas pessoas já trabalharam nele", diz William Gasarch, um cientista de computação da Universidade de Maryland em College Park. "Muitas vezes os teóricos trabalham em problemas que as pessoas realmente não se preocupam. Este não é o caso aqui."
Embora os computadores de hoje não possam tirar proveito deste avanço específico, Vassilevska-Williams também criou uma estrutura matemática que poderia permitir mais avanços teóricos que podem ser úteis para a computação. "Você pode pensar nisso como uma nova ferramenta para ser adicionada à caixa de ferramentas", diz ela.
Embora o novo método de multiplicação de matrizes, uma ferramenta essencial para a resolução de problemas em física, economia e na maior parte das áreas da ciência, não seja prático para o uso nos computadores atuais, é um salto teórico surpreendente que poderá um dia ter múltiplas aplicações. E está a criar uma agitação significativa na blogosfera matemática.
"Tudo isto é extremamente excitante, e é um dos melhores resultados obtidos na teoria nos últimos anos", escreveu Richard Lipton, um cientista de computação no Instituto de Tecnologia da Geórgia, em Atlanta, no seu blog.
"Na verdade, eu sabia há um mês que isto ia acontecer – foi muito difícil manter o segredo", escreveu Scott Aaronson, outro cientista de computação e bloguer, do Massachusetts Institute of Technology.
Reduzindo o valor de ómega
A matriz é um conjunto de números, e a multiplicação de matrizes é uma maneira de combinar duas matrizes para produzir uma terceira. A maneira mais simples de se multiplicar duas matrizes n × n - aquelas com n linhas e n colunas - requer mais ou menos n^3 passos, mas em 1969, Volker Strassen descobriu um algoritmo que fez isso em n^2.807 passos.
A multiplicação de matrizes é geralmente realizada utilizando o método simples n^3 ou usando o algoritmo de Strassen, que é mais complexo mas também mais eficiente para grandes matrizes, mas os teóricos têm tentado muitas outras maneiras de reduzir o número de passos, através da redução do valor do expoente, conhecida como ómega.
Em 1987, esta busca culminou com o mais rápido algoritmo conhecido há 24 anos. Foi desenvolvido por Don Coppersmith e Winograd Shmuel e colocou o valor de ómega em 2,376.
Solução enterrada
Agora, Virginia Vassilevska-Williams, que divide o seu tempo entre a Universidade da Califórnia, em Berkeley, e a Universidade de Stanford, mostrou que este pressuposto estava errado - ajustando o algoritmo para produzir um ómega de 2,373.
A ideia por trás da melhoria estava presente no método original de Coppersmith Winograd, que envolve essencialmente a aplicação de um algoritmo de partida duas vezes seguidas. O problema era que a aplicação do algoritmo de uma terceira vez aparentemente não produziu melhorias. "Isso levou a acreditar que níveis mais elevados de recursão não produziriam melhorias", diz Vassilevska-Williams, por isso eles desistiram. Cada aplicação do algoritmo envolveu a resolução de um número crescente de equações difíceis, e sem retorno no final não parecia valer a pena o trabalho duro.
Então, em 2010, Andrew Stothers da Universidade de Edinburgh, Reino Unido, aplicou o algoritmo quatro vezes como parte de sua tese de doutoramento, mas o resultado ficou “enterrado na tese”, o que fez com que passasse despercebido pela maioria comunidade matemática. Ele então deixou a sua pesquisa para trabalhar na indústria de serviços financeiros. "Não foi intencional o facto de eu não a ter divulgado", diz ele.
Caixa de ferramentas matemáticas
Quando Vassilevska-Williams, que estava a trabalhar de forma independente, deparou com a tese de Stothers, percebeu que poderia usar parte do seu trabalho. Ela aplicou o algoritmo de partida oito vezes para descobrir o valor ómega final de 2,373.
Vale a pena ficar animado sobre uma melhoria tão pequena? "Sim, porque tem resistido por tanto tempo e muitas pessoas já trabalharam nele", diz William Gasarch, um cientista de computação da Universidade de Maryland em College Park. "Muitas vezes os teóricos trabalham em problemas que as pessoas realmente não se preocupam. Este não é o caso aqui."
Embora os computadores de hoje não possam tirar proveito deste avanço específico, Vassilevska-Williams também criou uma estrutura matemática que poderia permitir mais avanços teóricos que podem ser úteis para a computação. "Você pode pensar nisso como uma nova ferramenta para ser adicionada à caixa de ferramentas", diz ela.
Sem comentários:
Enviar um comentário
Deixe aqui o seu comentário.