Video material in the course

Julia intro: https://play.kth.se/media/0_cg2dbl0v

Block 1: Iterative methods for large and sparse eigenvalue problems

• Rayleigh quotient:
  • 104 Rayleigh quotient definition and accuracy: https://play.kth.se/media/t/0_j5jfpeol
  • 105 Minimization interpretation https://play.kth.se/media/t/0_fwvwpvxb
• Power method:
  • 110 Definition & Introduction: https://play.kth.se/media/t/0_fikp6zrx
  • Proof of power method convergence:
    • 111 To which eigenvalue:  https://play.kth.se/media/t/0_elronlef
    • 112 Convergence speed: https://play.kth.se/media/t/0_dn4klwwu
• 120 Inverse iteration: https://play.kth.se/media/t/0_kodgxz18
• 130 Rayleigh quotient iteration: https://play.kth.se/media/t/0_q6evbded
• 140 Rayleigh-Ritz method derivation: https://play.kth.se/media/t/0_pgq7n2nt
• 141a Rayleigh-Ritz method convergence theory part 1:  Bauer-Fike theorem https://play.kth.se/media/0_xtk09cm4
• 141b Rayleigh-Ritz method convergence theory part 2:  Derivation of bound  https://play.kth.se/media/t/0_vrylvoyf
• 142 Rayleigh-Ritz method: small example https://play.kth.se/media/t/0_fnd3eqd3
• Numerical Gram-Schmidt orthogonalization:
  • 150 Classical Gram-Schmidt & Repeated Gram-Schmidt: https://play.kth.se/media/t/0_ru0cn21d
  • 151 Modified Gram-Schmidt: https://play.kth.se/media/t/0_inznie5i
  • 152 CPU-timing demo (beyond the scope of the course but may help to understand observations in HW1): https://play.kth.se/media/t/0_u6f5om44
• Arnoldi method:
  
  • 160 Arnoldi factorization and derivation of Arnoldi method: https://play.kth.se/media/t/0_xleo1rha
  • 162 Krylov subspaces and Arnoldi's method: https://play.kth.se/media/t/0_jzcqs8er
  • 165 Convergence of the Arnoldi method for eigenvalue problems: Part 1 statement of main theorem: https://play.kth.se/media/t/0_layolchr
  • 166 Convergence of the Arnoldi method for eigenvalue problems: Part 2 proof of main theorem: https://play.kth.se/media/t/0_0geih9f6
  • 167 Convergence of the Arnoldi method for eigenvalue problems: Part 3 convergence disks: https://play.kth.se/media/t/0_mr869wxy
  • 167b Convergence of the Arnoldi method for eigenvalue problems: Part 4 outlier theory: https://play.kth.se/media/t/0_cn0saapp
  • 168 Shift and invert Arnoldi method for eigenvalue problems: https://play.kth.se/media/t/0_vr45ztje
  • 170 Lanczos method: https://play.kth.se/media/t/0_6fz0pho5
  • 169 Breakdown: https://play.kth.se/media/t/0_g3jov29e

Block 2: Iterative methods for large and sparse linear systems

• 201 Application: CPU socket https://play.kth.se/media/t/0_n0cnxcqv
• 202a Plotting with against CPU-time (CG application): https://play.kth.se/media/t/0_o6mmqivi
• 202b Plotting with against CPU-time (Precond GMRES application): https://play.kth.se/media/0_rebb52fi
• GMRES
  • 210 GMRES derivation from AM: https://play.kth.se/media/t/0_bhu8ji9i (new)
  • 212 GMRES convergence theory 1: Convergence theory preparation:  https://play.kth.se/media/t/0_qx56u1v3
  • 213 GMRES convergence theory 2: Main convergence theorem : https://play.kth.se/media/t/0_r2unnt87
  • 214 GMRES convergence theory 3: Disk bound and rule-of-thumb:  https://play.kth.se/media/t/0_2zba1c2v
  • 215 GMRES convergence theory 4: Disk bound with outlier https://play.kth.se/media/t/0_78mlxlu8
  • 216 GMRES preconditioning: https://play.kth.se/media/t/0_jeixnf2y
  • 217 GMRES preconditioning demo: https://play.kth.se/media/t/0_unskflne
• 220 Application: Arnoldi-Tikhonov regularization https://play.kth.se/media/t/0_mmgg2y9i
• Conjugate gradients
  • 230 Conjugate Gradients intro: https://play.kth.se/media/t/0_rsdgaznt
  • 231 Conjugate Gradients derivation part 1: Residual is orthogonal to a Krylov subspace:  https://play.kth.se/media/t/0_0x1sgsz2
  • 232a Conjugate Gradients derivation part 2: Short term-recurrence ansatz: https://play.kth.se/media/t/0_6c1k5ej9
  • 232b  Conjugate Gradients derivation part 3: Orthogonality properties of r- and p- vectors https://play.kth.se/media/t/0_s1tl3mig
  • 233 CG demo: https://play.kth.se/media/t/0_ymj8gh8y
  • 234 CG preconditioning 1: https://play.kth.se/media/t/0_qj31rbuj
  • 235 CG preconditioning 2: https://play.kth.se/media/t/0_4pf3g58h (new recording)
• Conjugate gradients normal equations
  • 240 CGNE - derivation of conjugate gradients normal equations: https://play.kth.se/media/t/0_pgxt4plx
  • 241 CGNE convergence theory: https://play.kth.se/media/t/0_uhog3mui
  • 242 CGNE matlab demo: https://play.kth.se/media/t/0_j3ids6s0
• 250 BiCG from PCG: https://play.kth.se/media/t/0_xlka5ac7

Block 3: The QR-method

• 302: The two-phase approach: https://play.kth.se/media/t/0_iktgzhcp
• Phase 1: Hessenberg reduction
  • 312: Householder reflectors that map x to the direction of e1: https://play.kth.se/media/t/0_4fyax1bm
  • 313: Hessenberg reduction: https://play.kth.se/media/t/0_r9p5kfxs
• Phase 2: Hessenberg QR-method
  
  • 323 Givens rotations: Definition and example: https://play.kth.se/media/t/0_qs6gs4aq
  • 325 QR-factorization of Hessenberg via Givens derivation: https://play.kth.se/media/t/0_bv950zzu
  • 326 QR-factorization of Hessenberg via Givens (matlab demo): https://play.kth.se/media/t/0_bbmkydoo
• Acceleration and deflation:
  • 331: Shifted QR-method introduction: https://play.kth.se/media/t/0_e7xcfls9
  • 333: Shifted QR-method with exact shifts: https://play.kth.se/media/t/0_y3gbs2y9
  • 335: Shifted QR-method with Deflation: https://play.kth.se/media/t/0_v84xxo7m
• Convergence theory of QR-methog:
  • 341 Part 0. Overview of the convergence approach: https://play.kth.se/media/t/0_ufdf8abw
  • 344 Part 1. NSI <=> USI https://play.kth.se/media/t/0_q566cfc2
  • 345 Part 2. Convergence unnormalized simultaneous iteration for special case: https://play.kth.se/media/t/0_0gn999z7
  • 346 Part 3. Convergence unnormalized simultaneous iteration general: https://play.kth.se/media/t/0_5e12jksb
  • 349 Matlab illustration: USI convergence https://play.kth.se/media/0_9punjw92

Block 4: Algorithms for matrix functions

• 402 Application in data science: Estrada index and subgraph centrality TODO
• 403 Proof of the Taylor definition https://play.kth.se/media/t/0_mp1d50te  
• General methods
  • 414a Schur-Parlett for a 2x2 matrix: https://play.kth.se/media/t/0_hq17szfe
  • 414b Schur-Parlett: f(T) where T triangular https://play.kth.se/media/t/0_v78zlt6q (new)
• Specialized matrix function methods
  • 421 Scaling-and-squaring for the matrix exponendial:  https://play.kth.se/media/t/0_36lwyyq3
  • 423 Newton SQRTM: https://play.kth.se/media/t/0_hpdzaw0c
  • 424 Denman-Beavers iteration: https://play.kth.se/media/t/0_a4uw3wjj
  • 425 Matrix sign function: https://play.kth.se/media/t/0_hzu65o3d
• Krylov methods for f(A)b
  
  • 432 Shift invariance: https://play.kth.se/media/t/0_h9cvc79y
  • 434 FOM derivation https://play.kth.se/media/t/0_u4e77gi6
  • 437 Matlab example Krylov method for f(A)b (no audio): https://play.kth.se/media/t/0_41s7n5qv
• 441 Phi-functions and exponential integrators https://play.kth.se/media/t/0_p24djy88

• 101 Applications: https://play.kth.se/media/t/0_6hjn401v