Multiplicação de matrizes em

13

Eu estava pesquisando sobre multiplicação de matrizes, então eu primeiro visitei algoritmos de multiplicação de matrizes wiki . Nas referências, encontrei um artigo que afirma que usa o algoritmo O(n2log(n)) , gostaria de ler o artigo, mas é complicado e leva muito tempo para lê-lo, mas se houver alguém que leia este artigo ou conheça esse algoritmo, isso é verdade? e você conhece a idéia básica disso para descrevê-la um pouco.

Agradecemos antecipadamente, eu sei que é uma pergunta um pouco geral, mas, se eu achar que é uma boa abordagem, vou aprender detalhes.

ds.algorithms linear-algebra matrix-product Saeed
fonte
5
Eu acho que é útil entender melhor sua própria pergunta. Você está procurando um algoritmo sequencial ou paralelo? Nenhum algoritmo seqüencial para multiplicação de matrizes com o tempo O (n ^ 2 log n) é conhecido, e o artigo de Eve é um resultado parcial para tais algoritmos (eu não li o artigo, apenas o examinei). Se você se preocupa com o tempo paralelo, o tempo paralelo O (log n) (assumindo a adição escalar e multiplicação escalar em tempo constante) é padrão e você pode encontrar explicações, por exemplo, no livro Computational Complexity by Papadimitriou.
Tsuyoshi Ito
2
(1) Edite sua pergunta para que fique claro que você está perguntando sobre algoritmos seqüenciais. (2) Percebi que você adicionou a tag [quantum-computing]. Edite sua pergunta para explicar a relação com a computação quântica. (Meu palpite é que a sua pergunta é motivada pela computação quântica, mas a sua própria explicação é muito mais útil do que qualquer palpite.)
Tsuyoshi Ito
2
Eu recomendo que você exclua esta pergunta primeiro e depois repita mais tarde se achar que tem alguma pergunta.
precisa
3
@ Saeed: Esta questão foi discutida na meta e, atualmente, essa é a política do site, se você quiser discutir a política, use a meta. Por outro lado, você pode modificar a questão e evitar mencionar o artigo para torná-lo no tópico, por exemplo, modificá-la para se tornar "qual é o algoritmo mais conhecido para multiplicação de matrizes no modelo X?" e isso seria sobre o assunto. (nota: se você não pode verificar a exatidão de um trabalho inédito si mesmo e quero citá-lo, você deve esperar até que é e publicado peer-reviewed.)
Kaveh
3
Discussão relacionada sobre o Meta: É correto perguntar sobre a correção das pré-impressões em tópicos compatíveis com a manivela? Não estou afirmando que tudo o que está escrito nessa página se aplicará a essa pergunta, mas está pelo menos intimamente relacionado.
Tsuyoshi Ito

Respostas:

34

Me deparei com este artigo há cerca de um ano, mas não consegui lê-lo de perto. Posso dizer que não se acredita que a abordagem esteja correta. Na página 36 do mesmo artigo, há um comentário em anexo de Don Knuth, que aponta o que parece ser uma falha grave da abordagem.

Para entender este artigo, você precisará aprender sobre álgebra de grupo e teoria das representações. Será difícil se você nunca viu esse tipo de material antes.

Ryan Williams
fonte