4. You are to use the algorithm for Winograd\'s Method given on Handout #5 to mu

Question

4. You are to use the algorithm for Winograd's Method given on Handout #5 to multiply the following two matrices: a. Give the contents of the the CF and RF arrays. b. For each result element Cij give the value of the cross products. Show your work. c. Add the row factor, column factor, and the cross product term together to get the final value, and show the resulting C array. d. How many additions did you perform, and how many multiplications did you perform. e. How many useless additions and multiplications did you perform? (A useless operation is one in which one of the operands is 0.)

Explanation / Answer

public class Strassen
{

    public static double[][] multiply(double[][] A, double[][] B)
    {
        try
        {
            checkInputStrassen(A,B);
        }
        catch (RuntimeException e)
        {
            throw e;
        }
        return strassenRecursive(A,B);
    }

    private static double[][] reconstructAnswer(double[][] r, double[][] s,
            double[][] t, double[][] u)
    {
        int n = r.length*2;
        double[][] C = new double[n][n];
        copyBack(C,r,0,0);
        copyBack(C,s,0,n/2);
        copyBack(C,t,n/2,0);
        copyBack(C,u,n/2,n/2);
        return C;
    }

    private static void copyBack(double[][] C, double[][] r, int x, int y)
    {
        for (int i=0; i<r.length; i++)
        {
            for (int j=0; j<r.length; j++)
            {
                C[x+i][y+j] = r[i][j];
            }
        }
    }

    private static void copy(double[][] a, double[][] A, int x, int y)
    {
        for (int i=0; i<a.length; i++)
        {
            for (int j=0; j<a.length; j++)
            {
                a[i][j] = A[x+i][y+j];
            }
        }
    }

    private static double[][] strassenRecursive(double[][] A, double[][] B)
    {
        int n = A.length;
        if (n==1)
        {
            double[][] C = new double[1][1];
            C[0][0]=A[0][0]*B[0][0];
            return C;
        }

        double[][] r,s,t,u, a,b,c,d,e,f,g,h, P1,P2,P3,P4,P5,P6,P7;
        r = new double[n/2][n/2];       s = new double[n/2][n/2];       t = new double[n/2][n/2];      
        u = new double[n/2][n/2];       a = new double[n/2][n/2];       b = new double[n/2][n/2];      
        c = new double[n/2][n/2];       d = new double[n/2][n/2];       e = new double[n/2][n/2];      
        f = new double[n/2][n/2];       g = new double[n/2][n/2];       h = new double[n/2][n/2];
        P1 = new double[n/2][n/2];      P2 = new double[n/2][n/2];      P3 = new double[n/2][n/2];     
        P4 = new double[n/2][n/2];      P5 = new double[n/2][n/2];      P6 = new double[n/2][n/2];     
        P7 = new double[n/2][n/2];     
        copy(a,A,0,0);
        copy(b,A,0,n/2);
        copy(c,A,n/2,0);
        copy(d,A,n/2,n/2);
        copy(e,B,0,0);
        copy(f,B,0,n/2);
        copy(g,B,n/2,0);
        copy(h,B,n/2,n/2);

        P1= strassenRecursive(a, add(f,h,-1)); // P1 = a(f-h) = af-ah
        P2= strassenRecursive(add(a,b,1), h); // P2 = (a+b)h = ah+bh
        P3= strassenRecursive(add(c,d,1), e); // P3 = (c+d)e = ce+de
        P4= strassenRecursive(d, add(g,e,-1)); // P4 = d(g-e) = dg-de
        P5= strassenRecursive(add(a,d,1), add(e,h,1)); // P5 = (a+d)(e+h)=ae+de+ah+dh
        P6= strassenRecursive(add(b,d,-1), add(g,h,1)); // P6 = (b-d)(g+h)=bg-dg+bh-dh
        P7= strassenRecursive(add(a,c,-1), add(e,f,1)); // P7 = (a-c)(e+f)=ae-ce+af-cf

        r = add(add(P5,P4,1),add(P2,P6,-1),-1); // r = P5+P4-P2+P6 = ae+bg
        s = add(P1,P2,1); // s = P1+P2 = af+bh
        t = add(P3,P4,1); // t = P3+P4 = ce+dg
        u = add(add(P5,P1,1),add(P3,P7,1),-1); //u = P5+P1-P3-P7 = cf+dh
        return reconstructAnswer(r,s,t,u);
    }

    private static double[][] add(double[][] A, double[][] B, int signofB)
    {
        int n = A.length;
        double[][] C = new double[n][n];
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                C[i][j] = A[i][j] + signofB*B[i][j];
            }
        }
        return C;

    }

    private static void checkInputStrassen(double[][] A, double[][] B)
    {
        int p = A.length;
        if (p==0)
        {
            throw new IllegalArgumentException("Null matrix");
        }
        int n=p;
        while (n>1)
        {
            if (n%2 != 0)
            {
                throw new IllegalArgumentException("Non power of 2 matrix");
            }
            n/=2;
        }

        int q = A[0].length;
        if (q==0)
        {
            throw new IllegalArgumentException("Null matrix");
        }

        if (q!=p)
        {
            throw new IllegalArgumentException("Nonsquare Matrix");
        }

        for (int i=1; i<p; i++)
        {
            if (A[i].length != q)
            {
                throw new IllegalArgumentException("Inconsistent matrix");
            }
        }
        if (B.length != q)
        {
            throw new IllegalArgumentException("Inconsistent dimensions");
        }

        int r = B[0].length;
        if (r!=p)
        {
            throw new IllegalArgumentException("Nonsquare Matrix");
        }
        for (int i=1; i<q; i++)
        {
            if (B[i].length != r)
            {
                throw new IllegalArgumentException("Inconsistent matrix");
            }
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.