Current
enrollment
HOURS: TR 0530PM-0645PM
CU-Dravo, 626.
INSTRUCTOR:
Prof. Andrew Knyazev
Office: CU (Dravo) 644. Phone: 556-8102.
Office hours: by appointment
WWW: http://www-math.cudenver.edu/~aknyazev/
TEXTBOOKS:
Iterative Methods for Solving Linear Systems,
Anne Greenbaum
Format: Paperback, 220pp. ISBN: 089871396X
Publisher: Society for Industrial & Applied Mathematics Pub. Date: September 1997
$44 from SIAM directly,
$52 from amazon.com
SUBJECT:
The course will cover basic aspects of iterative methods and preconditioning
for linear systems and symmetric eigenvalue problems.
This is the highest-level graduate class.
It will require
an independed work and a significant intellectual effort
in particular, to learn
PETSc
and
Hypre
software packages
and basics of parallel
programming, though, help will be provided.
Projects will be
PETSc
and
Hypre
based
programming assignments using departmental high-performance parallel Beowulf Cluster,
supported by the NSF Award
DMS MRI 0079719.
It is expected that students solve most of the problems of the textbook, suggested as exersises after
every section, as their homework, but solutions will not be collected. Hard problems will be discussed in class.
GRADING will based on Projects:
CONTENTS: The class will follow the outline below, touching on each major
topic in a depth that will be determined by the pace of the class.
Chapter 1. Introduction
-
Brief Overview of the State of the Art
-
Hermitian Matrices
-
Non-Hermitian Matrices
-
Preconditioners
-
Notation
-
Review of Relevant Linear Algebra
-
Vector Norms and Inner Products
-
Orthogonality
-
Matrix Norms
-
The Spectral Radius
-
Canonical Forms and Decompositions
-
Eigenvalues and the Field of Values
Part I. Krylov Subspace Approximations
Chapter 2. Some Iteration Methods
-
Simple Iteration
-
Orthomin(1) and the Steepest Descent
-
Orthomin(2) and CG
-
Orthodir, MINRES, and GMRES
-
Derivation of MINRES and CG from the Lanczos Algorithm
Chapter 3. Error Bounds for CG, MINRES, and GMRES
-
Hermitian Problems---CG and MINRES
-
Non-Hermitian Problems---GMRES
Chapter 4. Effects of Finite Precision Arithmetic
-
Some Numerical Examples
-
The Lanczos Algorithm
-
Orthogonal Polynomials
Chapter 5. BiCG and Related Methods
-
The Two-Sided Lanczos Algorithm
-
The Biconjugate Gradient Algorithm
-
Which Method Should I Use?
Chapter 6. Is There a Short Recurrence for a Near-Optimal Approximation?
-
The Faber and Manteuffel Result
-
Implications
Chapter 7. Miscellaneous Issues
-
Symmetrizing the Problem
-
Error Estimation and Stopping Criteria
-
Attainable Accuracy
-
Computer Implementation
Part II. Preconditioners
Chapter 8. Overview and Preconditioned Algorithms
Chapter 9. Two Example Problems
Chapter 11. Incomplete Decomposition
-
Incomplete Cholesky Decomposition
-
Modified Incomplete Cholesky Decomposition
Chapter 12. Multigrid and Domain Decompositon Methods
-
Multigrid Methods
-
Aggregation Methods
-
Extension to More General Finite Element Equations
-
Multigrid Methods
-
Multigrid as a Preconditioner for Krylov Subspace Methods
-
Basic Ideas of Domain Decomposition Methods
-
Alternating Schwarz Method
-
Many Subdomains and the Use of Coarse Grids
-
Nonoverlapping Subdomains
If time allows, a short review of preconditioned eigensolvers will
be presented using
Templates for the Solution of Algebraic Eigenvalue Problems:
a Practical Guide, Section
Preconditioned Eigensolvers
by A. Knyazev.
Special dates (Tentative):