Randomized

Verify matrix multiplication using randomized Freivalds algorithm

Pinterest LinkedIn Tumblr

Freivalds algorithm is used to verify the correctness of the matrix multiplication. We can also use the native way to verify the matrix multiplication. But the current method is slow. It is a probabilistic randomized algorithm used to verify matrix multiplication.

A native algorithm would compute the product A x B explicitly and compare term by term whether this product equals C. Write a program to verify the matrix multiplication using Freivalds algorithm.

source Code

package com.dsacode.Algorithm.randomized;
 
import java.util.Arrays;
import java.util.Random;
 
public class VerifyMatrix {
     public static void main(String args[]){
         int n = 2;
         System.out.println("Dimesion of the matrices: "+n);
          
         double[][] a=new double[][]{{2, 3},{3, 4}};
         System.out.println("Matrix One values: " + Arrays.deepToString(a));
 
         double b[][]=new double[][]{{1, 0},{ 1, 2}};
         System.out.println("Matrix two values: " + Arrays.deepToString(b));
          
         double c[][] = new double[][]{{6,5},{8,7}};
         System.out.println("Result Matrix values: " + Arrays.deepToString(c));
          
         double [][]r = new double[n][1];
         Random random = new Random();
         for(int i=0; i < n; i++){
             r[i][0] = random.nextInt(2);
         }
 
         double br[][] = new double[n][1];
         @SuppressWarnings("unused")
        double cr[][] = new double[n][1];
         double abr[][] = new double[n][1];
 
         br = multiplymatrix(b, r, n);
         cr = multiplymatrix(c, r, n);
         abr = multiplymatrix(a, br, n);
 
         boolean flag = true;
 
         for(int i=0; i < n; i++)  {
             if(abr[i][0] == 0)
                 continue;
             else
                 flag = false;
         }
 
         if(flag == true)
             System.out.println("Successfully verified matrix multiplication using Freivalds algorithm");
         else
             System.out.println("Failed to verify matrix multiplication using Freivalds algorithm");
 
     }
 
   
 
     public static double[][] multiplymatrix(double[][] a, double[][] b, int n) {
         double result[][] = new double[n][1];
 
         for (int i = 0; i < n; i++){
             for (int j = 0; j < 1; j++) {
                 for (int k = 0; k < n; k++) {   
                     result[i][j] = result[i][j] + a[i][k] * b[k][j];
                 }
             }
         }
         return result;
     }
  }

Output

Dimesion of the matrices: 2
Matrix One values: [[2.0, 3.0], [3.0, 4.0]]
Matrix two values: [[1.0, 1.0], [0.0, 2.0]]
Result Matrix values: [[6.0, 5.0], [8.0, 7.0]]
Failed to verify matrix multiplication using Freivalds algorithm

Algorithm Explanation

Given three n x n matrices A, B, and C.
Verify whether A x B = C.
If verification success, return as verified successfully. Otherwise, returns false.

Time Complexity

Best CaseAverage CaseWorst Case
O(n^2)O(n^2)O(n^2)

Reference

https://en.wikipedia.org/wiki/Freivalds%27_algorithm#

Write A Comment