Strassen algorithm in vhdl

hi all I am currently struggling trying to write Strassens Algorithm for matrix multiplication in VHDL. I have written the code for 2x2 matrices, but now have to develop it to implement 4x4 matrices or larger. Can anyone help please. Thank You

Reply to
rsr1991
Loading thread data ...

Unless you have reached the limit of on-FPGA multipliers, the extra control complexity makes such an algorithm unattractive for real-world applications.

Is this an educational assignment?

--------------------------------------- Posted through

formatting link

Reply to
RCIngham

Why don't you do a practical implementation of Strassen's Algorithm, per the Wikipedia page:

"Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware."

My feeling on this is that you are only going to benefit from this algorithm if you have a pretty darn big matrix (32 by 32 is probably still "small"), a processor for which addition, subtraction, _and general- purpose ALU_ instructions are significantly cheaper than multiplication, and either a lot of engineering time to spend freely, or a desperate need to cut just a little bit (less than 14%) off of the time to do a matrix multiply.

Note that you are replacing eight (matrix) multiplies and four additions with seven multiplies -- and _eight_ additions or subtractions. On a processor, with IEEE floating point, I'm not sure that Strassen's Algorithm wouldn't take _more_ computational resources to complete that a bog-standard matrix multiply.

I could see incorporating this (or one of the more optimal algorithms) into a general-purpose math package (if it actually worked), but the notion of going to so much trouble for so little gain kind of boggles my mind -- wouldn't you get more speedup by hand-flogging your timing, and increasing your clock rate a bit, or otherwise tuning the rest of your algorithm?

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
 Click to see the full signature
Reply to
Tim Wescott

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.