Strassen's algorithm: Difference between revisions

Line 956:

[https://github.com/hollance/Matrix/blob/master/Matrix.swift '''Matrix Class'''] by [https://github.com/ozgurshn ozgurshn]

// Matrix Strassen Multiplication

func strassenMultiply(matrix1: Matrix, matrix2: Matrix) -> Matrix {

precondition(matrix1.columns == matrix2.columns,

"Two matrices can only be matrix multiplied if one has dimensions mxn & the other has dimensions nxp where m, n, p are in R")

// Transform to square matrix

let maxColumns = Swift.max(matrix1.rows, matrix1.columns, matrix2.rows, matrix2.columns)

let pwr2 = nextPowerOfTwo(num: maxColumns)

Line 975:

Line 978:

}

// Get strassen result and transfer to array with proper size

let formulaResult = strassenFormula(matrix1: sqrMatrix1, matrix2: sqrMatrix2)

var finalResult = Matrix(rows: matrix1.rows, columns: matrix2.columns)

Line 985:

Line 989:

}

// Calculate next power of 2

func nextPowerOfTwo(num: Int) -> Int {

return Int(pow(2,(ceil(log2(Double(num))))))

}

// Multiply Matrices Using Strassen Formula

func strassenFormula(matrix1: Matrix, matrix2: Matrix) -> Matrix {

precondition(matrix1.rows == matrix1.columns && matrix2.rows == matrix2.columns, "Matrices need to be square")

Line 994:

Line 1,000:

let rowHalf = matrix1.rows / 2

// Strassen Formula https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/

var a = Matrix(rows: rowHalf, columns: rowHalf)

var b = Matrix(rows: rowHalf, columns: rowHalf)

Line 1,017:

Line 1,023:

}

let p1 = strassenFormula(matrix1: a, matrix2: (f - h))

let p1 = strassenFormula(matrix1: a, matrix2: (f - h)) // a * (f - h)

let p2 = strassenFormula(matrix1: (a + b), matrix2: h)

let p2 = strassenFormula(matrix1: (a + b), matrix2: h) // (a + b) * h

let p3 = strassenFormula(matrix1: (c + d), matrix2: e)

let p3 = strassenFormula(matrix1: (c + d), matrix2: e) // (c + d) * e

let p4 = strassenFormula(matrix1: d, matrix2: (g - e))

let p4 = strassenFormula(matrix1: d, matrix2: (g - e)) // d * (g - e)

let p5 = strassenFormula(matrix1: (a + d), matrix2: (e + h))

let p5 = strassenFormula(matrix1: (a + d), matrix2: (e + h)) // (a + d) * (e + h)

let p6 = strassenFormula(matrix1: (b - d), matrix2: (g + h))

let p6 = strassenFormula(matrix1: (b - d), matrix2: (g + h)) // (b - d) * (g + h)

let p7 = strassenFormula(matrix1: (a - c), matrix2: (e + f))

let p7 = strassenFormula(matrix1: (a - c), matrix2: (e + f)) // (a - c) * (e + f)

⚫

let ~~result11~~ = p5 + p4 - p2 + p6

let ~~result12~~ = p1 + p2

let result11 = p5 + p4 - p2 + p6 // p5 + p4 - p2 + p6

let ~~result21~~ = p3 + p4

let result12 = p1 + p2 // p1 + p2

let ~~result22~~ = p1 + p5 - p3 - p7

let result21 = p3 + p4 // p3 + p4

⚫

let result22 = p1 + p5 - p3 - p7 // p1 + p5 - p3 - p7

var result = Matrix(rows: matrix1.rows, columns: matrix1.rows)

Line 1,043:

Line 1,050:

func main(){

// Matrix Class https://github.com/hollance/Matrix/blob/master/Matrix.swift

var a = Matrix(rows: 2, columns: 2)

a[row: 0] = [1, 2]