Add Randomized Matrix Multiplication Verifier

This commit implements a Monte Carlo method to verify matrix multiplication for both integer and decimal valued matrices. The algorithm generates random binary vectors, multiplies them with the matrices, and compares the results. If any mismatch is found, the multiplication is deemed incorrect. This efficient verification avoids full matrix multiplication by using partial calculations. It also accounts for floating-point precision with a small tolerance and ensures matrix dimensions are consistent before verification.
TheAlgorithms · Menil-dev · May 11, 2025 · May 11, 2025 · May 11, 2025 · May 11, 2025
commit 78fae04773f8e8043c2462a2aed1b85f2de51a75
@@ -0,0 +1,112 @@
+import java.util.Random;
+
+/*
+   This class implements the Randomized Matrix Multiplication Verification.
+   It generates a random vector and performs verification using Freivalds' Algorithm.
+   @author Menil-dev
+ */
+public class MatrixMultiplicationVerifier {
+
+  private MatrixMultiplicationVerifier() {
+        throw new UnsupportedOperationException("Utility class");
+    }
+
+  /*
+      It multiplies input matrix with randomized vector.
+      @params matrix which is being multiplied currently with random vector
+      @params random vector generate for every iteration.
+
+      This basically calculates dot product for every row, which is used to verify whether the product of matrices is valid or not.
+      @returns matrix of calculated dot product.
+  */
+    static int[] multiply(int[][] matrix, int[] vector) {
+        int n=vector.length, result[]=new int[n];
+        for(int i=0;i<n;i++)
+            for(int j=0;j<n;j++)
+                result[i]+=matrix[i][j]*vector[j];
+        return result;
+    }
+
+  /*
+      @actual function that performs verification function
+      @params, all three input matrices of int type, number of iterations
+  */
+    public static boolean verify(int[][] A, int[][] B, int[][] C, int iterations) {
+      if (A.length==0 || B.length==0 || C.length==0 || A[0].length==0 || B[0].length==0 || C[0].length==0) {
+            return A.length==B[0].length && B.length==C.length && C[0].length==A[0].length;  // Basic dimension consistency check
+        }
+      //Basic integrity checks on number of iterations.
+      if (iterations<=0) {
+            throw new IllegalArgumentException("Number of iterations must be positive");
+        }
+      int n = A.length;
+      if (iterations>2*n) {
+          throw new IllegalArgumentException("Number of iterations should not exceed 2 * n where n is the matrix size");
+      }
+
+      // Actual logic to verify the multiplication
+        int n=A.length; Random rand=new Random();
+        for(int t=0;t<iterations;t++) {          
+            int[] randomizedVector=new int[n];
+          //This generates a random binary vector of first dimension of C matrix(Output Matrix).
+            for(int i=0;i<n;i++) r[i]=rand.nextInt(2);        
+            int[] Br=multiply(B,r), ABr=multiply(A,Br), Cr=multiply(C,r);
+            for(int i=0;i<n;i++)
+                if(ABr[i]!=Cr[i]) return false;        // if any product mismatches, return condition.
+        }
+        return true;
+    }
+
+
+  /*
+    It multiplies input matrix of double type with randomized vector.
+    @params matrix which is being multiplied currently with random vector.
+    @params random vector generated for every iteration.
+
+    This basically calculates dot product for every row, which is used to verify whether the product of matrices is valid or not.
+*/
+static double[] multiply(double[][] matrix,double[] vector) {
+    int n=vector.length;
+    double[] result = new double[n];
+    for(int i=0;i<n;i++)
+        for(int j=0;j<n;j++)
+            result[i] += matrix[i][j] * vector[j];
+    return result;
+}
+
+/*
+    Actual function that performs the verification.
+    @params, all three input matrices of double type, number of iterations
+*/
+public static boolean verify(double[][] A,double[][] B,double[][] C,int iterations) {
+    if (A.length==0 || B.length==0 || C.length==0 || A[0].length==0 || B[0].length==0 || C[0].length==0) {
+        return A.length==B[0].length && B.length==C.length && C[0].length==A[0].length;  // Basic dimension consistency check
+    }
+    // Basic integrity checks on number of iterations.
+    if (iterations<=0) {
+        throw new IllegalArgumentException("Number of iterations must be positive");
+    }
+    int n=A.length;
+    if (iterations>2*n) {
+        throw new IllegalArgumentException("Number of iterations should not exceed 2 * n where n is the matrix size");
+    }
+
+    // Actual logic to verify the multiplication
+    Random rand=new Random();
+    for(int t=0;t<iterations;t++) {
+        double[] randomizedVector=new double[n];
+        // This generates a random binary vector of the first dimension of C matrix (Output Matrix).
+        for(int i=0;i<n;i++) 
+            randomizedVector[i]=rand.nextInt(2);  // Random binary values 0 or 1
+
+        double[] Br=multiply(B,randomizedVector);
+        double[] ABr=multiply(A,Br);
+        double[] Cr=multiply(C,randomizedVector);
+
+        for(int i=0;i<n;i++)
+            if(Math.abs(ABr[i]-Cr[i])>1e-9)  // Allowing a small tolerance for floating-point comparisons
+                return false;  // If any product mismatches, return false.
+    }
+    return true;
+}
+}