Estou procurando informações sobre a complexidade computacional da multiplicação de matrizes de matrizes retangulares. A Wikipedia afirma que a complexidade de multiplicar por é (multiplicação de livros escolares). B ∈ R n × p O ( m n p )
Eu tenho um caso em que e são muito menores que , e esperava obter uma complexidade melhor que linear em , à custa de tornar a dependência de e pior que linear.n p p m n
Alguma ideia?
Obrigado.
Nota: a razão pela qual espero que seja possível é por causa do resultado bem conhecido de uma dependência menor que cúbica em se (quando as matrizes são todas quadradas).m = n = p
Respostas:
O trabalho clássico de Coppersmith mostra que, para alguns , pode-se multiplicar uma matriz n × n α por uma matriz n α × n em operações aritméticas ˜ O ( n 2 ) . Este é um ingrediente crucial do recente resultado comemorado de Ryan Williams.α > 0 n × nα nα× n O~( n2)
François le Gall melhorou recentemente o trabalho de Coppersmith, e seu artigo acaba de ser aceito no FOCS 2012. Para entender esse trabalho, você precisará de algum conhecimento da teoria da complexidade algébrica. O artigo de Virginia Williams contém alguns indicadores relevantes. Em particular, o trabalho de Coppersmith é completamente descrito em Algebraic Complexity Theory , o livro.
Uma linha diferente de trabalho concentra-se na multiplicação de matrizes aproximadamente . Você pode conferir este trabalho de Magen e Zouzias. Isso é útil para lidar com matrizes muito grandes, digamos, multiplicando uma matriz e uma matriz N × n , onde N ≫ n .n × N N×n N≫ n
A abordagem básica é amostrar as matrizes (isso corresponde a uma redução de dimensionalidade aleatória) e multiplicar as matrizes amostradas muito menores. O truque é descobrir quando e em que sentido isso dá uma boa aproximação. Ao contrário do trabalho anterior, que é completamente impraticável, os algoritmos de amostragem são práticos e até necessários para manipular grandes quantidades de dados.
fonte