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 20 : Full size:
PDF.
Reduced: PDF .
Posted on:
Wed 12 Apr 2023 02:04:54 PM CDT
Topics:
Back to scientific computing; Parallel methods;
Domain Decomposition techniques;
Distributed sparse matrices;
Distributed sparse matvec; communication;
Distributed preconditioners;
Additive and Multiplicative Schwarz;
Schur complement techniques;
Graph partitioning.
- Set number 19 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue 11 Apr 2023 04:06:25 PM CDT
Topics:
Supervised learning; basics; labeled data;
Classification problems; KNN classification;
Linear Classifiers; Fisher Lin. Discrimants;
Support Vector Machines; Deep Neural Networks.
- Set number 18 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun 09 Apr 2023 03:54:29 PM CDT
Topics:
Clustering; Basic method: K-means; Similarity graphs; kNN graphs;
Measures of separation: edge cuts, normalized cuts, etc;
Building a kNN graph; Application: Segmentation.
Graph embeddings; Laplacean Eigenmaps;
Locally Linear Embeddings (LLE);
Explicit mappings; PCA, LPP, ONPP.
- Set number 17 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun 02 Apr 2023 04:57:05 PM CDT
Topics:
Graph Laplaceans and their application;
Graph partitioning; Spectral graph partitioning;
Introduction to Clustering.
- Set number 16 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sat 25 Mar 2023 11:17:59 AM CDT.
Note: reposted Sun Apr 9 18:46:57 CDT 2023 - some definitions of centralities changed
Topics:
Back to graphs; paths in graphs; Perron Frobenius theorem;
Powers of matrices; Notions of centrality; Page Rank centrality; Other notions of node centrality.
- Set number 15 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue 21 Mar 2023 06:07:01 PM CDT
Topics:
Eigenvalue problems, continued; Preconditioniong;
Shift-invert; polynomial preconditioning; implicit restarts;
The Davidson algorithm; Jacobi-Davidson; Harmonic Ritz values.
(Note: A subset of these topics will be covered)
- Set number 14 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue 14 Mar 2023 04:00:42 PM CDT
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 13 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun 12 Mar 2023 02:31:27 PM CDT
Topics:
Preconditioning; Introduction; Preconditioned iterations;
Preconditioned CG; Preconditioned FOM/GMRES; Standard Preconditioners
ILU preconditopners; ILU(0), ILU(p), ILUT.
- Set number 12 : Full size:
PDF.
Reduced: PDF .
Posted on:
Wed 01 Mar 2023 10:44:54 AM CST
Topics:
Convergence results; Background: Best uniform approximation;
Chebyshev polynomials; Analysis of the CG algorithm;
Analysis in the non-Hermitian case.
- Set number 11 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue 21 Feb 2023 03:44:54 PM CST
Topics:
Krylov subspace methods (Continued); Practical variants:
Restarting & truncating; Hermitian case: The Lanczos algorithm;
Conjugate gradients.
- Set number 10 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun 19 Feb 2023 02:17:12 PM CST
Topics:
Krylov subspace methods; Introduction; Krylov subspaces;
Gram Schmidt process (review); The Arnoldi process;
FOM and GMRES.
- Set number 9 : Full size:
PDF.
Reduced: PDF .
Posted on:
Tue 14 Feb 2023 03:04:50 PM CST
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 8 : Full size:
PDF.
Reduced: PDF .
Posted on:
Mon 13 Feb 2023 08:16:17 AM CST
Topics:
Direct methods (Cont.); Sparse LU/Cholesky factorizations;
The four stages of a sparse direct solver;
Elimination trees; Symbolic factorization.
Multifrontal methods; Supernodes; Existing software.
(Last set of notes on direct solvers).
- Set number 7 : Full size:
PDF.
Reduced: PDF .
Posted on:
Sun 12 Feb 2023 10:59:48 AM CST
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 05 Feb 2023 04:48:35 PM CST
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:
Tue 31 Jan 2023 08:35:50 AM CST
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:
Sun 29 Jan 2023 04:22:51 PM CST
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:
Tue 24 Jan 2023 11:00:46 AM CST
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 20 Jan 2023 11:11:07 AM CST
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:
Mon 16 Jan 2023 09:40:37 AM CST
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 2023