MATH 7664 ITERATIVE METHODS IN NUMERICAL LINEAR ALGEBRA

Spring 2004. University of Colorado at Denver

HOURS: CU-Dravo, MW 4-5:15.

INSTRUCTOR:
Prof. Andrew Knyazev
Office: CU (Dravo) 644. Phone: 556-8102.
Office hours: by appointment
WWW: http://math.ucdenver.edu/~aknyazev/
Email: aknyazev@math.ucdenver.edu

TEXTBOOKS:

Please note that the SIAM offers 30% off list price discounts on books to SIAM members and at present every graduate student at the UC Denver can get a FREE SIAM membership! Read about Complimentary Graduate Student Memberships and join SIAM today!

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:

• Hypre install with LOBPCG drivers
• Hypre linear solvers scalability on our Beowulf cluster
• Testing the latest Hypre distribution
• Hypre eigenvalue solvers scalability on our Beowulf cluster

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

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

• Hermitian Problems---CG and MINRES
• Non-Hermitian Problems---GMRES

• Some Numerical Examples
• The Lanczos Algorithm
• Orthogonal Polynomials

• The Two-Sided Lanczos Algorithm
• The Biconjugate Gradient Algorithm
• Which Method Should I Use?

• The Faber and Manteuffel Result
• Implications

• Symmetrizing the Problem
• Error Estimation and Stopping Criteria
• Attainable Accuracy
• Computer Implementation

Chapter 8. Overview and Preconditioned Algorithms

Chapter 9. Two Example Problems

• The Diffusion Equation
• Poisson's Equation

• Incomplete Cholesky Decomposition
• Modified Incomplete Cholesky Decomposition

• 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

Special dates (Tentative):