Tables of Contents for Templates for the Solution of Algebraic Eigenvalue Problems

search for books and compare prices

Tables of Contents for Templates for the Solution of Algebraic Eigenvalue Problems

Chapter/Section Title

Page #

Page Count

List of Symbols and Acronyms

xxi

List of Iterative Algorithm Templates

xxiii

List of Direct Algorithms

xxv

List of Figures

xxvii

List of Tables

xxix

Introduction

1

6

Why Eigenvalue Templates?

1

1

Intended Readership

2

1

Using the Decision Tree to Choose a Template

3

1

What Is a Template?

3

1

Organization of the Book

4

3

A Brief Tour of Eigenproblems

7

30

Introduction

7

4

Numerical Stability and Conditioning

10

1

Hermitian Eigenproblems

11

3

J. Demmel

Eigenvalues and Eigenvectors

11

1

Invariant Subspaces

12

1

Equivalences (Similarities)

12

1

Eigendecompositions

12

1

Conditioning

12

1

Specifying an Eigenproblem

13

1

Related Eigenproblems

13

1

Example

14

1

Generalized Hermitian Eigenproblems

14

4

J. Demmel

Eigenvalues and Eigenvectors

15

1

Eigenspaces

15

1

Equivalences (Congruences)

15

1

Eigendecompositions

15

1

Conditioning

16

1

Specifying an Eigenproblem

16

1

Related Eigenproblems

17

1

Example

17

1

Singular Value Decomposition

18

5

J. Demmel

Singular Values and Singular Vectors

18

1

Singular Subspaces

19

1

Equivalences

19

1

Decompositions

19

1

Conditioning

20

1

Specifying a Singular Value Problem

20

1

Related Singular Value Problems

21

1

Example

22

1

Non-Hermitian Eigenproblems

23

5

J. Demmel

Eigenvalues and Eigenvectors

23

1

Invariant Subspaces

24

1

Equivalences (Similarities)

24

1

Eigendecompositions

24

2

Conditioning

26

1

Specifying an Eigenproblem

26

1

Related Eigenproblems

27

1

Example

28

1

Generalized Non-Hermitian Eigenproblems

28

8

J. Demmel

Eigenvalues and Eigenvectors

29

1

Deflating Subspaces

29

1

Equivalences

29

1

Eigendecompositions

29

2

Conditioning

31

1

Specifying an Eigenproblem

32

1

Related Eigenproblems

33

1

Example

33

1

Singular Case

34

2

Nonlinear Eigenproblems

36

1

J. Demmel

An Introduction to Iterative Projection Methods

37

8

Introduction

37

1

Basic Ideas

37

6

Y. Saad

Spectral Transformations

43

2

R. Lehoucq

D. Sorensen

Hermitian Eigenvalue Problems

45

64

Introduction

45

4

Direct Methods

49

2

Single- and Multiple-Vector Iterations

51

5

M. Gu

Power Method

51

1

Inverse Iteration

52

1

Rayleigh Quotient Iteration

53

1

Subspace Iteration

54

2

Software Availability

56

1

Lanczos Method

56

11

A. Ruhe

Algorithm

57

2

Convergence Properties

59

1

Spectral Transformation

60

1

Reorthogonalization

61

2

Software Availability

63

1

Numerical Examples

63

4

Implicitly Restarted Lanczos Method

67

13

R. Lehoucq

D. Sorensen

Implicit Restart

67

2

Shift Selection

69

1

Lanczos Method in GEMV Form

70

1

Convergence Properties

71

1

Computational Costs and Tradeoffs

72

1

Deflation and Stopping Rules

73

1

Orthogonal Deflating Transformation

74

5

Implementation of Locking and Purging

79

1

Software Availability

80

1

Band Lanczos Method

80

8

R. Freund

The Need for Deflation

81

1

Basic Properties

82

3

Algorithm

85

1

Variants

86

2

Jacobi-Davidson Methods

88

1

G. Sleijpen

H. van der Vorst

Basic Theory

88

3

Basic Algorithm

91

4

Restart and Deflation

95

4

Computing Interior Eigenvalues

99

3

Software Availability

102

1

Numerical Example

103

2

Stability and Accuracy Assessments

105

4

Z. Bai

R. Li

Generalized Hermitian Eigenvalue Problems

109

26

Introuduction

109

3

Transformation to Standard Problem

112

1

Direct Methods

113

1

Single- and Multiple-Vector Iterations

114

2

M. Gu

Lanczos Methods

116

7

A. Ruhe

Jacobi-Davidson Methods

123

4

G. Sleijpen

H. van der Vorst

Stability and Accuracy Assessments

127

8

Z. Bai

R. Li

Positive Definite B

128

2

Some Combination of A and B is Positive Definite

130

5

Singular Value Decomposition

135

14

Introduction

135

3

Direct Methods

138

2

Iterative Algorithms

140

6

J. Demmel

What Operations Can One Afford to Perform?

140

1

Which Singular Values and Vectors Are Desired?

141

1

Golub-Kahan-Lanczos Method

142

3

Software Availability

145

1

Numerical Example

146

1

Related Problems

146

3

J. Demmel

Non-Hermitian Eigenvalue Problems

149

84

Introduction

149

3

Balancing Matrices

152

5

T. Chen

J. Demmel

Direct Balancing

153

1

Krylov Balancing Algorithms

154

1

Accuracy of Eigenvalues Computed after Balancing

155

2

Direct Methods

157

1

Single- and Multiple-Vector Iterations

158

3

M. Gu

Power Method

159

1

Inverse Iteration

159

1

Subspace Iteration

159

1

Software Availability

160

1

Arnoldi Method

161

5

Y. Saad

Basic Algorithm

161

2

Variants

163

1

Explicit Restarts

163

1

Deflation

163

3

Implicitly Restarted Arnoldi Method

166

19

R. Lehoucq

D. Sorensen

Arnoldi Procedure in GEMV Form

167

2

Implicit Restart

169

3

Convergence Properties

172

1

Numerical Stability

173

1

Computational Costs and Tradeoffs

174

1

Deflation and Stopping Rules

175

1

Orthogonal Deflating Transformation

176

7

Eigenvector Computation with Spectral Transformation

183

1

Software Availability

184

1

Block Arnoldi Method

185

4

R. Lehoucq

K. Maschhoff

Block Arnoldi Reductions

185

2

Practical Algorithm

187

2

Lanczos Method

189

7

Z. Bai

D. Day

Algorithm

189

4

Convergence Properties

193

2

Software Availability

195

1

Notes and References

195

1

Block Lanczos Methods

196

9

Z. Bai

D. Day

Basic Algorithm

196

3

An Adaptively Blocked Lanczos Method

199

5

Software Availability

204

1

Notes and References

204

1

Band Lanczos Method

205

11

R. Freund

Deflation

206

1

Basic Properties

206

4

Algorithm

210

4

Application to Reduced-Order Modeling

214

1

Variants

215

1

Lanczos Method for Complex Symmetric Eigenproblems

216

5

R. Freund

Properties of Complex Symmetric Matrices

216

1

Properties of the Algorithm

217

2

Algorithm

219

1

Solving the Reduced Eigenvalue Problems

219

1

Software Availability

220

1

Notes and References

220

1

Jacobi-Davidson Methods

221

7

G. Sleijpen

H. van der Vorst

Generalization of Hermitian Case

221

1

Schur Form and Restart

221

3

Computing Interior Eigenvalues

224

3

Software Availability

227

1

Numerical Example

227

1

Stability and Accuracy Assessments

228

5

Z. Bai

R. Li

Generalized Non-Hermitian Eigenvalue Problems

233

48

Introduction

233

1

Direct Methods

234

1

Transformation to Standard Problems

235

3

Jacobi-Davidson Method

238

8

G. Sleijpen

H. van der Vorst

Basic Theory

238

2

Deflation and Restart

240

1

Algorithm

241

3

Software Availability

244

1

Numerical Example

244

2

Rational Krylov Subspace Method

246

3

A. Ruhe

Symmetric Indefinite Lanczos Method

249

11

Z. Bai

T. Ericsson

T. Kowalski

Some Properties of Symmetric Indefinite Matrix Pairs

250

2

Algorithm

252

4

Stopping Criteria and Accuracy Assessment

256

1

Singular B

257

1

Software Availability

258

1

Numerical Examples

258

2

Singular Matrix Pencils

260

17

B. Kagstrom

Regular Versus Singular Problems

261

1

Kronecker Canonical Form

262

1

Generic and Nongeneric Kronecker Structures

263

1

Ill-Conditioning

264

2

Generalized Schur-Staircase Form

266

1

GUPTRI Algorithm

267

4

Software Availability

271

1

More on GUPTRI and Numerical Examples

271

5

Notes and References

276

1

Stability and Accuracy Assessments

277

4

Z. Bai

R. Li

Nonlinear Eigenvalue Problems

281

34

Introduction

281

1

Quadratic Eigenvalue Problems

281

8

Z. Bai

G. Sleijpen

H. van der Vorst

Introduction

281

2

Transformation to Linear Form

283

1

Spectral Transformations for QEP

284

2

Numerical Methods for Solving Linearized Problems

286

1

Jacobi-Davidson Method

287

2

Notes and References

289

1

Higher Order Polynomial Eigenvalue Problems

289

1

Nonlinear Eigenvalue Problems with Orthogonality Constraints

290

25

R. Lippert

A. Edelman

Introduction

290

1

MATLAB Templates

291

2

Sample Problems and Their Differentials

293

4

Numerical Examples

297

7

Modifying the Templates

304

4

Geometric Technicalities

308

7

Common Issues

315

22

Sparse Matrix Storage Formats

315

5

J. Dongarra

Compressed Row Storage

315

1

Compressed Column Storage

316

1

Block Compressed Row Storage

316

1

Compressed Diagonal Storage

317

1

Jagged Diagonal Storage

318

1

Skyline Storage

319

1

Matrix-Vector and Matrix-Matrix Multiplications

320

6

J. Dongarra

P. Koev

X. Li

Blas

320

1

Sparse Blas

321

3

Fast Matrix-Vector Multiplication for Structured Matrices

324

2

A Brief Survey of Direct Linear Solvers

326

6

J. Demmel

P. Koev

X. Li

Direct Solvers for Dense Matrices

328

1

Direct Solvers for Band Matrices

328

1

Direct Solvers for Sparse Matrices

329

2

Direct Solvers for Structured Matrices

331

1

A Brief Survey of Iterative Linear Solvers

332

2

H. van der Vorst

Parallelism

334

3

J. Dongarra

X. Li

Preconditioning Techniques

337

32

Introduction

337

2

Inexact Methods

339

13

K. Meerbergen

R. Morgan

Matrix Transformations

340

1

Inexact Matrix Transformations

340

2

Arnoldi Method with Inexact Cayley Transform

342

1

Davidson Method

343

3

Jacobi--Davidson Method with Cayley Transform

346

1

Preconditioned Lanczos Method

346

2

Inexact Rational Krylov Method

348

4

Inexact Shift-and-Invert

352

1

Preconditioned Eigensolvers

352

17

A. Knyazev

Introduction

352

2

General Framework of Preconditioning

354

2

Preconditioned Shifted Power Method

356

1

Preconditioned Steepest Ascent/Descent Methods

357

1

Preconditioned Lanczos Methods

358

2

Davidson Method

360

1

Methods with Preconditioned Inner Iterations

361

1

Preconditioned Conjugate Gradient Methods

362

1

Preconditioned Simultaneous Iterations

363

4

Software Availability

367

2

Appendix. Of Things Not Treated

369

4

Bibliography

373

32

Index

405