Ŀ¼

listofsymbolsandacronyms

listofiterativealgorithmtemplates

listofdirectalgorithms

listoffigures

listoftables

1introduction

1.1whyeigenvaluetemplates?

1.2intendedreadership

1.3usingthedecisiontreetochooseatemplate

1.4whatisatemplate?

1.5organizationofthebook

2abrieftourofeigenproblems

2.1introduction

2.1.1numericalstabilityandconditioning

2.2hermitianeigenproblems

j.dem mel

2.2.1eigenvaluesandeigenvectors

2.2.2invariantsubspaces

2.2.3equivalences(similarities)

.2.2.4eigendecompositions

2.2.5conditioning

2.2.6specifyinganeigenproblem

2.2.7relatedeigenproblems

2.2.8example

2.3generalizedhermitianeigenproblems

j.dernrnel

2.3.1eigenvaluesandeigenvectors

2.3.2eigenspaces

2.3.3equivalences(congruences)

2.3.4eigendecompositions

2.3.5conditioning

2.3.6specifyinganeigenproblem

2.3.7relatedeigenproblems

2.3.8example

2.4singularvaluedecomposition

j.demrnel

2.4.1singularvaluesandsingularvectors

2.4.2singularsubspaces

2.4.3equivalences

2.4.4decompositions

2.4.5conditioning

2.4.6specifyingasingularvalueproblem

2.4.7relatedsingularvalueproblems

2.4.8example

2.5non-hermitianeigenproblerns

j.demmel

2.5.1eigenvaluesandeigenvectors

2.5.2invariantsubspaces

2.5.3equivalences(similarities)

2.5.4eigendecompositions

2.5.5conditioning

2.5.6specifyinganeigenproblem

2.5.7relatedeigenproblems

2.5.8example

2.6generalizednon-hermitianeigenproblerns

j.demmel

2.6.1eigenvaluesandeigenvectors

2.6.2deflatingsubspaces

2.6.3equivalences

2.6.4eigendecompositions

2.6.5conditioning

2.6.6specifyinganeigenproblem

2.6.7relatedeigenproblems

2.6.8example

2.6.9singularcase

2.7nonlineareigenproblems

j.demmel

3anintroductiontoiterativeprojectionmethods

3.1introduction

3.2basicideas

y.saad

3.3spectraltransformations

r.lehoucqandd.sorensen

4hermitianeigenvalueproblems

4.1introduction

4.2directmethods

4.3single-andmultiple-vectoriterations

m.gu

4.3.1powermethod

4.3.2inverseiteration

4.3.3rayleighquotientiteration

4.3.4subspaceiteration

4.3.5softwareavailability

4.4lanczosmethod

a.ruhe

4.4.1algorithm

4.4.2convergenceproperties

4.4.3spectraltransformation

4.4.4reorthogonalization

4.4.5softwareavailability

4.4.6numericalexamples

4.5implicitlyrestartedlanczosmethod

r.lehouc,qandd.sorensen

4.5.1implicitrestart

4.5.2shiftselection

4.5.3lanczosmethodingemvform

4.5.4convergenceproperties

4.5.5computationalcostsandtradeoffs

4.5.6deflationandstoppingrules

4.5.7orthogonaldeflatingtransformation

4.5.8implementationoflockingandpurging

4.5.9softwareavailability

4.6bandlanczosmethod

r.freund

4.6.1theneedfordeflation

4.6.2basicproperties

4.6.3algorithm

4.6.4variants

4.7jacobi-davidsonmethods

g.sleijpenandh.vandervorst

4.7.1basictheory

4.7.2basicalgorithm

4.7.3restartanddeflation

4.7.4computinginterioreigenvalues

4.7.5softwareavailability

4.7.6numericalexample

4.8stabilityandaccuracyassessments

z.baiandr.li

5generalizedhermitianeigenvalueproblems

5.1introduction

5.2transformationtostandardproblem

5.3directmethods

5.4single-andmultiple-vectoriterations

m.gu

5.5lanczosmethods

a.ruhe

5.6jacobi-davidsonmethods

g.sleijpenandh.vandervorst

5.7stabilityandaccuracyassessments

z.baiandr.li

5.7.1positivedefiniteb

5.7.2somecombinationofaandbispositivedefinite

6singularvaluedecomposition

6.1introduction

6.2directmethods

6.3iterativealgorithms

j.demmel

6.3.1whatoperationscanoneaffordtoperform?

6.3.2whichsingularvaluesandvectorsaredesired?

6.3.3golub-kahan-lanczosmethod

6.3.4softwareavailability

6.3.5numericalexample

6.4relatedproblems

j.demmel

7non-hermitianeigenvalueproblems

7.1introduction

7.2balancingmatrices

t.chenandj.demmel

7.2.1directbalancing

7.2.2krylovbalancingalgorithms

7.2.3accuracyofeigenvaluescomputedafterbalancing

7.3directmethods

7.4single-andmultiple-vectoriterations

m.gu

7.4.1powermethod

7.4.2inverseiteration

7.4.3subspaceiteration

7.4.4softwareavailability

7.5arnoldimethod

y.saad

7.5.1basicalgorithm

7.5.2variants

7.5.3explicitrestarts

7.5.4deflation

7.6implicitlyrestartedarnoldimethod

r.lehoucqandd.sorensen

7.6.1arnoldiprocedureingemvform

7.6.2implicitrestart

7.6.3convergenceproperties

7.6.4numericalstability

7.6.5computationalcostsandtradeoffs

7.6.6deflationandstoppingrules

7.6.7orthogonaldeflatingtransformation

7.6.8eigenvectorcomputationwithspectraltransformation

7.6.9softwareavailability

7.7blockarnoldimethod

r.lehoucqandk.maschhoff

7.7.1blockarnoldireductions

7.7.2practicalalgorithm

7.8lanczosmethod

z.baiandd.day

7.8.1algorithm

7.8.2convergenceproperties

7.8.3softwareavailability

7.8.4notesandreferences

7.9blocklanczosmethods

z.baiandd.day

7.9.1basicalgorithm

7.9.2anadaptivelyblockedlanczosmethod

7.9.3softwareavailability

7.9.4notesandreferences

7.10bandlanczosmethod

r.freund

7.10.1deflation

7.10.2basicproperties

7.10.3algorithm

7.10.4applicationtoreduced-ordermodeling

7.10.5variants

7.11lanczosmethodforcomplexsymmetriceigenproblems

r.freund

7.11.1propertiesofcomplexsymmetricmatrices

7.11.2propertiesofthealgorithm

7.11.3algorithm

7.11.4solvingthereducedeigenvalueproblems

7.11.5softwareavailability

7.11.6notesandreferences

7.12jacobi-davidsonmethods

g.sleijpenandii.vandervorst

7.12.1generalizationofhermitiancase

7.12.2schurformandrestart

7.12.3computinginterioreigenvalues

7.12.4softwareavailability

7.12.5numericalexample

7.13stabilityand"accuracyassessments

z.baiandr.li

8generalizednon-hermitianeigenvalueproblems

8.1introduction

8.2directmethods

8.3transformationtostandardproblems

8.4jacobi-davidsonmethod

g.sleijpenandh.vandervorst

8.4.1basictheory

8.4.2deflationandrestart

8.4.3algorithm

8.4.4softwareavailability

8.4.5numericalexample

8.5rationalkrylovsubspacemethod

a.ruhe

8.6symmetricindefinitelanczosmethod

z.bai,t.ericsson,andt.kowalski

8.6.1somepropertiesofsymmetricindefinitematrixpairs

8.6.2algorithm

8.6.3stoppingcriteriaandaccuracyassessment

8.6.4singularb

8.6.5softwareavailability

8.6.6numericalexamples

8.7singularmatrixpencils

b.kagstrom

8.7.1regularversussingularproblems

8.7.2kroneckercanonicalform

8.7.3genericandnongenerickroneckerstructures

8.7.4ill-conditioning

8.7.5generalizedschur-staircaseform

8.7.6guptrialgorithm

8.7.7softwareavailability

8.7.8moreonguptriandnumericalexamples

8.7.9notesandreferences

8.8stabilityandaccuracyassessments

z.baiandr.li

9nonlineareigenvalueproblems

9.1introduction

9.2quadraticeigenvalueproblems

z.bai,g.sleijpen,andii.vandervorst

9.2.1introduction

9.2.2transformationtolinearform

9.2.3spectraltransformationsforqep

9.2.4numericalmethodsforsolvinglinearizedproblems

9.2.5jacobi-davidsonmethod

9.2.6notesandreferences

9.3higherorderpolynomialeigenvalueproblems

9.4nonlineareigenvalueproblemswithorthogonalityconstraints

r.lippertanda.edelman

9.4.1introduction

9.4.2matlabtemplates

9.4.3sampleproblemsandtheirdifferentials

9.4.4numericalexamples

9.4.5modifyingthetemplates

9.4.6geometrictechnicalities

10commonissues

10.1sparsematrixstorageformats

j.dongarra

10.1.1compressedrowstorage

10.1.2compressedcolumnstorage

10.1.3blockcompressedrowstorage

10.1.4compresseddiagonalstorage

10.1.5jaggeddiagonalstorage

10.1.6skylinestorage

10.2matrix-vectorandmatrix-matrixmultiplications

j.dongarra,p.koev,andx.li

10.2.1blas

10.2.2sparseblas

10.2.3fastmatrix-vectormultiplicationforstructuredmatrices

10.3abriefsurveyofdirectlinearsolvers

j.demmel,p.koev,andx.li

10.3.1directsolversfordensematrices

10.3.2directsolversforbandmatrices

10.3.3directsolversforsparsematrices

10.3.4directsolversforstructuredmatrices

10.4abriefsurveyofiterativelinearsolvers

h.vandervorst

10.5parallelism

j.dongarraandx.li

11preconditioningtechniques

11.1introduction

11.2inexactmethods

k.meerbergenandr.morgan

11.2.1matrixtransformations

11.2.2inexactmatrixtransformations

11.2.3arnoldimethodwithinexactcayleytransform

11.2.4davidsonmethod

11.2.5jacobi-davidsonmethodwithcayleytransform

11.2.6preconditionedlanczosmethod

11.2.7inexactrationalkrylovmethod

11.2.8inexactshift-and-invert

11.3preconditionedeigensolvers

a.knyazev

11.3.1introduction

11.3.2generalframeworkofpreconditioning

11.3.3preconditionedshiftedpowermethod

11.3.4preconditionedsteepestascent/descentmethods

11.3.5preconditionedlanczosmethods

11.3.6davidsonmethod

11.3.7methodswithpreconditionedinneriterations

11.3.8preconditionedconjugategradientmethods

11.3.9preconditionedsimultaneousiterations

11.3.10softwareavailability

appendix.ofthingsnottreated

bibliography

index