Content

•  
   Danksagung
•  
   Abstract
•  
   Contents
•  
   Nomenclature
•  
   1 Introduction
•  
   1.1 Eigenvalue problems
•  
   1.1.1 Scalar product and orthogonality
•  
   1.1.2 Norms
•  
   1.1.3 Hermitian and positive definite matrices
•  
  1.2 Vector iteration methods
•  
   1.2.1 The family of power iteration methods
•  
   1.2.1.1 Definite pairs
•  
   1.2.2 Eigendecomposition
•  
   1.2.2.1 Definite pairs
•  
   1.2.2.2 Power iteration
•  
   1.3 Subspace iteration
•  
   1.3.1 Vector projection and orthogonalization
•  
   1.3.2 Gram-Schmidt orthonormalization
•  
   1.3.2.1 Definite pairs
•  
   1.3.3 Invariant subspaces
•  
   1.3.3.1 Power iteration
•  
   1.3.3.2 Definite pairs
•  
   1.3.4 Rayleigh-Ritz
•  
   1.3.4.1 Power iteration
•  
   1.3.4.2 Definite pairs
•  
   1.3.5 Compatible pencils and harmonic Rayleigh-Ritz
•  
  1.4 Spectral filters
•  
  1.4.1 Projection and projectors
•  
   1.4.1.1 Definite pairs
•  
   1.4.2 Spectral projectors
•  
   1.4.2.1 Definite pairs
•  
   1.5 Matrix functions
•  
   1.5.1 Filtering functions and approximate projectors
•  
  1.6 Iteration and convergence
•  
   1.6.1 Convergence
•  
   1.6.2 Metrics and residual
•  
   1.6.3 Residual bounds
•  
  1.7 Digression: Related algorithms
•  
   1.7.1 Orthogonal iteration
•  
   1.7.2 The Arnoldi and Lanczos methods
•  
   1.7.2.1 Definite pairs
•  
   1.7.2.2 Restarts
•  
   1.7.3 Other methods
•  
   2 Spectral projection algorithms
•  
  2.1 Polynomial filters
•  
   2.1.1 Polynomial approximation
•  
   2.1.2 Chebyshev polynomials
•  
   2.1.2.1 Window function
•  
   2.1.2.2 Application
•  
   2.1.3 Matrix polynomials
•  
   2.1.4 Gibbs phenomenon and smoothing kernels
•  
   2.1.5 Restrictions
•  
   2.1.6 Discrete approximation
•  
   2.2 Contour integration
•  
   2.2.1 Representation of the window function
•  
  2.2.2 Numerical integration
•  
   2.2.2.1 Trapezoidal rule
•  
   2.2.2.2 Midpoint rule
•  
   2.2.2.3 Gauss-Legendre quadrature
•  
   2.2.3 Computation
•  
   2.2.4 Selection function
•  
   2.3 Zolotarev approximation
•  
   2.3.1 Approximation of the sign function
•  
   2.3.2 Window function
•  
   2.3.3 Partial fraction form
•  
   2.3.4 Computation of Jacobi's elliptic functions
•  
   2.4 Electronic filter design
•  
   2.4.1 Butterworth Filter
•  
   2.4.1.1 Design
•  
   2.4.2 Chebyshev Type-I Filter
•  
   2.4.2.1 Design
•  
   2.4.3 Chebyshev Type-II Filter
•  
   2.4.3.1 Design
•  
   2.4.4 Elliptic Filter
•  
   2.4.4.1 Computation of inverse elliptic functions
•  
   2.4.4.2 Design
•  
  2.5 Sakurai-Sugiura-type methods
•  
   2.5.1 A root finding method for analytic functions
•  
   2.5.2 An improved root finding method
•  
  2.5.3 Application to generalized eigenvalue problems
•  
   2.5.3.1 Blocking and Eigenvectors
•  
   2.5.3.2 Rayleigh-Ritz
•  
   2.5.3.3 Filtering functions
•  
   2.5.3.4 Transformations of the weight function
•  
   2.5.3.5 Computation
•  
   2.5.3.6 Relation to spectral projection
•  
  2.6 Other filtering methods
•  
   2.6.1 Rational filter types
•  
   2.6.2 Delta filters
•  
   2.6.3 Least squares
•  
   2.6.4 Beyond conventional subspace iteration
•  
  3 BEAST
•  
   3.1 The BEAST framework
•  
   3.1.1 Basics
•  
   3.1.2 Parallelism
•  
   3.1.2.1 Process group hierarchy
•  
   3.1.2.2 Interval communication protocol
•  
   3.1.3 Orthogonalization layer
•  
  3.2 Meet the BEAST – short feature overview
•  
   3.2.1 Related features
•  
   3.2.2 Linear solvers
•  
   3.2.2.1 Callback interface
•  
   3.2.2.2 A (hybrid) parallel direct solver for banded linear systems
•  
   3.2.3 Unrelated features
•  
   3.2.4 Layer structure
•  
   3.3 Feeding the BEAST – Applications
•  
   4 Taming the BEAST – Quality of results
•  
  4.1 Experiments
•  
   4.1.1 Synthesis of non-trivial sparse definite matrix pencils with predefined spectrum
•  
   4.1.2 Matrix test set
•  
   4.1.3 Ritz value pairing
•  
   4.2 Convergence revisited
•  
   4.2.1 Undersized searchspaces
•  
   4.2.1.1 On-the-fly increase of searchspace size
•  
   4.2.1.2 Detection of undersized searchspaces
•  
   4.2.2 Enlarged searchspaces
•  
   4.2.2.1 On-the-fly restriction of searchspace size
•  
   4.2.2.2 Locking
•  
   4.2.2.3 Rank deficiency
•  
   4.2.2.4 Further reduction
•  
   4.2.2.5 Optimization of searchspace size
•  
   4.2.2.6 Addendum
•  
   4.2.3 SSM effective filter
•  
   4.2.4 Ritz phantoms
•  
   4.2.4.1 Disturbance of convergence
•  
  4.2.5 Clustered eigenvalues
•  
   4.2.5.1 Quasi-multiplicity and Quasi-eigenspaces
•  
   4.2.5.2 Expulsion of clustered values
•  
   4.2.5.3 Clustered super convergence
•  
   4.2.5.4 Disturbances through Ritz phantoms
•  
  4.2.6 Comparison of filter functions
•  
   4.2.6.1 Definition of transition band and stopband gain
•  
   4.2.6.2 Fair conditions
•  
   4.2.6.3 Strict searchspace size
•  
   4.2.6.4 Relaxed searchspace size
•  
   4.2.6.5 Choice of interval
•  
   4.2.7 Difficulty of linear systems
•  
  4.3 Achievable residual
•  
   4.3.1 Absolute rock bottom
•  
   4.3.1.1 Mixed precision
•  
   4.3.1.2 Linear solving effort
•  
   4.3.2 Kick-off residual
•  
   4.3.3 Saturation residual
•  
   4.4 Termination criteria
•  
   4.5 Achievable orthogonality
•  
   4.5.1 Theoretical limit
•  
   4.5.2 Estimated upper bound
•  
   4.5.3 Directional overlap
•  
   4.5.3.1 Verification of orthogonality bounds
•  
   4.6 Evolution of orthogonality
•  
   4.7 Remarks
•  
  5 Taming the BEAST – Orthogonalization
•  
   5.1 The many orthogonalities of BEAST
•  
   5.2 Establishing intra-orthogonality
•  
   5.2.1 QR decomposition
•  
   5.2.2 QR via Givens rotations
•  
   5.2.3 QR via Householder reflections
•  
   5.2.4 Gram-Schmidt QR
•  
   5.2.5 B-orthogonality
•  
   5.2.6 Cholesky QR
•  
   5.2.7 Rank revelation
•  
   5.2.8 Methods based on singular value decomposition
•  
   5.2.9 SVQB
•  
   5.2.10 B-orthogonal QR via SVQB
•  
   5.2.11 Parallel block-orthogonalization
•  
   5.2.12 TSQR
•  
   5.2.13 Condition and multi-orthogonalization
•  
   5.2.14 Weak Gram-Schmidt
•  
   5.2.14.1 Computational effort
•  
   5.2.15 Residual
•  
   5.2.16 Fitness for purpose
•  
   5.3 Establishing inter-orthogonality
•  
   5.3.1 Intermediate orthogonalization
•  
   5.3.2 Post-iteration and retention of orthogonality
•  
   5.3.3 Overlapping intervals
•  
   5.3.4 Orthogonalization sequences
•  
  5.3.5 Block Gram-Schmidt
•  
   5.3.5.1 Parallel application
•  
   5.3.6 Residual
•  
   5.3.7 Orthogonalization order
•  
   5.3.8 A posteriori orthogonalization
•  
   5.3.9 Detection and removal of duplicates
•  
   5.3.10 Butterfly orthogonalization
•  
   5.3.11 Block weak Gram-Schmidt
•  
   5.3.12 Butterfly results
•  
   5.3.13 Regular residual updates
•  
   5.3.14 Skipping intra-orthogonalization
•  
   5.3.15 Reduction of interaction distance
•  
   5.3.16 Large examples
•  
   5.3.17 Shifting scheme
•  
   5.3.18 Application-specific requirements
•  
   5.3.19 Performance
•  
   5.4 Upshot
•  
  Conclusion and outlook
•  
   Conclusion
•  
   Outlook
•  
  A Algorithms for elliptic functions
•  
   A.1 Computation of Jacobi's elliptic functions
•  
   A.1.1 The Algebraic-Geometric Mean
•  
   A.2 Computation of inverse elliptic functions
•  
   Index
•  
   List of Algorithms
•  
   List of Experiments
•  
   List of Figures
•  
   List of Tables
•  
   Bibliography