Multiplicación matricial en

13

Estaba buscando la multiplicación de matrices, así que primero visito los algoritmos de multiplicación de matrices wiki . En las referencias encontré un artículo que afirma que usa el algoritmo , leería el artículo pero es complicado y lo haré toma demasiado tiempo leerlo, pero si hay alguien que lee este artículo o conoce este algoritmo, ¿es cierto? y conoces la idea básica de esto para describirlo un poco.O(norte2losol(norte))

Gracias de antemano, sé que es una pregunta un poco general, pero si encuentro que es un buen enfoque, aprenderé detalles.

ds.algorithms linear-algebra matrix-product Saeed
fuente
55
Creo que es útil entender mejor su propia pregunta. ¿Estás buscando un algoritmo secuencial o un algoritmo paralelo? No se conocen algoritmos secuenciales para la multiplicación de matrices con el tiempo O (n ^ 2 log n), y el artículo de Eve es un resultado parcial hacia dichos algoritmos (no leí el artículo, simplemente lo hojeé). Si le importa el tiempo paralelo, entonces el tiempo paralelo O (log n) (suponiendo que la suma escalar y la multiplicación escalar en tiempo constante) es estándar y puede encontrar una explicación en, por ejemplo, el libro Complejidad computacional de Papadimitriou.
Tsuyoshi Ito
2
(1) Edite su pregunta para que quede claro que está preguntando sobre algoritmos secuenciales. (2) Me di cuenta de que agregaste la etiqueta [computación cuántica]. Edite su pregunta para explicar la relación con la computación cuántica. (Mi conjetura es que su pregunta está motivada por la computación cuántica, pero su explicación es mucho más útil que cualquier conjetura.)
Tsuyoshi Ito
2
Te recomiendo que primero borres esta pregunta y luego vuelvas a publicarla si encuentras que tienes una pregunta.
Suresh Venkat
3
@Saeed: Este tema se ha discutido en el meta y actualmente esta es la política del sitio, si desea discutir la política use el meta. Por otro lado, puede modificar la pregunta y evitar mencionar el documento para abordar el tema, por ejemplo, modificar la pregunta para que se convierta en "¿cuál es el algoritmo más conocido para la multiplicación de matrices en el modelo X?" y eso sería sobre el tema. (nota al margen: si no puede verificar la corrección de un documento inédito y desea citarlo, debe esperar hasta que sea revisado por pares y publicado).
Kaveh
3
Discusión relacionada sobre Meta: ¿Está bien preguntar acerca de la corrección de las preimpresiones sobre temas amigables con las manivelas? No estoy afirmando que todo lo escrito en esa página se aplicará a esta pregunta, pero al menos está estrechamente relacionado.
Tsuyoshi Ito

Respuestas:

34

Me encontré con este artículo hace aproximadamente un año, pero no he podido leerlo de cerca. Puedo decirle que no se cree que el enfoque sea correcto. En la página 36 del mismo documento, hay un comentario adjunto de Don Knuth, quien señala lo que parece ser una grave deficiencia del enfoque.

Para comprender este documento, deberá aprender sobre álgebra grupal y teoría de la representación. Será difícil si no has visto ese tipo de material antes.

Ryan Williams
fuente