close Warning: Can't synchronize with repository "(default)" (/var/svn/tolp does not appear to be a Subversion repository.). Look in the Trac log for more information.

Opened 14 years ago

Last modified 14 years ago

#1348 new task

Posible mejora del tiempo de cálculo del producto de matrices cuadradas

Reported by: lmperez@… Owned by: Víctor de Buen Remiro
Priority: low Milestone: Numerical methods
Component: Math Version: head
Severity: normal Keywords: BLAS, Coppersmith, Winograd
Cc:

Description

Hola Tol, he encontrado un paper (​http://www.cs.berkeley.edu/~virgi/matrixmult.pdf)
donde se explica un algoritmo que rompe el límite de Coppersmith-Winograd para la multiplicación de matrices cuadradas, bajando el tiempo computacional hasta 2.373. Actualmente tol opera a 2.8 usando BLAS.
Entiendo que podría ser una mejora a tener en cuenta.

Un saludo

Change History (1)

comment:1 Changed 14 years ago by Víctor de Buen Remiro

Milestone: Mantainance → Numerical methods
Type: defect → task

Actualmente TOL utiliza la función DGEMM de BLAS que supuestamente implementa el producto usual de matriz por matriz que debería tener complejidad 3 exacta pero por lo visto usan en realidad el algoritmo original de Strassen que tiene en torno a 2.8

Yo he encontrado una función ​DGEMMW en FORTRAN que implementa la variedad de Winograd del algoritmo de Strassen y que tiene complejidad 2.376 que es básicamente la misma que la que la de Vassilevska: 2.3727 de la que no encuentro código open-source.

DGEMMW
a highly portable Level 3 BLAS implementation of Winograd's variant
of Strassen's matrix multiplication algorithm
by douglas-craig@CS.YALE.EDU ("Craig C. Douglas")  Nov 27 1995

Habría que convertirla en C y tratar de incorporarla a TOL a ver si funciona bien.

Note: See TracTickets for help on using tickets.