From 71043.3326@CompuServe.COM Fri Aug  9 23:48:24 1996
Received: from arl-img-6.compuserve.com (arl-img-6.compuserve.com [149.174.217.136]) by cs.sunysb.edu (8.6.12/8.6.9) with ESMTP id XAA13834 for <skiena@CS.SunySB.EDU>; Fri, 9 Aug 1996 23:48:16 -0400
Received: by arl-img-6.compuserve.com (8.6.10/5.950515)
	id XAA25384; Fri, 9 Aug 1996 23:42:38 -0400
Date: 09 Aug 96 23:40:46 EDT
From: Stan Wagon&JoanHutchinson <71043.3326@CompuServe.COM>
To: "INTERNET:skiena@CS.SunySB.EDU" <skiena@CS.SunySB.EDU>
Subject: Re: Strassen's algorithm
Message-ID: <960810034046_71043.3326_GHI95-1@CompuServe.COM>
Status: RO

Here, w/o comment or promises of efficiency, is what I did some years ago:



(*The following implements Strassen's algorithm for
matrix multiplication*)

firsthalf[W_]  := Take[W,  Length[W]/2]
secondhalf[W_] := Take[W, -Length[W]/2]

prod[{x_}, {y_}] := {x y}
prod[A_, B_]:=
Block[{term=Table[Null,{7}],
	A11,A12,A21,A22,B11,B12,B21,B22,C1,C2,C},
			If[Length[A] == 1, (Print[hi];A.B),(*delete line*)
			A11 = Map[firsthalf,  firsthalf[A] ];
			A12 = Map[secondhalf, firsthalf[A] ];
			A21 = Map[firsthalf,  secondhalf[A]];
			A22 = Map[secondhalf, secondhalf[A]];
			B11 = Map[firsthalf,  firsthalf[B] ];
			B12 = Map[secondhalf, firsthalf[B] ];
			B21 = Map[firsthalf,  secondhalf[B]];
			B22 = Map[secondhalf, secondhalf[B]];
			
			term[[1]] = prod[A12 - A22, B21 + B22];
			term[[2]] = prod[A11 + A22, B11 + B22];
			term[[3]] = prod[A11 - A21, B11 + B12];
			term[[4]] = prod[A11 + A12, B22];
			term[[5]] = prod[A11,       B12 - B22];
			term[[6]] = prod[A22,       B21 - B11];
			term[[7]] = prod[A21 + A22, B11];
	
		C1 = Join[term[[1]]+term[[2]]-term[[4]]+term[[6]],
				        term[[6]]+term[[7]]];
		C2 = Join[term[[4]]+term[[5]],
		          term[[2]]-term[[3]]+term[[5]]-term[[7]]];
  
  		Table[Join[C1[[i]],C2[[i]]],{i,Length[A]}]  		
  		]]