Skip to main content

daybs

User since Oct 28, 2022
1 Posts

Recent Posts

strassens algo

Oct 13, 2022daybs

0 likes • 5 views

// This function takes a matrix and outputs 4 equal size submatrices, starting from top left going to bottom right.
const split = (matrix: number[][]): number[][][] => {
const n: number = matrix.length
const mid: number = n/2
const C11: number[][] = new Array<Array<number>> // first n/2 rows intersection first n/2 columms
const C12: number[][] = new Array<Array<number>> // first n/2 rows intersection last n/2 columns
const C21: number[][] = new Array<Array<number>> // last n/2 rows intersection first n/2 columns
const C22: number[][] = new Array<Array<number>> // last n/2 rows intersection last n/2 columns
for(let i: number = 0; i < mid; i++) {
C11.push([])
C12.push([])
for (let j: number = 0; j < mid; j++) {
C11[i].push(matrix[i][j])
}
for (let j: number = mid; j < n; j++) {
C12[i].push(matrix[i][j])
}
}
for(let i: number = 0; i < mid; i++) {
C21.push([])
C22.push([])
for (let j: number = 0; j < mid; j++) {
C21[i].push(matrix[i+mid][j])
}
for (let j: number = mid; j < n; j++) {
C22[i].push(matrix[i+mid][j])
}
}
return [C11, C12, C21, C22]
}
// This function takes 4 matrices, in order from top left to bottom right, and combines them into one matrix
const combine = (A: number[][], B: number[][], C: number[][], D: number[][]): number[][] => {
const n: number = A.length*2
const combo: number[][] = new Array<Array<number>>
// Populate combo with temporary 0s
for(let i: number = 0; i < A.length; i++) {
combo.push([])
for (let j: number = 0; j < A.length; j++) {
combo[i].push(A[i][j])
}
for (let j: number = A.length; j < n; j++) {
combo[i].push(B[i][j-A.length])
}
}
for(let i: number = A.length; i < n; i++) {
combo.push([])
for (let j: number = 0; j < A.length; j++) {
combo[i].push(C[i-A.length][j])
}
for (let j: number = A.length; j < n; j++) {
combo[i].push(D[i-A.length][j-A.length])
}
}
return combo
}
// Basic matrix addition function
const matrix_add = (A: number[][], B: number[][]): number[][] => {
const matrix_sum: number[][] = [[]]
const n: number = A.length
for(let i: number = 0; i < n; i++) {
matrix_sum[i] = []
for (let j: number = 0; j < n; j++) {
matrix_sum[i][j] = A[i][j] + B[i][j]
}
}
return matrix_sum
}
// Basic matrix subtraction function
const matrix_subtract = (A: number[][], B: number[][]): number[][] => {
const matrix_diff: number[][] = [[]]
const n: number = A.length
for(let i: number = 0; i < n; i++) {
matrix_diff[i] = []
for (let j: number = 0; j < n; j++) {
matrix_diff[i][j] = A[i][j] - B[i][j]
}
}
return matrix_diff
}
const strassen = (A: number[][], B: number[][]): number[][] => {
const n: number = A.length
var C: number[][] = [[]]
// Populate C with temporary 0s
for(let i: number = 0; i < n; i++) {
C[i] = []
for (let j: number = 0; j < n; j++) {
C[i][j] = 0
}
}
// Once the matrices reach a small enough size, compute using the brute force method
if (n <= 2) {
for (let i: number = 0; i < n; i++) {
for (let j: number = 0; j < n; j++) {
for (let z: number = 0; z < n; z++) {
C[i][j] = C[i][j] + (A[i][z]*B[z][j])
}
}
}
return C
}
// Create independent variables from function that returns an array with array destructuring.
const [a, b, c, d] = split(A)
const [e, f, g, h] = split(B)
// Using Strassen's method to calculate 1 less product
const p1: number[][] = strassen(matrix_add(a, d), matrix_add(e,h))
const p2: number[][] = strassen(d, matrix_subtract(g, e))
const p3: number[][] = strassen(matrix_add(a, b), h)
const p4: number[][] = strassen(matrix_subtract(b, d), matrix_add(g, h))
const p5: number[][] = strassen(a, matrix_subtract(f, h))
const p6: number[][] = strassen(matrix_add(c, d), e)
const p7: number[][] = strassen(matrix_subtract(a, c), matrix_add(e, f))
const C11: number[][] = matrix_add(matrix_subtract(matrix_add(p1, p2), p3), p4)
const C12: number[][] = matrix_add(p5, p3)
const C21: number[][] = matrix_add(p6, p2)
const C22: number[][] = matrix_subtract(matrix_subtract(matrix_add(p5, p1), p6), p7)
C = combine(C11, C12, C21, C22)
return C
}
const M1: number[][] = [[1,3],[7,5]]
const M2: number[][] = [[6,8],[4,2]]
const M_Product: number[][] = strassen(M1, M2)
console.log("Matrix 1:")
console.log(M1)
console.log("Matrix 2:")
console.log(M2)
console.log("Product: ")
console.log(M_Product)

Post Statistics

Posts

No Posts Found

It looks like daybs has no public posts

Likes

Please Log In

You must be authenticated to view a user's likes

Shared

Please Log In

You must be authenticated to view a user's shared posts

Profile Privacy

Multi-Factor Authentication

Multi-Factor Authentication (MFA) is an authentication method that requires you to provide two or more verification factors to gain access to your account. In addition to username and password, MFA requires you to verify your email on every login, which decreases the likelihood of someone stealing your account.

Change Password

Forgot Password?

Identity Color

Changes the color of your profile icon and cursor highlight in the live code editor. You and other users will be able to view this change.

Delete Account

Deleting your account is permanent. All data associated with your account will be lost.