#Ross Berkowitz 4th Homework #Posting Permission Granted #read("C:\\Users\\Ross\\Documents\\em14\\hw4.txt"); Help:=proc(): print(MatMultRG(A,B), Strassen(A,B), Randmat(n,R)): end: ################ 3 ###################### #MatMultRG(A,B) Inputs two matrices A and B (of any dimension) and computes AB using the #definition of matrix multiplication (i.e. MatMultR) MatMultRG:=proc(A,B) local AB,C,D,n,m,i,j: n:=nops(A): if nops(B)<>n then RETURN(FAIL): fi: C:=PadZeros(A): D:=PadZeros(B): AB:=MatMultR(C,D): [seq([seq(AB[i][j],j=1..n)],i=1..n)]: end: ################ 4 ##############################3 #Strassen multiplies two square matrices A and B whose dimension #is a power of 2 using Strassen's Algorithm Strassen:=proc(A,B) local n,i,A11,A12,A21,A22,B11,B12,B21,B22, M1,M2,M3,M4,M5,M6,M7,M8,C11,C12,C21,C22: n:=nops(A): if nops(B)<>n then RETURN(FAIL): fi: if not type(log[2](n),integer) then RETURN(FAIL): fi: if n=1 then RETURN([[A[1][1]*B[1][1]]]): fi: A11:=[seq([op(1..n/2,A[i])],i=1..n/2)]: A12:=[seq([op(n/2+1..n,A[i])],i=1..n/2)]: A21:=[seq([op(1..n/2,A[i])],i=n/2+1..n)]: A22:=[seq([op(n/2+1..n,A[i])],i=n/2+1..n)]: B11:=[seq([op(1..n/2,B[i])],i=1..n/2)]: B12:=[seq([op(n/2+1..n,B[i])],i=1..n/2)]: B21:=[seq([op(1..n/2,B[i])],i=n/2+1..n)]: B22:=[seq([op(n/2+1..n,B[i])],i=n/2+1..n)]: M1:=Strassen(MatAdd(A11,A22),MatAdd(B11,B22)): M2:=Strassen(MatAdd(A21,A22),B11): M3:=Strassen(A11,MatSubt(B12,B22)): M4:=Strassen(A22,MatSubt(B21,B11)): M5:=Strassen(MatAdd(A11,A12),B22): M6:=Strassen(MatSubt(A21,A11),MatAdd(B11,B12)): M7:=Strassen(MatSubt(A12,A22),MatAdd(B21,B22)): C11:=MatAdd(MatAdd(M1,M7),MatSubt(M4,M5)): C12:=MatAdd(M3,M5): C21:=MatAdd(M2,M4): C22:=MatAdd(MatSubt(M1,M2),MatAdd(M3,M6)): [seq([op(C11[i]),op(C12[i])],i=1..nops(C11)), seq([op(C21[i]),op(C22[i])],i=1..nops(C21))]: end: #MatSubt Inputs matrices A,B and outputs A-B MatSubt:=proc(A,B) local i,j: [seq([seq(A[i][j]-B[i][j],j=1..nops(A[i]))],i=1..nops(A))]: end: ##################### 5 ######################### #Randmat inputs a dimension n and a number R and outputs a random nxn matrix #which takes values between 0 and R Randmat:=proc(n,R)local i,j,rando: rando:=rand(0..R): [seq([seq(rando(),j=1..n)],i=1..n)]: end: ################### 6 ################################# #Yes I saw a difference in this case. for n=2^7 MatMultR took 82 seconds to multiply #two matrices while Strassen only took 63 seconds. Interestingly this leed shrank considerably when I used nonpositive matrices to 87 seconds to 80. #################### Class Stuff #C4.txt: Feb. 3 2014. Distance-learning class (due to University closing due to snow storm) Help4:=proc(): print( MatAdd(A,B),MatMult(A,B), PadZeros(A), ,MatMultR(A,B) ) : print(Tra(A), RandMat(m,n,R)): end: #Tra(A): the transpose of the matrix A Tra:=proc(A) local i,j: [seq([seq(A[i][j],i=1..nops(A))],j=1..nops(A[1]))]: end: #RandMat(m,n,R): a random m by n matrix with entries between -R and R #given as a list of lists RandMat:=proc(m,n,R) local ra,i,j: ra:=rand(-R..R): [seq([seq(ra(),j=1..n)],i=1..m)]: end: #MatAdd(A,B): adds two matrices of the same size given as lists of lists MatAdd:=proc(A,B) local i,j: if nops(A)<>nops(B) then print(Not the same number of rows): RETURN(FAIL): fi: if nops({seq(nops(A[i]),i=1..nops(A))})<>1 then print(Rows do not all the same lengths, hence, A, is not a matrix ): RETURN(FAIL): fi: if nops({seq(nops(B[i]),i=1..nops(B))})<>1 then print(Rows do not all the same lengths, hence, B, is not a matrix ): RETURN(FAIL): fi: if nops(A)>0 and nops(A[1])<>nops(B[1]) then print(Not the same number of columns): RETURN(FAIL): fi: [seq([seq(A[i][j]+B[i][j],j=1..nops(A[i]))],i=1..nops(A))] end: #MatMult(A,B): multiplies two matrices A and B MatMult:=proc(A,B) local i,j,k: if nops({seq(nops(A[i]),i=1..nops(A))})<>1 then print(Rows do not all the same lengths, hence, A, is not a matrix ): RETURN(FAIL): fi: if nops({seq(nops(B[i]),i=1..nops(B))})<>1 then print(Rows do not all the same lengths, hence, B, is not a matrix ): RETURN(FAIL): fi: if nops(A[1])<>nops(B) then print(number of columns of, A, is not the same as the number of rows of, B): print(hence can't multiply them.): RETURN(FAIL): fi: [seq([seq( add(A[i][k]*B[k][j],k=1..nops(A[i])), j=1..nops(B[1]))],i=1..nops(A))]: end: #PadZeros(A): given a square matrix A pads it with zero to make its #dimension a powr of 2 PadZeros:=proc(A) local i,n,n1: if nops(A)<>nops(A[1]) then print(not a square matrix): RETURN(FAIL): fi: n:=nops(A): if type(log[2](n),integer) then A: else n1:=2^ceil(log[2](n)): [seq([op(A[i]),0$(n1-n)],i=1..nops(A)),[0$n1]\$(n1-n)]: fi: end: #MatMultR(A,B): multiplies two square matrices A and B whose dimension #is a power of 2 MatMultR:=proc(A,B) local n,i,A11,A12,A21,A22,B11,B12,B21,B22, M1,M2,M3,M4,M5,M6,M7,M8,C11,C12,C21,C22: n:=nops(A): if nops(B)<>n then RETURN(FAIL): fi: if not type(log[2](n),integer) then RETURN(FAIL): fi: if n=1 then RETURN([[A[1][1]*B[1][1]]]): fi: A11:=[seq([op(1..n/2,A[i])],i=1..n/2)]: A12:=[seq([op(n/2+1..n,A[i])],i=1..n/2)]: A21:=[seq([op(1..n/2,A[i])],i=n/2+1..n)]: A22:=[seq([op(n/2+1..n,A[i])],i=n/2+1..n)]: B11:=[seq([op(1..n/2,B[i])],i=1..n/2)]: B12:=[seq([op(n/2+1..n,B[i])],i=1..n/2)]: B21:=[seq([op(1..n/2,B[i])],i=n/2+1..n)]: B22:=[seq([op(n/2+1..n,B[i])],i=n/2+1..n)]: M1:=MatMultR(A11,B11): M2:=MatMultR(A12,B21): M3:=MatMultR(A11,B12): M4:=MatMultR(A12,B22): M5:=MatMultR(A21,B11): M6:=MatMultR(A22,B21): M7:=MatMultR(A21,B12): M8:=MatMultR(A22,B22): C11:=MatAdd(M1,M2): C12:=MatAdd(M3,M4): C21:=MatAdd(M5,M6): C22:=MatAdd(M7,M8): [seq([op(C11[i]),op(C12[i])],i=1..nops(C11)), seq([op(C21[i]),op(C22[i])],i=1..nops(C21))]: end: #Tra(A): the transpose of the matrix A Tra:=proc(A) local i,j: [seq([seq(A[i][j],i=1..nops(A))],j=1..nops(A[1]))]: end: #RandMat(m,n,R): a random m by n matrix with entries between -R and R #given as a list of lists RandMat:=proc(m,n,R) local ra,i,j: ra:=rand(-R..R): [seq([seq(ra(),j=1..n)],i=1..m)]: end: