3 people like it.

# Parallel Strassen Matrix Multiplication

Strassen's Multiplication Algorithm works much better than the standard approach when the matrix is large. The program implements a parallel version of it.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: ``` ``````open Microsoft.FSharp.Math open System.Threading.Tasks open System.IO let splitMatrix (original : Matrix) = let (oldRows, oldCols) = original.Dimensions let newRows = oldRows >>> 1 let newCols = oldCols >>> 1 let c11 = original.[0..(newRows - 1), 0..(newCols - 1)] let c12 = original.[0..(newRows - 1), newCols..(oldCols - 1)] let c21 = original.[newRows..(oldRows - 1), 0..(newCols - 1)] let c22 = original.[newRows..(oldRows - 1), newCols..(oldCols - 1)] (c11, c12, c21, c22) let integrateMatrix(a11 : Matrix, a12 : Matrix, a21 : Matrix, a22 : Matrix) = let (oldRows, oldCols) = a11.Dimensions let (rows, cols) = (oldRows <<< 1, oldCols <<< 1) let helper i j = if (i < oldRows) then if (j < oldCols) then a11.[i, j] else a12.[i, (j - oldCols)] else if (j < oldCols) then a21.[(i - oldRows), j] else a22.[(i - oldRows), (j - oldCols)] Matrix.init rows cols helper let rec Strassen (A : Matrix, B : Matrix) = let (rows, cols) = A.Dimensions if (rows <= 64) then A * B else let (a11, a12, a21, a22) = splitMatrix(A) let (b11, b12, b21, b22) = splitMatrix(B) let M1 = Task.Factory.StartNew(fun () -> Strassen ((a11 + a22), (b11 + b22))) let M2 = Task.Factory.StartNew(fun () -> Strassen ((a21 + a22), b11)) let M3 = Task.Factory.StartNew(fun () -> Strassen (a11, (b12 - b22))) let M4 = Task.Factory.StartNew(fun () -> Strassen (a22, (b21 - b11))) let M5 = Task.Factory.StartNew(fun () -> Strassen ((a11 + a12), b22)) let M6 = Task.Factory.StartNew(fun () -> Strassen ((a21 - a11), (b11 + b12))) let M7 = Strassen ((a12 - a22), (b21 + b22)) let c11 = M1.Result + M4.Result - M5.Result + M7 let c12 = M3.Result + M5.Result let c21 = M2.Result + M4.Result let c22 = M1.Result - M2.Result + M3.Result + M6.Result integrateMatrix(c11, c12, c21, c22) ``````
namespace Microsoft
namespace Microsoft.FSharp
namespace System
namespace System.IO
val splitMatrix : original:'a -> 'b * 'c * 'd * 'e

Full name: Script.splitMatrix
val original : 'a
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val oldRows : int
val oldCols : int
val newRows : int
val newCols : int
val c11 : 'b
val c12 : 'c
val c21 : 'd
val c22 : 'e
val integrateMatrix : a11:'a * a12:'b * a21:'c * a22:'d -> 'e

Full name: Script.integrateMatrix
val a11 : 'a
val a12 : 'b
val a21 : 'c
val a22 : 'd
val rows : int
val cols : int
val helper : (int -> int -> 'f)
val i : int
val j : int
val Strassen : A:int * B:int -> int

Full name: Script.Strassen
val A : int
val B : int
val cols : obj
val a11 : int
val a12 : int
val a21 : int
val a22 : int
val b11 : int
val b12 : int
val b21 : int
val b22 : int
Multiple items
member AsyncState : obj
member Dispose : unit -> unit
member Exception : AggregateException
member Id : int
member IsCanceled : bool
member IsCompleted : bool
member IsFaulted : bool
...

--------------------
member Result : 'TResult with get, set

--------------------
Task(action: System.Action<obj>, state: obj) : unit

--------------------
Task(function: System.Func<obj,'TResult>, state: obj) : unit
Multiple items

--------------------
Multiple items

--------------------