Date: Wed, 20 Nov 1996 22:33:11 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 8751
Last-modified: Sun, 17 Nov 1996 13:43:49 GMT
B573, Section 1179: Scientific Computing II
B573: Scientific Computing II
- Iterative Solution of Large Scale Systems - Fall 1996
- B573, Section 1179
- 2:00-3:20PM, MW
- 115 Lindley Hall
Contents
General Information
- Instructor:
- Prerequisites:
-
Mathematics M343 and one of M303 or M301, and a working knowledge of Fortran, C, or C++.
Students should be able to write and run programs under a UNIX operating system.
- Textbook:
- Iterative Methods for Sparse Linear Systems by Yousef Saad.
This is intended as a reference work, and the material covered in this
course is not identical to that in the textbook.
Office Hours
Same as on the home page: Mon - Wed, 9:00 - 10:00 AM.
Course Description
This course is for students in the sciences and applied mathematics whose research involves solving
large sparse linear systems on a computer, and for computer scientists interested in learning
the computational problems encountered in scientific and engineering codes.
Sparse linear systems occur in most large scale physical modeling
programs and often the setting up and solution of them accounts for the majority of the computer time.
This course will focus on practical methods and their computer implementation,
with a minimal amount of the underlying mathematical theory.
High level tools will be used in order to quickly implement and test methods.
Existing software will also be used whenever possible,
to avoid building everything from scratch, and to learn how to use existing software resources.
Course goals include the ability to understand the influence of computer
architecture on the choice of methods and data structures,
the strengths and weaknesses of basic methods, common sources of large sparse linear systems,
and the resulting implications for choosing methods and implementations.
Students will finish the semester with a toolkit of solvers that they can
then use for solving scientific problems, for
probing computer architectures, or
for obtaining a deeper understanding of the methods commonly used in
scientific computing.
Tentative Course Outline
- A quick start: everything you knew about solving linear systems from your linear algebra course.
- Introduction
- Basic linear algebra you haven't seen before
- Sources of large sparse linear systems
- Computer architecture basics
- Data structures and stopping tests
- Iterative methods: pre-1972 technology
- Linear stationary
- Conjugate gradients (CG): theory
- CG convergence properties
- Preconditioning CG
- Computational kernels and software resources
- Expressing iterative methods in terms of kernel operations
- Toolkits for sparse system manipulations: Sparskit, Sparse BLAS
- Packages: PetsC, Aztec, SPLIB, Templates
- Finding and using numerical software from the Net
- Iterative methods: recent technology
- Basic derivation ideas: orthogonalization, restarts, truncation
- CG on normal equations
- Generalized Conjugate Residuals, Orthomin(m), GCR(m)
- Generalized Minimal Residuals, GMRES(m)
- Bi-conjugate gradients, CG-squared, CG-Stab, QMR
- Preconditioning and related ideas
- Scaling/equilibration
- Incomplete factorization
- Polynomial methods and preconditioning
- Other "preconditioning" methods
- Crafting a solution strategy
- Choice of solvers
- Choice of preconditioners
- Choice of stopping test(s)
- Reading the literature: judicious use of a jaundiced eye
Class Newsgroup
The course newsgroup, ac.csci.b573, will be
used to post announcements, assignments, corrections, and any exceptions
to usual office hours. Use it to post
questions related to the course or share related information with the
class. You are responsible for checking the newsgroup frequently, since
any changes or corrections to assignments will appear there.
Grading Policies
Grades are based on projects involving writing and/or analyzing computer programs.
Written reports are required for these projects.
Each assignment will have questions intended to begin your thinking process,
not end it. Grading will also be based on the questions you raise and answer in these projects.
For example, if the question is "Which of the methods A and B is faster,"
simply saying "A" is not sufficient. You should also ask the underlying
question ``What measure of fast is appropriate here?'', "Why is A faster?", etc.
Most projects you can tackle in groups.
However, you must give full attribution for any outside sources you use for ideas, software, or help.
Also, I reserve the right to call on any member of the group to
present/explain/defend/justify the group's work and to base the
entire group's grade on that member's performance. So be careful who you team up with!
Cheating
Don't. You can get away with virtually any lifting or scavenging of material,
provided you cite the source. If your citation is "I photocopied another student's
write-up" then you won't get many points on the assignment, but at least you
won't be branded with a scarlet "P" and tarred and feathered.
Assignments
Assignments will be given often; a total of 10-15 will
be given (depending on the chunk size of each one!).
Lecture Notes
This is not a full or complete set of lecture notes; in the
words of a not-so-great philosopher, "You had to be there".
If you miss a lecture,
be sure to check with other students in the class for what went on.
These are in Postscript, since latex2html still is not up to snuff
for papers with lots of math symbols.