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@cs.umn.edu ! ]
- Set number 16 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue Apr 16 15:54:01 CDT 2019
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:
Mon Apr 15 12:12:31 CDT 2019
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 Apr 9 16:39:17 CDT 2019
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:
Mon Apr 8 17:19:45 CDT 2019
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:
Sun Mar 24 17:14:26 CDT 2019
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 10 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun Mar 10 17:02:59 CDT 2019
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 5 09:29:39 CST 2019
Topics:
Back to graphs; Graph Laplaceans;
Graph partitioning; Spectral Graph Partitioning; Introduction to Clustering.
- Set number 8 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun Mar 3 14:04:44 CST 2019
Topics:
Direct methods and sparse LU/Cholesky factorizations;
The four stages of a sparse direct solver;
Elimination trees; Symbolic factorization.
- Set number 7 : Full size:
PDF.
Reduced: PDF .
Posted on:
Mon Feb 25 11:37:51 CST 2019
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 24 17:21:16 CST 2019
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:
Fri Feb 15 11:01:15 CST 2019
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:
Fri Feb 1 14:21:57 CST 2019
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).
Supplement: (login needed)
paper on: Random walks in graphs
- Set number 3 : Full size:
PDF.
Reduced: PDF .
Posted on:
Fri Feb 1 14:19:47 CST 2019
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:
Fri Jan 25 10:42:14 CST 2019
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 22 13:08:07 CST 2019
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 2019