Qual algoritmo tem desempenho para a multiplicação de matrizes 4×4 de transformações afins

A Wikipedia lista quatro algoritmos para multiplicação de matrizes de duas matrizes nxn .

O clássico que um programador escreveria é O (n ³ ) e é listado como “Multiplicação da matriz do livro escolar”. Sim. O (n ³ ) é um pouco de sucesso. Vamos dar uma olhada no próximo melhor.

O algoritmo Strassen é O (n ^2,807 ). Este funcionaria – tem algumas restrições (como o tamanho é uma potência de dois) e tem uma advertência na descrição:

Em comparação com a multiplicação de matrizes convencional, o algoritmo adiciona uma carga de trabalho O (n ² ) considerável em adição / subtração; portanto, abaixo de um determinado tamanho, será melhor usar a multiplicação convencional.

Para aqueles que estão interessados neste algoritmo e suas origens, consulte Como Strassen surgiu com seu método de multiplicação de matrizes? pode ser uma boa leitura. Ele dá uma dica da complexidade dessa carga de trabalho inicial O (n ² ) que é adicionada e por que isso seria mais caro do que apenas fazer a multiplicação clássica.

Então, realmente é O (n ² + n ^2.807 ) com aquele bit sobre o expoente inferior n sendo ignorado ao escrever O grande. Parece que se você estão trabalhando em uma bela matriz 2048×2048, isso pode ser útil. Para uma matriz 4×4, provavelmente vai encontrá-la mais lenta, já que a sobrecarga consome o outro tempo.

E então há o Latoeiro – Winogrado algoritmo que é O (n ^2.373 ) com algumas melhorias. Ele também vem com uma advertência:

O algoritmo Coppersmith – Winograd é frequentemente usado como um bloco de construção em outros algoritmos para provar limites de tempo teóricos. No entanto, ao contrário do algoritmo de Strassen, não é usado na prática porque só fornece uma vantagem para matrizes tão grandes que não podem ser processado por hardware moderno.

Então, é melhor quando você está trabalhando em matrizes supergrandes, mas, novamente, não é útil para uma matriz 4×4.

Isso se reflete novamente na página da wikipedia em Multiplicação de matrizes: algoritmos sub-cúbicos que explicam por que as coisas funcionam mais rápido:

Existem algoritmos que pr ovide melhores tempos de execução do que os simples. O primeiro a ser descoberto foi o algoritmo de Strassen, desenvolvido por Volker Strassen em 1969 e frequentemente referido como “multiplicação de matriz rápida”. É baseado em uma maneira de multiplicar duas matrizes 2 × 2 que requer apenas 7 multiplicações (em vez de o usual 8), às custas de várias operações adicionais de adição e subtração. Aplicar isso recursivamente fornece um algoritmo com um custo multiplicativo de O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). O algoritmo de Strassen é mais complexo e a estabilidade numérica é reduzida em comparação com o algoritmo ingênuo, mas é mais rápido nos casos em que n> 100 ou mais e aparece em várias bibliotecas, como BLAS.

E isso vai ao cerne de por que os algoritmos são mais rápidos – você troca alguma estabilidade numérica e alguma configuração adicional. Essa configuração adicional para uma matriz 4×4 é muito mais do que o custo de fazer mais multiplicação.

E agora, para responder à sua pergunta:

Mas existem alguns algoritmos que são especialmente eficientes para matrizes tão pequenas?

Não, não há algoritmos otimizados para multiplicação de matrizes 4×4 porque o O (n ³ ) funciona razoavelmente até começar a descobrir que está disposto a dar um grande golpe em sobrecarga. Para sua situação específica, pode haver alguma sobrecarga em que você possa incorrer sabendo coisas específicas de antemão sobre suas matrizes (como a quantidade de dados que serão reutilizados), mas realmente a coisa mais fácil de fazer é escrever um bom código para o O (n ³ ) solução, deixe o compilador lidar com isso e analise-o posteriormente para ver se você realmente tem o código sendo o ponto lento na multiplicação da matriz.

Relacionado no Math.SE: Número mínimo de multiplicações necessárias para inverter uma matriz 4×4

Freqüentemente, algoritmos simples são os mais rápidos para conjuntos muito pequenos, porque algoritmos mais complexos geralmente usam alguma transformação que adiciona alguma sobrecarga. Acho que sua melhor aposta não é em um algoritmo mais eficiente (acho que a maioria das bibliotecas usa métodos diretos), mas em uma implementação mais eficiente, por exemplo, usando extensões SIMD (assumindo código x86 ou amd64), ou escrito à mão em assembly . Além disso, o layout da memória deve ser bem pensado. Você deve ser capaz de encontrar recursos suficientes sobre isso.

Para multiplicação 4×4 tapete / tapete, as melhorias algorítmicas estão frequentemente disponíveis . O algoritmo básico de complexidade de tempo cúbico tende a se sair muito bem e qualquer coisa mais sofisticada do que isso tem mais probabilidade de degradar em vez de melhorar os tempos. Em geral, algoritmos sofisticados são inadequados se não houver “um fator de escalabilidade envolvido (por exemplo: tentar classificar rapidamente um array que sempre tem 6 elementos em oposição a uma inserção simples ou classificação por bolha). Fazer coisas como a transposição da matriz aqui para melhorar a localidade de referência também não ajudam na localidade de referência quando uma matriz inteira pode caber em uma ou duas linhas de cache. Nesse tipo de escala em miniatura, se você estiver fazendo multiplicação 4×4 tapete / tapete em massa, as melhorias geralmente virão de otimizações de micro-nível de instruções e memória, como o alinhamento adequado da linha de cache.

Comentários

• Ótima resposta! Eu ‘ nunca ouvi falar do acrônimo SoA (pelo menos, em holandês é um acrônimo para ‘ seksueel overdraagbare aandoening ‘ que significa ‘ doença sexualmente transmissível ‘ … mas que ‘ esperançosamente não é o que você quer dizer aqui). A técnica parece clara, e ‘ estou até bastante surpreso de que haja um nome para ela. O que significa SoA?
• @Ruben Structure of Arrays em oposição a Arrays of Structures. SoAs também podem ser PITAs – melhor salvos para seus caminhos mais críticos. Aqui está ‘ um link interessante que encontrei sobre o assunto: stackoverflow.com/questions/17924705/…
• Você pode querer mencionar C ++ 11 / C11 alignas .

Se você tiver certeza de que precisará apenas multiplicar 4×4 matrizes, então você não precisa se preocupar com um algoritmo geral. Você pode apenas pegar duas dicas e usar isto:

(Eu recomendo fortemente a tradução de alguma forma automatizada).

O compilador seria então posicionado de forma ideal para otimizar esse código (para reutilizar somas parciais, reordenar a matemática etc.), pois ele pode ver tudo, não há loops dinâmicos e nenhum fluxo de controle.

É difícil imaginar que isso possa ser superado sem usando intrínsecos.