Contents

• • Acknowledgements
  • Nederlandse samenvatting
  • Outline of the thesis
  
  
• Introduction to semiseparable matrices
  • Semiseparable and related matrices, definitions and properties
    • Definitions for semiseparable and related matrices
    • The nullity theorem
    • Inverse of structured rank matrices
    • Generalizations of the nullity theorem
    • The generator definition, investigated
      • Common misunderstandings about generator representable semiseparable matrices
      • A theoretical problem, with numerical consequences
      • Connection between the generator representable semiseparable and semiseparable matrices
    • Conclusions
  • The representation of semiseparable matrices
    • The definition of a representation
    • The generator representation
    • The representation based on the diagonal and subdiagonal
    • A new representation for symmetric semiseparable matrices
    • Other types of representations
    • Some examples
    • Retrieving the representation from a semiseparable matrix
    • Some algorithms connected to the representation
      • Swapping the representation
      • A fast matrix vector multiplication
      • The determinant of a semiseparable matrix in order $O(n)$ flops.
    • Conclusions
  • An overview of semiseparable matrices.
    • Oscillation matrices
      • Introduction
      • Definition and examples
      • The inverse of a one-pair matrix
      • The example of the one-pair matrix
      • Some other interesting applications
      • The connection with eigenvalues and eigenvectors
    • Semiseparable matrices as covariance matrices
      • The multinomial distribution
      • Some other matrices
    • Discretization of integral equations
    • Orthogonal rational functions
    • An historical overview of the literature
    • Conclusions
  
  
• The reduction of matrices to semiseparable matrices
  • Reduction algorithms to semiseparable form
    • An orthogonal similarity reduction to semiseparable form
    • A similarity reduction applied to a nonsymmetric matrix
    • Reduction to lower (upper) semiseparable form
    • Conclusions
  • Convergence properties of the reductions
    • The Arnoldi(Lanczos)-Ritz values
      • Ritz values and Arnoldi(Lanczos)-Ritz values
      • Necessary conditions to obtain the Arnoldi(Lanczos)-Ritz values as eigenvalues in the already reduced block of the matrix
      • Sufficient conditions to obtain the convergence behavior
      • Some general remarks
    • Convergence properties of the reduction to semiseparable form
      • Lanczos-Ritz values in a similarity reduction to semiseparable form
      • subspace iteration in the similarity reduction
      • subspace iteration and the Lanczos convergence behavior
    • Convergence properties of the reduction to Hessenberg-like
    • Transformation to upper triangular semiseparable form
      • Lanczos-Ritz values
      • subspace iteration
    • Conclusions
  • Implementation of the algorithm and numerical experiments
    • Reduction to symmetric semiseparable
    • Similarity reduction to Hessenberg-like
    • The reduction to upper triangular semiseparable form
    • Numerical experiments
      • Experiment 1
      • Experiment 2
      • Experiment 3
      • Experiment 4
    • Numerical experiments
    • Numerical experiments: Deflation possibilities
    • Conclusions
  
  
• QR-algorithms
  • Theoretical results for $QR$-algorithms
    • The $QR$-factorization of Hessenberg-like plus diagonal matrices
    • Unreduced Hessenberg-like matrices
    • A $QR$-step maintains the Hessenberg-like structure
    • The reduction to unreduced Hessenberg-like form
    • The implicit $Q$-theorem
    • Conclusions
  • Implicit $QR$-algorithms for semiseparable matrices
    • An implicit $QR$-algorithm for symmetric semiseparable matrices
      • Unreduced symmetric semiseparable matrix
      • The shift $\kappa$
      • An implicit $QR$-step on a symmetric semiseparable matrix
      • Proof of the correctness of the implicit approach
    • An implicit $QR$-algorithm for Hessenberg-like matrices
      • The shift $\kappa$
      • An implicit $QR$-step on the Hessenberg-like matrix
      • Chasing the disturbance in the matrix $Z_2$
    • An implicit $QR$-algorithm for computing the singular values
      • The standard $QR$-method for the calculation of the singular values
      • Unreduced upper triangular semiseparable matrices and the shift $\kappa$
      • The new method via upper triangular semiseparable matrices
      • Chasing the bulge
      • One iteration of the new method applied to upper triangular semiseparable matrices.
    • Conclusions
  • Implementations and numerical experiments of $QR$-algorithms
    • Implementation of the $QR$-factorization
    • The $QR$-algorithm for symmetric semiseparable matrices
    • The reduction to unreduced form
    • The $QR$-algorithm for symmetric semiseparable matrices
    • Deflation after a step of the $QR$-algorithm
    • Computing the eigenvectors
      • Computing all the eigenvectors
      • Selected eigenvectors
      • The eigenvectors of an arbitrary symmetric matrix $A$
    • The implementation of the $QR$-algorithms
    • Tests on the symmetric eigenvalue solver
      • The block experiment
      • Stewart's devil's stairs
      • Problem matrices
      • Cutting off the last eigenvalue
    • The $QR$-algorithm for the computation of the singular values
    • Conclusions
  • Software package for semiseparable matrices
    • General tools
      • Retrieving the Givens-vector representation
      • Constructing the matrices from the representation
      • Various tools
    • Reduction Algorithms
    • $QR$-tools
      • $QR$-solver
      • Reduction to unreduced form
      • An implicit $QR$-step without shift
      • An implicit $QR$-step with shift
      • The eigen(singular)value decomposition
    • Eigenvalue and singular value tools
  • Conclusions and future research
  
  
• Bibliography
• Index
  • Curriculum Vitae
  
  
• About this document ...