C S C I 8 3 1 4
Lecture Notes
Note: Reduced means 4 viewgraphs per page.
Full size is one per page.
[ For any problems send e-mail to saad@umn.edu ! ]
- Set number 16 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Apr 13 17:09:27 CDT 2021
Topics:
Eigenvalue problems. Introduction; Projection methods;
Subspace iteration; Arnoldi's method; Restarting; Deflation;
The symmetric Lanczos algorithm; Reorthogonalization;
Convergence of the Lanczos process; Lanczos biorthogonalization.
- Set number 15 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Mar 30 15:22:22 CDT 2021
Topics:
Convergence results; Background: Best uniform approximation;
Chebyshev polynomials; Analysis of the CG algorithm;
Analysis in the non-Hermitian case.
- Set number 14 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Mar 23 18:50:37 CDT 2021
Topics:
Krylov subspace methods (Continued); Practical variants:
Restarting & truncating; Hermitian case: The Lanczos algorithm;
Conjugate gradients.
- Set number 13 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Sun Mar 21 16:13:09 CDT 2021
Topics:
Krylov subspace methods; Introduction; Krylov subspaces;
Gram Schmidt process (review); The Arnoldi process;
FOM and GMRES.
- Set number 12 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Wed Mar 10 10:24:27 CST 2021
Topics:
Introduction to iterative methods. Background and motivation;
Basic iterations: relaxation techniques.
Projection-type methods; Background on projectors;
Projectors and subspaces; General results;
One-dimensonal projection methods; Steepest descent;
Minimal Residual; Residual norm steepest descent.
- Set number 11 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Mon Mar 8 12:53:57 CST 2021
Topics:
Graph methods, continued. Graph embeddings;
Laplacean Eigenmaps; Locally Linear Embeddings (LLE);
Explicit mappings; PCA, LPP, ONPP.
- Set number 10 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Mon Mar 8 12:52:29 CST 2021
Topics:
Clustering; Basic method: K-means; Similarity graphs; kNN graphs;
Measures of separation: edge cuts, normalized cuts, etc;
Building a kNN graph; Application: Segmentation.
- Set number 9 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Mar 2 07:04:34 CST 2021
Topics:
Back to graphs; Graph Laplaceans;
Graph partitioning; Spectral graph partitioning; Introduction to Clusterin
- Set number 8 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Sun Feb 21 18:20:34 CST 2021
Topics:
Direct methods and sparse LU/Cholesky factorizations;
The four stages of a sparse direct solver;
Elimination trees; Symbolic factorization.
Multifrontal methods; Supernodes.
- Set number 7 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Feb 16 08:44:13 CST 2021
Topics:
Reordering and permutations; Band reduction techniques;
Reversed Cuthill Mc Kee; Multicoloring methods
Minimal degree ordering and variants;
Nested dissection; complexity for model problems.
- Set number 6 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Sun Feb 14 17:12:38 CST 2021
Topics:
Introduction to Sparse linear systems; Versions of LU
factorizations (dense case); Sparse Column Cholesky;
Graph model for Sparse Gaussian Elimination;
Rose and Tarjan's Fill path theorem.
- Set number 5 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Mon Feb 8 10:19:41 CST 2021
Topics:
Triangular systems; Solving sparse triangular
systems with sparse right-hand-sides.
LU factorization from Sparse triangular solves
- Set number 4 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Feb 2 18:09:50 CST 2021
Topics:
Background on graph theory; general definitions; implementations;
Paths and cycles; connected graphs; acyclic graphs;
Graph traversals; Depth-First Search; Topological sorting;
Graph models; Graphs and sparse matrices;
Bipartitie representations; Hypergraphs;
Application: paths in graphs; Markov chains (brief).
- Set number 3 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Sun Jan 31 14:39:52 CST 2021
Topics:
General data structures for sparse matrices;
Sparse matrix formats; COO, CSR, CSC; etc.
Matrix vector products
- Set number 2 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Sun Jan 24 19:21:53 CST 2021
Topics:
Origins of sparse matrices; Typical problems;
Discretization of Partial Differential Equations;
In brief: Finite Differences and Finite Element methods
- Set number 1 : Full size:
PDF.  
Reduced: PDF .  
Posted on:
Tue Jan 19 10:11:02 CST 2021
Topics:
Introduction; Types of problems seen in this course ;
General introduction; Motivation; historical perspective;
Pointers to resources; Sparse matrices - definition;
Structured, unstructured sparsity; sparse matrices in matlab.
csci 8314 - Spring 2021