Geometry and the complexity of matrix multiplicati

arXiv:cs/0703059v1[cs.CC]12Mar2007GEOMETRYANDTHECOMPLEXITYOFMATRIXMULTIPLICATIONJ.M.LANDSBERGAbstract.Wesurveyresultsinalgebraiccomplexitytheory,focusingonmatrixmultiplication.Ourgoalsare(i.)toshowhowopenquestionsinalgebraiccomplexitytheoryarenaturallyposedasquestionsingeometryandrepresentationtheory,(ii.)tomotivateresearcherstoworkonthesequestions,and(iii.)topointoutrelationswithmoregeneralproblemsingeometry.ThekeygeometricobjectsforourstudyarethesecantvarietiesofSegrevarieties.Weexplainhowthesevarietiesarealsousefulforalgebraicstatistics,thestudyofphylogeneticinvariants,andquantumcomputing.1.Introduction1.1.Strassen’salgorithm.LetAandBbe2×2matricesA=a11a12a21a22,B=b11b12b21b22.RecalltheusualalgorithmtocalculatethematrixproductC=AB:(1)c11=a11b11+a12b21,c12=a11b12+a12b22,c21=a21b11+a22b21,c22=a21b12+a22b22.Thisalgorithmuses8multiplicationsandforn×nmatricesitusesn3.Question:Istherea“better”algorithmformultiplyingmatrices?By“better”onecouldmeananalgorithmthatusesfewerarithmeticoperations(+,−,∗),orsimplyfewermultiplications.Thenumberofmultiplicationsneededgovernsthetotalnumberofarithmeticoperationsinsuchawaythatasymptoticresultsdependprimarilyonthenumberofmultiplicationsused.(SeeDefinition1.2foraprecisestatement.)Inthisarticlewefocusexclusivelyonminimizingmultiplications.(Inactualimplementationsmemorycostisalsoanimportantfactor.)In1969Strassen[54]madethefollowingdiscovery.SetI=(a11+a22)(b11+b22),II=(a21+a22)b11,III=a11(b12−b22)IV=a22(−b11+b21)V=(a11+a12)b22VI=(−a11+a21)(b11+b12),VII=(a12−a22)(b21+b22),Keywordsandphrases.MSC68Q17,borderrank,complexityofmatrixmultiplication,secantvarieties.12J.M.LANDSBERGNowcheckforyourselfthatifC=AB,thenc11=I+IV−V+VII,c21=II+IV,c12=III+V,c22=I+III−II+VI.Thustheaboveisanalgorithmformultiplyingtwobytwomatricesperformingonlysevenmultiplications.Remark1.1.Strassenwasattemptingtoprove,byprocessofelimination,thatsuchanalgorithmdidnotexistwhenhearrivedatit.Wewillseein§3whytheresultcouldhavebeenanticipatedusingelementaryalgebraicgeometry.1.2.Thecomplexityofmatrixmultiplication.InStrassen’salgorithmtheentriesofthematricesneednotbescalars-theycouldbeelementsofanalgebra.LetA,Bbe4×4matrices,andwriteA=a11a12a21a22,B=b11b12b21b22.whereaij,bijare2×2matrices.WemayapplyStrassen’salgorithmtogettheblocksofC=ABintermsoftheblocksofA,Bperforming7multiplicationsof2×2matrices.SincewecanapplyStrassen’salgorithmtoeachblock,wecanmultiply4×4matricesusing72=49multiplicationsinsteadoftheusual43=64.Infact,ifA,Bare2k×2kmatrices,wemaymultiplythemusing7kmultiplicationsratherthantheusual(2k)3.Evenifnisnotapoweroftwo,wecanstillsavemultiplicationsasymptoticallybyenlargingthedimensionsofourmatrices,placingzerosinthenewentries,toobtainmatriceswhosesizeisapoweroftwo.Asymptoticallywecanmultiplyn×nmatricesusingO(nlog2(7))≃O(n2.81)operations,asletn=2kandwrite7k=(2k)asok(log27)=ak(log22)andweobtaina=log27.Definition1.2.Theexponentøofmatrixmultiplicationisø=inf{h∈R|Matn×nmaybemultipliedusingO(nh)scalarmultiplications}.Strassen’salgorithmshowsø≤log2(7)2.81.Remark1.3.Ifonereplacesthephrase“scalarmultiplications”withthephrase“arithmeticoperations”inthedefinition,øisunchanged,see[14],Proposition15.1.MatrixmultiplicationofsquarematricesisabilinearmapthatwedenoteMn,n,n:Cn2×Cn2→Cn2.(Inthisarticlewerestrictourattentiontothecomplexnumbers,soe.g.,allvectorspacesarefinitedimensionalvectorspacesoverC.)Whendiscussingaminimalnumberofarithmeticoperations(ormultiplications)forexecutingabilinearmap,itisusuallywithinthecontextofaclassofalgorithms.Anaturalclassofalgorithmsforexecutingabilinearmapisasfollows:letA,B,Cbevectorspaces,letA∗:={f:A→C|fislinear}denotethedualvectorspace(andsimilarlyforB),andletT:A×B→Cbeabilinearmap.Chooseαi∈A∗,βi∈B∗,ci∈CsuchthatT(v,w)=Pri=1αi(v)βi(w)ci.TheminimalnumberroverallsuchpresentationsofTiscalledtherankofTanddenotedR(T).Arelatednotion,morenaturaltogeometryanddefinedin§2,isthatofborderrank,denotedR(T).AnotherconceptthatcomesintoplaywhendiscussingthespaceofallbilinearmapsA×B→C,isthetypicalrank,whichistherankofagenericbilinearmapA×B→C.Strassen’salgorithmshowsthattherankofthemultiplicationoftwobytwomatricesisatmostseven,andWinograd[57]provedthatinfactitequalsseven.GEOMETRYANDTHECOMPLEXITYOFMATRIXMULTIPLICATION31.3.Overview.Toexaminethecomplexityofmatrixmultiplicationmoregeometrically,wefirst,in§2,rephraseitusingtensors.Next,in§3,weintroducealgebraicvarietieswhichstratifythespaceoftensors,thesecantvarietiesofSegrevarieties.(Theabove-mentionedborderrankofatensordescribesitslocationwithrespecttothisstratification.)Thisisdoneintwosteps,firstintroducingsecantvarietiestoanyalgebraicvarietyin§3.1;thenspecializingtoSegrevarietiesin§3.2.WealsorephrasethemainopenproblemsinthecomplexityofmatrixmultiplicationintermsofsecantvarietiesofSegrevarieties.In§3.3wesummarizetheknownresults.Beforediscussingthoseresultsindetail,wetaketwodetours.Inthefirst,wedescribetwoproblemsfromalgebraicgeometrywheresecantvarietiesarise:thepolynomialWaringproblemandHartshorne’sconjectureonlinearnormality.Thesearedescribedinin§4.Inthesecond,wedescrib