ALINEARHOMOTOPYMETHODFORCOMPUTINGGENERALIZEDTENSOREIGENPAIRSByLipingChenADISSERTATIONSubmittedtoMichiganStateUniversityinpartialentoftherequirementsforthedegreeofAppliedMathematics|DoctorofPhilosophy2016ABSTRACTALINEARHOMOTOPYMETHODFORCOMPUTINGGENERALIZEDTENSOREIGENPAIRSByLipingChenAtensorisamultidimensionalarray.Ingeneral,anmth-orderandn-dimensionaltensorcanbeindexedasA=(Ai1i2:::im),whereAi1i2:::im2Cfor1i1;i2;:::;imn.LetAbeanmthordern-dimensionaltensorandBbeanm0thordern-dimensionaltensor.Ascalar2Candavectorx2Cnnf0giscalledageneralizedB-eigenpairofAifAxm1=Bxm01withBxm0=1whenm6=m0.tchoicesofByieldtversionsofthetensoreigenvalueproblem.Asonecansee,computingtensoreigenpairsamountstosolvingapolynomialsystem.Toallsolutionsofapolynomialsystem,thehomotopycontinuationmethodsareveryusefulintermsofcomputationalcostandstoragespace.Bytakingadvantageofthesolu-tionstructureofthetensoreigenproblem,twoeasy-to-implementlinearhomotopymethodswhichfollowtheoptimalnumberofpathswillbeproposedtosolvethegeneralizedtensoreigenproblemwhenm6=m0.Withproperimplementation,thesemethodscanallequiv-alenceclassesofisolatedeigenpairs.AMATLABsoftwarepackageTenEig2.0hasbeendevelopedtoimplementthesemethods.Numericalresultsareprovidedtoshowitsciencyandeness.TomyfamilyiiiACKNOWLEDGMENTSIwouldliketogratefullyandsincerelythankmyadvisorProfessorTien-YienLiforhisconstantguidance,support,understandingandencouragementsduringmyyearsatMichiganStateUniversity.Especiallyatthistime,althoughhewassosick(hehadabladdercancerandjustasurgeryaboutthreeweeksbeforemythesisdefense)andcouldnotstandupthesedays,hestillsupportedmetodefenseinthissemestersothatIcanheadtoworkontime.IwouldliketothankDr.ChichiaChiu,Dr.PatriciaLamm,Dr.GabrielNagyandDr.MoxunTang,forservingasmembersofmythesiscommittee.IamsoindebtedtoDr.ChichiaChiuforsupportingmeasaresearchassistantduringmyyearPhDstudy.IamgratefultoDr.PatriciaLamm,Dr.SheldonNewhouseandDr.GabrielNagyforgivingmetheopportunitytoworkonWeBWorKandprovidinglettersofreference.IamalsogratefultoDr.PeiruWuandDr.ZhengfangZhoufortheirhelpintheseyears.SpecialthankstoProfessorLixingHanforintroducingthetensoreigenproblemstousandgivingmealotofadviceonthissubject.Ialsowanttotakethisopportunitytothankmyfriends,myacademicbrothersandsisters.SpecialthankstoDr.JiuDingandDr.XiaoshenWangforrecommendingmetostudyaboard.Finally,andmostimportantly,Iwouldliketothankmyfamilyfortheircontinuousandstrongsupport.ivTABLEOFCONTENTSLISTOFTABLES....................................viLISTOFFIGURES...................................viiChapter1Introduction...............................11.1Tensor.......................................11.2Tensoreigenvalueandeigenvectorproblems..................21.3Generalizedtensoreigenvalueandeigenvectorproblems............61.4Problemformulation...............................8Chapter2Constructalinearhomotopytocomputegeneralizedtensoreigenpairs.................................112.1Preliminaries...................................112.2Constructalinearhomotopytocomputegeneralizedtensoreigenpairswhenm>m0......................................162.3Constructalinearhomotopytocomputegeneralizedtensoreigenpairswhenm<m0......................................33Chapter3Implementationofthelinearhomotopymethods........513.1Alinearhomotopyalgorithmtocomputetensoreigenpairs..........513.2Algorithmstocomputesolutionsofthestartingsysteminthelinearhomotopyalgorithm.....................................533.3Algorithmtofollowsolutionpathsofthelinearhomotopy..........543.4Evaluatingpolynomialsandderivatives.....................59Chapter4Numericalresults............................694.1Theofthenewevaluationmethod..................694.2Computingcomplextensoreigenpairs......................704.3Computingrealtensoreigenpairs........................73BIBLIOGRAPHY....................................75vLISTOFTABLESTable3.1:TableT.....................................61Table4.1:Comparisonofon-lineandapproacheswithTable-Tmethod....70Table4.2:ComparisonofAlgorithm3.1.1withteneigform>m0.........71Table4.3:ComparisonofAlgorithm3.1.1withteneigform<m0.........71Table4.4:ComparisonofAlgorithm3.1.1withteneigforcomputingE-eigenpairs72Table4.5:Z-eigenvaluesofthetensorinExample4.3.1(*denotesthattheCPUtimeusedbyAlgorithm3.6([9])whenitndsthethreelargestZ-eigenvalues)74viLISTOFFIGURESFigure1.1:Athird-order,two-dimensionaltensor.....................1Figure2.1:DiagramofQwhenm=3,m0=4andn=3................38Figure3.1:Anexampleoftheevaluationgraph......................66Figure3.2:Anexampleoftheevaluationfunction................67viiChapter1Introduction1.1TensorThetensorconsideredhereisamultidimensionalarray,insteadofthetensorinphysicsandengineering[17]ortensorinmathematics[28].Ar,n-dimensionaltensorisann-vector.Asecond-order,n-dimensionaltensorisannnmatrix.Ingeneral,anm-thordern-dimensionaltensorcanbeindexedasA=(Ai1i2:::im);whereAi1i2:::im2Cfor1i1;i2;:::;imn.Wedenotethesetofallmth-order,n-dimensionaltensorsonCbyC[m;n].SeeFigure1.1forathird-ordertwo-dimensionaltensor.a111a112a121a122a211a212a221a222Figure1.1:Athird-order,two-dimensionaltensorAtensorAissymmetricifitsentriesareinvariantunderpermutation.Forexample,a1third-ordertensorA2C[3;n]issymmetricifAijk=Aikj=Ajik=Ajki=Akij=Akjiforalli;j;k=1;:::;n.AtensorA2C[m;n]iscalledadiagonaltensorifAii:::i6=0andallotherentriesarezero.Inparticular,adiagonaltensorwithonesalongthediagonaliscalledanidentitytensor.1.2TensoreigenvalueandeigenvectorproblemsLetA2C[m;n],x:=(x1;:::;xn)T2Cn,andx[m]:=(xm1;xm2;:::;xmn)T.ThetensorAinducesanmth-degreehomogeneouspolynomialgivenbyAxm:=nXi1;;im=1Ai1imxi1ximinx1;:::;xn.Bythetensorproduct[23],Axm1denotesann-vectorwhosejthentryis(Axm1)j=nXi2;;im=1Aj;i2imxi2xim:ThefollowingnotionofeigenpairsforcomplextensorswasintroducedbyQi[21]in2005.DEFINITION1.2.1.SupposeA2C[m;n],wherem2andn1.Wecallanumber2CaneigenvalueofAifitandanonzerovectorx2Cnaresolutionsofthefollowinghomogeneouspolynomialequation:Axm1=[m1];(1.1)2andcalledthesolutionxaneigenvectorofAassociatedwiththeeigenvalue.Atthesametime,Lim[14]proposedatheoryofeigenvalues,eigenvectors,singularvalues,andsingularvectorsfortensorsfromavariationalapproach.Sincethen,tensoreigenvalueshavefoundapplicationsinautomaticcontrol,tensorimaging,imageauthenticityvspectralhypergraphtheory,andquantumentanglement,etc.,see,forexample,[3,7,10,18,22,24,25,26].Inthefollowinganapplicationofthetensoreigenvalueinautomaticcontrolisdescribed[18].Consideranautonomousnonlineardynamicalsystem_x=g(x);wherex(t)2DˆRnisthesystemstatevectorandg:D!Rniscontinuous.ItiswellknownthatLyapunovsmethodcanbeusedtodeterminewhetherthissystemisasymptoticallystable.Moresp,ifamultivariatepositivepolynomialf(x)canbefoundsuchthatrf(x)Tg(x)<0;8x2Rn;x6=0thenthesystem_x=g(x)isasymptoticallystable.Herewecallf(x)positiveteiff(x)>0;8x2Rn;x6=0:(1.2)Toapropermultivariatepositivepolynomial,letusconsiderthepositive3nitenessofaneven-degreehomogeneouspolynomialgivenbyf(x)=nXi1;:::;im=1ai1:::imxi1xim;(1.3)wheremisevenandai1:::im'saretheentriesofasymmetrictensorA2R[m;n].LetAxm:=f(x):By(1.2),thepositiveoff(x)becomesAxm>0;8x2Rn;x6=0:(1.4)ItisequivalenttothepositivenessofminfAxmkxkmm=1g;(1.5)wherekxkmm=xm1++xmn.TousethemethodofLagrangemultiplier,letL(x):=Axm(kxkmm1):ThenthecriticalpointmustsatisfyrxL(x)=0;rL(x)=0:(1.6)4WhenAissymmetric,itwasprovedin[12]rx(Axm)=mAxm1:Then(1.6)impliesmAxm1[m1]=0;kxkmm1=0;or,Axm1[m1]=0;(1.7)kxkmm=1;whichistheeigenvalueproblemin(1.1)withnormalizationconditionkxkmm=1.Multiplyingbothsidesof(1.7)byxTfromtheleftyieldsxTAxm1Tx[m1]=0:Clearly,xTAxm1=AxmandxTx[m1]=kxkmm.Itfollowsthat=Axm:Hence(1.5)canbereplacedbyminfkxkmm=1g:5Consequentlyf(x)in(1.3)ispositiveniteifthesmallestrealeigenvalueofthecorre-spondingtensorAispositive.1.3Generalizedtensoreigenvalueandeigenvectorprob-lemsVariousofeigenvaluesfortensorshavebeenproposedintheliterature,includingE-eigenvaluesandQi-eigenvaluesinthecomplexandZ-eigenvalues,H-eigenvalues,andD-eigenvaluesinthereal[14,21,24].In[6],Chang,Pearson,andZhangintroducedanotionofgeneralizedeigenvaluesfortensorsthatsseveraltypesofeigenvalues.Re-centlythishasbeenfurthergeneralizedbyCui,Dai,andNie[9].Inthissection,generalizedtensoreigenvalueproblemswillbeintroduced.LetA2C[m;n]andx:=(x1;:::;xn)T2Cn.For1km,letA(k)xm1beann-vectorwhosejthentryis(A(k)xm1)j=nXi1;;ik1;ik+1;;im=1Ai1ik1jik+1imxi1xik1xik+1xim:Whenk=1,A(1)xm1istheAxm1intheprevioussection.Thenotionofmode-kgeneralizedeigenpairsforcomplextensorswasbyChen,HanandZhou[8]asfollows.DEFINITION1.3.1.SupposeA2C[m;n]andB2C[m0;n],wherem2;m02;n1.AssumeBxm0asafunctionofxisnotidenticallyzero.For1km,(x)2C(Cnnf0g)isamode-kB-eigenpairofAif6whenm=m0,A(k)xm1=Bxm1;(1.8)whenm6=m0,A(k)xm1=Bxm01;Bxm0=1;(1.9)ForsuitableA,m0andB,manynttypesoftensoreigenpairsintheliter-aturewerecontainedin(1.8)or(1.9).Forinstance,ForA2R[m;n],anE-eigenpair[14,21]isasapair(x)2CCnnf0gsuchthatAxm1=xTx=1:(1.10)Thisisamode-1B-eigenpairwithm0=2andBbeingthennidentitymatrix.ArealE-eigenpairiscalledaZ-eigenpair[14,21].ForA2R[m;n],letD2Rnnbeasymmetricpositivematrix,(x)2RRnnf0giscalledaD-eigenpair[24]ifAxm1=x;xTDx=1:Thisisarealmode-1B-eigenpairwithm0=2andB=D.ForA2R[m;n],aQi-eigenpair[21]isasapair(x)2CCnnf0gsuchthatAxm1=[m1];(1.11)wherex[m1]:=(xm11;xm12;:::;xm1n)T.Thisisamode-1B-eigenpairwithm0=m7andBbeingtheidentitytensor.ArealQi-eigenpairiscalledanH-eigenpair[21].ForA2R[m;n],aCPZ-eigenpair[6]isasapair(x)2CCnnf0gsuchthatAxm1=Bxm1:Thisisamode-1B-eigenpairwithm=m0.ForsymmetrictensorsA2R[m;n]andB2R[m0;n],aCDN-eigenpair[9]isasapair(x)2CCnnf0gsuchthatAxm1=Bxm01;Bxm0=1:Thisisamode-1B-eigenpairwithAandBbeingsymmetric.1.4ProblemformulationLetA2C[m;n]andB2C[m0;n].Asonecanseefrom1.3.1,computingmode-kB-eigenpairsofAamountstosolvingA(k)xm1=Bxm01followedbynormalizingxforBxm0=1whenm6=m0.AsdiscussedinRemark2.1in[8],thesolutionsetofA(k)xm1=Bxm01consistsoftequivalenceclasses.If(x)isasolution,wedenoteitscorrespondingequivalenceclassby[(x)]:=f(0;x0)j0=tmm0x0=tx;t2Cnf0gg:Whenm6=m0,imposingthenormalizationconditionBxm0=1,theproblem(1.9)hasm0eigenpairsfromeachequivalenceclass.Accordingtothisobservation,theproblemofsolving8theeigenvalueproblem(1.9)canbeconvertedtosolvingthefollowingpolynomialsystemP(x)=0B@A(k)xm1Bxm01Tx+01CA=0;(1.12)where2Cnand02Carerandomlychosen.Whenm6=m0,foreachsolutionof(1.12)obtainedwenormalizeitforaneigenpair(;x)satisfying(1.9),thenm0equivalenteigenpairs(0;x0)bysetting0=tmm0andx0=txwithtbeingarootoftm0=1.Notethat(1.12)isapolynomialsystem.Toallsolutionsofapolynomialsystem,thehomotopycontinuationmethodsareverytintermsofcomputationalcostandstoragespace(see,forexample,[13],[29]).In[8],Chen,HanandZhouproposedtwohomotopycontinuationmethods(Algorithms3.1and3.2in[8])forcomputingalleigenpairsofageneralrealorcomplextensor.Sp,whileAlgorithm3.1isalinearhomotopymethodwhichhandlesthecasem=m0;Algorithm3.2,whichhandlesthecasem6=m0,isbasedonapolyhedralhomotopymethod.Themosttimeconsumingpartofhomotopycontinuationmethodsisthepathfollowingstep.Thepolyhedralhomotopymethodshavetheadvantagethatincertainsituationstheycanfollowmuchfewerpathsthancontinuationmethodsusingotherhomotopies,suchasthetotaldegreehomotopy(see,forexample,[13]).Asindicatedin[1],however,thepolyhedralhomotopymethodsinvolveahighlycomplicatedcombinatorialprocessforthemaximalrootcountforagivensparsestructureandsettingupacompatiblehomotopy.Thismakestheimplementationofapolyhedralhomotopymethodverysophisticated.Inthisarticle,alinearhomotopymethodwillbeproposedtosolve(1.12)whenm6=m0.Itisshownthatthemethodallisolatedeigenpairsofproblem(1.9).Thismethodis9easytoimplement.Moreover,themethodfollowsanoptimalnumberofpathsbyfullyusingthesolutionstructureofproblem(1.9),makingitantandcompetitivehomotopymethodforcomputingeigenpairsofgeneraltensors.Thisdissertationisorganizedasfollows.Wedescribethelinearhomotopymethods,showingthesemethodscanallisolatedeigenpairsinChapter2.AdetailedalgorithmwithsomeimplementationtipswillbegiveninChapter3.Finally,wegivesomenumericalresultsinChapter4.10Chapter2ConstructalinearhomotopytocomputegeneralizedtensoreigenpairsLetA2C[m;n]andB2C[m0;n].AsdiscussedinSection1.4,theproblemofcomputingmode-kB-eigenpairsin(1.9)isequivalenttosolving(1.12),andwhenm6=m0,wenormalizeittosatisfyBxm0=1.Inthischapter,wewillconstructtwolinearhomotopymethodstocomputeallisolatedzerosofthepolynomialsystem(1.12)form>m0andm<m0respectively,andtherebycomputealltheeigenpairs.2.1PreliminariesThefollowingtwolemmasaboutcot-parameterhomotopyplayanessentialroleinourconstruction.LEMMA2.1.1(Theorem7.1.1in[29]).LetF(z;c)beasystemofpolynomialsinnvariablesandlparameters,F(z;c):CnCl!Cn;thatis,F(z;c)=(f1(z;c);:::;fn(z;c))Tandeachfi(z;c)ispolynomialinbothzandc.11Furthermore,letN(c)denotethenumberofnonsingularsolutionsasafunctionofc:N(c):=#ˆz2CnF(z;c)=0;det@F@z(z;c)6=0˙:Then(1)N(c)isanditisthesame,sayNF,foralmostallc2Cl.(2)forallc2Cl,N(c)NF.HereisanexampletoillustrateLemma2.1.1.LetF(z1;q1;q2;q3):CC3!CbeasF(z1;q1;q2;q3):=q1z21+q2z1+q3;whichisapolynomialbothinthevariablez1andintheparametersq1;q2;q3.BytheofN(q),wehaveN(q)=#ˆz12CF:=q1z21+q2z1+q3=0;@F@z1:=2q1z1+q26=0˙:Therefore,q1z21+q2z1+q3=0alwayshastwosolutionsz1=q2+qq224q1q32q1orq2qq224q1q32q1aslongasq16=0.Andthesesolutionswillsatisfy2q1z1+q26=0aslongasq224q1q36=0.DenoteQs:=f(q1;q2;q3)jq1=0orq224q1q3=0g:Thenforanyq:=(q1;q2;q3)2C3nQs,N(q)isequalto2.NotethatQshasmeasure0in12C3.Inthissense,wesayforalmostallq2C3,N(q)isequaltothesamenumber2,whichisdenotedbyNFinLemma2.1.1.Moreover,foranyq:=(q1;q2;q3)2Qs,wehavethefollowingthreecases:(i).Ifq1=0butq224q1q3=q226=0,thenF=q2z1+q3islinear.SoN(q)=1.(ii).Ifq16=0butq224q1q3=0,thenF=0hasnononsingularsolutions.SoN(q)=0.(iii).Ifq1=0andq224q1q3=q22=0,thenF=q3.Whenq36=0,F=0hasnosolutions.Whenq3=0,F=0hasnononsingularsolutions.SoN(q)=0inthiscase.Fromtheabovediscussion,weconcludethatN(q)isequaltoNFforalmostallq2C3andN(q)NFforallq2C3.LEMMA2.1.2(Theorem8.3.1in[29]).LetF(z;c),N(c)andNFbeasinLemma2.1.1.SupposeF(z;c)islinearinc.Letf(z)=F(z;c1)forsomegivenc12Cl.Ifg(z)=F(z;c0)forsomec02ClhasNFnonsingularzeros,thenthelinearhomotopyh(z;t):=(1t)g(z)+tf(z)=0hasNFnonsingularsolutionpathsont2[0;1)whoseendpointsast!1includealloftheisolatedrootsoff(z)=0inCn.Hereisarandomlychosennonzerocomplexnumberofabsolutevalue1.Lemma2.1.1andLemma2.1.2suggestthefollowingstepstoconstructourlinearhomo-topyforallisolatedsolutionsofthesystemP(x)=0in(1.12)whenm6=m0:Step1.ConstructapolynomialsystemF(x;c),wherecdenotesthesetofparam-eters,makingF(x;c)linearincandF(x;c1)=P(x)forcertainparametersetc1.13Step2.ComputeNFasinLemma2.1.1forF(x;c);Step3.Findaparametersetc0suchthatG(x):=F(x;c0)hasNFnonsingularzeros.ThenbyLemma2.1.2,alltheisolatedzerosofP(x)canbefoundbytracingthesolutionpathsofthelinearhomotopyH(x;t):=(1t)G(x)+tP(x)fromt=0tot=1.Weshallfollowtheabovethreestepstoconstructourlinearhomotopyforthecaseofm>m0andm<m0separately.LetP(x):=(p1(x);:::;pn(x))Tbeapolynomialsystemwithx:=(x1;:::;xn)T.For:=(1;:::;n)2(Zn0)T,writex:=x11xnnandjj:=1++n.ThenP(x)canbewrittenasP(x):=0BBBBBBB@p1(x):=P2S1c1x...pn(x):=P2Sncx1CCCCCCCA;(2.1)whereS1;:::;Snaresubsetsof(Zn0)Tandc2C:=Cnf0garethecotsofthecorrespondingmonomials.Hereforeachi=1;:::;n,Siiscalledthesupportofpi(x)anditsconvexhullRi:=conv(Si)inRniscalledtheNewtonpolytopeofpi(x).Then-tuple(S1;:::;Sn)iscalledthesupportofP(x).Fornonnegativevariables1;:::;n,let141R1++nRnbetheMinkowskisumof1R1;:::;nRn,i.e.,1R1++nRn:=f1r1++nrnjri2Ri;i=1;:::;ng:Then-dimensionalvolumeof1R1++nRn,denotedbyVoln(1R1++nRn),isahomogeneouspolynomialofdegreenin1;:::;n(See,forexample,Proposition4.9of[4]foraproof).Thecotofthemonomial12:::ninVoln(1R1++nRn)iscalledthemixedvolumeofR1;:::;Rn,denotedbyMVn(R1;:::;Rn),orthemixedvolumeofthesupportsS1;:::;Sn,denotedbyMVn(S1;:::;Sn).ItisalsocalledthemixedvolumeofP(x)ifnoambiguityexists.Thefollowingtheoremrelatesthenumberofsolutionsofapolynomialsystemtoitsmixedvolume.LEMMA2.1.3.(Bernstein'sTheorem)[2]Thenumberofisolatedzerosin(C)n,countingmultiplicities,ofapolynomialsystemP(x)=(p1(x);:::;pn(x))TwithsupportsS1;:::;SnisboundedbythemixedvolumeMVn(S1;:::;Sn).Moreover,forgenericchoicesofthecoinpi,thenumberofisolatedzerosisexactlyMVn(S1;:::;Sn).AnapparentlimitationofLemma2.1.3isthatitonlycountstheisolatedzerosofapolynomialsystemin(C)nratherthanCn.Todealwiththisissue,LiandWanggavethefollowingtheorem.LEMMA2.1.4.[16]ThenumberofisolatedzerosinCn,countingmultiplicities,ofapolynomialsystemP(x)=(p1(x);:::;pn(x))TwithsupportsS1;:::;SnisboundedbythemixedvolumeMVn(S1[f0g;:::;Sn[f0g).ThefollowinglemmawasgivenasExercise7onpage338of[4].15LEMMA2.1.5.ConsiderapolynomialsystemP(x)=(p1(x);:::;pn(x))TwithsupportsS1=S2==Sn=S.ThenMVn(S;:::;S)=n!Voln(conv(S)):Recallthatann-simplexistobetheconvexhullofn+1pointsz1;:::;zn+1suchthatz2z1;:::;zn+1z1arelinearlyindependentin(Rn)T.ItcanbeshownthatforthissimplexVoln(conv(z1;z2;:::;zn+1))=1n!det0BBBBB@z2z1...zn+1z11CCCCCA:(2.2)2.2Constructalinearhomotopytocomputegeneral-izedtensoreigenpairswhenm>m0LetD2C[m;n],E2C[m0;n]andL2C[2;n].Letvdiag(L):=(L11;:::;Lnn)T.Writec:=fD;E;Lg:(2.3)ConsiderF1(x;c)=0B@Dxm1Exm01Lx[mm0]+vdiag(L)Tx+01CA:(2.4)ItisclearthatF1islinearinc.Takingc1:=fA;B;0g;(2.5)16weobtainF1(x;c1)=P(x),whichisourtargetsystem(1.12).LetNF1beinLemma2.1.1forF1(x;c).TocomputeNF1,weprovethefollowingtheorem.THEOREM2.2.1.LetF1(x;c)beasin(2.4)andcasin(2.3)bethesetofparameters.Thenthenumberofisolatedzeros,countingmultiplicities,ofF1(x;c)isboundedby(m1)n(m01)nmm0:Whencisgeneric,F1(x;c)hasexactly((m1)n(m01)n)=(mm0)isolatedzeros.Proof:FortherandomhyperplaneTx+0=0,i.e.,1x1++nxn+0=0,in(2.4),withoutloss,wesupposen6=0.Thenxn=a1x1++an1xn1+b;(2.6)whereai=infori=1;:::;n1andb=0n.Noticethatthenumberofsolutionsof(2.4)inCn+1isthesameasthenumberofsolutionsinCnoftheresultingsystemT(x1;:::;xn1)bysubstituting(2.6)intothenequationsof(2.4).DenotethecorrespondingsupportsofTbyS1;:::;Sn.WeclaimthatMVn(S1[f0g;:::;Sn[f0g)=(m1)n(m01)nmm0:(2.7)Ifthisisproved,letNdenotethenumberofisolatedzerosof(2.4)inCn.Then(2.7)impliesN(m1)n(m01)nmm0:17Whentheparametersetc=fD;E;Lgisgeneric,theequalityintheaboveholdsbyusingLemma2.1.3andLemma2.1.4.Toprove(2.7),letc:=fD;E;Lgbegeneric.Similarto(2.4)thecorrespondingpolyno-mialsystembeingsolvedisT(x)=0B@Dxm1Exm01Lx[mm0]+vdiag(L)Tx+01CA=0:(2.8)Substituting(2.6)intothenequationsof(2.8)yieldsanewsystemT(x1;:::;xn1).LetS1;:::;SnbethecorrespondingsupportsofT.SinceD,EandLaregeneric,withoutlossofgeneralityonecanassumethatallmonomialsxmm01;:::;xmm0nwithfx11x22:::xnni2Z0;1+2++n=m1gandf11x22:::xnni2Z0;1+2++n=m01gwillappearineachofthenequationsin(2.8).Itfollowsthatallmonomialsfx11x22:::xn1n1i2Z0;1+2++n1m1gandf11x22:::xn1n1i2Z0;1+2++n1m01g18willappearineachequationofT.Consequently,S1;:::;SnareallequaltoS:=f(0;)2(Zn10)T;jjm1g[f(1;)2(Zn10)T;jjm01g:LetQbetheconvexhullofS.Denotethei-thunitvectorin(Rn)Tbyeifori=1;:::;n.ThenverticesofQaregivenbyzi=8>>>>>>>>><>>>>>>>>>:0;i=0(m1)en+1i;1in1e1;i=ne1+(m01)e2n+1i;n+1i2n1:(2.9)Fromwhich,zn+i=e1+m01m1zi;0in1:Thisindicatesthatzn;:::;z2n1arescalingofz0;:::;zn1respectivelybyafactor(m01)=(m1)followedbyashift.Actually,eachzn+iisobtainedbymovingzialongthelineli(t):=(1t)zi+tzn+i;0in1(2.10)astchangingfrom0to1.Simplecomputationyieldsli(t)=8><>:te1;i=0te1+(m1+(m0m)t)en+1i;1in1:(2.11)19WenowclaimthatQ=[t2[0;1]conv(l0(t);:::;ln1(t)):(2.12)Toprovethis,letq2Q,thenthereexisti0(i=0;1;:::;2n1)suchthatP2n1i=0i=1andq=2n1Xi=0izi:(2.13)Substituting(2.9)into(2.13)yieldsq=2n1Xi=nie1+n1Xi=1[i(m1)+n+i(m01)]en+1i:(2.14)Toshowq2St2[0;1]conv(l0(t);:::;ln1(t)),weneedtot2[0;1]andi0(i=0;:::;n1)suchthatPn1i=0i=1andq=n1Xi=0ili(t):(2.15)Substituting(2.11)into(2.15),wehaveq=0te1+n1Xi=1i[te1+(m1+(m0m)t)en+1i]=t n1Xi=0i!e1+n1Xi=1i[m1+(m0m)t]en+1i=te1+n1Xi=1i[m1+(m0m)t]en+1i:(2.16)20Comparing(2.14)with(2.16),ifwechooset=2n1Xj=nj;i=i(m1)+n+i(m01)m1+(m0m)t;i=1;:::;n1;0=1n1Xi=1i;andrewritethedenominatorofi(fori=1;;n1)asm1+(m0m)2n1Xj=nj=m1+(m01+1m)2n1Xj=nj=(m1)(12n1Xj=nj)+(m01)2n1Xj=nj=(m1)n1Xj=0j+(m01)2n1Xj=nj;thenwehavet2[0;1],i0fori=0;;n1,andPn1i=0i=1.Moreover,(2.15)holds.Thisshowsq2St2[0;1]conv(l0(t);:::;ln1(t)).Therefore,Qˆ[t2[0;1]conv(l0(t);:::;ln1(t)):Ontheotherhand,letq2St2[0;1]conv(l0(t);:::;ln1(t)).Thenthereexistt2[0;1],i0(i=0;:::;n1)suchthatPn1i=0i=1and(2.15)holds.By(2.10),q=n1Xi=0i((1t)zi+tzn+i)=n1Xi=0i(1t)zi+n1Xi=0itzn+i:21Leti=8><>:i(1t);i=0;:::;n1;int;i=n;:::;2n1:Thenq=2n1Xi=0izi;wherei0foreachiandP2n1i=0i=1.Therefore,q2Q.WeconcludethatSt2[0;1]conv(l0(t);:::;ln1(t))ˆQ.TocomputethevolumeofQ,letq:=(q1;:::;qn)2Q,by(2.12)thereexistt2[0;1]andi0(i=0;:::;n1)suchthatPn1i=0i=1andq=n1Xi=0ili(t):By(2.11)andPn1i=0i=1,q=l0(t)(1n1Xi=1i)+n1Xi=1ili(t)=l0(t)+n1Xi=1i(li(t)l0(t))=te1+n1Xi=1i(m1+(m0m)t)en+1iwitht2[0;1],i0andPn1i=1i1.Let@(q1;:::;qn)=@(t;1;:::;n1)betheJacobianmatrixofq1;:::;qnwithrespecttot;1;:::;n1.Thendet@(q1;:::;qn)@(t;1;:::;n1)=det0BBBBBBBBB@e1+Pn1i=1i(m0m)en+1i(m1+(m0m)t)en...(m1+(m0m)t)e21CCCCCCCCCA=(m1+(m0m)t)n1:22Bythechangeofvariables(See,forexample,[27]),thevolumeofQis:Voln(Q)=Zq2Qdq=1Z0ZPn1i=1i1i0det@(q1;:::;qn)@(t;1;:::;n1)1:::n1dt=1Z0(m1+(m0m)t)n1dtZPn1i=1i1i01:::n1=Z10(m1+(m0m)t)n1(n1)!dt(2.17)=(m1)n(m01)n(mm0)n!;where(2.17)holdsbecausetheregionf(1;:::;n1)Pn1i=1i1;i0gisastandard(n1)-simplexwithvolume1=(n1)!(See,forexample,Exercise2and3onpage307of[4])).Therefore,byLemma2.1.5,MVn(S1;:::;Sn)=n!Voln(Q)=(m1)n(m01)nmm0:Notingthatfori=1;:::;n,Si[f0gisasubsetofSi.HenceMVn(S1[f0g;:::;Sn[f0g)MVn(S1;:::;Sn);andthereforeMVn(S1[f0g;:::;Sn[f0g)(m1)n(m01)nmm0:(2.18)Ontheotherhand,considertheidentitytensorsD2C[m;n]andE2C[m0;n]suchthat23Dii:::i=1,Eii:::i=1andallotherentriesarezero.LetLbennzeromatrix.Then(2.4)becomes0BBBBBBBBB@xm11m011...xm1nm01nTx+01CCCCCCCCCA=0BBBBBBBBB@xm011(xmm01)...xm01n(xmm0n)Tx+01CCCCCCCCCA=0;(2.19)where=(1;;n)2Cnandi'saregeneric.Clearly,x=0cannotbeasolutionsincegenerically06=0.Thusatleastoneofxmm01=0;:::;xmm0n=0(2.20)mustbevalid.Assumei(1in)equationsof(2.20)hold.Iftheiequationsof(2.20)hold,thenxmm0j=0;j=1;;i;xm01j=0;j=i+1;;n:Forj=i+1;;n,xjcanbe0withmultiplicitym01.Alsofromtheiequations,xmm02=xmm01;:::;xmm0i=xmm01:Soeachxj(j=2;:::;n)canbeexpressedbyx1inmm0ways.Correspondingly,x1canbedetermineduniquelyunderthechoicesofxi+1;:::;xnandthelastlinearequation,sois.Therefore,thereare(m01)ni(mm0)i1solutionsintotaliftheiequationsof(2.20)arevalid.Thisargumentholdsforanyiequationsof(2.20)arechosentobevalid.24Sothereare0B@ni1CA(m01)ni(mm0)i1solutionswheniequationsof(2.20)aretrue.Sinceimaybeanyoneoff1;;ng,thenumberofzerosof(2.20)intotalshouldbenXi=10B@ni1CA(m01)ni(mm0)i1=1mm0nXi=10B@ni1CA(m01)ni(mm0)i=1mm0[(m01+mm0)n(m01)n]=(m1)n(m01)nmm0:ByLemma2.1.4,MVn(S1[f0g;:::;Sn[f0g)(m1)n(m01)nmm0:Combiningtheaboveinequalitywith(2.18),wehaveMVn(S1[f0g;:::;Sn[f0g)=(m1)n(m01)nmm0:2LetNF1beinLemma2.1.1forF1(x;c)in(2.4).Inthefollowinglemma,wecomputeNF1.25LEMMA2.2.1.LetNF1beasinLemma2.1.1forF1(x;c)asin(2.4).ThenNF1=(m1)n(m01)nmm0:(2.21)Proof:ByLemma2.1.1,NF1istheupperboundofthenumberofthenonsingularzerosofF1(x;c)in(2.4).Sincenonsingularzerosareisolatedzeros,Theorem2.2.1impliesthatNF1(m1)n(m01)nmm0:Ontheotherhand,F1(x;c)in(2.4)has((m1)n(m01)n)=(mm0)nonsingularzeroswhencisgeneric.SobyLemma2.1.1,(m1)n(m01)nmm0NF1:2Nowitisttoaparametersetc0suchthatF1(x;c0)in(2.4)hasNF1nonsingularzeros.Letc0:=fI[m;n];I[m0;n];Gg;(2.22)whereI[m;n]isthem-thorderndimensionalidentitytensor,G2C[2;n]isadiagonalmatrixwithGii=i(i=1;:::;n)beingrandomlychosennonzerocomplexnumbers.LetG1(x):=F1(x;c0):26ThenG1(x)=0BBBBBBBBB@xm11m0111xmm01+1...xm1nm01nnxmm0n+nTx+01CCCCCCCCCA=0BBBBBBBBB@(xm0111)(xmm01)...(xm01nn)(xmm0n)Tx+01CCCCCCCCCA;(2.23)THEOREM2.2.2.LetG1(x)andNF1beasin(2.23)and(2.21)respectively.ThenG1(x)hasexactlyNF1,asgivenin(2.21),nonsingularzeros.Proof:Itcanbeassertedthatatleastoneofxmm01=0;...(2.24)xmm0n=0mustbetrue.Otherwisesystem(2.23)isequivalenttoanoverdeterminedsystemofn+1equationsinnunknowns,whichhasnosolutionsduetorandomness.Assumethati(127in)equationsof(2.24)aretrue.Iftheiequationsof(2.24)hold,thenxmm01=0;...xmm0i=0;xm01i+1i+1=0;...xm01nn=0Fromthe(i+1)-thequationtothen-thequation,eachxj(j=i+1;:::;n)canbeanyoneofthe(m01)-throotofj.Alsofromtheiequations,xmm02=xmm01;...xmm0i=xmm01:Soeachxj(j=2;:::;n)canbeexpressedinx1bymm0ways.Correspondingly,x1canbedetermineduniquelybyxi+1;:::;xnandthelastequation,andcanalsobedetermineduniquely.Therefore,thereare(m01)ni(mm0)i1solutionsintotaliftheiequationsof(2.24)hold.Thisreasoningholdsforanyiequationsof(2.24)aretrue.Sothereare0B@ni1CA(m01)ni(mm0)i128solutionsinthissituation.Sinceimaybeanyoneoff1;:::;ng,thenumberofisolatedzerosofG1(x)intotalshouldbenXi=10B@ni1CA(m01)ni(mm0)i1=1mm0nXi=10B@ni1CA(m01)ni(mm0)i=1mm0[(m01+mm0)n(m01)n]=(m1)n(m01)nmm0:WenowshowthateachzeroofG1(x)in(2.23)mustbenonsingular.Asdiscussedabove,anyzero(;x)ofG1(x)(xj)mm0=0;j2Ii(xj)m01j=0;j2f1;;ngnIi1x1++nxn+0=0;whereIiisanindexsetwhichcontainsielementsoff1;:::;ngfor1in.Withoutlossofgenerality,weassumeIi=f1;:::;ig.Then(xj)mm0=0;j=1;;i;(xj)m01j=0;j=i+1;;n;(2.25)1x1++nxn+0=0:LetDG1(x)betheJacobianofG1(x)withrespectto(x).ToshowDG1(;x)is29nonsingular,letAj(x):=(xm01jj);Bj(x):=(m01)xm02j(xmm0j)+(mm0)xmm01j(xm01jj)forj=1;:::;n.ThenDG1(x)=0BBBBBBBBBBBBBBBBBBBBB@A1B1......AiBiAi+1Bi+1......AnBn01:::ii+1:::n1CCCCCCCCCCCCCCCCCCCCCA:NotethatAj(;x)=8><>:((xj)m01j);j=1;:::;i0;j=i+1;:::;nandby(2.25),Bj(;x)=8><>:(mm0)(xj)mm01((xj)m01j);j=1;:::;i(m01)(xj)m02((xj)mm0);j=i+1;:::;n:30Forsimplicity,writeAj:=Aj(;x)andBj:=Bj(;x).ThenDG1(;x)=0BBBBBBBBBBBBBBBBBBBBB@A1B1......AiBi0Bi+1......0Bn01:::ii+1:::n1CCCCCCCCCCCCCCCCCCCCCA:Sodet(DG1(;x))=0@nYj=i+1(1)(i+1)+(i+2)Bj1Adet0BBBBBBBBBBBBBBBBBBBBBBBB@A1B1......Al1Bl1AlBlAl+1Bl+1......AiBi01:::l1ll+1:::i1CCCCCCCCCCCCCCCCCCCCCCCCA31=0@nYj=i+1(1)Bj1AiXl=1(1)(i+1)+(l+1)ldet0BBBBBBBBBBBBBBBBBBBBB@A1B1......Al1Bl1Al0Al+1Bl+1......AiBi1CCCCCCCCCCCCCCCCCCCCCA:Furthermore,det(DG1(;x))=(1)ni0@nYj=i+1Bj1AiXl=1(1)(i+1)+(l+1)l(1)l+1AliYk=1k6=lBk=(1)n+10@nYj=i+1Bj1AiXl=1lAliYk=1k6=lBk=(1)n+10@nYj=i+1Bj1AiXl=1l[((xl)m01l)]iYk=1k6=l(mm0)(xk)mm01((xk)m01k)=(1)n(mm0)i10@nYj=i+1Bj1A iYk=1((xk)m01k)!iXl=1l0BB@iYk=1k6=l(xk)mm011CCA6=0by(2.25).2ByLemmas2.1.1,2.1.2,Theorem2.2.1,Lemma2.2.1andTheorem2.2.2,wehaveprovedthefollowingtheorem.32THEOREM2.2.3.LetH1(x;t)bedasH1(x;t):=(1t)G1(x)+tP(x);t2[0;1](2.26)whereG1(x)andP(x)aregivenby(2.23)and(1.12)respectively.ThenfollowingsolutionpathsofH1(x;t)=0in(2.26)willgiveallisolatedsolutionsof(1.12)form>m0.2.3Constructalinearhomotopytocomputegeneral-izedtensoreigenpairswhenm<m0Letc=fD;E;Lgasin(2.3).ConsiderF2(x;c)=0B@Dxm1Exm01vdiag(L)+Lx[m0m]Tx+01CA:(2.27)ClearlyF2(x;c)islinearinc.Forc1=fA;B;0gin(2.5),F2(x;c1)agreeswithourtargetsystem(1.12).SimilartoTheorem2.2.1wehavethefollowingtheorem.THEOREM2.3.1.LetF2(x;c)begivenasin(2.27)withthesetofparameterscbeingasin(2.3).Thenthenumberofisolatedzeros,countingmultiplicities,ofF2(x;c)isboundedaboveby(m01)n(m1)nm0m:Whencisgeneric,F2(x;c)hasexactly((m01)n(m1)n)=(m0m)isolatedzeros.Proof:FortherandomhyperplaneTx+0=0,i.e.,1x1++nxn+0=0,in33(2.27),wemaysupposen6=0.Thenxn=a1x1++an1xn1+b;(2.28)whereai=infori=1;:::;n1andb=0n.Noticethatthenumberofsolutionsof(2.27)inCn+1isthesameasthenumberofsolutionsinCnofthesystemT(x1;:::;xn1)resultingfromsubstituting(2.28)intothenequationsin(2.27).DenotethecorrespondingsupportsofTbyS1;:::;Sn.WeclaimthatMVn(S1[f0g;:::;Sn[f0g)=(m01)n(m1)nm0m:(2.29)LetNdenotethenumberofisolatedzerosof(2.27)overC.Then(2.29),whenitisproved,impliesN(m01)n(m1)nm0m:Whentheparametersetc=fD;E;Lgisgeneric,theequalityintheaboveholdsfromLemma2.1.3andLemma2.1.4.Toprove(2.29),letc:=fD;E;Lgbegeneric.Similarto(2.27)thecorrespondingpolynomialsystemisT(x)=0B@Dxm1Exm01vdiag(L)+Lx[m0m]Tx+01CA=0:(2.30)Substituting(2.28)intothenequationsof(2.30)yieldsanewsystemT(x1;:::;xn1).LetS1;:::;SnbethecorrespondingsupportsofT.SinceD,EandLaregeneric,without34lossofgeneralityonecanassumethatallmonomials1;m0m1;:::;m0mnwithfx11x22:::xnni2Z0;1+2++n=m1gandf11x22:::xnni2Z0;1+2++n=m01gwillappearineachofthenequationsin(2.8).Therefore,aftersubstituting(2.6)intothenequationsof(2.8),allmonomialsfx11x22:::xn1n1i2Z0;1+2++n1m1gandf11x22:::xn1n1i2Z0;1+2++n1m01garecontainedineachequationofT.Consequently,S1;:::;SnareallequaltoS:=f(0;)2(Zn10)T;jjm1g[f(1;)2(Zn10)T;jjm01g:LetQbetheconvexhullofS.TocomputethevolumeofQ,weemployageometricapproachhere.Asbefore,denotethei-thunitvectorin(Rn)Tbyeifori=1;:::;n.ThentheverticesofQarezi=8>>>>>>>>><>>>>>>>>>:0;i=0(m1)en+1i;1in1e1;i=ne1+(m01)e2n+1i;n+1i2n1:(2.31)35So,zn+i=e1+m01m1zi;0in1:Fromwhichzn;:::;z2n1arescalingofz0;:::;zn1byafactor(m01)=(m1)followedbyashiftrespectively.Infact,eachzn+iisobtainedbymovingzialongthelineli(t):=(1t)zi+tzn+i;0in1(2.32)astchangingfrom0to1.Asimplecomputationyieldsli(t)=8><>:te1;i=0te1+(m1+(m0m)t)en+1i;1in1:(2.33)Noticethatwhenm1+(m0m)t=0,i.e.,t=(1m)=(m0m),eachli(1in1)willhavethesameintersectionpointw:=1mm0me1withthelinel0(t).Moreover,allthecoordinatesofz0;z1;:::;zn1are0andallthecoordinatesofzn;:::;z2n1are1.Writezi:=8><>:(0;yi);i=0;1;:::;n1(1;yi);i=n;:::;2n1:36Denotethei-thunitvectorin(Rn1)Tbyuifori=1;:::;n1.By(2.31),yi=8>>>>><>>>>>:0;i=0;n(m1)uni;i=1;:::;n1(m01)u2ni;i=n+1;:::;2n1:Let0betheconvexhullofy0;y1;:::;yn1and1betheconvexhullofyn;:::;y2n1.Then0isasimplexwithvoln10)=1(n1)!det0BBBBBBBBB@y1y0y2y0...yn1y01CCCCCCCCCA=1(n1)!det0BBBBBBBBB@(m1)un1(m1)un2...(m1)u11CCCCCCCCCA=(m1)n1(n1)!det0BBBBBBBBB@un1un2...u11CCCCCCCCCA=(m1)n1(n1)!:Similarly,1isalsoasimplexwithvoln11)=(m01)n1(n1)!:Therefore,whenm<m0,astdecreasesfrom1to0to(1m)=(m0m),1shrinksto0andthenshrinkstoonepointw.SeeFigure2.1forthecaseofm=3,m0=4andn=3.37wz3z4z5z0z1z2Figure2.1:DiagramofQwhenm=3,m0=4andn=3LetQ0:=conv(z0;z1;:::;zn1;w);Q1:=conv(zn;zn+1;:::;z2n1;w):Thenvoln(Q)=voln(Q1)voln(Q0):38NotethatVoln(Q0)=1n!det0BBBBBBBBBBBBB@z1z0z2z0...zn1z0wz01CCCCCCCCCCCCCA=1n!det0BBBBBBBBBBBBB@(m1)en(m1)en1...(m1)e21mm0me11CCCCCCCCCCCCCA=(m1)n(m0m)n!det0BBBBBBBBBBBBB@enen1...e2e11CCCCCCCCCCCCCA=(m1)n(m0m)n!det0BBBBB@e1...en1CCCCCA=(m1)n(m0m)n!andVoln(Q1)=1n!det0BBBBBBBBBBBBB@zn+1znzn+2zn...z2n1znwzn1CCCCCCCCCCCCCA=1n!det0BBBBBBBBBBBBB@(m01)en(m01)en1...(m01)e21m0m0me11CCCCCCCCCCCCCA=(m01)n(m0m)n!det0BBBBBBBBBBBBB@enen1...e2e11CCCCCCCCCCCCCA=(m01)n(m0m)n!det0BBBBB@e1...en1CCCCCA=(m01)n(m0m)n!:Hence,Voln(Q)=(m01)n(m0m)n!(m1)n(m0m)n!=(m01)n(m1)n(m0m)n!:(2.34)39Therefore,byLemma2.1.5,MVn(S1;:::;Sn)=n!Voln(Q)=(m01)n(m1)nm0m:SinceSi[f0gisasubsetofSifori=1;:::;n,itfollowsthatMVn(S1[f0g;:::;Sn[f0g)MVn(S1;:::;Sn):Consequently,MVn(S1[f0g;:::;Sn[f0g)(m01)n(m1)nm0m:(2.35)Fortheotherdirection,considertheidentitytensorsD2C[m;n]andE2C[m0;n]inwhichDii:::i=1,Eii:::i=1andallotherentriesarezero.LetLbethennzeromatrix.Then(2.27)becomes0BBBBBBBBB@xm11m011...xm1nm01nTx+01CCCCCCCCCA=0BBBBBBBBB@xm11(1m0m1)...xm1n(1m0mn)Tx+01CCCCCCCCCA=0;(2.36)where=(1;;n)2Cnaregeneric.Apparentlyx=0cannotbeasolutionsince06=0intheaugmentedrandomhyperplane.Henceatleastoneof1m0m1;:::;1m0mn(2.37)mustbezero.Assumei(1in)itemsof(2.37)arezero.Iftheiitemsof(2.37)are40zero,then1m0mj=0;j=1;;i;xm1j=0;j=i+1;;n:Fromthe(i+1)-thequationtothen-thequation,eachxj(j=i+1;:::;n)canbe0withmultiplicitym1.Butcannotbe0,otherwisethenequationswillresultinx1==xn=0makingthelastequationof(2.36)invalid.Thusfromtheiequations,xm0m2=xm0m1;:::;xm0mi=xm0m1:Soeachxj(j=2;:::;n)canbeexpressedinx1bym0mways.Correspondingly,x1canbedetermineduniquelybythechoicesofxi+1;:::;xnandthelastequation,andcanalsobedetermineduniquely.Therefore,thereare(m1)ni(m0m)i1solutionsintotaliftheiequationsof(2.37)arevalid.Thisargumentholdsforanyiequationsof(2.37)arevalid.Inthissituation,thereare0B@ni1CA(m1)ni(m0m)i1solutions.Sinceimaybeanyoneoff1;:::;ng,thenumberofzerosof(2.37)intotalshould41benXi=10B@ni1CA(m1)ni(m0m)i1=1m0mnXi=10B@ni1CA(m1)ni(m0m)i=1m0m[(m1+m0m)n(m1)n]=(m01)n(m1)nm0m:ByLemma2.1.4,MVn(S1[f0g;:::;Sn[f0g)(m01)n(m1)nm0m:So,MVn(S1[f0g;:::;Sn[f0g)=(m01)n(m1)nm0m:2LetNF2beasinLemma2.1.1withF2(x;c)beingasin(2.27).SimilartoLemma2.2.1,wehavethefollowinglemma.LEMMA2.3.1.LetNF2beasinLemma2.1.1withF2(x;c)beingasin(2.27).ThenNF2=(m01)n(m1)nm0m:(2.38)Proof:ByLemma2.1.1,NF2isanupperboundofthenumberofnonsingularzerosof42F2(x;c)in(2.27).Sincenonsingularzerosareisolatedzeros,byTheorem2.3.1,NF2(m01)n(m1)nm0m:Ontheotherhand,F2(x;c)in(2.27)has((m01)n(m1)n)=(m0m)nonsingularzeroswhencisgeneric.SobyLemma2.1.1,(m01)n(m1)nm0mNF2:2Letc0=fI[m;n];I[m0;n];Ggbeasin(2.22)andG2(x):=F2(x;c0):Then,G2(x)=0BBBBBBBBB@xm11m0111+1xm0m1...xm1nm01nn+nxm0mnTx+01CCCCCCCCCA=0BBBBBBBBB@(xm111)(1m0m1)...(xm1nn)(1m0mn)Tx+01CCCCCCCCCA:(2.39)THEOREM2.3.2.LetG2(x)andNF2beasin(2.39)and(2.38)respectively.ThenG2(x)hasexactlyNF2nonsingularzeros.43Proof:Atleastoneoftheequations1m0m1=0;...(2.40)1m0mn=0musthold,otherwisesystem(2.39)isequivalenttoanoverdeterminedsystemofn+1equationsinnunknowns,whichhasnosolutionsduetorandomness.Assumethati(1in)equationsof(2.40)aretrue.Withoutloss,wemaysupposetheyaretheiequations.Then1m0m1=0;...1m0mi=0;xm1i+1i+1=0;...xm1nn=0Fromthe(i+1)-thequationtothen-thequation,eachxj(j=i+1;:::;n)canbeoneofthe(m1)-throotofj.Alsofromtheiequations,=0cannotbeasolution,since(2.39)willthenbeanoverdeterminedsystemwithn+1equationsinnunknowns.44Consequently,xm0m2=xm0m1;...xm0mi=xm0m1:Soeachxj(j=2;:::;n)canbeexpressedinx1bym0mways.Thus,x1canbedetermineduniquelybythechoicesofxi+1;:::;xnandthelastequation,andcanalsobedetermineduniquely.Therefore,thereare(m1)ni(m0m)i1solutionsintotalinthissituation.Thisargumentholdsforanyiequationsof(2.24)arevalid,andthereare0B@ni1CA(m1)ni(m0m)i1isolatedsolutions.Sinceimaybeanyoneoff1;:::;ng,thenumberofzerosofG2(x)intotalshouldbenXi=10B@ni1CA(m1)ni(m0m)i1=1m0mnXi=10B@ni1CA(m1)ni(m0m)i=1m0m[(m1+m0m)n(m1)n]=(m01)n(m1)nm0m:WenowshowthateachisolatedzeroofG2(x)mustbenonsingular.Asdiscussed45above,anyzero(;x)ofG2(x)1(xj)mm0=0;j2Ii(xj)m1j=0;j2f1;;ngnIi1x1++nxn+0=0;whereIiisanindexsetcontainingidistinctelementsoff1;:::;ngforsome1in.Withoutlossofgenerality,weassumeIi=f1;:::;ig.Hence1(xj)mm0=0;j=1;;i;(xj)m1j=0;j=i+1;;n;(2.41)1x1++nxn+0=0:forsome1in.LetDG2(x)betheJacobianofG2(x)withrespectto(x).ToshowDG2(;x)isnonsingular,letAj(x):=xm0mj(xm1jj);Bj(x):=(m1)xm2j(1mm0j)(m0m)m0m1j(xm1jj)46forj=1;:::;n.ThenDG2(x)=0BBBBBBBBBBBBBBBBBBBBB@A1B1......AiBiAi+1Bi+1......AnBn01:::ii+1:::n1CCCCCCCCCCCCCCCCCCCCCA:NoticethatAj(;x)=8><>:(xj)m0m((xj)m1j);j=1;:::;i0;j=i+1;:::;nandBj(;x)=8><>:(m0m)(xj)m0m1((xj)m1j);j=1;:::;i(m1)(xj)m2(1(xj)m0m);j=i+1;:::;n47by(2.41).Forsimplicity,writeAj:=Aj(;x)andBj:=Bj(;x).ThenDG2(;x)=0BBBBBBBBBBBBBBBBBBBBB@A1B1......AiBi0Bi+1......0Bn01:::ii+1:::n1CCCCCCCCCCCCCCCCCCCCCA:So,det(DG2(;x))=0@nYj=i+1(1)(i+1)+(i+2)Bj1Adet0BBBBBBBBBBBBBBBBBBBBBBBB@A1B1......Al1Bl1AlBlAl+1Bl+1......AiBi01:::l1ll+1:::i1CCCCCCCCCCCCCCCCCCCCCCCCA48=0@nYj=i+1(1)Bj1AiXl=1(1)(i+1)+(l+1)ldet0BBBBBBBBBBBBBBBBBBBBB@A1B1......Al1Bl1Al0Al+1Bl+1......AiBi1CCCCCCCCCCCCCCCCCCCCCA:And,det(DG2(;x))=(1)ni0@nYj=i+1Bj1AiXl=1(1)(i+1)+(l+1)l(1)l+1AliYk=1k6=lBk=(1)n+10@nYj=i+1Bj1AiXl=1lAliYk=1k6=lBk=(1)n+10@nYj=i+1Bj1AiXl=1l[(xl)m0m((xl)m1l)]iYk=1k6=l[(m0m)(xk)m0m1((xk)m1k)]=(1)n(mm0)i10@nYj=i+1Bj1A iYk=1((xk)m1k)!iXl=1lxl0BB@iYk=1k6=l(xk)m0m11CCA6=0by(2.41).249ByLemmas2.1.1,2.1.2,Theorem2.3.1,Lemma2.3.1andTheorem2.3.2,wehaveprovedthefollowingtheorem.THEOREM2.3.3.LetH2(x;t):=(1t)G2(x)+tP(x);t2[0;1](2.42)whereG2(x)andP(x)aregivenby(2.39)and(1.12)respectively.ThenfollowingsolutionpathsofH2(x;t)=0in(2.42)willgiveallisolatedsolutionsof(1.12)form<m0.50Chapter3ImplementationofthelinearhomotopymethodsBasedonTheorem2.2.3andTheorem2.3.3inChapter2,alinearhomotopyalgorithmcanbeconstructedtocomputegeneralizedtensoreigenpairs.3.1AlinearhomotopyalgorithmtocomputetensoreigenpairsSupposem6=m0,A2C[m;n]andB2C[m0;n].AsdiscussedinSection1.4,computingeigen-pairssatisfying(1.9)isequivalenttosolving(1.12)intheplace,followedbynormalizingthecorrespondingsolutionforaneigenpair.AccordingtoTheorem2.2.3andTheorem2.3.3inChapter2,thefollowinglinearhomotopyisusefultosolveP(x)in(1.12):H(x;t)=(1t)G(x)+tP(x)=0;t2[0;1);(3.1)whereisarandomlychosencomplexnumberontheunitcircle,G(x)isgivenin(2.23)whenm>m0and(2.39)whenm<m0.Wenowpresentourlinearhomotopyalgorithmforcomputinggeneralizedtensoreigen-pairswhenm6=m0.51ALGORITHM3.1.1.(Computemode-kB-eigenpairsofA,whereA2C[m;n],B2C[m0;n].)Step1.ComputeallsolutionsofG(x)=0asgivenin(2.23)or(2.39).Step2.Computeallsolutions(x)of(1.9)byfollowingthepathsfromt=0tot=1usingthelinearhomotopyH(x;t)=0din(3.1).Step3.ComputearepresentativefromeachequivalencesolutionclassofA(k)xm1=Bxm01bynormalizingeach(x)obtainedinStep2foraneigenpair(;x),i.e.,=(Bxm0)(mm0)=m0;x=x(Bxm0)1=m0tosatisfy(1.9).Step4.Computem0equivalenteigenpairs(0;x0)foreach(;x)obtainedinStep2by0=tmm0andx0=txwithtbeingarootoftm0=1.REMARK3.1.1.Ifonlyonerepresentativefromeachequivalenceclassisrequired(see,forexample,[5]),thenStep4intheaboveAlgorithmcanbeskipped.REMARK3.1.2.Whenm6=m0,itwasshown(Theorem2.3[8])thatifAhaslymanyequivalenceclassesofBeigenpairs,thenthenumberofequivalenceclassesofBeigenpairs,countingmultiplicities,isboundedbyK(m;m0;n)=(m1)n(m01)nmm0:(3.2)Furthermore,ifAandBaregenerictensors,thenAhasK(m;m0;n)equivalenceclassesofBeigenpairs,countingmultiplicities.Asaconsequence,theoptimalnumberofpathstofollowforsolvingthesystem(1.12)isK(m;m0;n).Ourstartingsystem(2.23)or(2.39)has52exactlyK(m;m0;n)nonsingularsolutions.Therefore,Algorithm3.1.1followstheoptimalnumber,makingitanthomotopymethodforcomputinggeneralizedeigenpairs.3.2AlgorithmstocomputesolutionsofthestartingsysteminthelinearhomotopyalgorithmInthissection,twoalgorithmswillbedescribedtocomputesolutionsofthestartingsystemG(x)in(3.1),whichisG1(x)asin(2.23)whenm>m0andG2(x)asin(2.39)whenm<m0.ThefollowingalgorithmgivesamethodtocomputeallsolutionsofG1(x).ALGORITHM3.2.1.(ComputeallthesolutionsofG1(x).)Step1.Fori=1;:::;n,chooseIitobeanindexsetcontainingielementsoff1;:::;ng.Step2.ForeachIichoseninStep1,letkbethesmallestintegercontainedinIi.Foreachj2f1;:::;ngnfkg,computexjbyxj=8>><>>:e2ˇlimm0xk;j2Iinfkge2ˇpim01j;j2f1;:::;ngnIi(3.3)wherelcanbechosenfromf0;1;:::;mm01gandpcanbechosenfromf0;1;:::;m02g.Step3.ForthechosenlandpfromStep2,substituteallxj's(exceptxk)givenby(3.3)toTx+0=0tocomputexk.Step4.ForthechosenlandpfromStep2,substitutexkbackinto(3.3),allthexj'scanbeobtained,and=xmm0k:ThefollowingalgorithmistocomputeallsolutionsofG2(x).53ALGORITHM3.2.2.(ComputeallthesolutionsofG2(x).)Step1.Fori=1;:::;n,chooseIitobeanindexsetcontainingielementsoff1;:::;ng.Step2.ForeachIiselectedinStep1,letkbethesmallestintegercontainedinIi.Foreachj2f1;:::;ngnfkg,computexjbyxj=8><>:e2ˇlim0mxk;j2Iinfkge2ˇpim1j;j2f1;:::;ngnIi(3.4)wherel2f0;1;:::;m0m1gandp2f0;1;:::;m2g.Step3.ForthechosenlandpinStep2,substituteallxj's(exceptxk)givenby(3.4)toTx+0=0tocomputexk.Step4.ForlandpselectedinStep2,substitutexkbackinto(3.4),allthexj'scanbeobtained.Foranonzeroxj,canbecomputedby=1xm0mj:3.3AlgorithmtofollowsolutionpathsofthelinearhomotopyInthissection,wewillproposeanalgorithmtofollowthesolutionpathsofthelinearhomotopy(3.1).Letu:=(x).Then(3.1)becomesH(u;t)=(1t)G(u)+tP(u)=0;t2[0;1]:(3.5)54DenotethesolutionsetofG(u)=0bywhichcanbecomputedusingAlgorithm3.2.1orAlgorithm3.2.2.ALGORITHM3.3.1.(Followsolutionpathsof(3.5).)Step1.Let(uk;tk):=(u(tk);tk).Taket0=0,andletu02.Forthenextpoint(u1;t1)onthesolutionpathofH(u;t)=(1t)G(u)+tP(u)=0;t2[0;1]in(3.5),thefollowingstepsareemployed:PredictionStepbyEulermethod:Computethetangentvectordudttoasolutionpathu(t)ofH(u;t)=0at(u0;t0)bysolvingthelinearsystemHu(u0;t0)dudt=Ht(u0;t0)fordudt.Thencomputetheapproximation~utou1by~u=u0+tdudt;t1=t0+t;wheretisthestepsize.CorrectionStep:UseNewton'siterations,i.e.,fori=0;1;2;:::,computevi+1=vi[Hu(vi;t1)]1H(vi;t1)withv0=~uuntilkH(vJ;t1)kisverysmall.Thenletu1=vJ.Whentheiterationfailstoconverge,55thePredictionStepwillberepeatwitht=t2.Step2.Pathfollowing:Followthepathsfromt=t1tot=1usingtheprediction-correctionstrategy.Given(uk;tk),tothenextpoint(uk+1;tk+1)onthesolutionpathofH(u;t)=0asin(3.5),thefollowingstepsareemployed:PredictionStepbythecubicHermiteinterpolation:Computethetangentvectordudttoasolutionpathu(t)ofH(u;t)=0at(uk1;tk1)and(uk;tk)bysolvingthelinearsystemHu(uk1;tk1)dudtt=tk1=Ht(uk1;tk1)fordudtt=tk1andHu(uk;tk)dudtt=tk=Ht(uk;tk)fordudtt=tk.Let~u(t)bethecubicpolynomialwhichinterpolatesu(t)andu0(t)att=tk1andt=tk.Namely,~u(tk1)=uk1;~u(tk)=ukand~u0(tk1)=dudtt=tk1;~u0(tk)=dudtt=tk:Then~u(tk+1)canbetakenasthepredictionofu(t)attk+1,i.e.,anapproximationtouk+1.Here,tk+1=tk+twithtbeingthestepsize.CorrectionStep:UseNewton'siterations,i.e.,fori=0;1;2;:::,computevi+1=vi[Hu(vi;tk+1)]1H(vi;tk+1)withv0=~u(tk+1)56untilkH(vJ;tk+1)kisverysmall.Thenletuk+1=vJ.Whentheiterationfailstoconverge,thePredictionStepwillberepeatwitht=t2.Step3.Endgame.WhentNisverycloseto1,thecorrespondinguNshouldbeveryclosetoazerouofP(u)=P(x).SoNewton'siterationsu(k+1)=u(k)[DP(u(k))]1P(u(k));u(0)=uN;k=0;1;:::willbeusedagaintorourapproximation~utou.IfDP(u)isnonsingular,then~uwillbeaverygoodapproximationofuwithmultiplicity1.IfDP(u)issingular,~uiseitheranisolatedsingularzeroofP(u)withmultiplicityl>1orinapositivedimensionalsolutioncomponentofP(u)=0.WeuseastrategysuggestedinChapterVIIIof[13](seealso[29])todeterminewhether~uisanisolatedzerowithmultiplicitybiggerthan1orinapositivedimensionalsolutioncomponentofP(u)=0.Byusingrandomcomplexnumbersintheformulationofhomotopy,withprobabilityonethesolutionpathsdonotintersectwitheachotherorgotoyfor0<t<1theoretically.Practically,however,twosolutionpathsmaybecomeveryclosetoeachotherandthemagnitudeofsomecomponentsofasolutionpathmaybecomeverylargeduringtheprocedureofpathtracking.Thiscausesvariousnumericalsuchasmissingsolutions,losingorstability.InourimplementationofAlgorithms3.3.1,weusethefollowingstrategiestoaddresstheseissues.Whentracingtwopathsthataretlyclose,itispossibleforthepathtracingalgorithmtojumpfromonepathtotheotherandthusresultinmissingofzeros.Tominimizethechanceforcurvejumpingandkeepthe,ourFirstStrategyis:ThestepsizetinStep1andStep2ofAlgorithm3.3.1ischosenadaptively.Initially,t=0:1=(n+1),57wheren+1isthenumberofunknownvariablesx1;:::;xnin(1.12)or(1.9).Similarto[15],ifmorethanthreestepsofNewtoniterationswererequiredtoconvergewithinthedesiredaccuracy,tishalved.Ontheotherhand,ifseveralconsecutivesteps(thedefaultbeing2)werenotcut,tisdoubled,uptoaprescribedmaximumvalue(thedefaultbeing0:1=(n+1)).Althoughthisadaptiveapproachcanoftenreducethepossibilityofcurvejumpingsignif-icantly,curvejumpingcanstilloccurinsomeoccasions.OurSecondStrategyis:Tocheckifthereexistcurvejumpings,allfoundsolutionsarestoredinabinarysearchtree.Eachtimewhenanewsolutionisfound,wecanquickly(withtimecomplexityO(logN),whereNisthenumberofsolutions)whetherthereisanyexistingsolutionthatisnumericallyiden-ticaltothenewsolution,thatis,theencebetweenthemislessthanathreshold(thedefaultbeing106).IftwonumericallyidenticalsolutionsaredetectedandtheconditionnumbersoftheirJacobianmatricesarelessthanathreshold(thedefaultbeing1010),thecurvejumpinghaslikelyoccurred.Wethenretracethetwoassociatedcurveswithmorerestrictedparameters.Whenthemagnitudeofsomecomponentsofcertainsolutioncurvebecomeverylargeatt02(0;1),tracingthesepathsmayfailduetonumericalinstability.Thisissuecanbelargelyresolvedbyfollowingpathsintheprojectivespace(see,forexample,[29]).However,empiricallyitismoretimeconsumingtofollowallpathsintheprojectivespace.InourimplementationofAlgorithms3.3.1,ourThirdStrategyis:Toretracesolutioncurvesintheprojectivespaceonlyforthosepathsthataredetectedtohaveverylargesolutioncomponents.Forexample,whenm>m0,totraceapathintheprojectivespace,wehomogenize58eachpolynomialequationof(2.26)inthevariablesx1;:::;xn,namely^H(^x;t)=(1t)0BBBBBBBBB@(xm0111xm010)(xmm01mm010)...(xm01nnxm010)(xmm0nmm010)Tx+0x01CCCCCCCCCA+t0BBBBBBBBB@(A(k)xm1)1mm010(Bxm01)1...x0(A(k)xm1)nmm010(Bxm01)na1x1+a2x2++anxn+bx01CCCCCCCCCA=0;(3.6)where^x=(x0;x1;:::;xn)T.Thenfollowthesolutioncurveof(3.6)intheprojectivespace.Noticethatin(3.6)if(^x)isasolution,sois(^x)for2Cnf0g.Thusalongthepathwecanalwaysscale(^x)tokeepeachcomponent'smagnitudeinasuitablerange.Tothebestofourknowledge,Strategies2and3havenotbeenusedinotherimplemen-tationsofhomotopymethods,althoughsomepackagesmaytraceallcurvesintheprojectivespace.3.4EvaluatingpolynomialsandderivativesTheprediction-correctionprocessforfollowingthehomotopypathsofH(x;t)=(1t)G(x)+tP(x)=059requiresthecomputationofH(x;t),Ht(x;t),andtheJacobianmatrixDH(x;t)=[H(x;t);Hx(x;t)]fort2[0;1].Whatisessentialinthoseevaluationsistheevaluationofmultivariatepolynomialsandtheirpartialderivatives.InHOM4PS[15],amultivariatepolynomialg(x1;;xn)wasevaluatedviaHorner'sruleforunivariatepoly-nomials.Thebasicideaistosingleoutavariable,sayx1,andconsiderg(x1;;xn)asapolynomialinx1withcotsinx2;;xn.Bythesameapproach,thosecoients,aspolynomialsinonelessvariable,wereevaluatedbysinglingoutanothervariable.Thismaycontinueuntilthevariablesareexhausted.Inasinglevariablecase,Horner'srulehasbeenprovedtobeoptimal[19,20],i.e.,anyotheralgorithmstoevaluateapolynomialmustuseatleastasmanyoperations(additionsandmultiplications)asHorner'smethod.However,inmultivariatecases,itisnotguaranteed.Aspointedoutin[15],thesamepowersofsomevariableswillbecomputedrepeatedlyinthismanner.Toimprovethe,inHOM4PS2.0,atableTofsizenMisprecomputedtostoreallpossiblepowersofxi;i=1;;nwhereMisthemaximumpowerofallthevariablesintheentirepolynomialsystem.Forexample,forthefollowingsystem[15]:P(x1;x2;x3)=0BBBBB@2x61+3x42+5x5313x61x42+2x61x53+4x42x5355x61x42x5371CCCCCA;(3.7)themaximumdegreeofx1is6,x2is4,andx3is5,soM=6.WeestablishTableTinTable3.1.WiththistableT(i;j),thevalueofamonomialcanbeeasilyobtained.Forinstance,thequantityofx61x42x53isT(1;6)T(2;4)T(3;5).SincethismethodmainlybasesonTableT,wecallitTable-Tmethod.AbigadvantageoftheTable-Tmethodisthatthosepowersofeachvariableinvolved60x1x21x31x41x51x61x2x22x32x42x3x23x33x43x53Table3.1:TableTinanymonomialevaluationswillonlyneedtobecomputedonce,nomatterhowoftentheyappear.However,someshortcomingsexist:1.TherearesomeredundantcomputationsinTable3.1.Forexample,ifonlythevalueofx61isrequired,thevalueofx51andx41arenotneededsincex61=x31x31,x31=x21x1,andx21=x1x1.Alittlemoreextremeexampleisthatifonlyx100isindemand,insteadofcomputingfromx2;x3untilx100,onemaycomputeitinthefollowingway:x100=x50x50;x50=x25x25;x25=x13x12;x13=x12x;x12=x6x6;x6=x3x3;x3=x2x;x2=xx;whereonly8middlevaluesneedtobecomputedincomparisontocomputing99middlevaluespreviously.612.Themethodcannottakeadvantageofcomputingsomehigherdegreemonomialbytheproductoftwolowerdegreemonomials.Forinstance,inthepolynomialsystem(3.7),thevalueofx61x42x53maysettobex61x42x53wherevaluesofx61x42andx53arealreadycomputedinthetwopolynomials.Comparingtotheoldway,i.e.,x61x42x53=T(1;6)T(2;4)T(3;5),onelessmultiplicationisrequired.3.IfthesamemonomialappearsintpolynomialsorinitsJacobianmatrix,there-peatedcomputationofthismonomialisinevitableintheaboveapproach.Forexample,forthesystemP(x1;x2;x3)=(p1(x1;x2;x3);p2(x1;x2;x3);p3(x1;x2;x3));wherep1=x61x53+3x51x42+5x531p2=3x61x42+2x61x53+4x42x535(3.8)p3=5x61x42x537;themonomialx61x53appearsinbothp1andp2.Andthemonomialx51x42appearsinbothp1and@p2@x1=18x51x42+12x51x53.Intheaboveapproach,thosequantitieswillbecomputedrepeatedly.Toresolvethoseissues,thefollowingnewmethodhasbeendeveloped.Step1.Collectallthemonomialsfromthegivenpolynomialsandtheirderivatives,anddividethemintotgroupsaccordingtotheirdegrees.Sincethecotsofthemonomialsarenotinfollowingthehomotopypaths,onlyvariablepartsofthe62monomialsareselected,theircotswillbecalculatedseparately.Fortheconvenienceoffuturecomputations,eachgroupisorganizedasalinkedlistwitheachnodebeingamonomialandthenodesaresortedalphabeticallyandalsobythepowersofeachvariable.Forduplicatedmonomials,theyonlyneedtoappearonce.Thisaccountsfortheproblemstatedin3above.Forexample,theJacobianmatrixof(3.8)is0BBBBB@6x51x53+15x41x4212x51x325x61x43+25x4318x51x42+12x51x5312x61x32+16x32x5310x61x43+20x42x4330x51x42x5320x61x32x5325x61x42x431CCCCCA:(3.9)Collectingallthemonomialsfrom(3.8)and(3.9)andputtingthemintotlinkedlistsbasedontheirdegreesyieldsfollowingstructure:1!x1!x2!x34!x435!x538!x51x32!x41x42!x42x43!x32x539!x61x32!x51x42!x42x53(3.10)10!x61x42!x61x43!x51x5311!x61x5314!x61x42x43!x61x32x53!x51x42x5315!x61x42x53Herex1;x2,andx3arealsointhestructurebecausetheyaretheinitialvaluesneededto63evaluatethemonomials.Step2.Startingfromthemonomialswiththehighestdegreetodegree2,foreachmonomialx,searchallthenodesinthelinkedliststotwolowerdegreemonomialsxandxsuchthattheirproductisequaltox,i.e.=+.Withoutlossofgenerality,letusassumethatjjjj.Sincejjj2kjj<jj,weonlyneedtosearchthemonomialswithdegreebetweenjjj2kandjj1inordertoapossiblemonomialxwith.For:=(1;:::;n)and:=(1;:::;n),bywemeaniifori=1;:::;n.Therearethreecases:Case1:Ifthereexisttwomonomialsxandxinthelinkedlistssuchthatx=xx.Thenlabeltherelationinthestructure.Forexample,aswecanseefrom(3.10),x61x42x53istheproductofx61x42x43andx3,x61x42x43istheproductofx61x42andx43,thentheirrelationswillbemarkedinthestructureasshowninthelinkedlistsofdegree14and15inFigure3.1;Case2:Ifxisinthelinkedlistsbutx=xisnotinthelists,thenaddanewmonomialxintothelinkedlistsandthenlabeltherelation.Ifthereareseveralchoicesforx,choosetheonewiththelargestdegree.Take(3.10)forinstance,x43isafactorofx42x43butx42isnotinthelinkedlists.Inthiscase,addx42intothelinkedlistwithdegree4;Case3:Thereisnomonomialxsatisfyingtheconditions.Let=d=2eand=,addxandxintothelinkedlistsandlabeltherelation.If=,themonomialonlyneedstobeaddedonce.Forexample,thereisnomonomialwithdegreebetween5and9whichisafactorofx61x43in(3.10).Let=d=2e=d[604]=2e=[302],then=isequalto,weonlyneedtoaddthemonomialx31x23tothelinkedlists.64Similarly,inordertoevaluatex51x32,twolowerdegreemonomialsx31x22andx21x12areaddedintothelinkedlists.Applyingtheaboverulesto(3.10),resultsinFigure3.1.Step3.EvaluatemonomialsfromthelowestdegreetothehighestdegreeinthelinkedlistsbasedontheevaluationdiagramobtainedinStep2(See,forexample,Figure3.1).SinceourlinkedlistsisbuiltaccordingtothecriteriathateverymonomialofhigherdegreecanbeevaluatedbycomputingtheproductoftwomonomialsoflowerdegreesinStep2,thevaluesofallthemonomialscanbeevaluatedinthisstep.Step4.Computethevaluesofthepolynomialsandtheirderivativesbyusingthemonomials'values.Forthisgoal,therearetwoapproaches.On-lineevaluation:wemaintainamappingbetweenthemonomialsinthepolynomialsandtheirderivativeswiththeonesinthelinkedlistsinthememory.Togetthevalueofapolynomial,wereplacethemonomialwiththevaluesinthelinkedlistsrst,thensumupthevaluestoobtainthepolynomial'svalue;evaluation:wecreateanewfunctionwhichcontainsalltheevaluationrulesintheharddisk.SoifwewanttoevaluateapolynomialsystemanditsJacobianmatrix,allweneedtodoistocallthatnewfunctionwiththevalueofxandcotsasinputs.SeeFigure3.2foranexampleoftheevaluationfunction.Thereasonwhyweneedtwotapproachesisthatnormallyevaluationismuchmoretthanon-lineevaluation.However,somelanguages,likeC++andFortran,donotsupportevaluation,i.e.onecannotdynamicallycreateanewfunctionandrequiretheprogramtocallit.Fortheselanguages,inordertousethenewcreatedfunctionstored65Figure3.1:Anexampleoftheevaluationgraph66Figure3.2:Anexampleoftheevaluationfunction67inaseparatetheshouldbecompliedbeforewecanuseit.Inthiscase,oneprefersanon-lineevaluation.68Chapter4NumericalresultsInthissection,wepresentsomenumericalresultstoshowtheenessandofAlgorithm3.1.1.ThenumericalexperimentswerecarriedoutusingMATLAB2013a,onaThinkpadT400laptopcomputerwithanIntel(R)dualcoreCPUat2.80GHzand2GBofRAM,runningtheWindows7operatingsystem.4.1TheofthenewevaluationmethodAsdiscussedinSection3.4,themosttime-consumingprocedureinAlgorithm3.1.1isinfactevaluationofpolynomialsandtheirderivativesandnewapproacheshavebeenproposedtoexecutetheseevaluations.Inthissection,wecomparetheofournewapproacheswiththeTable-TmethodusedinHOM4PS2.0.EXAMPLE4.1.1.Inthisexample,weintendtocomparetheoftheon-lineandapproachesdescribedinSection3.4withtheTable-Tmethod.AllthesethreeapproachesareusedinStep2ofAlgorithm3.1.1computeB-eigenpairsofatensorA,whereA2C[m;n];B2C[m0;n]aregenerictensorswithm6=m0.Eachtensorwasgeneratedusingrandn(n;;n)+irandn(n;;n)inMATLAB.ThenumericalresultsarereportedinTable4.1.Asitshows,theon-lineandapproachesareconsiderablyfasterthanTable-Tmethod,andthespeed-upratioincreasesasthenumberofeigenpairsbecomesbigger.The69(m;m0;n)NumberTable-TOn-lineapproachapproachSpeed-upofmethodCPUSpeed-upCPUSpeed-upratioofeigenpairstime(s)time(s)ratiotime(s)ratio(3;2;5)3138.72.316.81.232.31.9(4;2;5)121605.021.827.812.349.21.8(4;3;5)211735.124.430.110.172.82.4(5;6;4)3691746.064.627.022.577.62.9(5;3;5)4963215.295.133.837.086.92.6Table4.1:Comparisonofon-lineandapproacheswithTable-Tmethodapproachisabout2-3timesfasterthantheon-lineapproachastestedinMATLAB.4.2ComputingcomplextensoreigenpairsWecomparetheperformanceofAlgorithm3.1.1withthatofAlgorithm3.2proposedin[8].Algorithm3.2usespolyhedralhomotopymethods.IthasbeenimplementedasafunctionteneiginthetensoreigenvaluepackageTenEig1.1([8]).ThefunctionteneigisbasedonasophisticatedpolyhedralhomotopypolynomialsystemsolverPSOLVE([30]).Numericalresultsin[8]showthatteneigistlymoretthanthepopularNSolveinMathematicaforcomputinggeneralizedeigenpairsin(1.9).EXAMPLE4.2.1.WeintendtoallisolatedB-eigenpairsofatensorA,whereA2C[m;n];B2C[m0;n]aregenerictensorswithm6=m0.Eachtensorwasgeneratedusingrandn(n;;n)+irandn(n;;n)inMATLAB.Thenumericalresultsform>m0andm<m0arereportedinTable4.2andTable4.3respectively.Inthesetables,K(m;m0;n)in(3.2))representsthetheoreticalboundofthenumberofequivalenceclassesofisolatedB-eigenpairsofAwhenm6=m0.ForgenerictensorsAandB,thisistheexactnumberofequivalenceclassesofB-eigenpairsofA.NotethatbyRemark2.1in[8]andAlgorithm3.1.1,thetotalnumberofeigenpairsis70m0K(m;m0;n).LetNdenotethenumberofequivalenceclassesofB-eigenpairsfoundbyAlgorithm3.1.1orteneiginthetables.(m;m0;n)K(m;m0;n)MethodNCPUtime(s)(3;2;7)127Algorithm3.1.11275.9teneig12710.1(4;2;6)364Algorithm3.1.136424.2teneig36429.3(4;3;5)211Algorithm3.1.121110.1teneig21113.1(5;4;5)781Algorithm3.1.178168.7teneig78182.6(6;5;4)369Algorithm3.1.136927.7teneig36928.1(7;6;4)671Algorithm3.1.167154.4teneig67174.0Table4.2:ComparisonofAlgorithm3.1.1withteneigform>m0(m;m0;n)K(m;m0;n)MethodNCPUtime(s)(3;4;6)665Algorithm3.1.166542.5teneig66562.7(3;5;5)496Algorithm3.1.149637.2teneig49647.4(4;5;4)175Algorithm3.1.11758.8teneig1759.6(4;5;5)781Algorithm3.1.178172.9teneig781104.3(5;6;4)369Algorithm3.1.136922.5teneig36931.8(7;8;3)127Algorithm3.1.11278.4teneig1279.7Table4.3:ComparisonofAlgorithm3.1.1withteneigform<m0EXAMPLE4.2.2.ConsiderallE-eigenpairsofagenerictensorA.TensorA2C[m;n]wasgeneratedusingrandn(n;;n)+irandn(n;;n)inMATLAB.Inthiscase,tensorBisthennidentitymatrix.71ThenumericalresultsarereportedinTable4.4.Inthistable,K(m;2;n)in(3.2))representstheboundofthenumberofequivalenceclassesofisolatedE-eigenpairsofA.SincetensorAisgeneric,ithasexactlyK(m;2;n)equivalenceclassesofE-eigenpairs(see,[5]).NdenotesthenumberofequivalenceclassesofE-eigenpairsfoundbyAlgorithm3.1.1orteneig.(m;n)K(m;2;n)MethodNCPUtime(s)(3;9)511Algorithm3.1.151132.4teneig51147.3(3;10)1023Algorithm3.1.1102373.5teneig1023130.5(4;7)1093Algorithm3.1.1109369.8teneig1093117.5(4;8)3280Algorithm3.1.13280380.6teneig3280565.1(5;5)341Algorithm3.1.134118.8teneig34121.6(5;6)1365Algorithm3.1.11365117.8teneig1365167.9(6;5)781Algorithm3.1.178169.7teneig78199.3(6;6)3906Algorithm3.1.13906622.3teneig3906975.9(7;4)259Algorithm3.1.125915.2teneig25920.8(7;5)1555Algorithm3.1.11555211.3teneig1555230.8Table4.4:ComparisonofAlgorithm3.1.1withteneigforcomputingE-eigenpairsFromTables1{3,whilebothAlgorithm3.1.1andteneigallB-eigenpairsofagenerictensorA,Algorithm3.1.1ismoretintermsofCPUtime.WebelievetheofAlgorithm3.1.1isachievedbecauseofitsemploymentofthelinearhomotopy(3.1)withsimplestartingsystem(2.23)or(2.39).Thealgorithmteneig,ontheotherhand,usesapolyhedralhomotopyinwhichmixedvolumecomputationisrequired.Thealong72witheasyimplementationmakesAlgorithm3.1.1acompetitivemethodforcomputingtensoreigenpairswhenm6=m0.4.3ComputingrealtensoreigenpairsSometimes,onlyrealeigenpairsareofinterest.Assuggestedin[8],onecancomputeallthecomplexeigenpairsandusetapproachestoextractrealeigenpairsfromcomplexeigenpairs.HereweuseAlgorithm3.1.1tocomputecomplexeigenpairsandfollowthesameprocedureindicatedinAlgorithm4.1in[8]toacquirerealeigenpairsfromthesecomplexeigenpairs.ForcomputingallrealeigenvaluesofasymmetrictensortheonlyavailablemethodsatthistimeareAlgorithm3.6in[9]andAlgorithm4.1in[8].Inthefollowingexample,wecomparetheperformanceofourmethodswiththeirs.EXAMPLE4.3.1.ConsiderthesymmetrictensorA2R[4;n](Example4.16in[9])inthepolynomialformAx4=(x1x2)4++(x1xn)4+(x2x3)4++(x2xn)4++(xn1xn)4:ShowninTable4.5,ournewalgorithmobtainedalltheZ-eigenvaluesfoundbyAlgorithm3.6in[9]andAlgorithm4.1in[8]fortn.Remarkably,whenn=8;9;10,ournewalgorithmandAlgorithm4.1in[8]canalltheZ-eigenvaluesinareasonableamountoftime,but[9]reportsthatAlgorithm3.6canonlythethreelargestZ-eigenvalues.TheCPUtimesusedbythesethreealgorithmsarelistedinthetable.(TheCPUtimes73byAlgorithm3.6([9])arefrom[9]1.)ThecorrespondingZ-eigenvectorsarenotdisplayed.Apparently,asitshows,ournewalgorithmleadstoalargespeed-up,rangingupto239s,overAlgorithm3.6in[9]onallthesystems,especiallyforlargeones.ComparedtoAlgorithm4.1in[8],thenewalgorithmisabout1.4timesfaster.nCPUtime(s)Alg3.6Alg4.1New([9])([8])Alg40.00004.00005.00005.33333.61.71.150.0000,4.1667,4.2500,5.5000,6.2500274.55.44.060.0000,4.0000,4.5000,6.0000,7.2000280.215.511.870.0000,4.0833,4.1667,4.7500,4.8846,9565.658.340.14.9000,6.5000,8.166780.0000,4.0000,4.2667,4.2727,4.3333,938:2244.1165.35.0000,5.2609,5.3333,7.0000,9.142990.0000,4.0500,4.1250,4.5000,5.2500,4173:8788.0544.05.6250,5.7857,7.5000,10.1250100.0000,4.0000,4.1667,4.1818,4.2500,15310:52665.61893.64.6667,4.7500,4.7593,4.7619,5.5000,5.9808,6.2500,8.0000,11.1111Table4.5:Z-eigenvaluesofthetensorinExample4.3.1(*denotesthattheCPUtimeusedbyAlgorithm3.6([9])whenitthethreelargestZ-eigenvalues)1ItshouldbecautiouswhencomparingtheCPUtimesusedbythetwomethodsbecauseoftcomputerswereused.74BIBLIOGRAPHY75BIBLIOGRAPHY[1]D.L.Bates,J.D.Hauenstein,A.J.SommeseandC.W.Wampler,NumericallySolvingPolynomialSystemswithBertini,SocietyforIndustrialandAppliedMathematics,Philadelphia,2013.[2]D.N.Bernstein,Thenumberoftherootsofasystemofequations,Funct.Anal.Appl.,1975,9:183-185.[3]J.CooperandA.Duttle,Spectraofuniformhypergraphs,LinearAlgebraanditsApplications,2012,436:3268{3292.[4]D.A.Cox,J.Little,andD.O'Shea,UsingAlgebraicGeometry,2nded.,Springer-Verlag,NewYork,NY,2005.[5]D.CartwrightandB.Sturmfels,Thenumberofeigenvaluesofatensor,LinearAlgebraanditsApplications,2013,438:942{952.[6]K.C.Chang,K.PearsonandT.Zhang,Oneigenvaluesofrealsymmetrictensors,JournalofMathematicalAnalysisandApplications,2009,350:416{422.[7]K.C.Chang,L.Qi,andT.Zhang,Asurveyofthespectraltheoryofnonnegativetensors,NumericalLinearAlgebrawithApplications,2013,20:891{912.[8]L.Chen,L.HanandL.Zhou,Computingtensoreigenvaluesviahomotopymethods,SIAMJournalonMatrixAnalysisandApplications,2016,37:290{319.[9]C.Cui,Y.-H.DaiandJ.Nie,Allrealeigenvaluesofsymmetrictensors,SIAMJournalonMatrixAnalysisandApplications,2014,35:1582{1601.[10]S.Hu,Li.Qi,andB.Zhang,Thegeometricmeasureofentanglementofpurestateswithnonnegativeamplitudesandthespectraltheoryofnonnegativetensors,arXiv:1203.3675,2012.[11]T.KoldaandB.Bader,Tensordecompositionsandapplications,SIAMReview,2009,51(3):455-500.76[12]T.G.KoldaandJ.R.Mayo,Shiftedpowermethodforcomputingtensoreigenpairs,SIAMJournalonMatrixAnalysisandApplications,2011,32:1095-1124.[13]T.Y.Li,Solvingpolynomialsystemsbythehomotopycontinuationmethod,HandbookofNumericalAnalysis,XI,2003,209{304.[14]L.-H.Lim,Singularvaluesandeigenvaluesoftensors:avariationalapproach,Proceed-ingsoftheIEEEInternationalWorkshoponComputationalAdvancesinMulti-SensorAdaptiveProcessing(CAMSAP'05),2005,1:129{132.[15]T.L.Lee,T.Y.Li,andC.H.Tsai,Hom4PS-2.0,asoftwarepackageforsolvingpoly-nomialsystemsbythepolyhedralhomotopycontinuationmethod,Computing,2008,83:109{133.[16]T.Y.LiandX.Wang,TheBKKrootcountinCn,Math.Comp.,1996,65:1477-1484.[17]M.Narasimhan,PrinciplesofContinuumMechanics,JohnWiley&Sons,NewYork,1993.[18]Q.Ni,L.QiandF.Wang,Aneigenvaluemethodfortestingpositiveofamultivariateform,AutomaticControl,IEEETransactionson,2008,53:1096-1197.[19]A.M.Ostrowski,OntwoproblemsinabstractalgebraconnectedwithHorner'srule,StudiesinMath.Mech.,1954,40-48.[20]Y.JaPan,Onmeansofcalculatingvaluesofpolynomials,RussianMath.Surveys,1966,21:105-136.[21]L.Qi,Eigenvaluesofarealsupersymmetrictensor,JournalofSymbolicComputation,2005,40:1302{1324.[22]L.Qi,W.Sun,andY.Wang,Numericalmultilinearalgebraanditsapplications,FrontiersofMathematicsinChina,2007,2:501{526.[23]L.QiandK.L.Teo,Multivariatepolynomialminimizationanditsapplicationinsignalprocessing,JournalofGlobalOptim.,2003,26:419{433.[24]L.Qi,Y.Wang,andE.X.Wu,D-eigenvaluesofkurtosistensors,JournalofComputationalandAppliedMathematics,2008,221:150{157.77[25]L.Qi,G.Yu,andE.X.Wu,Higherorderpositivesemi-dtensorimaging,SIAMJournalonImagingSciences,2010,3:416{433.[26]L.Qi,G.Yu,andY.Xu,Nonnegativeorientationdistributionfunction,JournalofMathematicalImagingandVision,2013,45:103-113.[27]W.Rudin,PrinciplesofMathematicalAnalysis,3rdedition,McGraw-Hill,NewYork,2006.[28]V.DeSilvaandL.Lim,Tensorrankandtheill-posednessofthebestlow-rankap-proximationproblem,SIAMJ.MatrixAnal.Appl.,2008,30:1084-1127.[29]A.J.SommeseandW.W.Wampler,TheNumericalSolutionofSystemsofPolynomialsArisinginEngineeringAndScience,WorldScienPubCoInc,2005.[30]Z.ZengandT.Y.Li,NACLab,AMatlabToolboxforNumericalAlgebraicComputa-tion,ACMCommunicationsinComputerAlgebra,2013,47:170{173.78