Login Barrapunto
Multiplicación de matrices en O(n^2,373)
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)».
« El Tribunal de Justicia Europeo prohíbe a los proveedores de Internet espiar a sus usuarios | Otra vez más, en defensa de los derechos fundamentales en Internet »
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)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.
Desde un k, para todo n >= k, es el mejor.
(Puntos:1, Informativo)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.
Es un método hasta cierto punto
(Puntos:2)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).
¡Cuaternios!
(Puntos:1, Informativo)Offtopic
(Puntos:2)( http://www.traperware.com/ )
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