Historias
Slashboxes
Comentarios
 

Login Barrapunto

Login

[ Crear nueva cuenta ]

Multiplicación de matrices en O(n^2,373)

editada por rvr el Miércoles, 30 Noviembre de 2011, 16:00h   Printer-friendly   Email story
fernand0 nos cuenta «No se si habrá muchos barrapunteros interesados en el coste teórico de algunas operaciones más o menos frecuentes. Menos aún si tenemos en cuenta que este tipo de resultados suelen ser mas teóricos que de utilidad práctica inmediata, pero por si acaso ahí va. En 2.373 nos avisaban de la publicación de resultados que rebajarían el coste (insisto, teórico) del producto eficiente de dos matrices cuadrada, que hasta hace no mucho estaba en O(n^2,376) y que el año pasado había mejorado la cota a O(n^2,374). Recordar que el método que se nos ocurre a todos rápidamente que es la múltiplicación de filas por columnas a lo 'bruto' tiene un coste de O(n^3)».

Mostrar opciones Umbral:
Y recuerda: Los comentarios que siguen pertenecen a las personas que los han enviado. No somos responsables de los mismos.
  • Bastante utilidad práctica

    (Puntos:2, Interesante)
    por pobrecito hablador el Miércoles, 30 Noviembre de 2011, 17:03h (#1295142)

    Si existe un algoritmo para reducir el número de operaciones en la multiplicación de matrices, entonces su utilidad práctica es inmediata, porque multiplicar matrices y vectores es lo que hacen todo el rato las GPUs actuales cuando procesan gráficos 3D.

    Un sistema de referencia se representa mediante una matriz llamada "de transformación homogénea" cuya dimensión es 4x4. A partir de ahí casi todas las operaciones como rotar, escalar, trasladar o proyectar son operaciones de multiplicación con matrices de 4x4.

    Es decir, que tal vez estos resultados den lugar a tarjetas gráficas con mayor rendimiento, aunque supongo que el caso particular de n=4 lo deben tener estudiado ya los fabricantes hasta la saciedad.

    [ Responder ]
  • por pobrecito hablador el Jueves, 01 Diciembre de 2011, 08:34h (#1295168)
    Para n menor que k, utilizar el método de peor orden.

    Para n mayor o igual que k, utilizar el método de mejor orden.

    Por si habéis olvidado, se estaba hablando de orden de complejidad para tendencia ASINTÓTICA.
    [ Responder ]
  • por pedro_fortuny (29526) el Jueves, 01 Diciembre de 2011, 11:37h (#1295180)
    Porque el algoritmo todavía no está implementado y tras un vistazo somero al paper, es más teórico que práctico.

    Por otro lado, esto es como multiplicar números con la transformada de fourier: si lo haces para números de 128bits estás cometiendo un error (cuesta más fabricar la transformada que hacer la cuenta de la vieja). Si lo haces para números de 1024bits, A LO MEJOR te compensa (not that sure).
    [ Responder ]
  • ¡Cuaternios!

    (Puntos:1, Informativo)
    por pobrecito hablador el Jueves, 01 Diciembre de 2011, 12:47h (#1295181)
    El uso de cuaternios evita el hacer operaciones costosas con matrices. La mayoría de operaciones de rotación de vectores se realizan desde hace tiempo con cuaternios y no con la multiplicación de matrices. Reducir el tiempo de proceso de un algoritmo es siempre ventajoso pero dudo que una reducción tan poco significativa pueda resultar notoria para aplicaciones de usuario o GPUs, como apuntaba algún comentario anterior.
    [ Responder ]
  • Offtopic

    (Puntos:2)
    por sinman (586) <sinman@terra.es> el Jueves, 01 Diciembre de 2011, 16:11h (#1295192)
    ( http://www.traperware.com/ )
    Casi se me saltan las lágrimas de emoción al leer los comentarios.

    Barrapunto es como un anciano de 90 años, que de vez en cuando tiene un momento de lucidez y te cuenta una historia que te deja boquiabierto.

    De vez en cuando, muy de vez en cuando, Barrapunto vuelve a ser lo que era ;)
    [ Responder ]
  • 2 respuestas por debajo de tu umbral de lectura actual.