COMPUTINGTENSOREIGENPAIRSUSINGHOMOTOPYMETHODS
By
LiangminZhou
ADISSERTATION
Submittedto
MichiganStateUniversity
inpartialentoftherequirements
forthedegreeof
AppliedMathematics|DoctorofPhilosophy
2015
ABSTRACT
COMPUTINGTENSOREIGENPAIRSUSINGHOMOTOPYMETHODS
By
LiangminZhou
Tensoreigenvalueproblemshavefoundimportantapplicationsinautomaticcontrol,sta-
tisticaldataanalysis,tensorimaging,imageauthenticityvspectralhy-
pergraphtheoryandquantumentanglement,etc.Theconceptofmode-
k
generalizedeigen-
valuesandeigenvectorsofatensorisintroducedandsomepropertiesofsucheigenpairsare
proved.Inparticular,anupperboundforthenumberofequivalenceclassesofgeneralized
tensoreigenpairsusingmixedvolumeisderived.Basedonthisboundandthestructures
oftensoreigenvalueproblems,twohomotopycontinuationtypealgorithmstosolvetensor
eigenproblemsareproposed.Withproperimplementation,thesemethodscanallequiv-
alenceclassesofisolatedgeneralizedeigenpairsandsomegeneralizedeigenpairscontained
inthepositivedimensionalcomponents(ifthereareany).Analgorithmthatcombinesa
straightforwardapproachandaNewtonhomotopymethodisintroducedtoextractrealgen-
eralizedeigenpairsfromtheavailablecomplexgeneralizedeigenpairs.AMATLABsoftware
package
TenEig1.1
hasbeendevelopedtoimplementthesemethods.Numericalresultsare
presentedtoillustratetheenessandof
TenEig1.1
forcomputingcomplex
orrealgeneralizedeigenpairs.
Tomyparents
iii
ACKNOWLEDGMENTS
IwouldliketoexpressmydeepestgratitudetomyadvisorProfessorTien-YienLiforhis
well-timedguidance,encouragementandsupportallthetime.Withouthishelp,Icouldnot
havebeenabletosurvivemyPh.Dlife.WhenIfailedmyattempttotakequalifying
examsandreallythoughtIwassuchaloser,itwashimwhousedhisownstoryabout
qualifyingexamstoremindmeinwhichwayIcandobetter.WhenIhadnoclueon
myresearchandfeltIwassuchadullperson,itwashimwhocanalwayspointoutmy
problemfromourdiscussionandgivemesomesmallenlighteningproblems.Workingon
theseproblemsdiddeepenmyunderstandingonmyownproblemandwidenmyhorizon
onmath.Overtheyears,Hisdiligent,persistentandoptimisticattitudetowardsresearch,
teachingandlifehasbeeninspiringmeallthetime.
IwouldliketothankDr.ChichiaChiu,Dr.KeithPromislow,Dr.JianliangQianand
Dr.ZhengfangZhou,forservingasmembersofmythesiscommittee.Iamgratefulto
ProfessorLixingHanforintroducingsuchaninterestingprojecttome,helpingmebuilda
wholeviewofthedevelopmentofthetensoreigenproblemsandgivingmealotofadvice
onthissubject.SpecialthanksgotoProfessorZhonggangZeng,withouthisencouragement
onimplementingaMATLABversionofHOM4PS2.0,ProfessorLixingHanwouldhavenot
beenabletousandwewouldnothavethischancetoworkonsuchawonderfulproject.
IwanttotakethisopportunitytothankthosefriendswithwhomIhavesharedlaughters
andtears,upsanddowns:YuChenandJunshanLin,forbeingsuchreliablefriends;Hongli
Gao,forbeingaproblem-solver;QinfengGao,forbeingsohumorousandmakinglifeso
joyful;XianfengHu,forbeingsuchafantasticcook;QiTangandZixuanWang,forsharing
somuchtogether;XinYang,foralwaysstudyingdiligentlyandmotivatingme;QiongZheng,
iv
forhavingsuchawonderfulchancetobefriendstoyou.
Lastbutnotleast,Ioweadebtofthankstomyfamily,whosealwaysbeingtherehas
beenlightingupmywayawayfromhomeandbackintohome.
v
TABLEOFCONTENTS
LISTOFTABLES
....................................
vii
Chapter1Introduction
...............................
1
Chapter2Tensoreigenvaluesandeigenvectors
................
4
2.1ofgeneralizedmode-
k
tensoreigenvalueandeigenvectors.....4
2.2Propertiesofgeneralizedmode-
k
tensoreigenvalues..............8
Chapter3Theupperboundofthenumberofequivalenceclassesoftensor
eigenpairs
.................................
12
3.1Introduction....................................12
3.2Preliminaries...................................13
3.3MainTheorembasedonBernstein'sTheorem.................15
Chapter4Computingcomplextensoreigenpairsbyhomotopymethods26
4.1Usinghomotopycontinuationmethodstosolvepolynomialsystems.....26
4.2Constructionofalinearhomotopytosolvetensoreigenpairs.........31
4.3Numericalalgorithmsofusinghomotopycontinuationmethodstosolvetensor
eigenpairs.....................................37
Chapter5Computingrealtensoreigenpairsbyhomotopymethods
...
41
5.1UsingNewtonhomotopymethodtorealtensoreigenpairs........41
5.2Astraightforwardapproachtorealtensoreigenpairs...........45
5.3AnumericalalgorithmofrealtensoreigenpairsbasedontheNewton
homotopyandthestraightforwardapproach..................53
Chapter6Implementationandnumericalresults
...............
54
6.1Examplesforcomputingcomplexeigenpairs..................55
6.2Computingsingulartensoreigenpairs......................59
6.3ExamplesforComputingRealEigenpairs....................64
APPENDIX
........................................
68
BIBLIOGRAPHY
....................................
77
vi
LISTOFTABLES
Table5.1:IsolatedZ-eigenpairsofthetensorinExample5.2.1.........46
Table6.1:Comparisonof
teig
and
eeig
with
PSOLVE
and
NSolve
.......57
Table6.2:Performanceof
teig
oncomputingQi-eigenpairsofcomplexrandom
tensors..................................57
Table6.3:Performanceof
eeig
oncomputingE-eigenpairsofcomplexrandom
tensors..................................58
Table6.4:Performanceof
teig
and
teneig
oncomputinggeneralizedeigenpairs
ofcomplexrandomtensors.......................59
Table6.5:EigenpairsofthetensorinExample6.2.1...............61
Table6.6:Z-eigenpairsofthetensorinExample6.3.1..............65
Table6.7:H-eigenpairsofthetensorinExample6.3.1..............65
Table6.8:
zeig
vsAlgorithm3.6([12]):CPUtime................66
Table6.9:Z-eigenvaluesofthetensorinExample6.3.3(*denotesthattheCPU
timeusedbyAlgorithm3.6([12])whenitthethreelargest
Z-eigenvalues)..............................67
TableA.1:Z-eigenpairsofthetensorinProblem1................69
TableA.2:Z-eigenvaluesofthetensorinProblem3................70
TableA.3:Z-eigenvaluesofthetensorinProblem4................71
TableA.4:Z-eigenpairsofthetensorinProblem5................72
TableA.5:Z-eigenpairsofthetensorinProblem7................73
TableA.6:Z-eigenpairsofthetensorinProblem8................73
TableA.7:Z-eigenpairsofthetensorinProblem9................74
vii
TableA.8:Z-eigenpairsofthetensorinProblem10................75
TableA.9:Z-eigenpairsofthetensorinProblem11................75
TableA.10:Z-eigenpairsofthetensorinProblem12................76
viii
Chapter1
Introduction
EigenvaluesoftensorswereintroducedbyQi[35]andLim[29]in2005.Sincethen,tensor
eigenvalueshavefoundapplicationsinautomaticcontrol,statisticaldataanalysis,
tensorimaging,imageauthenticityvn,spectralhypergraphtheory,andquantum
entanglement,etc.,seeforexample,[7,10,21,35,36,38,39,40]andthereferencestherein.
Thetensoreigenvalueproblemhasbecomeanimportantsubjectofnumericalmultilinear
algebra.
Variousofeigenvaluesfortensorshavebeenproposedintheliterature,includ-
ingE-eigenvaluesandeigenvaluesinthecomplexandZ-eigenvalues,H-eigenvalues,and
D-eigenvaluesinthereal[29,35,38].In[6],Chang,Pearson,andZhangintroduceda
notionofgeneraleigenvaluesfortensorsthatseveraltypesofeigenvalues.Recently
thishasbeenfurthergeneralizedbyCui,Dai,andNie[12].
Unlikethematrixeigenvalueproblem,computingeigenvaluesofthethirdorhigherorder
tensorsisstillinitsinfancy[18].Severalalgorithmswhichaimatcomputingoneorsome
eigenvaluesofatensorhavebeendevelopedrecently.Thesealgorithmsaredesignedfor
tensorsofcertaintype,suchasentry-wisenonnegativeorsymmetrictensors.
Fornonnegativetensors,Ng,Qi,andZhou[33]proposedapower-typemethodforcom-
putingthelargestH-eigenvalueofanonnegativetensor.MoversionsoftheNi-Qi-Zhou
methodhavebeenproposedin[31,48,49].
Forrealsymmetrictensors,Hu,Huang,andQi[20]proposedasequential
1
programmingmethodforcomputingextremeZ-eigenvalues.KoldaandMayo[23]proposed
ashiftedpowermethod(SSHOPM)forcomputingoneZ-eigenvalue.Theyhaveimproved
SSHOPMin[24]byupdatingtheshiftparameteradaptively.Theresultingmethodcanbe
usedtocomputearealgeneraleigenvalue.Han[17]proposedanunconstrainedoptimization
methodforcomputingarealgeneraleigenvalueforevenorderrealsymmetrictensors.The
methodsin[17,23,24]canmoreeigenvaluesofasymmetrictensoriftheyareexecuted
multipletimesusingtstartingpoints.Recently,Cui,Dai,andNie[12]proposeda
methodforcomputingallrealgeneralizedeigenvalues.
Inthisarticle,wefocusoncomputing
all
eigenpairsofageneralrealorcomplextensor.
Asindicatedinthenextchapter,eigenpairsofatensoractuallyamountstosolving
asystemofpolynomials.Naturallyonewouldtempttousemethodsinalgebraicgeometry
suchastheoebnerbasismethodandresultantmethod[9]forthispurpose.Thesemethods
canobtainsymbolicsolutionsofapolynomialsystem,whichareaccurate.However,they
areexpensiveintermsofcomputationalcostandstoragerequirement.Moreover,they
aretobeparallelized.Aclassofnumericalmethods,thehomotopycontinuation
methods,canreleasetheseshortcomings.Duringthepastfewdecades,remarkableprogresses
havebeenmadeonhomotopycontinuationmethodsforsolvingpolynomialsystems,seefor
example,[3,26,27,32,41].
Inthisthesiswewillcomputecomplexeigenpairsofgeneraltensorsbyusinghomotopy
continuationmethodstosolvetheircorrespondingpolynomialsystems.Anattractingfeature
ofthehomotopycontinuationmethodsistheircapabilityofallisolatedsolutionsof
polynomialsystemsandsomesolutionsinthepositivedimensionalsolutioncomponents.We
proposetwohomotopytypealgorithmsforcomputingcomplexeigenpairsofatensor.These
algorithmsallowustoallequivalenceclassesofisolatedeigenpairsofageneraltensor
2
andsomeeigenpairsinpositivedimensionaleigenspaces(ifthereareany).Wealsopresenta
homotopymethodandastraightforwardapproachtocomputerealeigenpairsbasedonthe
availablecomplexeigenpairs.Numericalresultsexhibitedtheenessandof
ourmethods.
Thisdissertationisorganizedasfollows.InChapter2,wemode-
k
generalized
eigenvaluesandeigenvectorswhichextendthematrixrighteigenpairsandlefteigenpairsto
higherordertensors.Somepropertiesofsucheigenpairsareproved.InChapter3,anupper
boundforthenumberofequivalenceclassesofgeneralizedtensoreigenpairsusingmixed
volumeisderived.InChapter4,basedontheboundsderivedinChapter3twohomotopy
methodsarepresentedtocomputemode-
k
generalizedcomplexeigenpairs.InChapter5,
ahomotopymethodandastraightforwardapproachtocomputerealmode-
k
generalized
eigenpairsareproposed.Finally,numericalresultsarepresentedinChapter6.
3
Chapter2
Tensoreigenvaluesandeigenvectors
2.1ofgeneralizedmode-
k
tensoreigenvalue
andeigenvectors
Let
F
=
C
or
R
bethecomplexortherealLet
m

2,
m
0

2,and
n
bepositive
integers.Denotethesetofall
m
th-order,
n
-dimensionaltensorsonthe
F
by
F
[
m;n
]
.A
tensorin
F
[
m;n
]
isindexedas
A
=(
A
i
1
i
2

i
m
)
;
where
A
i
1
i
2

i
m
2
F
,for1

i
1
;i
2
;

;i
m

n
.
For
x
2
C
n
,thetensor
A
ascalarfunction
A
x
m
:=
n
X
i
1
;

;i
m
=1
A
i
1
i
2

i
m
x
i
1
x
i
2

x
i
m
:
(2.1)
For1

k

m
,
A
(
k
)
x
m

1
isan
n
-vectorwhose
j
thentryisas
(
A
(
k
)
x
m

1
)
j
=
n
X
i
1
;

;i
k

1
;i
k
+1
;

;i
m
=1
A
i
1

i
k

1
ji
k
+1

i
m
x
i
1

x
i
k

1
x
i
k
+1

x
i
m
:
(2.2)
When
k
=1,thenotationforthevector
A
(1)
x
m

1
isas
A
x
m

1
.
Arealtensor
A2
R
[
m;n
]
is
positive
ifthescalarfunction
A
x
m
ispositiveforall
4
x
2
R
n
nf
0
g
.Atensor
A2
F
[
m;n
]
is
symmetric
ifitsentries
A
i
1
i
2

i
m
areinvariantunder
anypermutationsoftheirindices
i
1
;i
2
;

;i
m
.Atensor
A2
F
[
m;n
]
iscalledthe
m
th-order
unittensorif
A
i
1
;:::;i
m
=
8
>
<
>
:
1
;
when
i
1
=

=
i
m
0
;
otherwise.
Wenowintroducethefollowingmode-
k
generalizedeigenvalueforageneral
tensor
A
.
DEFINITION2.1.1
Let
A2
F
[
m;n
]
and
B2
F
[
m
0
;n
]
.Assumethat
B
x
m
0
isnotidentically
zero.For
1

k

m
,ifthereexistascalar

2
C
andavector
x
2
C
n
nf
0
g
suchthat

when
m
6
=
m
0
,
A
(
k
)
x
m

1
=

B
x
m
0

1
;
B
x
m
0
=1;(2.3)

when
m
=
m
0
,
A
(
k
)
x
m

1
=

B
x
m

1
;
(2.4)
thenwecall

amode-
k
B
-eigenvalueof
A
and
x
amode-
k
B
-eigenvectorassociatedwith

.
Together
(
x
)
iscalledamode-
k
B
-eigenpairof
A
.
If

2
R
;x
2
R
n
,then

iscalledamode-
k
B
R
-eigenvalueof
A
and
x
amode-
k
B
R
-
eigenvectorassociatedwith

,and
(
x
)
amode-
k
B
R
-eigenpairof
A
.
Denotethesetofallmode-
k
B
eigenvaluesof
A
by
˙
B
(
A
(
k
)
)
.
REMARK2.1.1
Let(
x
)beamode-
k
B
-eigenpairof
A
.By(2.3)or(2.4),(
x
)isa
solutionof
A
(
k
)
x
m

1
=

B
x
m
0

1
,sois(

0
;x
0
)with

0
=
t
m

m
0

and
x
0
=
tx
for
t
2
C
nf
0
g
.
Hencethesolutionspaceof
A
(
k
)
x
m

1
=

B
x
m
0

1
consistsoftequivalenceclasses.
5
Wedenotesuchanequivalenceclassby
[(
x
)]:=
f
(

0
;x
0
)
j

0
=
t
m

m
0
x
0
=
tx;t
2
C
nf
0
gg
:
When
m
6
=
m
0
,takingarbitrary(

0
;x
0
)
2
[(
x
)]andsubstituting
x
0
=
tx
into
B
x
m
0
=1
in(2.3)yields
t
m
0
=1,whichgives
m
0
tvaluesfor
t
.Hencethenormalization
B
x
m
0
=1in(2.3)restrictsthechoicesof
m
0
representativesolutionsfromeachequivalence
class.
Inlaterdiscussions,weoftenchooseonerepresentativefromeachequivalenceclass.
REMARK2.1.2
Ifonlyonerepresentativeisneededfromeachequivalenceclassofeigen-
pairs,wecansolve
A
(
k
)
x
m

1
=

B
x
m
0

1
augmentedwithanadditionallinearequation
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
=0
;
(2.5)
withgenericcomplexnumbers
a
1
;:::;a
n
;b
.Thennormalizetheresultingsolutionstosatisfy
B
x
m
0
=1inthecase
m
6
=
m
0
.
Theeigenvalues/eigenvectorsin[6,12,35,38]aremode-1eigenvalues/eigenvectors.
Thetensorsconsideredinthosepapersareprimarilyrealsymmetrictensors.Forsymmet-
rictensors,thesetsofmode-
k
B
-eigenpairsandmode-1
B
-eigenpairsarethesameforany
k
.Therefore,mode-1eigenvaluesservethepurposeofthosearticles.Nonetheless,non-
symmetrictensorsalsoappearinapplicationsandtheoreticalstudies,see,forexample,
[4,5,14,33,45,46].In[29],Limmode-
k
eigenvalues/eigenvectorsfornonsymmetric
realtensors
A
when
B
isthe
m
0
thorderunittensorforsome
m
0

2.2.1.1
containsmoregeneral
A
and
B
.
6
Asin[6,12],2.1.1adaptsaapproachtotensoreigenvalues.It
coversvarioustypesoftensoreigenvaluesintheliterature,including

If
A2
R
[
m;n
]
,
m
0
=2,and
B
istheidentitymatrix
I
n
2
R
n

n
,themode-1
B
-eigenpairs
aretheE-eigenpairsandthemode-1
B
R
-eigenpairsaretheZ-eigenpairsdin[35],
whichsatisfy
A
x
m

1
=
x
T
x
=1
:
(2.6)

If
A2
R
[
m;n
]
,
m
0
=2and
B
=
D
,where
D
2
R
n

n
isasymmetricpositive
matrix,the
B
R
-eigenpairsaretheD-eigenpairsin[38],whichsatisfy
A
x
m

1
=
x;x
T
Dx
=1
:
(2.7)

If
A2
R
[
m;n
]
,
m
=
m
0
and
B
=
I
istheunittensor,thenmode-1
B
-eigenpairs
in[35]satisfying
A
x
m

1
=

[
m

1]
;
(2.8)
where
x
[
m

1]
=[
x
m

1
1
;x
m

1
2
;

;x
m

1
n
]
T
,iscalledaQi-eigenpair.

If
A2
R
[
m;n
]
,
m
=
m
0
and
B
=
I
istheunittensor,thenmode-1
B
R
-eigenvaluesare
theH-eigenvaluesin[35].
7
2.2Propertiesofgeneralizedmode-
k
tensoreigenval-
ues
When
m
=
m
0
=2and
B
=
I
n
(the
n

n
identitymatrix),thenmode-1eigenvectorsare
righteigenvectorsof
A
andmode-2eigenvectorsarelefteigenvectorsof
A
,andthemode-1
andmode-2eigenvaluesaretheeigenvaluesofmatrix
A
,i.e.,
˙
B
(
A
(1)
)=
˙
B
(
A
(2)
).However,
when
m

3,
˙
B
(
A
(
k
)
)and
˙
B
(
A
(
l
)
)arenotequalingeneralwhen
k
6
=
l
,unless
A
hasa
certaintypeofsymmetry.Thefollowingexampleillustratesthis
EXAMPLE2.2.1
Letthetensor
A2
R
[3
;
2]
be
A
111
=1
;A
121
=2
;A
211
=3
;A
221
=4
;
A
112
=5
;A
122
=6
;A
212
=7
;A
222
=0
:
Choose
m
0
=2and
B
=
I
2
(the2

2identitymatrix).Inthiscase,if(
x
)isan
B
-eigenpair
of
A
,sois(



x
).Wefollow[4],taking(
x
)and(



x
)asthesameeigenpair.Then
˙
B
(
A
(1)
)=
f
0
:
4105
;
4
:
3820
;
9
:
8995
g
;
˙
B
(
A
(2)
)=
f
0
:
2851
;
4
:
3536
;
9
:
5652
g
;
˙
B
(
A
(3)
)=
f
0
:
2936
;
4
:
3007
;
9
:
4025
g
:
Clearly,
˙
B
(
A
(
k
)
)
6
=
˙
B
(
A
(
l
)
)when
k
6
=
l
.
PROPOSITION2.2.1
Let
A2
F
[
m;n
]
and
B2
F
[
m
0
;n
]
.If
(
x
)
isamode-
k
B
-eigenpair
and
(
x
)
isamode-
l
B
-eigenpairof
A
suchthat
B
x
m
0
6
=0
,then

=

.
8
Proof
:Since(
x
)isamode-
k
B
-eigenpairof
A
,
A
(
k
)
x
m

1
=

B
x
m
0

1
:
(2.9)
Recallthat
A
(
k
)
x
m

1
isby
A
(
k
)
x
m

1
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
(
A
(
k
)
x
m

1
)
1
.
.
.
(
A
(
k
)
x
m

1
)
j
.
.
.
(
A
(
k
)
x
m

1
)
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
with(
A
(
k
)
x
m

1
)
j
givenby(2.2).Similarly,
B
x
m
0

1
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
(
B
x
m
0

1
)
1
.
.
.
(
B
x
m
0

1
)
j
.
.
.
(
B
x
m
0

1
)
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
;
where
(
B
x
m
0

1
)
j
=
n
X
i
2
;:::;i
m'
=1
B
ji
2
:::i
m'
x
i
2
:::x
i
m'
:
Thenmultiplyingbothsidesof(2.9)by
x
T
fromtheleftyields
x
T
A
(
k
)
x
m

1
=

T
B
x
m
0

1
:
9
By
x
T
A
(
k
)
x
m

1
=
A
x
m
and
x
T
B
x
m
0

1
=
B
x
m
0
.So
A
x
m
=

B
x
m
0
:
Similarly,(
x
)isamode-
l
B
-eigenpairof
A
willimplythat
A
x
m
=

B
x
m
0
.Therefore,

B
x
m
0
=

B
x
m
0
.Henceif
B
x
m
0
6
=0,then

=

.
2
Let
A2
F
[
m;n
]
.For1

k<l

m
,tensor
G2
F
[
m;n
]
issaidtobethe
h
k;l
i
transpose
of
A
if
G
i
1

i
k

1
i
l
i
k
+1

i
l

1
i
k
i
l
+1

i
m
=
A
i
1

i
k

1
i
k
i
k
+1

i
l

1
i
l
i
l
+1

i
m
;
forall1

i
1
;

;i
m

m
.Denotethe
h
k;l
i
transpose
of
A
by
A
h
k;l
i
.Wesaytensor
A
is
h
k;l
i
partiallysymmetric
if
A
h
k;l
i
=
A
:
Itisclearthatthefollowingpropositionholds.
PROPOSITION2.2.2
Let
A2
F
[
m;n
]
and
B2
F
[
m
0
;n
]
.Assume
B
x
m
0
isnotidentically
zero.Let
k;l
beintegerssuchthat
1

k<l

m
.Then

(
x
)
isamode-
k
B
-eigenpairof
A
ifandonlyifitisamode-
l
B
-eigenpairof
A
h
k;l
i
.

Thesetsofmode-
k
B
-eigenpairsandmode-
l
B
-eigenpairsarethesameif
A
is
h
k;l
i
partiallysymmetric.
Forasymmetrictensor,thefollowingpropositionwasshownin[23].
10
PROPOSITION2.2.3
Let
A2
F
[
m;n
]
beasymmetrictensor.Thenthegradientof
A
x
m
isgivenby
r
(
A
x
m
)=
m
A
x
m

1
:
REMARK2.2.1
Theoreticalpropertiesofmode-1eigenvaluesoftensorssuchasthePerron-
Frobeniustheory([5,14,45,46])fornonnegativetensorscanbeparallellydevelopedfor
mode-
k
eigenvalues.However,asHornandJohnsonannouncedin[19]:"Oneshouldnotdis-
misslefteigenvectorsasmerelyaparalleltheoreticalalternativetorighteigenvectors.Each
typeofeigenvectorcanconveytinformationaboutamatrix,"webelievemode-1
throughmode-
m
eigenpairscanconveytinformationaboutageneraltensoroforder
m

3.
11
Chapter3
Theupperboundofthenumberof
equivalenceclassesoftensor
eigenpairs
Inthischapter,wepresentthederivationofanupperboundforthenumberofequivalence
classesofmode-
k
eigenpairs.
3.1Introduction
Thenumberofequivalenceclassesoftensoreigenpairshasbeendiscussedinmanypapers.
ForQi-eigenvalueproblemsin(2.8),if(
x
)isaQi-eigenpair,sois(
tx
)forany
t
2
C
nf
0
g
.
Qi[35]showedthattheQi-eigenvaluesarerootsofaunivariatepolynomialandproved
thefollowingtheorem.
THEOREM3.1.1
Let
A2
R
[
m;n
]
beasymmetrictensorand
m
beaneveninteger.Then
A
hasexactly
n
(
m

1)
n

1
Qi-eigenvalues.
ForE-eigenvalueproblemsasin(2.6),thefollowingtheoremwasprovedin[4]
usingtechniquesfromtoricvariety[11,15].
12
THEOREM3.1.2
Ifatensor
A2
C
[
m;n
]
hasmanyequivalenceclassesofE-
eigenpairsover
C
thentheirnumber,countingmultiplicities,isequalto
(
m

1)
n

1
m

2
:
Iftheentriesof
A
aregeneric,thenallmultiplicitiesareequalto1,sothereare
exactly
((
m

1)
n

1)
=
(
m

2)
equivalenceclassesofeigenpairs.
Asin2.1.1,Remark2.1.1andRemark2.1.2,thenumberofequivalenceclasses
ofmode-
k
generalized
B
-eigenpairsforgeneraltensors
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
isequal
tothenumberofisolatedsolutionsofthefollowingsystemofpolynomials
T
(
x
)=
0
B
B
B
B
B
B
B
B
B
@
(
A
(
k
)
x
m

1
)
1


(
B
x
m
0

1
)
1
.
.
.
(
A
(
k
)
x
m

1
)
n


(
B
x
m
0

1
)
n
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
1
C
C
C
C
C
C
C
C
C
A
=0
;
(3.1)
where

and
x
:=(
x
1
;

;x
n
)
T
aretheunknowns,
a
1
;:::;a
n
;b
arerandomcomplexnum-
bers.Wemaythereforeusetheclassicresultsonthenumberofsolutionsofapolynomial
systemtostudythenumberofequivalenceclassesoftensoreigenpairs.
3.2Preliminaries
Intheplace,weintroducesomecommonlyusednotationsandLet
P
(
x
):=
(
p
1
(
x
)
;:::;p
n
(
x
))
T
beapolynomialsystemwith
x
:=(
x
1
;:::;x
n
)
T
.For

:=(

1
;:::;
n
)
2
13
(
Z
n

0
)
T
,write
x

:=
x

1
1

x

n
n
and
j

j
=

1
+

+

n
.Considerthepolynomialsystem
P
(
x
):=
0
B
B
B
B
B
B
B
@
p
1
(
x
):=
P

2
S
1
c
1

x

.
.
.
p
n
(
x
):=
P

2
S
n
c

x

1
C
C
C
C
C
C
C
A
;
(3.2)
where
S
1
;:::;S
n
aregivensubsetsof(
Z
n

0
)
T
and
c

2
C

:=
C
nf
0
g
.Foreach
i
=1
;:::;n
,
S
i
iscalledthesupportof
p
i
(
x
)anditsconvexhull
R
i
:=conv(
S
i
)in
R
n
iscalledtheNewtonpolytopeof
p
i
(
x
).The
n
-tuple(
S
1
;:::;S
n
)iscalledthesupportof
P
(
x
).Forpositivevariables

1
;:::;
n
,let

1
R
1
+

+

n
R
n
bethe
Minkowski
sumof

1
R
1
;:::;
n
R
n
,i.e.,

1
R
1
+

+

n
R
n
:=
f

1
r
1
+

+

n
r
n
j
r
i
2
R
i
;i
=1
;:::;n
g
:
Itwasshownin[8]thatthe
n
-dimensionalvolumeof

1
R
1
+

+

n
R
n
,denotedby
Vol
n
(

1
R
1
+

+

n
R
n
),isahomogeneouspolynomialofdegree
n
in

1
;:::;
n
.The
cotofthemonomial

1

2


n
inthispolynomialiscalledthe
mixedvolume
of
R
1
;:::;R
n
,denotedbyMV
n
(
R
1
;:::;R
n
).Sometimeswecallitmixedvolumeofthesup-
ports
S
1
;:::;S
n
,denotedbyMV
n
(
S
1
;:::;S
n
),orthemixedvolumeof
P
(
x
)ifnoambiguities
exist.Thefollowingtheoremrelatesthenumberofisolatedsolutionsin(
C

)
n
ofapolynomial
systemtoitsmixedvolume.
THEOREM3.2.1
(
Bernstein'sTheorem
)[2]
Thenumberofisolatedzerosin
(
C

)
n
,
countingmultiplicities,ofapolynomialsystem
P
(
x
)=(
p
1
(
x
)
;:::;p
n
(
x
))
T
withsupports
S
1
;:::;S
n
isboundedabovebythemixedvolume
MV
n
(
S
1
;:::;S
n
)
.Moreover,forgeneric
14
choicesofthecoin
p
i
,thenumberofisolatedzerosin
(
C

)
n
isexactlyequalto
MV
n
(
S
1
;:::;S
n
)
.
AlimitationofTheorem3.2.1isthatitonlycountstheisolatedzerosofapolynomial
systemin(
C

)
n
ratherthan
C
n
.Todealwiththisissue,LiandWanggavethefollowing
theorem.
THEOREM3.2.2
[30]
Thenumberofisolatedzerosin
C
n
,countingmultiplicities,ofa
polynomialsystem
P
(
x
)=(
p
1
(
x
)
;:::;p
n
(
x
))
T
withsupports
S
1
;:::;S
n
isboundedaboveby
themixedvolume
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)
.
Thefollowinglemmawasgivenasanexercisein[8].
LEMMA3.2.1
Forapolynomialsystem
P
(
x
)=(
p
1
(
x
)
;:::;p
n
(
x
))
T
withsupports
S
1
=
S
2
=

=
S
n
=
S
,
MV
n
(
S;:::;S
)=
n
!Vol
n
(conv(
S
))
:
Recallthatan
n
-simplexistheconvexhullof
n
+1points
z
1
;:::;z
n
+1
suchthat
z
2

z
1
;:::;z
n
+1

z
1
arelinearlyindependentin(
R
n
)
T
,andbyasimplecomputation
Vol
n
(conv(
z
1
;z
2
;:::;z
n
+1
))=
1
n
!











det
0
B
B
B
B
B
@
z
2

z
1
.
.
.
z
n
+1

z
1
1
C
C
C
C
C
A











:
3.3MainTheorembasedonBernstein'sTheorem
Anupperboundforthenumberofequivalenceclassesofmode-
k
eigenpairswhichgeneralizes
resultsin[4,35]isgiveninthefollowingtheorem.
15
THEOREM3.3.1
Let
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
.Assume
B
x
m
0
isnotidenticallyzero
and
k
isanintegersatisfying
1

k

m
.Assume
A
hasmanyequivalenceclasses
ofmode-
k
B
-eigenpairsover
C
.
(a)If
m
=
m
0
,thenthenumberofequivalenceclassesofmode-
k
B
-eigenpairs,counting
multiplicities,isboundedby
n
(
m

1)
n

1
:
If
A
and
B
aregenerictensors,then
A
hasexactly
n
(
m

1)
n

1
equivalenceclassesof
mode-
k
B
-eigenpairs,countingmultiplicities.
(b)If
m
6
=
m
0
,thenthenumberofequivalenceclassesofmode-
k
B
-eigenpairs,counting
multiplicities,isboundedby
(
m

1)
n

(
m
0

1)
n
m

m
0
:
If
A
and
B
aregenerictensors,then
A
hasexactly
((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)
equivalenceclassesofmode-
k
B
-eigenpairs,countingmultiplicities.
Proof
:Asmentionedbefore,thenumberofequivalenceclassesofmode-
k
B
-eigenpairsof
A
is
equaltothenumberofsolutionsof(3.1).Fortherandomhyperplane
a
1
x
1
+

+
a
n
x
n
+
b
=0
in(3.1),wesupposewithoutloss,
a
n
6
=0.Then
x
n
=
c
1
x
1
+

+
c
n

1
x
n

1
+
d;
(3.3)
where
c
i
=

a
i
=a
n
for
i
=1
;:::;n

1and
d
=

b=a
n
,andthenumberofsolutionsof(3.1)in
C
n
+1
isthesameasthenumberofsolutionsin
C
n
oftheresultingsystem
T

(
x
1
;:::;x
n

1
)
16
bysubstituting(3.3)intothe
n
equationsof(3.1).Let
z
:=(
x
1
;:::;x
n

1
)andlet
thesupportsof
T

be
S
1
;:::;S
n
.Weclaimthat
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)=
8
>
>
<
>
>
:
n
(
m

1)
n

1
;m
=
m
0
(
m

1)
n

(
m
0

1)
n
m

m
0
;m
6
=
m
0
:
(3.4)
Asaconsequence,when
N
isthenumberofequivalenceclassesofmode-
k
B
-eigenpairsof
A
over
C
,then
N

n
(
m

1)
n

1
for
m
=
m
0
and
N

(
m

1)
n

(
m
0

1)
n
m

m
0
for
m
6
=
m
0
.When
A
and
B
aregeneric,theaboveequalityholdsbyTheorem3.2.1and
Theorem3.2.2.
Toprove(3.4),let

A2
C
[
m;n
]
and

B2
C
[
m
0
;n
]
begenerictensors.Similarto(3.1)the
polynomialsystemcorrespondingtotheeigenproblem

A
(
k
)
x
m

1
=


B
x
m
0

1
is

T
(
x
)=
0
B
B
B
B
B
B
B
B
B
@
(

A
(
k
)
x
m

1
)
1


(

B
x
m
0

1
)
1
.
.
.
(

A
(
k
)
x
m

1
)
n


(

B
x
m
0

1
)
n
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
1
C
C
C
C
C
C
C
C
C
A
=0
:
(3.5)
Since

A
and

B
aregeneric,withoutlossofgeneralityonemayassumeallmonomials
f
x

1
1
x

2
2
:::x

n
n




i
2
Z

0
;
1
+

2
+

+

n
=
m

1
g
17
and
f


1
1
x

2
2
:::x

n
n




i
2
Z

0
;
1
+

2
+

+

n
=
m
0

1
g
willappearineachofthe
n
equationsin(3.5).Therefore,aftersubstituting(3.3)into
the
n
equationsof(3.5),eachequationofthenewsystem

T

(
z
):=

T

(
x
1
;:::;x
n

1
)
containsallmonomials
f
x

1
1
x

2
2
:::x

n

1
n

1




i
2
Z

0
;
1
+

2
+

+

n

1

m

1
g
and
f


1
1
x

2
2
:::x

n

1
n

1




i
2
Z

0
;
1
+

2
+

+

n

1

m
0

1
g
Sothesupports

S
1
;:::;

S
n
of

T

areallequalto

S
:=
f
(0
;
)



2
(
Z
n

1

0
)
T
;
j

j
m

1
g[f
(1
;
)



2
(
Z
n

1

0
)
T
;
j

j
m
0

1
g
:
Let

Q
betheconvexhullof

S
.Thenverticesof

Q
aregivenbythefollowingpointsin(
Z
n
)
T
:
z
0
=(0
;
0
;:::;
0)
;
z
1
=(0
;
0
;:::;
0
;m

1)
;
z
2
=(0
;
0
;:::;
0
;m

1
;
0)
;
.
.
.
z
n

1
=(0
;m

1
;
0
;:::;
0)
;
18
z
n
=(1
;
0
;:::;
0)
;
z
n
+1
=(1
;
0
;:::;
0
;m
0

1)
;
z
n
+2
=(1
;
0
;:::;
0
;m
0

1
;
0)
;
.
.
.
z
2
n

1
=(1
;m
0

1
;
0
;:::;
0)
:
Denotethe
i
-thunitvectorin(
R
n
)
T
by
e
i
for
i
=1
;:::;n
.Then
z
i
=
8
>
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
:
0
;i
=0
(
m

1)
e
n
+1

i
;
1

i

n

1
e
1
;i
=
n
e
1
+(
m
0

1)
e
2
n
+1

i
;n
+1

i

2
n

1
Tocomputethevolumeof

Q
,wedivideitintofollowing
n
simplices

Q
1
:=conv(
z
0
;z
1
;:::;z
n
)
;

Q
2
:=conv(
z
1
;z
2
;:::;z
n
+1
)
;
.
.
.

Q
i
:=conv(
z
i

1
;z
i
;:::;z
n
+
i

1
)
;
.
.
.

Q
n
:=conv(
z
n

1
;z
n
;:::;z
2
n

1
)
:
19
Itfollowsthat
Vol
n
(

Q
1
)=
1
n
!















det
0
B
B
B
B
B
B
B
B
B
@
z
1

z
0
z
2

z
0
.
.
.
z
n

z
0
1
C
C
C
C
C
C
C
C
C
A















=
1
n
!



















det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
(
m

1)
e
n
(
m

1)
e
n

1
.
.
.
(
m

1)
e
2
e
1
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A



















=
(
m

1)
n

1
n
!



















det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
e
n
e
n

1
.
.
.
e
2
e
1
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A



















=
(
m

1)
n

1
n
!











det
0
B
B
B
B
B
@
e
1
.
.
.
e
n
1
C
C
C
C
C
A











=
(
m

1)
n

1
n
!
:
(3.6)
Obviouslythat
z
n
iscontainedineach

Q
i
for
i
=2
;:::;n
,so
Vol
n
(

Q
i
)=
1
n
!



























det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
z
i

1

z
n
z
i

z
n
.
.
.
z
n

1

z
n
z
n
+1

z
n
.
.
.
z
n
+
i

1

z
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A



























=
1
n
!






























det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
(
m

1)
e
n
+2

i

e
1
(
m

1)
e
n
+1

i

e
1
.
.
.
(
m

1)
e
2

e
1
(
m
0

1)
e
n
(
m
0

1)
e
n

1
.
.
.
(
m
0

1)
e
n
+2

i
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A






























:
20
Furthercomputationgives
Vol
n
(

Q
i
)=
1
n
!






























det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@

e
1
(
m

1)
e
n
+1

i
.
.
.
(
m

1)
e
2
(
m
0

1)
e
n
(
m
0

1)
e
n

1
.
.
.
(
m
0

1)
e
n
+2

i
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A






























=
(
m

1)
n

i
(
m
0

1)
i

1
n
!






























det
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@

e
1
e
n
+1

i
.
.
.
e
2
e
n
e
n

1
.
.
.
e
n
+2

i
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A






























=
(
m

1)
n

i
(
m
0

1)
i

1
n
!











det
0
B
B
B
B
B
@
e
1
.
.
.
e
n
1
C
C
C
C
C
A











=
(
m

1)
n

i
(
m
0

1)
i

1
n
!
:
(3.7)
Comparing(3.6)with(3.7),(3.7)actuallyalsoholdsfor
i
=1.Thus
Vol
n
(

Q
)=
n
X
i
=1
Vol
n
(

Q
i
)=
n
X
i
=1
(
m

1)
n

i
(
m
0

1)
i

1
n
!
:
Therefore,byLemma3.2.1
MV
n
(

S
1
;:::;

S
n
)=
n
!Vol
n
(

Q
)=
n
X
i
=1
(
m

1)
n

i
(
m
0

1)
i

1
:
Notethatfor
i
=1
;:::;n
,
S
i
[f
0
gˆ

S
i
.Hence
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)

MV
n
(

S
1
;:::;

S
n
)=
n
X
i
=1
(
m

1)
n

i
(
m
0

1)
i

1
:
21
Consequently,
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)

n
X
i
=1
(
m

1)
n

1
=
n
(
m

1)
n

1
(3.8)
for
m
=
m
0
and
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)

(
m

1)
n
m
0

1
n
X
i
=1

m
0

1
m

1

i
=
(
m

1)
n
m
0

1
m
0

1
m

1

1


m
0

1
m

1

n

1

m
0

1
m

1
=(
m

1)
n
1


m
0

1
m

1

n
m

m
0
=
(
m

1)
n

(
m
0

1)
n
m

m
0
(3.9)
for
m
6
=
m
0
.
Ontheotherhand,for
m
=
m
0
,letthediagonaltensors
A2
C
[
m;n
]
and
B2
C
[
m;n
]
be
suchthat
A
ii:::i
=
i
,
B
ii:::i
=1andallotherentrieszero.Thenthenumberofequivalence
classesofmode-
k
B
-eigenpairsof
A
isequaltothenumberofsolutionstothefollowing
systemofpolynomials
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
x
m

1
1


m

1
1
2
x
m

1
2


m

1
2
.
.
.
nx
m

1
n


m

1
n
x
1
+
x
2
+

+
x
n

1
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=0
:
22
Thezerosofthissystemare(
x
1
;:::;x
n
)=(1
;
1
;
0
;:::;
0),(2
;
0
;
1
;
0
;:::;
0),...,(
n;
0
;:::;
0
;
1)
andeachzerohasmultiplicity(
m

1)
n

1
.ByTheorem3.2.2,
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)

n
(
m

1)
n

1
:
Combiningwith(3.8),wehave
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)=
n
(
m

1)
n

1
:
For
m
6
=
m
0
,considerthediagonaltensors
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
suchthat
A
ii:::i
=1,
B
ii:::i
=1andallotherentriesarezero.Assume
m>m
0
.Thenthenumberof
equivalenceclassesofmode-
k
B
-eigenpairsof
A
isequaltothenumberofsolutionstothe
followingsystemofpolynomials
0
B
B
B
B
B
B
B
B
B
@
x
m

1
1


m
0

1
1
.
.
.
x
m

1
n


m
0

1
n
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
1
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@
x
m
0

1
1
(
x
m

m
0
1


)
.
.
.
x
m
0

1
n
(
x
m

m
0
n


)
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
1
C
C
C
C
C
C
C
C
C
A
=0
;
(3.10)
where
a
1
;:::;a
n
;b
arerandomcomplexnumbers.Obviously
x
=0cannotbeasolution
sinceitfailstosatisfytheaugmentedrandomhyperplane.AsdiscussedinRemark2.1.1,
thehyperplaneisaddedtoensurethatonlyonerepresentativefromeachequivalenceclass
canbeselected.Soweneedtothenumberofequivalenceclassesofeigenpairs(
x
)
fromthe
n
equationsof(3.10).Foreachd

,thereare
m

1choicesforeach
x
i
andamongthosechoices,
m
0

1ofthemarezeros.Excludingthosecombinationswhich
23
make
x
=0,thereare(
m

1)
n

(
m
0

1)
n
choicesfor
x
1
;:::;x
n
intotal.Furthermore,
foreacheigenvalue

,let
x
bethecorrespondingsolutionofthe
n
equationsof(3.10).
Then
tx
with
t
m

m
0
=1isalsoasolutionassociatedwith

.Thusforeacheigenvalue

,
solvingthe
n
equationsof(3.10)resultsin
m

m
0
correspondingsolutionsof
x
.By
Remark2.1.1,these
m

m
0
solutionsareactuallyequivalent.Therefore,thereshouldbe
((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)equivalenceclassesofeigenpairs,i.e.,(3.10)musthave
((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)isolatedzerosin
C
n
+1
intotal.ByTheorem3.2.2,
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)

((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)
:
Combiningtheaboveinequalitywith(3.9)gives
MV
n
(
S
1
[f
0
g
;:::;S
n
[f
0
g
)=((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)
:
2
REMARK3.3.1
(a)ForQi-eigenpairs,wehave
m
0
=
m
.Using(a)inTheorem3.3.1theupperboundof
thenumberofequivalenceclassesofQi-eigenpairsis
n
(
m

1)
n

1
.Thisresultincludes
Theorem3.1.1provedin[35],inwhichthisboundofthenumberofQi-eigenvaluesis
restrictedtoasymmetrictensorwhen
m
iseven.
(b)ForE-eigenpairs,
m
0
=2.Using(b)inTheorem3.3.1theupperboundofthenumber
ofequivalenceclassesofE-eigenpairsis((
m

1)
n

1)
=
(
m

2),whichagreeswith
Theorem3.1.2provedin[4].
24
(c)TheupperboundsprovidedinTheorem3.3.1isveryusefulindesigningeho-
motopymethodsforcomputingmode-
k
generalizedeigenpairs.Infact,thehomotopy
methoddescribedinAlgorithm4.3.1forthecase
m
=
m
0
inthenextchapterrelieson
thebound
n
(
m

1)
n

1
.
25
Chapter4
Computingcomplextensoreigenpairs
byhomotopymethods
Let
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
.AsdiscussedinChapter2,theproblemofcomputingmode-
k
B
-eigenpairsof
A
in(2.3)isequivalenttosolving(3.1),andwhen
m
6
=
m
0
,wenormalize
(
x
)tosatisfy
B
x
m
0
=1.Forpolynomialsystem(3.1),thehomotopycontinuationmethod
iscommonlyusedtoitsnumericalsolutions.
4.1Usinghomotopycontinuationmethodstosolvepoly-
nomialsystems
Thebasicideaofusinghomotopycontinuationmethodtosolveageneralpolynomialsystem
P
(
x
)=(
p
1
(
x
)
;:::;p
n
(
x
))
T
=0asin(3.2)istodeform
P
(
x
)toanotherpolynomial
system
Q
(
x
)withknownsolutionsintheplace.Thenundercertainconditions,asmooth
curvethatemanatesfromasolutionof
Q
(
x
)=0willleadtoasolutionof
P
(
x
)=0.
Fortheclassicallinearhomotopy[1]:
H
(
x;t
)=(1

t
)
Q
(
x
)+
tP
(
x
)=0
;t
2
[0
;
1]
;
(4.1)
where

isagenericnonzerocomplexnumber,if
Q
(
x
)ischosenproperly,thefollowing
26
propertieshold:

Property0
(Triviality)
Thesolutionsof
Q
(
x
)=0areknownoreasytosolve.

Property1
(Smoothness)
Thesolutionsetof
H
(
x;t
)=0for0
<t<
1consistsofa
numberofsmoothpaths,eachcanbeparameterizedby
t
in[0
;
1).

Property2
(Accessibility)
Everyisolatedsolutionof
H
(
x;
1)=
P
(
x
)=0canbe
reachedbysomepathemanatingfromasolutionof
H
(
x;
0)=
Q
(
x
)=0.
Let
d
1
;:::;d
n
bethedegreesofpolynomials
p
1
(
x
)
;:::;p
n
(
x
)respectively.Then
d
1

d
2

d
n
iscommonlyknownasthe
totaldegree
ortheBezoutnumberofthesystem
P
(
x
).Atypicalchoiceofastartingsystem
Q
(
x
)in(4.1)satisfyingProperties0-2is
Q
(
x
):=
0
B
B
B
B
B
@
a
1
x
d
1
1

b
1
.
.
.
a
n
x
d
n
n

b
n
1
C
C
C
C
C
A
;
where
a
1
;:::;a
n
;b
1
;:::;b
n
arerandomcomplexnumbers.Thecorrespondinglinearhomo-
topyisknownasthe
totaldegreehomotopy
,see[27,32,43].Hereallthe
d
1

d
2

d
n
solutionsof
Q
(
x
)=0canbeeasilysolved.Bytracking
d
1

d
2

d
n
numberofsolution
pathsof(4.1)wecanalltheisolatedsolutionsof
P
(
x
)=0.However,mostofthe
polynomialsystemsinapplicationsusuallyhavefarfewerthan
d
1

d
2

d
n
isolated
solutions.Inthiscase,manyofthe
d
1

d
2

d
n
pathswilldivergetoyas
t
!
1
resultinginhugewastefulcomputations.
The
polyhedral
homotopycontinuationmethod[22]basedonBernstein'sTheorem[2]
makesamajoradvanceinthisregard.Forthishomotopy,thenumberofpathsthatneedto
betracedisthe
mixedvolume
ofthepolynomialsystem,whichgenerallyprovidesamuch
27
tighterboundthanBezout'snumberforthenumberofisolatedzerosofthepolynomial
system.Inmostoccasionsthenewmethodsubstantiallyreducestheamountofextraneous
paths.Themethodofusingpolyhedralhomotopycontinuationmethodtosolve
P
(
x
)=
(
p
1
(
x
)
;:::;p
n
(
x
))
T
in(3.2)withsupports
S
1
;:::;S
n
containsthefollowingtwomajorstages
(See[26,27]):
Stage1.
MixedCellComputation.
Foreachsupport
S
i
,let
S
0
i
:=
S
i
[f
0
g
for
i
=1
;:::;n
.
Recallthatthenumberofisolatedzerosof(3.2)in
C
n
isboundedabovebyMV
n
(
S
0
1
;:::;S
0
n
)
byTheorem3.2.2.For
i
=1
;:::;n
,let
w
i
:
S
0
i
!
R
beareal-valuedfunctionofrandomly
chosenimagesandwrite
^
S
0
i
:=
f
^

:=(
;w
j
(

))
j

2
S
0
i
g
.For
^

:=(
;
1)
2
R
n
+1
with

=(

1
;:::;
n
)
T
2
R
n
,let
h
^
;
^

i
betheEuclideaninnerproductof^

and
^

.Acollection
ofpairs(
f

11
;
12
g
;:::;
f

n
1
;
n
2
g
)with
f

i
1
;
i
2
g
S
0
i
for
j
=1
;:::;n
iscalleda
mixed
cell
of
S
0
1
;:::;S
0
n
ifthereexists
^

:=(
;
1)
2
R
n
+1
with

2
R
n
suchthat
h
^

i
1
;
^

i
=
h
^

i
2
;
^

i
<
h
^
;
^

i
;
for

2
S
0
i
nf

i
1
;
i
2
g
;
(4.2)
where

iscalledthe
innernormal
ofthismixedcell.
AllthemixedcellswiththeirinnernormalsinStage1canbefoundbysolvingvarious
linearprogrammingproblems[25].
Stage2.
Constructionofapolyhedralhomotopyandpathtracking.
Foreachmixedcell
(
f

11
;
12
g
;:::;
f

n
1
;
n
2
g
)withinnernormal

satisfying(4.2)foundinStage1,let
d
i
:=min

2
S
0
i
h
^
;
^

i
;i
=1
;:::;n:
28
Constructthefollowingpolyhedralhomotopy
H
(
x;t
)=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
h
1
(
x;t
):=
P

2
S
0
1
((1

t
)
c
1

+
tc
1

)
x

t
h
^
;
^


d
1
.
.
.
h
i
(
x;t
):=
P

2
S
0
i
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
i
.
.
.
h
n
(
x;t
):=
P

2
S
0
n
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=0
;t
2
[0
;
1]
;
(4.3)
whereeach
c

isarandomlychosennonzerocomplexnumberforeach
i
=1
;:::;n
and

2
S
0
i
.Obviouslywhen
t
=1,
H
(
x;
1)=
P
(
x
).When
t
=0,since
h
i
(
x;t
)=
X

2
S
0
i
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
i
=
X

2
S
0
i
h
^
;
^

i
=
d
i
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
i
+
X

2
S
0
i
h
^
;
^

i
>d
i
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
i
=((1

t
)
c

i
1
+
tc

i
1
)
x

i
1
+((1

t
)
c

i
2
+
tc

i
2
)
x

i
2
+
X

2
S
0
i
h
^
;
^

i
>d
i
((1

t
)
c

+
tc

)
x

t
h
^
;
^


d
i
;
wehave
h
i
(
x;
0)=
c

i
1
x

i
1
+
c

i
2
x

i
2
29
foreach
i
=1
;:::;n
.Hence
H
(
x;
0)=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@

c
1

11
x

11
+
c
1

12
x

12
.
.
.

c

i
1
x

i
1
+
c

i
2
x

i
2
.
.
.

c

n
1
x

n
1
+
c

n
2
x

n
2
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=0
:
Thisisabinomialsystemhaving
k

:=det



















0
B
B
B
B
B
B
B
B
B
B
B
B
B
@

11


12
.
.
.

i
1


i
2
.
.
.

n
1


n
2
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A



















nonsingularsolutionsin(
C

)
n
.Averyetandstablenumericalmethodexistsfor
allthosesolutions[27].Startingfromthesesolutionstotracksolutionpathsof(4.3),
wewillreachsomesolutionsof
P
(
x
)=0.tmixedcellswiththeircorresponding
innernormals

willdevotetpolyhedralhomotopies
H
(
x;t
)asin(4.3).These
thomotopieswillreachtisolatedzerosof
P
(
x
)=0asprovedin[27].And
30
thetotalnumberofpathsneededtobetrackedhereis
X

k

=
X

det



















0
B
B
B
B
B
B
B
B
B
B
B
B
B
@

11


12
.
.
.

i
1


i
2
.
.
.

n
1


n
2
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A



















;
whichagreeswiththemixedvolumeMV
n
(
S
0
1
;:::;S
0
n
).
Althoughthepolyhedralhomotopycontinuationmethodusuallyfollowsfewerpathsthan
theclassicallinearhomotopymethod,themixedcellcomputationinvolvedmaybecome
veryexpensiveespeciallyforlargepolynomialsystems.Thusifalinearhomotopycanbe
constructedsothatonlymixedvolumenumberofpathsneedtobetraced,thesystemshould
besolvedbyusingalinearhomotopyinsteadofthepolyhedralhomotopy.
4.2Constructionofalinearhomotopytosolvetensor
eigenpairs
Tosolve(3.1),onecancertainlyusethepolyhedralhomotopycontinuationmethodimple-
mentedinHOM4PS[26],PHCpack[42],PHoM[16],PSOLVE[47](whichisaMATLAB
implementationofHOM4PS),orthetotaldegreehomotopycontinuationmethodimple-
mentedinBertini[3].However,usingthesemethodstosolve(3.1)directlydoesnottake
advantageofthespecialstructuresofatensoreigenproblem.Wewillintroducetwohomo-
topytypealgorithmsherethatutilizesuchstructures.
31
Theorem3.3.1assertsthatthemixedvolumeof(3.1)is
n
(
m

1)
n

1
for
m
=
m
0
and
((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)for
m
6
=
m
0
,whichisfarlessthantheBezout'snumber,
m
n
for
m
=
m
0
,andmax
f
(
m

1)
n
;
(
m
0
)
n
g
for
m
6
=
m
0
.Fromthisstandpoint,weconstruct
alinearhomotopywithwhichonlymixedvolumenumberofpathsneedtobetraced.
Forthislinearhomotopy,theknowledgeofmultihomogeneousBezout'snumber[41]
isrequired.Forapolynomialsystem
P
(
x
)=(
p
1
(
x
)
;:::;p
n
(
x
))
T
in(3.2),where
x
=
(
x
1
;:::;x
n
),wepartitionthevariables
x
1
;:::;x
n
into
k
groups
y
1
=(
x
(1)
1
;:::;x
(1)
l
1
)
;y
2
=
(
x
(2)
1
;:::;x
(2)
l
2
)
;:::;y
k
=(
x
(
k
)
1
;:::;x
(
k
)
l
k
)with
l
1
+

+
l
k
=
n
.Let
d
ij
bethedegreeof
p
i
withrespectto
y
j
for
i
=1
;:::;n
and
j
=1
;:::;k
.ThenthemultihomogeneousBezout's
numberof
P
(
x
)withrespectto(
y
1
;:::;y
k
)isthecotof

l
1
1

l
2
2
:::
l
k
k
intheproduct
n
Y
i
=1
(
d
i
1

1
+

+
d
ik

k
)
:
Thefollowingtheoremwillplayaveryimportantroleinconstructingourlinearhomotopy.
THEOREM4.2.1
[41]
Let
Q
(
x
)
beasystemofpolynomialshavingthesamemultihomoge-
neousstructureas
P
(
x
)
withrespecttocertainpartitionofthevariables
(
x
1
;:::;x
n
)
.Assume
Q
(
x
)=0
hasexactlythemultihomogeneousBezout'snumberofnonsingularsolutionswith
respecttothispartition,andlet
H
(
x;t
)=(1

t
)
Q
(
x
)+
tP
(
x
)=0
;
where
t
2
[0
;
1]
and

2
C

.For

=
re

,Properties1and2holdforallbutmany

.
32
For(3.1),when
m
=
m
0
thefollowingpolynomialsystem
G
(
x
)=
0
B
B
B
B
B
B
B
B
B
@
(
A
(
k
)
x
m

1
)
1


(
B
x
m

1
)
1
.
.
.
(
A
(
k
)
x
m

1
)
n


(
B
x
m

1
)
n
a
1
x
1
+
a
2
x
2
+

+
a
n
x
n
+
b
1
C
C
C
C
C
C
C
C
C
A
=0(4.4)
needstobesolved,where

and
x
:=(
x
1
;

;x
n
)
T
aretheunknowns,
a
1
;:::;a
n
;b
are
randomlychosencomplexnumbers.Considerthesystem
Q
(
x
)=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
(



1
)(
x
m

1
1


1
)
(



2
)(
x
m

1
2


2
)
.
.
.
(



n
)(
x
m

1
n


n
)
c
1
x
1
+
:::c
n
x
n
+
d
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=0
;
(4.5)
where
d
aswellas

i
;
i
;c
i
for
i
=1
;:::;n
aregenericnonzerocomplexnumbers.
THEOREM4.2.2
For
G
(
x
)
and
Q
(
x
)
givenabove,allisolatedzeros
(
x
)
of
G
(
x
)
in
C
n
+1
canbefoundbythehomotopy
H
(
x;t
)=(1

t
)
Q
(
x
)+
tG
(
x
)=0
;t
2
[0
;
1](4.6)
foralmostall

2
C

.
Proof
:Evidently,withrespecttothepartition(

)and(
x
1
;x
2
;:::;x
n
)ofthevariables
(
x
1
;x
2
;:::;x
n
),bothsystems(4.4)and(4.5)havedegree1in(

)anddegree
m

1in
33
(
x
1
;x
2
;:::;x
n
)forthe
n
equations,anddegree0in(

)anddegree1in(
x
1
;x
2
;:::;x
n
)
forthelastequation.Hence(4.4)and(4.5)havethesamemultihomogeneousBezout's
number,thatisthecotof

1

n
2
intheproduct
[1


1
+(
m

1)

2
]
n
(0


1
+1


2
)
;
whichis
0
B
@
n
1
1
C
A
(
m

1)
n

1
=
n
(
m

1)
n

1
:
Wenowshow
Q
(
x
)in(4.5)hasexactly
n
(
m

1)
n

1
zeros.Intheplace,if

is
equaltononeof

1
;:::;
n
,then(4.5)becomesasystemof
n
+1equationsand
n
unknowns,
whichisoverdeterminedwithgenericcots.Itthereforehasnosolutions.Thus

must
beequaltooneof

1
;:::;
n
.Assume

=

1
,then
x
1
;:::;x
n
canbedeterminedby
x
m

1
2


2
=0
.
.
.
x
m

1
n


n
=0
c
1
x
1
+
:::c
n
x
n
+
d
=0
Obviously,each
x
i
for
i
=2
;:::;n
canbechosenasoneofthe(
m

1)-throotof

i
and
x
1
canbesolvedbysubstitutingthechosen
x
2
;:::;x
n
intothelastequation.Sothereare
(
m

1)
n

1
solutionscorrespondingto

=

1
.Thisargumentholdsfor

beinganyofthe

i
's.Therefore,thereare
n
(
m

1)
n

1
solutionsintotal.
Itremainstoprovethateachsolutionof
Q
(
x
)=0in(4.5)isnonsingular.Asdiscussed
34
above,anysolution(


;x

)of(4.5)


=

i
(
x

1
)
m

1


1
=0
.
.
.
(
x

i

1
)
m

1


i

1
=0(4.7)
(
x

i
+1
)
m

1


i
+1
=0
.
.
.
(
x

n
)
m

1


n
=0
c
1
x

1
+

+
c
n
x

n
+
d
=0
Let
DQ
(
x
)betheJacobianof
Q
(
x
)at(
x
).Fornonsingularityof
DQ
(


;x

),let
A
j
(
x
):=
x
m

1
j


j
;B
j
(
x
):=(



j
)(
m

1)
x
m

2
j
35
for
j
=1
;:::;n
.Then
DQ
(
x
)=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
A
1
B
1
.
.
.
.
.
.
A
i

1
B
i

1
A
i
B
i
A
i
+1
B
i
+1
.
.
.
.
.
.
A
n
B
n
0
c
1
:::c
i

1
c
i
c
i
+1
:::c
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
:
With
A
j
(


;x

)=(
x

j
)
m

1


j
=0
;j
6
=
i
and
B
i
(


;x

)=(




i
)(
m

1)(
x

i
)
m

2
=(

i


i
)(
m

1)(
x

i
)
m

2
=0
;
36
wehave,by(4.7),
DQ
(


;x

)=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
0
B

1
.
.
.
.
.
.
0
B

i

1
A

i
0
0
B

i
+1
.
.
.
.
.
.
0
B

n
0
c
1
:::c
i

1
c
i
c
i
+1
:::c
n
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
;
where
A

j
:=
A
j
(


;x

)and
B

j
:=
B
j
(


;x

).Itfollowsthat
det(
DQ
(


;x

))=(

1)
i
+1
A

i
(

1)
n
+
i
c
i
Y
j
6
=
i
B

j
6
=0
by(4.7).
2
4.3Numericalalgorithmsofusinghomotopycontinu-
ationmethodstosolvetensoreigenpairs
Theorem4.2.2suggeststhat(4.6)canbeusedtosolve(3.1)when
m
=
m
0
.Write
u
:=(
x
),
then(4.6)becomes
H
(
u;t
)=(1

t
)
Q
(
u
)+
tG
(
u
)=0
;t
2
[0
;
1](4.8)
37
where
Q
and
G
arein(4.5)and(4.4)respectively.
Wenowpresentouralgorithmforcomputingmode-
k
generalizedeigenpairswhen
m
=
m
0
,i.e.,solving(4.4).
ALGORITHM4.3.1
(Computecomplexmode-
k
B
-eigenpairsof
A
,where
A
;
B2
C
[
m;n
]
,
i.e.,solving(4.4).)
Step1.
Computeallsolutionsof
Q
(
u
)
asdin(4.5).
Step2.
Pathfollowing:Followthepathsfrom
t
=0
to
t
=1
usingtheprediction-
correctionstrategy.Let
(
u
k
;t
k
):=(
u
(
t
k
)
;t
k
)
.Forthenextpoint
(
u
k
+1
;t
k
+1
)
onthe
solutionpathof
H
(
u;t
)=(1

t
)
Q
(
u
)+
tG
(
u
)=0
;t
2
[0
;
1]
asdin(4.8),thefollowingstepsareemployed:

PredictionStep:Computethetangentvector
du
dt
to
H
(
u;t
)=0
at
t
k
bysolvingthe
linearsystem
H
u
(
u
k
;t
k
)
du
dt
=

H
t
(
u
k
;t
k
)
for
du
dt
.Thencomputetheapproximation
~
u
to
u
k
+1
by
~
u
=
u
k
+
t
du
dt
;t
k
+1
=
t
k
+
t;
where

t
isthestepsize.Here
u
0
ischosentobeonesolutionof
Q
(
u
)=0
.

CorrectionStep:UseNewton'siterations,i.e.,for
i
=0
;
1
;
2
;:::
,compute
v
i
+1
=
v
i

[
H
u
(
v
i
;t
k
+1
)]

1
H
(
v
i
;t
k
+1
)
with
v
0
=~
u
38
until
k
H
(
v
J
;t
J
)
k
isverysmall.Thenlet
u
k
+1
=
v
J
.
Step3.
Endgame.When
t
N
isverycloseto1,thecorresponding
u
N
shouldbevery
closetoazero
u

of
G
(
u
)=
G
(
x
)
.SoNewton'siterations
u
(
k
+1)
=
u
(
k
)

[
DG
(
u
(
k
)
)]

1
G
(
u
(
k
)
)
;k
=0
;
1
;:::
willbeusedagaintorourapproximation
~
u
to
u

.If
DG
(
u

)
isnonsingular,then
~
u
willbeaverygoodapproximationof
u

withmultiplicity1.If
DG
(
u

)
issingular,
~
u
is
eitheranisolatedsingularzeroof
G
(
u
)
withmultiplicity
l>
1
orinapositivedimensional
solutioncomponentof
G
(
u
)=0
.WeuseastrategyprovidedinChapterVIIIof[27](see
also[41])todeterminewhether
~
u
isanisolatedzerowithmultiplicity
l>
1
orinapositive
dimensionalsolutioncomponentof
G
(
u
)=0
.
Step4.
Foreachsolution
u
=(
x
)
obtainedinStep3,normalize
x
with
i
0
:=
argmax
1

i

n
j
x
i
j
:
y
=
x
x
i
0
(4.9)
aneweigenpair
(
y
)
isobtained,sinceasmentionedin(2.4)andRemark2.1.1,if
(
x
)
is
aneigenpair,
(
tx
)
for
t
6
=0
isalsoaneigenpair.
REMARK4.3.1
Noticethatif
x
isarealeigenvectorassociatedwitharealeigenvalue

,
tx
forany
t
2
C
nf
0
g
willbeacomplexeigenvectorassociatedwiththesameeigenvalue

.If
atanystageacomplexeigenvectorlike
tx
isobtainedinStep3ofAlgorithm4.3.1,applying
(4.9)to
tx
willgiveanewrealeigenvector.Inthisregard,Step4isveryhelpfulfordetecting
realeigenpairs.
Tocomputemode-
k
generalizedtensoreigenpairswhen
m
6
=
m
0
,weusetheequivalence
39
classstructureoftheeigenproblemasdescribedinRemark2.1.1.Wesolve(3.1)by
PSOLVE[47]toarepresentative(
x
)fromeachequivalenceclassandthenall
m
0
eigenpairsfromeachequivalenceclassbysimplyusing

0
=
t
m

m
0
x
0
=
tx
,where
t
isa
rootof
t
m
0
=1.
Onemaysolve(2.3)directlyfor
m
0
eigenpairsfromeachequivalenceclass.However,
thisalternativemustfollow
m
0
timesmorepathsthantheaboveapproachcostingmore
computations.
Wenowpresentouralgorithmforcomputingmode-
k
generalizedeigenpairswhen
m
6
=
m
0
,i.e.,solving(2.3).
ALGORITHM4.3.2
(Computecomplexmode-
k
B
-eigenpairsof
A
,where
A2
C
[
m;n
]
;
B2
C
[
m
0
;n
]
with
m
6
=
m
0
,i.e.,solving(2.3).)
Step1.
UsingPSOLVEtogetallsolutions
(
x
)
of(3.1).
Step2.
Foreach
(
x
)
obtainedinStep1,if
B
x
m
0
6
=0
,normalizeittogetaneigenpair
(


;x

)
by


=

(
B
x
m
0
)
(
m

m
0
)
=m
0
;x

=
x
(
B
x
m
0
)
1
=m
0
tosatisfy(2.3).
Step3.
Compute
m
0
equivalenteigenpairs
(

0
;x
0
)
of
(


;x

)
by

0
=
t
m

m
0


and
x
0
=
tx

with
t
beingarootof
t
m
0
=1
.
40
Chapter5
Computingrealtensoreigenpairsby
homotopymethods
Insomeapplications,tensor
A
isrealandonlyrealeigenpairs(orrealeigenvalues)of
A
areofinterest([12,35]).Inthissituation,onlyrealzerosofthepolynomialsystem(2.3)or
(4.4)areneeded.Currentlythereisnoeemethodtoallrealzerosofapolynomial
systemdirectly.
5.1UsingNewtonhomotopymethodtorealten-
soreigenpairs
Forarealtensor
A
,arealeigenvaluemayhavecomplexeigenvectors.Toidentifyreal
eigenvalues,wemaycomputecomplexzeros(
x
)of(4.4)byAlgorithm4.3.1or(2.3)
byAlgorithm4.3.2,thenclassifytherealeigenvaluesbycheckingthesizeoftheirimaginary
parts.Sp,let(


;x

)beacomputedeigenpair.If
j
Im(


)
j
<
0
;
withthreshold

0
>
0,thenRe(


)willbetakenasarealeigenvalue.
Foraspoccasion,when
m
6
=
m
0
,if
m
0
m

m
0
isanonzerointegermultipleof4(for
41
example,
m
=5
;m
0
=4or
m
=10
;m
0
=8,)and
A
hasaneigenpair(


;x

)withapurely
imaginaryeigenvalue


=
bi
,where
b
2
R
,thenonecaneasilyshowthat(
b;
(

i
)
1
=
(
m

m
0
)
x

)
and(

b;i
1
=
(
m

m
0
)
x

)areeigenpairswithrealeigenvalues.Therefore,when
m
0
m

m
0
isa
nonzerointegermultipleof4,if(


;x

)isaneigenpairfoundbyAlgorithm4.3.2suchthat
j
Re(


)
j
<
0
;
thenwetakeIm(


)and

Im(


)asrealeigenvalues,withcorrespondingeigenvectors
(

i
)
1
=
(
m

m
0
)
x

and
i
1
=
(
m

m
0
)
x

.
Whenlookforrealtensoreigenpairs(i.e.,botheigenvaluesandeigenvectorsarereal),
thesituationbecomesmorecomplicated.Weproposeatwo-stepprocedure.First,compute
complexzeros(
x
)of(4.4)byAlgorithm4.3.1or(2.3)byAlgorithm4.3.2.Thenextract
allrealeigenpairs(
x
)fromthezerosjustcalculated.
Forvector
a
=(
a
1
;:::;a
n
)
T
2
C
n
,let
Im(
a
)=(Im(
a
1
)
;:::;
Im(
a
n
))
T
;
Re(
a
)=(Re(
a
1
)
;:::;
Re(
a
n
))
T
:
Suppose(


;x

)isaneigenpairfoundinthestep.Therearepossiblytwocases:(i)
(


;x

)isanisolatedeigenpair;(ii)(


;x

)isaneigenpaircontainedinapositivedimen-
sionalsolutioncomponentofsystem(4.4)or(2.3).
When(


;x

)isanisolatedeigenpair,take(Re(


)
;
Re(
x

))asarealeigenpairif
k
Im(


;x

)
k
2
<
0
:
If(


;x

)isaneigenpairinapositivedimensionalsolutioncomponentofsystem(4.4)
42
or(2.3),ingeneralrealeigenvectorsinducedbywhicharenotwarrantedevenifthecorre-
spondingeigenvalue


isreal.Inthiscase,weusethefollowingNewtonhomotopy[1]
H
(
x;t
):=
P
(
x
)

(1

t
)
P
(


;
Re(
x

))
;t
2
[0
;
1](5.1)
tofollowhomotopycurvesof
H
(
x;t
)=0in(
x
)
2
R
n
+1
forarealeigenpair.Notice
thatwhenfollowingcurvesinthecomplexspaceitisprovedin[27]thatthesolutioncurves
of(5.1)canbeparameterizedby
t
,butthesolutioncurvesof(5.1)maynotbeafunction
of
t
whenrestrictedintherealspace.Soadtmethodtofollowcurvesisneeded.In
thiscaseparameterizingthesolutioncurvesbythearclength
s
issuggestedin[27].For
simplicity,write
y
(
s
):=(

(
s
)
;x
(
s
)
;t
(
s
)),then(5.1)becomes
H
(
y
(
s
))=0.
Wenowsummarizeouralgorithmforcomputingarealeigenpairfromacomplexeigenpair
(


;x

)withreal


,whichisinapositivedimensionalsolutioncomponentof(4.4)or(2.3).
ALGORITHM5.1.1
(Tracesolutionpathsof(5.1)intherealspacetogetarealeigen-
pair.)
Step1.
Let
y
k
:=
y
(
s
k
)
andlet
y
0
=(


;
Re(
x

))
,tothenextpointonthesolution
pathof
H
(
y
)=0
,weusethefollowingstrategy:

PredictionStep:Computethetangentvector
dy
ds
to
H
(
y
)=0
at
y
k
bysolvingthe
system
DH
(
y
k
)
dy
ds
=0




dy
ds




2
=1
for
dy
ds
.Here
DH
(
y
k
)
istheJacobianof
H
withrespectto
y
evaluatedat
y
k
.Then
43
computetheapproximation
~
y
to
y
k
+1
by
~
y
=
y
k
+
s
dy
ds
;s
k
+1
=
s
k
+
s;
where

s
isastepsize.

CorrectionStep:UseNewton'siterationstosolve
˘
from
F
(
˘
):=
0
B
@
H
(
˘
)
(
˘

~
y
)

dy
ds
1
C
A
=0
withtheinitialpoint
˘
0
=~
y
,i.e.,for
i
=0
;
1
;
2
;:::
,compute
˘
i
+1
=
˘
i

[
DF
(
˘
i
)]

1
F
(
˘
i
)
until
k
F
(
˘
J
)
k
islessthanathresholdforsome
J
.Thenlet
y
k
+1
=
˘
J
.
Step2.
Endgame.DuringStep1ifaftermanyPrediction-CorrectionSteps
t
doesnotapproach1,thentheschemecannotprovidearealeigenpair,stop.Otherwise
when
t
(
s
N
)
isverycloseto1forsome
N
,thecorresponding
(

(
s
N
)
;x
(
s
N
))
isverycloseto
arealzero
u
R
:=(

R
;x
R
)
of
P
(
u
):=
P
(
x
)
.SoNewton'siterations
u
(
k
+1)
=
u
(
k
)

[
DP
(
u
(
k
)
)]

1
P
(
u
(
k
)
)
;k
=0
;
1
;:::
with
u
(0)
=(

(
s
N
)
;x
(
s
N
))
willbeemployedtorourapproximation
~
u
to
u
R
.Take
~
u
asarealeigenpair.
44
5.2Astraightforwardapproachtorealtensoreigen-
pairs
Aninterestingphenomenonisthatinsomespecialcases,therealeigenpairscanbeobtained
inamorestraightforwardmannerfromthecomplexeigenpairsfoundbyAlgorithm4.3.1or
Algorithm4.3.2,asillustratedinthefollowingexample.
EXAMPLE5.2.1
Letthetensor
A2
R
[3
;
5]
(Example4.11in[12],seealso[34])begiven
by
A
i;j;k
=
(

1)
i
i
+
(

1)
j
j
+
(

1)
k
k
;i;j;k
=1
;:::;
5
:
WewanttheZ-eigenpairsof
A
.Thecorrespondingpolynomialsystemtosolveis

3
x
2
1

3
x
1
x
2

25
6
x
1
x
3

7
2
x
1
x
4

22
5
x
1
x
5

7
6
x
2
x
3

1
2
x
2
x
4

7
5
x
2
x
5

7
6
x
2
3

13
6
x
3
x
4

181
60
x
3
x
5

1
2
x
2
4

19
10
x
4
x
5

7
5
x
2
5


1
=0

3
2
x
2
1

7
6
x
1
x
3

1
2
x
1
x
4

7
5
x
1
x
5
+
3
2
x
2
2
+
4
3
x
2
x
3
+
5
2
x
2
x
4
+
8
5
x
2
x
5

1
6
x
2
3
+
5
6
x
3
x
4

1
15
x
3
x
5
+
x
2
4
+
11
10
x
4
x
5
+
1
10
x
2
5


2
=0

7
3
x
2
1

5
3
x
1
x
2

10
3
x
1
x
3

13
6
x
1
x
4

46
15
x
1
x
5
+
2
3
x
2
2

1
3
x
2
x
3
+
5
6
x
2
x
4

1
15
x
2
x
5

x
2
3

5
6
x
3
x
4

26
15
x
3
x
5
+
1
6
x
2
4

17
30
x
4
x
5

11
15
x
2
5


3
=0

7
4
x
2
1

1
2
x
1
x
2

13
6
x
1
x
3

x
1
x
4

19
10
x
1
x
5
+
5
4
x
2
2
+
5
6
x
2
x
3
+2
x
2
x
4
+
x
2
x
5

5
12
x
2
3
+
1
3
x
3
x
4

17
30
x
3
x
5
+
3
4
x
2
4
+
3
5
x
4
x
5

3
20
x
2
5


4
=0

11
5
x
2
1

7
5
x
1
x
2

46
15
x
1
x
3

19
10
x
1
x
4

14
5
x
1
x
5
+
4
5
x
2
2

1
15
x
2
x
3
+
11
10
x
2
x
4
+
1
5
x
2
x
5

13
15
x
2
3

17
30
x
3
x
4

22
15
x
3
x
5
+
3
10
x
2
4

3
10
x
4
x
5

3
5
x
2
5


5
=0
x
2
1
+
x
2
2
+
x
2
3
+
x
2
4
+
x
2
5

1=0
45
Writetheabovepolynomialsystemas
P
(
x
)=0.UsingAlgorithm4.3.2,62solutions
ofthissystemarefound.Amongthem,4areisolatedsolutionswith
k
(Im(

)
;
Im(
x
)
k
assmall
asthemachineepsilon.Therefore,theseisolatedzeroscanbeastheZ-eigenpairs.
Notethatinthisexampleif(
x
)isaneigenpair,thensois(



x
).Table5.1liststwo
ofthesefourZ-eigenpairswithpositive

.

4
:
2876
9
:
9779
x
1

0
:
1859

0
:
7313
x
2
0
:
7158

0
:
1375
x
3
0
:
2149

0
:
4674
x
4
0
:
5655

0
:
2365
x
5
0
:
2950

0
:
4146
Table5.1:IsolatedZ-eigenpairsofthetensorinExample5.2.1
Fortheremaining58solutionsof
P
(
x
)=0,eachofthemhas

=0andiscontained
inapositivedimensionalsolutioncomponentof
P
(
x
)=0.Foreachofthesezeros,it
canbevthat(

Re(
x
)
=
k
Re(
x
)
k
2
)and(

Im(
x
)
=
k
Im(
x
)
k
2
)arebothsolutionsof
P
(
x
)=0.Forexample,oneofthese58zerosis
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@

x
1
x
2
x
3
x
4
x
5
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
0

0
:
7136

0
:
4086
i

0
:
1425

0
:
0266
i
0
:
9941

0
:
2291
i

0
:
0180+0
:
1180
i

0
:
1200+0
:
5464
i
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
:
46
Takingtherealandimaginarypartsoftheabove
x
andlet
˘
=(

0
:
7136
;

0
:
1425
;
0
:
9941
;

0
:
0180
;

0
:
1200)
T
;

=(

0
:
4086
;

0
:
0266
;

0
:
2291
;
0
:
1180
;
0
:
5464)
T
:
Normalizing
˘
and

respectivelygives
v
=(

0
:
5764
;

0
:
1151
;
0
:
8030
;

0
:
0146
;

0
:
0969)
T
;
w
=(

0
:
5599
;

0
:
0365
;

0
:
3139
;
0
:
1617
;
0
:
7487)
T
:
Simplecomputationshows
k
P
(0
;v
)
k
2
ˇ
5
:
8687

10

14
and
k
P
(0
;w
)
k
2
ˇ
5
:
4921

10

14
.
Therefore,(0
;v
)and(0
;w
)arebothZ-eigenpairs.Accordingly(

Re(
x
)
=
k
Re(
x
)
k
2
)and
(

Im(
x
)
=
k
Im(
x
)
k
2
)aretwoZ-eigenpairs.
Theaboveexamplesuggeststhatif(


;x

)isinapositivedimensionalsolutioncompo-
nentof(2.3)and


2
R
,then(


;
Re(
x

)
=
k
Re(
x

)
k
2
)and(


;
Im(
x

)
=
k
Im(
x

)
k
2
)maybe
mode-
k
B
R
eigenpairsof
A
.Thisprovidesastraightforwardapproachtorealeigenpairs
fromeigenpairsbelongtopositivedimensionalcomponents.Actually,thisapproachhas
beenquitesuccessfulforalltheexamples(e.g.,Example4.8,4.11,4.13,4.14)in[12]when
arealZ-eigenvaluehasitelymanyrealZ-eigenvectors.
Thisleadstothequestion:whatisthestructureoftheeigenspace
f
x
2
C
n
jA
x
m

1
=


B
x
m
0

1
;
B
x
m
0
=1
g
associatedwitharealeigenvalue


?Lookingintotheeigenspace
of


=0inExample5.2.1,i.e.,
f
x
2
C
5
j
P
(0
;x
)=0
g
,allthe58eigenvectorsobtained
fromAlgorithm4.3.2layonthehyperplane
x
1
+
x
2
+
x
3
+
x
4
+
x
5
=0.Thisobservation
stimulatesthefollowingproposition.
47
PROPOSITION5.2.1
Let
A2
R
[
m;n
]
and
B2
R
[
m
0
;n
]
.Let
k
beanintegerwith
1

k

m
,and

2
R
bearealmode-
k
B
eigenvalueof
A
.If
V
:=
f
x
2
C
n
jA
(
k
)
x
m

1
=

B
x
m
0

1
g
isacomplexlinearsubspaceof
C
n
,thenforany
x
=
˘
+

2
V
suchthat
˘;
2
R
n
and
˘
6
=0
;
6
=0
,

When
m
=
m
0
,
˘
and

arebothrealmode-
k
B
eigenvectorsof
A
associatedwith

.

When
m
6
=
m
0
,
B
˘
m
0
6
=0
and
B

m
0
6
=0
,thenormalizedvectors
v
:=
˘
(
B˘
m
0
)
1
=m
0
;w
:=

(
B
m
0
)
1
=m
0
arerealmode-
k
B
eigenvectorsof
A
associatedwith

.
Proof
:Let
x
2
V
.Then
A
(
k
)
x
m

1
=

B
x
m
0

1
:
Takingtheconjugateoftheaboveequationyields

A
(
k
)

x
m

1
=



B

x
m
0

1
:
Since

,
A
and
B
areallreal,
A
(
k
)

x
m

1
=

B

x
m
0

1
:
Itfollowsthat
x
2
V
.Since
V
isalinearsubspace,
˘
=(
x
+
x
)
=
2and

=(
x


x
)
=
(2
i
)are
alsoin
V
.Thus,when
m
=
m
0
,
˘
and

arebothrealmode-
k
B
eigenvectorsof
A
associated
48
with

.If
m
6
=
m
0
,wehave
B
v
m
0
=
n
X
i
1
;

;i
m
0
=1
B
i
1
i
2

i
m
0
v
i
1
v
i
2

v
i
m
0
=
n
X
i
1
;

;i
m
0
=1
B
i
1
i
2

i
m
0
˘
i
1
(
B˘
m
0
)
1
=m
0
˘
i
2
(
B˘
m
0
)
1
=m
0

˘
i
m
0
(
B˘
m
0
)
1
=m
0
=
P
n
i
1
;

;i
m
0
=1
B
i
1
i
2

i
m
0
˘
i
1
˘
i
2

˘
i
m
0
B˘
m
0
=
B˘
m
0
B˘
m
0
=1
:
So
v
isarealmode-
k
B
eigenvectorof
A
associatedwith

.Similarly,
Bw
m
0
=1and
w
is
alsoarealmode-
k
B
eigenvectorof
A
associatedwith

.
2
Consequently,whenZ-eigenpairsof
A2
R
[
m;n
]
areinconcern,let

2
R
bearealE-
eigenvalueof
A
.If
U
:=
f
x
2
C
n
jA
x
m

1
=

g
containsacomplexlinearsubspace
V
,
thenforany
x
=
˘
+

2
V
withnonzero
˘;
2
R
n
and
x
2
V
,
˘=
k
˘
k
2
and
=
k

k
2
areboth
Z-eigenvectorsof
A
associatedwith

.
Anaturalquestioniswhentheeigenspace
U
inProposition5.2.1willcontaina
linearsubspace
V
.Thefollowingpropositionssuggestsomepossibilities.
PROPOSITION5.2.2
Let
A
beathird-orderand
n
-dimensionalrank-onetensor,i.e.,
A
canbewrittenastheouterproductof
3
vectors
a;b;c
2
C
n
:
A
:=
a

b

c
with
A
ijk
:=(
a
i
b
j
c
k
)
;i;j;k
=1
;:::;n:
Let
W
:=span(
a;b;c
)
and
V
:=
W
?
.Then
U
:=
f
x
2
C
n
jA
x
2
=0
g
V
,i.e.,the
49
eigenspaceof
A
correspondingtotheeigenvalue0containsV.
Proof
:Ittoshowforany
x
2
V
,
A
x
2
=0.Actually,by
A
x
2
=
0
B
B
B
B
B
B
B
B
B
B
B
B
@
n
P
j;k
=1
a
1
b
j
c
k
x
j
x
k
n
P
j;k
=1
a
2
b
j
c
k
x
j
x
k
.
.
.
n
P
j;k
=1
a
n
b
j
c
k
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
A
:
Simplecomputationgives
A
x
2
=
0
B
B
B
B
B
B
B
B
B
B
B
B
@
a
1
n
P
j;k
=1
b
j
c
k
x
j
x
k
a
2
n
P
j;k
=1
b
j
c
k
x
j
x
k
.
.
.
a
n
n
P
j;k
=1
b
j
c
k
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
a
1
 
n
P
j
=1
b
j
x
j
! 
n
P
k
=1
c
k
x
k
!
a
2
 
n
P
j
=1
b
j
x
j
! 
n
P
k
=1
c
k
x
k
!
.
.
.
a
n
 
n
P
j
=1
b
j
x
j
! 
n
P
k
=1
c
k
x
k
!
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@
a
1
(
b
T
x
)(
c
T
x
)
a
2
(
b
T
x
)(
c
T
x
)
.
.
.
a
n
(
b
T
x
)(
c
T
x
)
1
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@
0
0
.
.
.
0
1
C
C
C
C
C
C
C
C
C
A
;
wherethelastequalityholdssince
x
2
span(
a;b;c
)
?
.
2
PROPOSITION5.2.3
Let
A
beathird-orderand
n
-dimensionaltensorwhichcanbe
50
decomposedas
A
=
r
X
l
=1
a
(
l
)

a
(
l
)

a
(
l
)
;
where
r<n
,
a
(
l
)
2
C
n
;l
=1
;
2
;

;r
.Let
W
=span(
a
(1)
;a
(2)
;

;a
(
r
)
)
andlet
V
=
W
?
.
Then
U
:=
f
x
2
C
n
jA
x
2
=0
g
V
,i.e.,theeigenspaceof
A
correspondingtotheeigenvalue
0containsV.
Proof
:Itisttoshow
A
x
2
=0forany
x
2
V
.By
A
ijk
=
r
X
l
=1

a
(
l
)

a
(
l
)

a
(
l
)

ijk
=
r
X
l
=1
a
(
l
)
i
a
(
l
)
j
a
(
l
)
k
;i;j;k
=1
;:::;n:
So
A
x
2
=
0
B
B
B
B
B
B
B
B
B
B
B
B
@
n
P
j;k
=1
A
1
jk
x
j
x
k
n
P
j;k
=1
A
2
jk
x
j
x
k
.
.
.
n
P
j;k
=1
A
njk
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
n
P
j;k
=1
 
r
P
l
=1
a
(
l
)
1
a
(
l
)
j
a
(
l
)
k
!
x
j
x
k
n
P
j;k
=1
 
r
P
l
=1
a
(
l
)
2
a
(
l
)
j
a
(
l
)
k
!
x
j
x
k
.
.
.
n
P
j;k
=1
 
r
P
l
=1
a
(
l
)
n
a
(
l
)
j
a
(
l
)
k
!
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
:
51
Then
A
x
2
=
0
B
B
B
B
B
B
B
B
B
B
B
B
@
n
P
j;k
=1
r
P
l
=1
a
(
l
)
1
a
(
l
)
j
a
(
l
)
k
x
j
x
k
n
P
j;k
=1
r
P
l
=1
a
(
l
)
2
a
(
l
)
j
a
(
l
)
k
x
j
x
k
.
.
.
n
P
j;k
=1
r
P
l
=1
a
(
l
)
n
a
(
l
)
j
a
(
l
)
k
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
@
r
P
l
=1
n
P
j;k
=1
a
(
l
)
1
a
(
l
)
j
a
(
l
)
k
x
j
x
k
r
P
l
=1
n
P
j;k
=1
a
(
l
)
2
a
(
l
)
j
a
(
l
)
k
x
j
x
k
.
.
.
r
P
l
=1
n
P
j;k
=1
a
(
l
)
n
a
(
l
)
j
a
(
l
)
k
x
j
x
k
1
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
r
P
l
=1
a
(
l
)
1
 
n
P
j;k
=1
a
(
l
)
j
a
(
l
)
k
x
j
x
k
!
r
P
l
=1
a
(
l
)
2
 
n
P
j;k
=1
a
(
l
)
j
a
(
l
)
k
x
j
x
k
!
.
.
.
r
P
l
=1
a
(
l
)
n
 
n
P
j;k
=1
a
(
l
)
j
a
(
l
)
k
x
j
x
k
!
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
@
r
P
l
=1
a
(
l
)
1
 
n
P
j
=1
a
(
l
)
j
x
j
! 
n
P
k
=1
a
(
l
)
k
x
k
!
r
P
l
=1
a
(
l
)
2
 
n
P
j
=1
a
(
l
)
j
x
j
! 
n
P
k
=1
a
(
l
)
k
x
k
!
.
.
.
r
P
l
=1
a
(
l
)
n
 
n
P
j
=1
a
(
l
)
j
x
j
! 
n
P
k
=1
a
(
l
)
k
x
k
!
1
C
C
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
B
B
@
r
P
l
=1
a
(
l
)
1

(
a
(
l
)
)
T
x

(
a
(
l
)
)
T
x

r
P
l
=1
a
(
l
)
2

(
a
(
l
)
)
T
x

(
a
(
l
)
)
T
x

.
.
.
r
P
l
=1
a
(
l
)
n

(
a
(
l
)
)
T
x

(
a
(
l
)
)
T
x

1
C
C
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@
0
0
.
.
.
0
1
C
C
C
C
C
C
C
C
C
A
;
wherethelastequalityisvalidbecause
x
2
span(
a
(1)
;:::;a
(
r
)
)
?
.
2
52
5.3Anumericalalgorithmofrealtensoreigen-
pairsbasedontheNewtonhomotopyandthestraight-
forwardapproach
Inthissection,wepresentthealgorithmforcomputingrealeigenpairsbasedonthestraight-
forwardapproachinSection5.2andAlgorithm5.1.1.
ALGORITHM5.3.1
(Computerealmode-
k
B
-eigenpairsof
A
,where
A2
R
[
m;n
]
;
B2
R
[
m
0
;n
]
)
Step1.
ComputeallcomplexeigenpairsusingAlgorithm4.3.1orAlgorithm4.3.2.Let
K
bethesetofresultingeigenpairs
(
x
)
with
j
Im(

)
j
<
0
(chosenthreshold).
Step2.
Foreacheigenpair
(


;x

)
2
K
:if
(


;x

)
isinapositivedimensionalsolution
componentof(4.4)or(2.3),gotoStep3.Otherwise,
(


;x

)
isanisolatedeigenpair.If
k
Im(
x

)
k
2
<
0
,thentake
(Re(


)
;
Re(
x

))
asarealeigenpairandstop.
Step3.
Set

=Re(


)
.If
m
=
m
0
,set
v
:=Re(
x

)
(if
Re(
x

)
6
=0
)and
w
:=Im(
x

)
(if
Im(
x

)
6
=0
);otherwise,set
v
:=
Re(
x

)
(
B
Re(
x

)
m
0
)
1
=m
0
(if
B
Re(
x

)
m
0
6
=0)
;
and
w
:=
Im(
x

)
(
B
Im(
x

)
m
0
)
1
=m
0
(if
B
Im(
x

)
m
0
6
=0)
:
If
(
v
)
or
(
w
)
isamode-
k
B
-eigenpairof
A
,thenwehaveobtainedarealeigenpairand
stop.Otherwise,gotoStep4.
Step4.
Startingfrom
(


;x

)
,useAlgorithm5.1.1toarealeigenpair.
53
Chapter6
Implementationandnumericalresults
BasedonthealgorithmsintroducedinChapter4andChapter5,aMATLABpackage
TenEig
1.1
hasbeendeveloped.Thepackage
TenEig1.1
canbedownloadedfrom
http://www.math.msu.edu/~chenlipi/TenEig.html
Considerthetensors
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
.In
TenEig1.1
,function
teig
com-
putesgeneralizedmode-
k
B
eigenvaluesandeigenvectorsofatensor
A
for
m
=
m
0
.The
inputofthisfunctionis:tensor
A
orthepolynomialform
A
x
m
if
A
issymmetric(forwhich
A
x
m

1
=
r
(
A
x
m
)
=m
fromProposition2.2.3),
B
(thedefaultistheunittensor),mode
k
(thedefaultvalueis1),andtheoutputis:mode-
k
B
eigenvaluesandeigenvectorsof
A
.In
general,
teig
computesgeneralizedcomplexmode-
k
B
eigenvaluesandeigenvectorsof
A
when
m
=
m
0
.Butbydefault,
teig
Qi-eigenvaluesandQi-eigenvectors.
Thefunction
teneig
computesgeneralizedmode-
k
B
eigenvaluesandeigenvectorsofa
tensor
A
for
m
6
=
m
0
.Theinputofthisfunctionis:tensor
A
orthepolynomialform(if
A
issymmetric)
A
x
m
,tensor
B
,mode
k
(thedefaultvalueis1),andtheoutputis:mode-
k
B
eigenvaluesandeigenvectorsof
A
.If
B
ischosenastheidentifymatrix,
teneig
computes
E-eigenvaluesandE-eigenvectorsof
A
asinQi[35].
SinceE-eigenpairsofatensorarefrequentlyindemand,ourpackageincludesaseparate
function
eeig
,whichonlycomputesE-eigenpairsofatensor.
Thepackagealsoincludestwofunctions
heig
and
zeig
tocomputerealeigenpairsofa
tensor:TheonecomputesH-eigenpairsandsecondonecomputesZ-eigenpairs.
54
Inthenexttwosections,numericalresultsarereportedtoillustratetheenessand
ofourmethodsforcomputingtensoreigenpairs.Allthenumericalexperiments
wereperformedonaThinkpadT400LaptopwithanIntel(R)dualcoreCPUat2.80GHz
and2GBofRAM,runningonaWindows7operatingsystem.Thepackage
TenEig1.1
usesMATLAB2013a.Intheexamples,weused
teig
or
teneig
tocomputegeneralized
tensoreigenpairs,
teig
tocomputeQi-eigenpairs,
eeig
tocomputeE-eigenvalues,
heig
to
compute(real)H-eigenpairs,and
zeig
tocompute(real)Z-eigenpairs,respectively.
6.1Examplesforcomputingcomplexeigenpairs
Inthissection,somenumericalexamplesexhibitingtheperformanceof
TenEig1.1
for
computingcomplextensoreigenpairsarepresented.
Wewillcompareourpackage
TenEig1.1
with
NSolve
,afunctioninMathematica(based
ontheoebnerbasis)forsolvingsystemsofalgebraicequations,incomputingcomplex
tensoreigenpairs.Let
T
(
m;n
):=
n
(
m

1)
n

1
;
E
(
m;n
):=((
m

1)
n

1)
=
(
m

2)
;
G
(
m;m
0
;n
):=((
m

1)
n

(
m
0

1)
n
)
=
(
m

m
0
)
:
RecallthatTheorem3.3.1showsfortensors
A2
C
[
m;n
]
and
B2
C
[
m
0
;n
]
,thenumber
ofequivalenceclassesofisolated
B
-eigenpairsof
A
isboundedby
T
(
m;n
)for
m
=
m
0
and
G
(
m;m
0
;n
)for
m
6
=
m
0
.Inparticular,asmentionedinRemark3.3.1,thenumber
ofequivalenceclassesofisolatedQi-eigenpairsisboundedby
T
(
m;n
)andthenumberof
55
equivalenceclassesofisolatedE-eigenpairsof
A
isboundedby
E
(
m;n
).
EXAMPLE6.1.1
Inthisexample,wecomparetheperformanceofour
TenEig1.1
with
NSolve
and
PSOLVE
.Moresp,whencomputingQi-eigenpairsofagenerictensor
A2
C
[
m;n
]
,
(a)
teig
isbasedonAlgorithm4.3.1usingthelinearhomotopygiveninTheorem4.2.2.
(b)
NSolve
and
PSOLVE
solvethepolynomialsystem
A
x
m

1
=

[
m

1]
augmentedbya
randomhyperplanein(4.4).
TocomputeE-eigenpairs,
(a)
eeig
isbasedonAlgorithm4.3.2whichsolvesthepolynomialsystem
A
x
m

1
=

augmentedwitharandomhyperplaneandthennormalizetheresultingsolutionstosatisfy
x
T
x
=1afterwards.
(b)
NSolve
and
PSOLVE
solvethepolynomialsystem
A
x
m

1
=

with
x
T
x
=1ap-
pendedby(2.3).
Thetensors
A
weregeneratedusing
randn
(
n;

;n
)+
i

randn
(
n;

;n
)inMATLAB.
Forinstance,
randn
(2
;
2
;
2)+
i

randn
(2
;
2
;
2)generatesathird-orderandtwodimensional
complextensor.ThecomputingresultsaregiveninTable6.1,inwhich,
N
denotesthe
numberofequivalenceclassesofQi-eigenpairsorE-eigenpairsfoundby
teig
,
eeig
,
PSOLVE
or
NSolve
,theCPUtimesareinseconds,"-"meansnoresultswerereturnedafter12hours.
Fromthetable,ourcodes
teig
and
eeig
allequivalenceclassesofQi-eigenpairsor
E-eigenpairsinreasonableamountoftimeforallcases.
NSolve
failstoprovideanyresults
in12hoursforsomecases(weterminateditafter12hours).Although
PSOLVE
successfully
allequivalenceclassesinmanycases,itdoesmissafewequivalenceclassessometime.
RegardingtheCPUtime,
PSOLVE
iscomparableto
teig
buttakesmoretimethan
eeig
.
56
(
m;n
)
T
(
m;n
)
Alg
N
time(s)
E
(
m;n
)
Alg
N
time(s)
(4
;
5)
405
teig
405
15.8
121
eeig
121
5.4
PSOLVE
404
14.0
PSOLVE
121
9.5
NSolve
405
3136.4
NSolve
121
486.6
(5
;
5)
1280
teig
1280
73.8
341
eeig
341
22.3
PSOLVE
1280
65.5
PSOLVE
341
38.6
NSolve
-
-
NSolve
341
9264.8
(5
;
6)
6144
teig
6144
606.5
1365
eeig
1365
166.5
PSOLVE
6144
694.2
PSOLVE
1365
283.6
NSolve
-
-
NSolve
-
-
(6
;
6)
18750
teig
18750
3721.3
3906
eeig
3906
990.2
PSOLVE
18748
4636.0
PSOLVE
3905
1721.0
NSolve
-
-
NSolve
-
-
Table6.1:Comparisonof
teig
and
eeig
with
PSOLVE
and
NSolve
EXAMPLE6.1.2
Inthisexampleweshowtheenessandof
teig
for
allequivalenceclassesofisolatedQi-eigenpairsofagenerictensor
A2
C
[
m;n
]
.Each
tensorwasgeneratedby
randn
(
n;

;n
)+
i

randn
(
n;

;n
)inMATLAB.Theresults
arereportedinTable6.2,inwhich
N
isthenumberofequivalenceclassesofisolatedQi-
eigenpairsfoundby
teig
and
T
(
m;n
)representstheboundofthenumberofequivalence
classesofisolatedQi-eigenpairs(seeRemark3.3.1(a)).
(
m;n
)
T
(
m;n
)
N
time(s)
(
m;n
)
T
(
m;n
)
N
time(s)
(3
;
5)
80
80
2.4
(3
;
6)
192
192
6.8
(3
;
7)
448
448
18.3
(3
;
8)
1024
1024
53.0
(3
;
9)
2304
2304
145.9
(3
;
10)
5120
5120
409.2
(4
;
3)
27
27
0.7
(4
;
4)
108
108
2.9
(4
;
5)
405
405
15.8
(4
;
6)
1458
1458
80.0
(4
;
7)
5103
5103
385.9
(4
;
8)
17496
17496
2115.5
(5
;
3)
48
48
1.2
(5
;
4)
256
256
8.8
(5
;
5)
1280
1280
73.8
(5
;
6)
6144
6144
606.5
(5
;
7)
28672
28672
5394.2
(6
;
3)
75
75
2.3
(6
;
4)
500
500
21.0
(6
;
5)
3125
3125
287.7
(6
;
6)
18750
18750
3721.3
(7
;
3)
108
108
3.6
(7
;
4)
864
864
51.5
(7
;
5)
6480
6480
981.3
Table6.2:Performanceof
teig
oncomputingQi-eigenpairsofcomplexrandomtensors
57
EXAMPLE6.1.3
Inthisexampleweshowtheenessandof
eeig
for
allequivalenceclassesofisolatedE-eigenpairsofagenerictensor
A2
C
[
m;n
]
.Each
generictensorwasgeneratedby
randn
(
n;

;n
)+
i

randn
(
n;

;n
)inMATLAB.The
resultsarereportedinTable6.3,inwhich
N
isthenumberofequivalenceclassesofE-
eigenpairsfoundby
eeig
and
E
(
m;n
)istheboundofthenumberofequivalenceclassesof
isolatedE-eigenpairs(seeRemark3.3.1(b)).
(
m;n
)
E
(
m;n
)
N
time(s)
(
m;n
)
E
(
m;n
)
N
time(s)
(3
;
5)
31
31
1.4
(3
;
6)
63
63
3.1
(3
;
7)
127
127
7.5
(3
;
8)
255
255
20.3
(3
;
9)
511
511
48.5
(3
;
10)
1023
1023
133.9
(4
;
3)
13
13
0.4
(4
;
4)
40
40
1.7
(4
;
5)
121
121
5.4
(4
;
6)
364
364
26.9
(4
;
7)
1093
1093
119.5
(4
;
8)
3280
3280
555.8
(5
;
3)
21
21
0.7
(5
;
4)
85
85
4.2
(5
;
5)
341
341
22.3
(5
;
6)
1365
1365
166.5
(5
;
7)
5461
5461
1330.7
(6
;
3)
31
31
1.2
(6
;
4)
156
156
9.5
(6
;
5)
781
781
100.4
(6
;
6)
3906
3906
990.2
(7
;
3)
43
43
1.9
(7
;
4)
259
259
21.3
(7
;
5)
1555
1555
245.0
Table6.3:Performanceof
eeig
oncomputingE-eigenpairsofcomplexrandomtensors
Accordingto[35],[7],and[4],forarandomlygeneratedtensor
A2
C
[
m;n
]
,ithas
T
(
m;n
)
numberofequivalenceclassesofQi-eigenpairsand
E
(
m;n
)numberofequivalenceclassesof
E-eigenpairs.Moreover,itsQi-eigenpairsandE-eigenpairsareisolated.FromTables6.2and
6.3,ourcode
teig
and
eeig
canallequivalenceclassesofQi-eigenpairsandE-eigenpairs
ofsuchtensorsintheexampleswetested.
EXAMPLE6.1.4
Theexamplehereexhibitstheenessandciencyof
teig
and
teneig
forallequivalenceclassesofisolated
B
-eigenpairsofagenerictensor
A
,
where
A2
C
[
m;n
]
;
B2
C
[
m
0
;n
]
aregenerictensors.Eachgenerictensorwasgeneratedby
58
randn
(
n;

;n
)+
i

randn
(
n;

;n
)inMATLAB.TheresultsarereportedinTable6.4,in
which
N
denotesthenumberofequivalenceclassesofeigenpairsfoundby
teig
or
teneig
,
T
(
m;n
)denotestheboundofthenumberofequivalenceclassesofisolated
B
-eigenpairsfor
m
=
m
0
,and
G
(
m;m
0
;n
)denotestheboundofthenumberofequivalenceclassesofisolated
B
-eigenpairsfor
m
6
=
m
0
(seeTheorem3.3.1).
teig(
m
=
m
0
)
teneig(
m
6
=
m
0
)
(
m;n
)
T
(
m;n
)
N
time(s)
(
m;m
0
;n
)
G
(
m;m
0
;n
)
N
time(s)
(3
;
7)
448
448
23.7
(3
;
2
;
7)
127
127
10.3
(3
;
8)
1024
1024
68.3
(3
;
4
;
6)
665
665
68.1
(3
;
9)
2304
2304
210.3
(3
;
5
;
5)
496
496
49.5
(4
;
5)
405
405
20.8
(4
;
2
;
6)
364
364
28.9
(4
;
6)
1458
1458
110.4
(4
;
3
;
5)
211
211
13.2
(4
;
7)
5103
5103
737.5
(4
;
5
;
4)
175
175
9.5
(5
;
5)
1280
1280
97.9
(5
;
4
;
5)
781
781
83.9
(5
;
6)
6144
6144
1178
(5
;
6
;
3)
61
61
2.6
(6
;
4)
500
500
29.9
(6
;
5
;
4)
369
369
30.7
(6
;
5)
3125
3125
449.4
(6
;
7
;
3)
91
91
6.0
(7
;
3)
108
108
4.4
(7
;
6
;
4)
671
671
77.1
(7
;
4)
864
864
77.6
(7
;
8
;
3)
127
127
9.4
Table6.4:Performanceof
teig
and
teneig
oncomputinggeneralizedeigenpairsofcomplex
randomtensors
Evidently,Table6.4showsthatour
teig
and
teneig
canallequivalenceclassesof
isolated
B
-eigenpairsof
A
forgenerictensors
A
and
B
inareasonableamountoftime.
6.2Computingsingulartensoreigenpairs
ItisknownthatthehomotopymethodusesNewton'smethodintheendgame.While
Newton'smethodconvergesrapidlyatnonsingularsolutionsofapolynomialsystemwith
highaccuracy,itmayjustattainafewcorrectdigitsatsingularsolutions.Therefore,when
homotopymethodsisusedtosolvethepolynomialsystem(3.1)forthetensoreigenvalue
59
problem,desirednumberoftdigitsforasingulareigenpair(


;x

)maynotbe
achievable,asthefollowingexampleshows.
EXAMPLE6.2.1
Considerthesymmetrictensor
A2
R
[6
;
3]
(Example4.10in[12],see
also[4])inthepolynomialform
A
x
6
=
x
4
1
x
2
2
+
x
2
1
x
4
2
+
x
6
3

3
x
2
1
x
2
2
x
2
3
:
TocomputeitsQi-eigenpairs,byProposition2.2.3,thecorrespondingpolynomialsystemis
1
6
(4
x
3
1
x
2
2
+2
x
1
x
4
2

6
x
1
x
2
2
x
2
3
)


5
1
=0
1
6
(2
x
4
1
x
2
+4
x
2
1
x
3
2

6
x
2
1
x
2
x
2
3
)


5
2
=0
1
6
(6
x
5
3

6
x
2
1
x
2
2
x
3
)


5
3
=0
a
1
x
1
+
a
2
x
2
+
a
3
x
3
+
b
=0
;
where
a
1
;a
2
;a
3
;b
arecomplexrandomnumbers.Letthesystembe
P
(
x
)=0.According
toQi[35],thetensor
A
shouldhave3(6

1)
3

1
=75eigenvalues.Table6.5listsallthe75
eigenvaluestogetherwiththeircorrespondingeigenvectors.Inthetable,

(
l
)
meansthereare
l
eigenvectorsassociatedwith

countingmultiplicities,themultiplicityofeacheigenpairas
asolutionof
P
(
x
)=0.Forinstance,

(
l
)
=

1
:
1445
(8)
indicatesthereare8eigenvectors
associatedwith

1
:
1445.Thecorresponding
x
T
=(1
;

(0
:
4209

0
:
9071
i
)
;

(0
:
4447+0
:
6965
i
))
withmultiplicity1representseachoffollowingfoureigenvectors:
60
(1
;
+(0
:
4209

0
:
9071
i
)
;
+(0
:
4447+0
:
6965
i
)),
(1
;
+(0
:
4209

0
:
9071
i
)
;

(0
:
4447+0
:
6965
i
)),
(1
;

(0
:
4209

0
:
9071
i
)
;
+(0
:
4447+0
:
6965
i
)),
(1
;

(0
:
4209

0
:
9071
i
)
;

(0
:
4447+0
:
6965
i
))
togetherwith

=

1
:
1445hasmultiplicity1asasolutionof
P
(
x
)=0.Ofcourse,
eigenpairswithmultiplicity1arenonsingularandalltheothersaresingular.

(
l
)
x
T
multiplicity

1
:
1445
(8)
(1
;

(0
:
4209

0
:
9071
i
)
;

(0
:
4447+0
:
6965
i
))
1
(1
;

(0
:
4209+0
:
9071
i
)
;

(0
:
4447

0
:
6965
i
))
1

1
3
(6)
(1
;

i;
0)
3
(1
;i;
0)
3
0
(14)
(0
;
1
;
0)
5
(1
;
0
;
0)
5
(

1
;
1
;

1)
1
(1
;
1
;

1)
1
(1
;
1
;
1)
1
(

1
;
1
;
1)
1
0
:
0555
(8)
(

0
:
4568
;
1
;

0
:
6856)
1
(1
;

0
:
4568
;

0
:
6856)
1
0
:
5445

0
:
5350
i
(8)
(

(0
:
7318+0
:
6111
i
)
;

(0
:
8490

0
:
2286
i
)
;
1)
1
(

(0
:
8490

0
:
2286
i
)
;

(0
:
7318+0
:
6111
i
)
;
1)
1
0
:
5445+0
:
5350
i
(8)
(

(0
:
8490+0
:
2286
i
)
;

(0
:
7318

0
:
6111
i
)
;
1)
1
(

(0
:
7318

0
:
6111
i
)
;

(0
:
8490+0
:
2286
i
)
;
1)
1
1
(15)
(0
;
0
;
1)
13
(1
;

1
;
0)
1
(1
;
1
;
0)
1
1
:
5

0
:
8660
i
(4)
(1
;

1
;

(0
:
5+0
:
8660
i
))
1
1
:
5+0
:
8660
i
(4)
(1
;

1
;

(0
:
5

0
:
8660
i
))
1
Table6.5:EigenpairsofthetensorinExample6.2.1
ByAlgorithm4.3.1,all75solutionsofthesystem
P
(
x
)=0canbefound,andveryac-
curatelyforthe46nonsingularsolutions.Forinstance,theapproximationtothenonsingular
61
solution(


;x

)=(0
;
1
;
1
;

1)
T
:
0
B
B
B
B
B
B
B
B
B
@


x

1
x

2
x

3
1
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@
0
:
000000000000000+0
:
000000000000000
i
1
:
000000000000000+0
:
000000000000000
i
1
:
000000000000000+0
:
000000000000000
i

1
:
000000000000000

0
:
000000000000000
i
1
C
C
C
C
C
C
C
C
C
A
achievesaccuracyuptothemachineprecision.However,thealgorithmcannotachieve
somanytdigitsforasingularsolution.Forexample,theapproximationtothe
singularsolution(


;x

)=(

1
=
3
;
1
;i;
0)
T
is
0
B
B
B
B
B
B
B
B
B
@


x

1
x

2
x

3
1
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@

0
:
333333333338482

0
:
000000000005507
i
1
:
000000000000000+0
:
000000000000000
i

0
:
000002043599517+0
:
999999061292030
i
0
:
000000000000000+0
:
000000000000000
i
1
C
C
C
C
C
C
C
C
C
A
:
Toimprovetheaccuracyofsingulareigenpairswefurtherusetheso-called
method(see[13]).
Let(
^

^
x
)beasingularzeroof
P
(
x
).Themethodstartsfromtheobservation
that
DP
(
^

^
x
)
2
C
n
+1
;n
+1
issingular.Assume
DP
(
^

^
x
)
2
C
n
+1
;n
+1
istofrank
d
.
Thenforalmostall
d

(
n
+1)randommatrix
R
,thematrix
2
6
4
DP
(
^

^
x
)
R
3
7
5
62
isoffullcolumnrank.Let
e
1
:=(1
;
0
;:::;
0)
T
2
R
d
.Thenitisclearthatthelinearsystem
2
6
4
DP
(
^

^
x
)
R
3
7
5
y
=
2
6
4
0
e
1
3
7
5
hasauniquesolution
y
=^
y
in
C
n
+1
.Wenowconstructanew(2(
n
+1)+
d
)

(
n
+1)system
Q
(
x;y
):=
2
6
6
6
6
6
4
P
(
x
)
2
6
4
DP
(
x
)
R
3
7
5
y

2
6
4
0
e
1
3
7
5
3
7
7
7
7
7
5
=0
:
If^
z
:=(
^

^
x;
^
y
)isasimplezeroof
Q
(
z
):=
Q
(
x;y
),
DQ
(^
z
)mustbeoffullrank.Denote
(
DQ
(
z
))
y
:=[(
DQ
(
z
))
T
(
DQ
(
z
))]

1
(
DQ
(
z
))
T
:
ThentheGaussian-Newtoniterations
z
(
j
+1)
=
z
(
j
)

(
DQ
(
z
(
j
)
))
y
Q
(
z
(
j
)
)for
j
=0
;
1
;:::
with
z
(0)
:=(


;x

;
^
y
)canbeused,untiltheresidue
k
Q
(
z
(
j
+1)
)
k
2
iswithinthedesired
accuracy.Thiswillleadtoamuchmoreaccurate(
~


;
~
x

).
If^
z
isamultiplezeroof
Q
(
z
):=
Q
(
x;y
),theprocedurecanberepeatedon
Q
(
z
)untilasatisfactory(
~


;
~
x

)isachieved.
63
ReturningtoExample6.2.1,whenthemethodisusedinconjunctionwithAlgo-
rithm4.3.1,theeigenpair(


;x

)=(

1
=
3
;
1
;i;
0)
T
canbecomputedremarkablyaccurate:
0
B
B
B
B
B
B
B
B
B
@
~


~
x

1
~
x

2
~
x

3
1
C
C
C
C
C
C
C
C
C
A
=
0
B
B
B
B
B
B
B
B
B
@

0
:
333333333333333+0
:
000000000000000
i
1
:
000000000000000+0
:
000000000000000
i
0
:
000000000000000+1
:
000000000000000
i

0
:
000000000000000+0
:
000000000000000
i
1
C
C
C
C
C
C
C
C
C
A
:
6.3ExamplesforComputingRealEigenpairs
Inthissection,numericalexamplesarepresentedtoillustratetheenessand
of
zeig
or
heig
forcomputingrealZ-eigenpairsorH-eigenpairsofatensor
A2
R
[
m;n
]
.
By2.1.1,(
x
)isaZ-eigenpairifandonlyif((

1)
m

2


x
)isaZ-eigenpair,
and(
x
)isanH-eigenpairifandonlyif(
tx
)isanH-eigenpairforanynonzero
t
2
R
.
Onlyonerepresentativefromeachequivalenceclassofeigenpairswillbelistedinourtables.
Thenotation

(
l
)
represents
l
eigenvectorsarefoundfortheeigenvalue

.Inthefollowing
tables,themultiplicityofaneigenpairmeansthemultiplicityofthiseigenpairasazeroof
thecorrespondingpolynomialsystem.Forconciseness,thepolynomialsystemthatsolves
thetensoreigenvalueproblemwillbeomitted.
EXAMPLE6.3.1
Considerthesymmetrictensor
A2
R
[6
;
3]
whosecorrespondingpolyno-
mialformistheMotzkinpolynomial:
A
x
6
=
x
6
3
+
x
4
1
x
2
2
+
x
2
1
x
4
2

3
x
2
1
x
2
2
x
2
3
:
StatedinExample5.9of[4],thistensorhas25equivalenceclassesofZ-eigenpairsasshown
64
inTable6.6.Exactly25equivalenceclassesofZ-eigenpairsarefoundby
zeig
,agreeingwith
theresultsof[4].Ittakes
zeig
about0.9secondsfortheentirecomputation.

x
T
multiplicity
0
(14)
(0
:
5774
;

0
:
5774
;

0
:
5774)
1
(1
;
0
;
0)
5
(0
;
1
;
0)
5
0
:
0156
(8)
(0
:
8253
;

0
:
2623
;

0
:
5000)
1
(0
:
2623
;

0
:
8253
;

0
:
5000)
1
0
:
2500
(2)
(0
:
7071
;

0
:
7071
;
0)
1
1
(0
;
0
;
1)
1
Table6.6:Z-eigenpairsofthetensorinExample6.3.1
AsshowninTable6.7alltheH-eigenpairsinExample4.10of[12]arealsofoundby
heig
.Theentirecomputationtimeis1.7seconds.

x
T
multiplicity
0
(14)
(

1
;
1
;

1)
1
(1
;
0
;
0)
5
(0
;
1
;
0)
5
0
:
0555
(8)
(

0
:
4568
;
1
;

0
:
6856)
1
(1
;

0
:
4568
;

0
:
6856)
1
1
(15)
(0
;
0
;
1)
13
(1
;

1
;
1)
1
Table6.7:H-eigenpairsofthetensorinExample6.3.1
Forcomputingallrealeigenvaluesofasymmetrictensortheonlyavailablemethodat
thistimeisAlgorithm3.6in[12].Inthenexttwoexamples,wecomparetheperformance
ofourmethodswithAlgorithm3.6in[12].
EXAMPLE6.3.2
Inthisexample,our
zeig
isusedtocomputetheZ-eigenvaluesof12
symmetrictensorsfrom[12].ThetestproblemsandnumericalresultsaregivenintheAp-
pendix.Fromthenumericalresults,our
zeig
alltheZ-eigenvaluesfoundbyAlgorithm
65
3.6([12])onthissetofproblems.TheCPUtimes
1
(inseconds)usedby
zeig
andbyAl-
gorithm3.6([12])areshowninTable6.8.(TheCPUtimesbyAlgorithm3.6arefrom
[12]).
Problem
zeig
Algorithm3.6([12])
time(s)
time(s)
1
0.3
9
2
4
400
3
0.3{0.4
5{20
4
0.1
1
5
0.6
9
6
1.8
10870
7
15.7
280
8
6.1
320
9
0.3
1
10
6.3
370
11
27.3
170
12
4.5
420
Table6.8:
zeig
vsAlgorithm3.6([12]):CPUtime
EXAMPLE6.3.3
Considerthesymmetrictensor
A2
R
[4
;n
]
(Example4.16in[12])inthe
polynomialform
A
x
4
=(
x
1

x
2
)
4
+

+(
x
1

x
n
)
4
+(
x
2

x
3
)
4
+

+(
x
2

x
n
)
4
+

+(
x
n

1

x
n
)
4
:
ShowninTable6.9,our
zeig
foundalltheZ-eigenvaluesfoundbyAlgorithm3.6in[12]
fort
n
.Noticethatwhen
n
=8
;
9
;
10,our
zeig
canalltheZ-eigenvaluesina
reasonableamountoftime,but[12]reportsthatAlgorithm3.6canonlythethree
1
Thecomputerusedin[12]isaThinkpadW520laptopwithanInteldualcoreCPUat2.20GHzand
8GBRAM.ThecomputerusedinthispaperisaThinkpadT400laptopwithanInteldualcoreCPUat
2.80GHzand2GBRAM.ThereadershouldbecautiouswhencomparingtheCPUtimeofthemethodssince
tcomputerswereused.
66
largestZ-eigenvalues.TheCPUtimesusedby
zeig
andAlgorithm3.6([12])arelistedin
thetable.(TheCPUtimesbyAlgorithm3.6([12])arefrom[12]
2
.)Thecorresponding
Z-eigenvectorsarenotdisplayed.
n

time(s)
zeig
Algorithm3.6([12])
4
0.00004.00005.00005.3333
1.7
3.6
5
0.0000,4.1667,4.2500,5.5000,6.2500
5.4
274.5
6
0.0000,4.0000,4.5000,6.0000,7.2000
15.5
280.2
7
0.0000,4.0833,4.1667,4.7500,4.8846,
58.3
9565.6
4.9000,6.5000,8.1667
8
0.0000,4.0000,4.2667,4.2727,4.3333,
244.1
938
:
2

5.0000,5.2609,5.3333,7.0000,9.1429
9
0.0000,4.0500,4.1250,4.5000,5.2500,
788.0
4173
:
8

5.6250,5.7857,7.5000,10.1250
10
0.0000,4.0000,4.1667,4.1818,4.2500,
2665.6
15310
:
5

4.6667,4.7500,4.7593,4.7619,5.5000,
5.9808,6.2500,8.0000,11.1111
Table6.9:Z-eigenvaluesofthetensorinExample6.3.3(*denotesthattheCPUtimeused
byAlgorithm3.6([12])whenitthethreelargestZ-eigenvalues)
2
Again,weshouldbecautiouswhencomparingtheCPUtimesusedbythetwomethodsbecauseof
tcomputerswereused.
67
APPENDIX
68
PROBLEM1
Considerthesymmetrictensor
A2
R
[4
;
3]
(Example4.1in[12],seealso
[35])withthepolynomialform
A
x
4
=
x
4
1
+2
x
4
2
+3
x
4
3
:
Our
zeig
obtainsalltheZ-eigenpairsfoundin[12](seeTableA.1),takingabout0.3seconds
tocarryouttheentirecomputation,whileAlgorithm3.6([12])needs9seconds
3
forthe
computation.

x
T
multiplicity
0
:
5455
(4)
(0
:
7385
;

0
:
5222
;

0
:
4264)
1
0
:
6667
(2)
(0
:
8165
;

0
:
5774
;
0)
1
0
:
7500
(2)
(0
:
8660
;
0
;

0
:
5000)
1
1
(1
;
0
;
0)
1
1
:
2
(2)
(0
;
0
:
7746
;

0
:
6325)
1
2
(0
;
1
;
0)
1
3
(0
;
0
;
1)
1
TableA.1:Z-eigenpairsofthetensorinProblem1
PROBLEM2
Fordiagonaltensor
D2
R
[5
;
4]
(Example4.2in[12])where
D
x
5
=
x
5
1
+
2
x
5
2

3
x
5
3

4
x
5
4
,considerthesymmetrictensor
A2
R
[5
;
4]
suchthat
A
x
5
=
D
(
Qx
)
5
where
Q
=(
I

2
w
1
w
T
1
)(
I

2
w
2
w
T
2
)(
I

2
w
3
w
T
3
)
and
w
1
;w
2
;w
3
arerandomlygeneratedunitvectors.Our
zeig
takesabout4.0secondsto
reachallthe30Z-eigenpairsfoundin[12],inwhichAlgorithm3.6spends400secondsto
3
AlltheCPUtimesbyAlgorithm3.6([12])arefrom[12].Thecomputerusedin[12]isaThinkpad
W520laptopwithanInteldualcoreCPUat2.20GHzand8GBRAM.Thecomputerusedinthispaper
isaThinkpadT400laptopwithanInteldualcoreCPUat2.80GHzand2GBRAM.Thereadershouldbe
cautiouswhencomparingtheCPUtimeofthemethodssincetcomputerswereused.
69
completethecomputation.The15nonnegativeZ-eigenvaluesare
0
:
2518
;
0
:
3261
;
0
:
3466
;
0
:
3887
;
0
:
4805
;
0
:
5402
;
0
:
5550
;
0
:
6057
;
0
:
8543
;
0
:
9611
;
1
:
0000
;
1
:
2163
;
2
:
0000
;
3
:
0000
;
4
:
0000
:
PROBLEM3
Considerthesymmetrictensor
A2
R
[4
;
3]
(Example4.3in[12],seealso
[35])withthepolynomialform
A
x
4
=2
x
4
1
+3
x
4
2
+5
x
4
3
+4
ax
2
1
x
2
x
3
;
where
a
isaparameter.Fortvaluesof
a
,our
zeig
foundallZ-eigenvaluesthat
appearedin[12],asshowninTableA.2.ThelastcolumnofthetableistheCPUtimeused
a

time(s)
0
0
:
9677
(4)
,1
:
2000
(2)
,1
:
4286
(2)
,1
:
8750
(2)
,2,3,5
0.4
0.25
0
:
8464
(2)
,1
:
0881
(2)
,1
:
2150
(2)
,1
:
4412
(2)
,1
:
8750
(2)
,2,3,5
0.4
0.5
0
:
7243
(2)
,1
:
2069
(2)
,1
:
2593
(2)
,1
:
4783
(2)
,1
:
8750
(2)
,2,3,5
0.4
1
0
:
4787
(2)
,1
:
6133
(2)
,1
:
8750
(2)
,2,3,5
0.3
3

0
:
5126
(2)
,1
:
8750
(2)
,2,2
:
2147
(2)
,3,5
0.3
TableA.2:Z-eigenvaluesofthetensorinProblem3
by
zeig
foreach
a
.Asonecansee
zeig
needs0.3to0.4secondstoalleigenpairsfor
tvaluesof
a
,butthistakesAlgorithm3.6([12])5to20seconds.
PROBLEM4
Considerthesymmetrictensor
A2
R
[4
;
2]
(Example4.4in[12],seealso
[35])inthepolynomialform
A
x
4
=3
x
4
1
+
x
4
2
+6
ax
2
1
x
2
2
;
70
where
a
isaparameter.TableA.3listedallZ-eigenvaluesfoundbyboth[12]and
zeig
.
a

time(s)

1

0
:
6000
(2)
,1,3
0.1
0
0
:
7500
(2)
,1,3
0.1
0
:
25
0
:
9750
(2)
,1,3
0.1
0
:
5
1,3
0.1
2
1,3,4
:
1250
(2)
0.1
3
1,3,5
:
5714
(2)
0.1
TableA.3:Z-eigenvaluesofthetensorinProblem4
Foreach
a
,ittakes
zeig
0.1second,butAlgorithm3.6([12])1second.
PROBLEM5
Considerthesymmetrictensor
A2
R
[4
;
3]
(Example4.5in[12],seealso[23]
or[34])suchthat
A
1111
=0
:
2883
;A
1112
=

0
:
0031
;A
1113
=0
:
1973
;A
1122
=

0
:
2485
;
A
1123
=

0
:
2939
;A
1133
=0
:
3847
;A
1222
=0
:
2972
;A
1223
=0
:
1862
;
A
1233
=0
:
0919
;A
1333
=

0
:
3619
;A
2222
=0
:
1241
;A
2223
=

0
:
3420
;
A
2233
=0
:
2127
;A
2333
=0
:
2727
;A
3333
=

0
:
3054
:
AlltheZ-eigenpairsfoundin[12]listedinTableA.4canalsobefoundby
zeig
.Forthe
entirecomputation,
zeig
takesabout0.6secondsbutAlgorithm3.6([12])9seconds.
PROBLEM6
Considerthesymmetrictensor
A2
R
[3
;
6]
(Example4.6in[12],seealso
[37])suchthat
A
iii
=
i
for
i
=1
;:::;
6and
A
i;i;i
+1
=10for
i
=1
;:::;
5andzerootherwise.
Again
zeig
didnotmissanyZ-eigenvaluesfoundin[12].The19nonnegativeZ-eigenvalues
71

x
T
multiplicity
-1.0954
(-0.5915,0.7467,0.3043)
1
-0.5629
(-0.1762,0.1796,-0.9678)
1
-0.0451
(0.7797,0.6135,0.1250)
1
0.1735
(0.3357,0.9073,0.2531)
1
0.2433
(-0.9895,-0.0947,0.1088)
1
0.2628
(-0.1318,0.4425,0.8870)
1
0.2682
(0.6099,0.4362,0.6616)
1
0.3633
(0.2676,0.6447,0.7160)
1
0.5105
(-0.3598,0.7780,-0.5150)
1
0.8169
(-0.8412,0.2635,-0.4722)
1
0.8893
(-0.6672,-0.2471,0.7027)
1
TableA.4:Z-eigenpairsofthetensorinProblem5
are:
3
:
99924
:
02254
:
24644
:
33585
:
14025
:
48175
:
52185
:
5668
5
:
56746
:
00007
:
21658
:
18898
:
59798
:
65968
:
734710
:
9711
15
:
429815
:
455216
:
2345
Ittakes
zeig
about1.8seconds,whileAlgorithm3.6([12])asmuchas10870seconds,for
theentirecomputation.
PROBLEM7
Considerthesymmetrictensor
A2
R
[4
;
6]
(Example4.7in[12],seealso
[28])withthepolynomialform

x
4
=(
x
1

x
2
)
4
+(
x
1

x
3
)
4
+(
x
1

x
4
)
4
+(
x
1

x
5
)
4
+(
x
1

x
6
)
4
+(
x
2

x
3
)
4
+(
x
2

x
4
)
4
+(
x
2

x
5
)
4
+(
x
2

x
6
)
4
+(
x
3

x
4
)
4
+(
x
3

x
5
)
4
+(
x
3

x
6
)
4
+(
x
4

x
5
)
4
+(
x
4

x
6
)
4
+(
x
5

x
6
)
4
:
All5Z-eigenvaluesfoundin[12]listedinTableA.5arealsofoundby
zeig
.Asmentioned
72

x
T
multiplicity

7
:
2000
(6)
(0
:
1826
;
0
:
1826
;
0
:
1826
;
0
:
1826
;
0
:
1826
;

0
:
9129)
1

6
:
0000
(15)
(0
:
7071
;
0
;
0
;
0
;
0
;

0
:
7071)
1

4
:
5000
(
?
)
(1
:
5703
;
1
:
5703
;

0
:
4923
;

0
:
4923
;

1
:
0780
;

1
:
0780)
-

4
:
0000
(10)
(0
:
4082
;
0
:
4082
;
0
:
4082
;

0
:
4082
;

0
:
4082
;

0
:
4082)
1
0
(
?
)
(0
:
4088
;
0
:
4088
;
0
:
4083
;
0
:
4083
;
0
:
4076
;
0
:
4076)
-
TableA.5:Z-eigenpairsofthetensorinProblem7
in[12],everypermutationofaZ-eigenvectorisalsoaZ-eigenvector.Weonlylistedthe
Z-eigenvectorwith
x
1

x
2

x
6
correspondingtooneZ-eigenvalue.Actuallythe
Z-eigenpairscorrespondingtoZ-eigenvalues0and

4
:
5formapositivedimensionalsolution
componentofthecorrespondingpolynomialsystem.Therefore,therearemany
Z-eigenvectorsassociatedwith0and

4
:
5.
zeig
484Z-eigenvectorsassociatedwith0
and180Z-eigenvectorsassociatedwith

4
:
5.OnlyoneoftheseZ-eigenvectorsforeachcase
islistedinTableA.6.
zeig
takesabout15.7secondstodotheentirecomputation,while
Algorithm3.6([12])spends280seconds.
PROBLEM8
Considerthesymmetrictensor
A2
R
[4
;
5]
(Example4.8in[12],seealso
[44])inthepolynomialform
A
x
4
=(
x
1
+
x
2
+
x
3
+
x
4
)
4
+(
x
2
+
x
3
+
x
4
+
x
5
)
4
:
Allthe3Z-eigenvaluesfoundin[12]arealsofoundby
zeig
,whichareshowninTableA.6.

x
T
multiplicity
0
(
?
)
(0
:
9736
;

0
:
4533
;

0
:
5063
;

0
:
0131
;
0
:
9712)
-
0.5000
(0
:
7071
;
0
;
0
;
0
;

0
:
7071)
1
24.5000
(0
:
2673
;
0
:
5345
;
0
:
5345
;
0
:
5345
;
0
:
2673)
1
TableA.6:Z-eigenpairsofthetensorinProblem8
73
Forthistensor,theZ-eigenpairscorrespondingtoZ-eigenvalue0formapositivedimen-
sionalsolutioncomponentofthecorrespondingpolynomialsystem.Thus,thereare
manyZ-eigenvectorsassociatedwithZ-eigenvalue0.
zeig
234ofthem.Onlyoneof
themislistedinTableA.6.
zeig
usesabout6.1seconds,whileittakesAlgorithm3.6([12])
320seconds,fortheentirecomputation.
PROBLEM9
Forthesymmetrictensor
A2
R
[3
;
3]
(Example4.9in[12],seealso[4])in
thepolynomialform
A
x
3
=2
x
3
1
+3
x
1
x
2
2
+3
x
1
x
2
3
:
TheZ-eigenpairscorrespondingtoZ-eigenvalue2formapositivedimensionalsolutioncom-
ponentofthecorrespondingpolynomialsystem.Thus,thereareitelymanyZ-eigenvectors
associatedwithZ-eigenvalue0.
zeig
7ofthem.OnlyoneofthemislistedinTableA.7.
zeig
usesabout0.3seconds,whileAlgorithm3.6([12])spends1second,todotheentire
computation.

x
T
multiplicity
2
(1
;
0
;
0)
-
TableA.7:Z-eigenpairsofthetensorinProblem9
PROBLEM10
Letthetensor
A2
R
[4
;n
]
(Example4.12in[12],seealso[34])be
A
i
1
;:::;i
4
=sin(
i
1
+
i
2
+
i
3
+
i
4
)
:
When
n
=5,exhibitedinTableA.8areallthe5Z-eigenvaluesfoundby
zeig
,whichagree
withthoseappearedin[12].
74

x
T
multiplicity
-8.8463
(0
:
5809
;
0
:
3563
;

0
:
1959
;

0
:
5680
;

0
:
4179)
1
-3.9204
(

0
:
1785
;
0
:
4847
;
0
:
7023
;
0
:
2742
;

0
:
4060)
1
0
(
?
)
(

0
:
9914
;
0
:
3771
;

0
:
2946
;

0
:
6360
;

0
:
0534)
-
4.6408
(0
:
5055
;

0
:
1228
;

0
:
6382
;

0
:
5669
;
0
:
0256)
1
7.2595
(0
:
2686
;
0
:
6150
;
0
:
3959
;

0
:
1872
;

0
:
5982)
1
TableA.8:Z-eigenpairsofthetensorinProblem10
Forthistensor,theZ-eigenpairscorrespondingtoZ-eigenvalue0formapositivedimen-
sionalsolutioncomponentofthecorrespondingpolynomialsystem.Thus,thereare
manyZ-eigenvectorsassociatedwith0.
zeig
234ofthem.Onlyoneofthemislisted
inTableA.8.
zeig
takesabout6.3secondswithAlgorithm3.6([12])using370secondsfor
theentirecomputation.
PROBLEM11
Considerthetensor
A2
R
[4
;n
]
(Example4.13in[12])suchthat
A
i
1
;:::;i
4
=tan(
i
1
)+

+tan(
i
4
)
:
When
n
=6,
zeig
foundallthe3Z-eigenvaluesfoundin[12],whicharegiveninTableA.9.

x
T
multiplicity
-133.2871
(0
:
1936
;
0
:
5222
;
0
:
3429
;
0
:
2287
;
0
:
6272
;
0
:
3559)
1
0
(
?
)
(

1
:
9950
;

0
:
5791
;
0
:
2737
;
1
:
6411
;
0
:
1326
;
0
:
5277)
-
45.5045
(0
:
6281
;
0
:
0717
;
0
:
3754
;
0
:
5687
;

0
:
1060
;
0
:
3533)
1
TableA.9:Z-eigenpairsofthetensorinProblem11
Forthistensor,theZ-eigenpairscorrespondingtoZ-eigenvalue0formapositivedimen-
sionalsolutioncomponentofthecorrespondingpolynomialsystem.Thus,thereare
manyZ-eigenvectorsassociatedwith0.
zeig
724ofthem.Onlyoneofthemislisted
75
inTableA.9.Ittakes
zeig
about27.3seconds,butAlgorithm3.6([12])170seconds,to
carryouttheentirecomputation.
PROBLEM12
Considerthetensor
A2
R
[5
;n
]
(Example4.14in[12])suchthat
A
i
1
;:::;i
5
=ln(
i
1
)+

+ln(
i
5
)
:
For
n
=4,allthe3Z-eigenvaluesfoundin[12]arealsofoundby
zeig
,whichareshownin
TableA.10.

x
T
multiplicity
0
(
?
)
(0
:
9914
;

1
:
2262
;
0
:
1847
;
0
:
0523)
-
0.7074
(

0
:
9054
;

0
:
3082
;
0
:
0411
;
0
:
2890)
1
132.3070
(0
:
4040
;
0
:
4844
;
0
:
5319
;
0
:
5657)
1
TableA.10:Z-eigenpairsofthetensorinProblem12
Forthisproblem,theZ-eigenpairscorrespondingtoZ-eigenvalue0formapositivedimen-
sionalsolutioncomponentofthecorrespondingpolynomialsystem.Thus,thereare
manyZ-eigenvectorsassociatedwith0.
zeig
166ofthem.Onlyoneofthemislisted
inTableA.9.Theentirecomputationtakes
zeig
about4.5seconds,whileAlgorithm3.6
([12])uses420seconds.
76
BIBLIOGRAPHY
77
BIBLIOGRAPHY
[1]E.L.AllgowerandK.Georg,
NumericalContinuationMethods,anIntroduction
,
SpringerSeriesinComput.Math.,Vol13,Springer-Verlag(Berlin,Heidelberg,New
York),1990.
[2]D.N.Bernstein,Thenumberoftherootsofasystemofequations,
Funct.Anal.Appl.
,
1975,9:183-185.
[3]D.L.Bates,J.D.Hauenstein,A.J.SommeseandC.W.Wampler,
NumericallySolving
PolynomialSystemswithBertini
,SocietyforIndustrialandAppliedMathematics,
Philadelphia,2013.
[4]D.CartwrightandB.Sturmfels,Thenumberofeigenvaluesofatensor,
LinearAlgebra
anditsApplications
,2013,438:942{952.
[5]K.C.Chang,K.PearsonandT.Zhang,Perron-Frobeniustheoremfornonnegative
tensors,
Commun.Math.Sci.
,2008,6(5):507{520.
[6]K.C.Chang,K.PearsonandT.Zhang,Oneigenvaluesofrealsymmetrictensors,
JournalofMathematicalAnalysisandApplications
,2009,350:416{422.
[7]K.C.Chang,L.Qi,andT.Zhang,Asurveyofthespectraltheoryofnonnegative
tensors,
NumericalLinearAlgebrawithApplications
,2013,20:891{912.
[8]D.A.Cox,J.Little,andD.O'Shea,
UsingAlgebraicGeometry
,2nded.,Springer-
Verlag,NewYork,NY,2005.
[9]D.A.Cox,J.Little,andD.O'Shea,
Ideals,Varieties,andAlgorithms:AnIntroduction
toComputationalAlgebraicGeometryandCommutativeAlgebra
,3rded.,Springer-
Verlag,Secaucus,NJ,USA,2007.
[10]J.CooperandA.Duttle,Spectraofuniformhypergrphs,
LinearAlgebraanditsAp-
plications
,2012,436:3268{3292.
[11]D.A.Cox,J.B.LittleandH.Schenck,
Toricvarieties
,graduatestudiesinmathematics,
Am.Math.Soc.2011,124.
78
[12]C.-F.Cui,Y.-H.DaiandJ.Nie,Allrealeigenvaluesofsymmetrictensors,
arXiv:1403.3720,2014.
[13]B.Dayton,T.LiandZ.Zeng,Multiplezerosofnonlinearsystems,
Math.Comp.
,2011,
80:2143{2168.
[14]S.Friedland,S.GaubertandL.Han,Perron-Frobeniustheoremfornonnegativemul-
tilinearformsandextensions,
LinearAlgebraandApplications
,2013,438:738{749.
[15]W.Fulton,
eIntroductiontotoricvarieties
,in:WilliamH.Roever(Ed.),in:Lectures
inGeometry,AnnalsofMathematicsStudies,vol.131,PrincetonUniversityPress,
Princeton,NJ,1993.
[16]T.Gunji,S.Kim,M.Kojima,A.Takeda,K.FujisawaandT.Mizutani,PHoM-A
polyhedralhomotopycontinuationmethod,
Computing
,2004,73:53-57.
[17]L.Han,Anunconstrainedoptimizationapproachforrealeigenvaluesofeven
ordersymmetrictensors,
NumericalAlgebra,ControlandOptimization
,2013,3:583{
599.
[18]C.HillierandL.-H.Lim,MosttensorproblemsareNP-hard,
JournaloftheACM
,
2013,60,no.6,art.45.
[19]R.HornandC.R.Johnson,
MatrixAnalysis
,2nded.,CambridgeUniversityPress,
2013.
[20]S.Hu,Z.Huang,andL.Qi,FindingtheextremeZ-eigenvaluesoftensorsviaasequen-
tialsemprogrammingmethod,
NumericalLinearAlgebrawithApplications
,
2013,20:972{984.
[21]S.Hu,Li.Qi,andB.Zhang,Thegeometricmeasureofentanglementofpure
stateswithnonnegativeamplitudesandthespectraltheoryofnonnegativetensors,
arXiv:1203.3675,2012.
[22]B.HuberandB.Sturmfels,Apolyhedralmethodforsolvingsparsepolynomialsys-
tems,
Math.Comp.
,1995,64:1541-1555.
[23]T.G.KoldaandJ.R.Mayo,Shiftedpowermethodforcomputingtensoreigenpairs,
SIAMJournalonMatrixAnalysisandApplications
,2011,32:1095{1124.
79
[24]T.G.KoldaandJ.R.Mayo,Anadaptiveshiftedpowermethodforcomputinggeneral-
izedtensoreigenpairs,
SIAMJournalonMatrixAnalysisandApplications
,2014,35:
1563-1581.
[25]T.L.LeeandT.Y.Li,MixedVolumeComputationinsolvingpolynomialsystems,
ContemporaryMathematics
,2011,556:97-112.
[26]T.L.Lee,T.Y.Li,andC.H.Tsai,Hom4PS-2.0,asoftwarepackageforsolvingpoly-
nomialsystemsbythepolyhedralhomotopycontinuationmethod,
Computing
,2008,
83:109{133.
[27]T.Y.Li,Solvingpolynomialsystemsbythehomotopycontinuationmethod,
Handbook
ofNumericalAnalysis
,XI,2003,209{304.
[28]G.Li,L.Qi,andG.Yu,TheZ-eigenvaluesofasymmetrictensoranditsapplica-
tiontospectralhypergraphtheory,
NumericalLinearAlgebrawithApplications
,2013,
20:1001-1029.
[29]L.-H.Lim,Singularvaluesandeigenvaluesoftensors:avariationalapproach,
Proceed-
ingsoftheIEEEInternationalWorkshoponComputationalAdvancesinMulti-Sensor
AdaptiveProcessing(CAMSAP'05)
,2005,1:129{132.
[30]T.Y.LiandX.Wang,TheBKKrootcountin
C
n
,
Math.Comp.
,1996,65:1477-1484.
[31]Y.Liu,G,Zhou,andN.F.Ibrahim,Analwaysconvergentalgorithmforthelargest
eigenvalueofanirreduciblenonnegativetensor,
JournalofComputationalandApplied
Mathematics
,2010,235:286{292.
[32]A.P.Morgan,
SolvingPolynomialSystemsUsingContinuationforEngineeringand
Problems
,SocietyforIndustrialandAppliedMathematics,Philadelphia,
2009.
[33]M.Ng,L.Qi,andG.Zhou,Findingthelargesteigenvalueofanonnegativetensor,
SIAMJournalonMatrixAnalysisandApplications
,2009,31:1090{1099.
[34]J.NieandL.Wang,relaxationsforbestrank-1tensorapproximations,
SIAMJournalonMatrixAnalysisandApplications
2014,35:1155{1179.
[35]L.Qi,Eigenvaluesofarealsupersymmetrictensor,
J.Symb.Comput.
,2005,40:1302{
1324.
80
[36]L.Qi,W.Sun,andY.Wang,Numericalmultilinearalgebraanditsapplications,
FrontiersofMathematicsinChina
,2007,2:501{526.
[37]L.Qi,F.Wang,andY.Wang,Z-eigenvaluemethodsforaglobaloptimizationpoly-
nomialoptimizationproblem,
MathematicalProgramming
,2009,118:301{306.
[38]L.Qi,Y.Wang,andE.X.Wu,D-eigenvaluesofkurtosistensors,
Journalof
ComputationalandAppliedMathematics
,2008,221:150{157.
[39]L.Qi,G.Yu,andE.X.Wu,Higherorderpositivesemi-dtensorimaging,
SIAMJournalonImagingSciences
,2010,3:416{433.
[40]L.Qi,G.Yu,andY.Xu,Nonnegativeorientationdistributionfunction,
JournalofMathematicalImagingandVision
,2013,45:103-113.
[41]A.J.SommeseandW.W.Wampler,
TheNumericalSolutionofSystemsofPolynomials
ArisinginEngineeringAndScience
WorldScienPubCoInc,2005.
[42]J.Verschelde,Algorithm795:PHCpack:Ageneral-purposesolverforpolynomial
systemsbyhomotopycontinuation,
ACMTrans.Math.Softw.
,1999,25:251-276.
[43]A.H.Wright,Findingallsolutionstoasystemofapolynomialequations,
Math.Comp.
,
1985,44:125-133.
[44]J.XieandA.Chang,OntheZ-eigenvaluesofthesignlessLaplaciantensorforaneven
uniformhypergraph,
NumericalLinearAlgebrawithApplications
,2013,20:1030-1045.
[45]Y.YangandQ.Yang,FurtherresultsforPerron-Frobeniustheoremfornonnegative
tensors,
SIAMJournalonMatrixAnalysisandApplications
,2010,31:2517{2530.
[46]Y.YangandQ.Yang,FurtherresultsforPerron-Frobeniustheoremfornonnegative
tensorsII,
SIAMJournalonMatrixAnalysisandApplications
,2011,32:1236{1250.
[47]Z.ZengandT.Li,NACLab:AMatlabToolboxforNumericalAlgebraicComputation,
ACMCommunicationsinComputerAlgebra
,2013,47:170-173.
[48]L.Zhang,L.Qi,andY.Xu,Findingthelargesteigenvalueofanirreducibletensorand
linearconvergenceforweaklypositivetensors,
JournalofComputationalMathematics
,
2012,30:24{33.
81
[49]G.Zhou,L.Qi,andS.-Y.Wu,Onthelargesteigenvalueofasymmetricnonnegative
tensor,
NumericalLinearAlgebrawithApplications
,2013,20:913{928.
82