Math 221 Matrix Computation 13 Sept. 1996
~~~~~~~~~~~~~~~~~~
MWF 9-10 in 405 Soda Hall, NOT 2 Evans.
Instructor: Prof. W. Kahan, <wkahan@cs> 642-5638
863 Evans Hall / 733 Soda Hall
TA: None; the Math. and CS. Depts. are too short of TAs.
Class Home Page: http://www.cs.berkeley.edu/~wkahan/ma221
~~~~~~~~~~~~~~~~
Text: "Numerical Linear Algebra"
~~~~~ Berkeley Lecture Notes in Mathematics, Volume I,
by James Demmel, dated Aug. 25, 1996
( Available from Copy Central, 2560 Bancroft Way.)
Auxiliary text:
LAPACK Users' Guide, 2nd ed., E. Anderson et al, SIAM, 1995.
This describes how to use a library of state-of-the-art linear
algebra programs first written in FORTRAN, translated to C.
The software is available on the WWW at
http://www.netlib.org/lapack,
and the manual itself at
http://www.netlib.org/lapack/lug/lapack\_lug.html.
Prerequisite knowledge:
~~~~~~~~~~~~~~~~~~~~~~~
Linear Algebra at the level of Math. 110;
Numerical Analysis at the level of Math. 128A or B, or Eng. 118;
Use of MATLAB; and programming in Fortran or C or C++ .
Matlab is an interactive, user-friendly interface to a large body of
numerical and graphics software, including linear algebra, and is
used widely for testing and prototyping algorithms. For some problems
a better expedient is mixed language programming,-- calling a Fortran
routine from C or C++, or a C routine from Matlab.
Computer Resources:
~~~~~~~~~~~~~~~~~~~
Access to a computer on which a recent version of Matlab runs is
essential for this course; Matlab should be accessible from every
computer on campus because we have a site-license for it. The same can
be said for a WWW browser like Netscape or Mosaic. Attendees of
Math. 221 who lack adequate access to these computer resources should
consult the instructor for help towards remedying that lack.
Matlab documentation is available from at least three sources. First,
Matlab has an extensive on-line help facility (just type "help" or
"help commandname" in Matlab). Second, a brief manual only slightly
out of date is available free on the class homepage. Third, current
and comprehensive manuals can be inspected or purchased in the Computer
Center on the second floor of Evans Hall.
Grading:
~~~~~~~~
Final Exam or Project: 75%, Occasional Homework Assignments: 25%,
roughly. The class must help decide soon whether the semester will end
with a final exam for all, or a project from each student. Such a
project must be a scientific work, publishable at least in principle
but not necessarily original, that demonstrates a student's mastery of
a significant part of the course material by building upon it.
Students are encouraged to collaborate on all assignments except the
final exam, if there is one; however, work handed in for grading by
each student must be his own, even if some of it is copied, and must
acknowledge all assistance obtained from others.
Assignments may require programming in the campus UNIX environment.
Programs will be of two kinds: Fortran, C or C++ (your choice),
and Matlab. Assignments to be written in Fortran or C or C++
will need subroutines from the libraries LAPACK, CLAPACK, LINPACK
or EISPACK. Credit will be earned not by the program nor by results
obtained from it but rather by a competent explanation of the program's
design and its results.
Syllabus:
~~~~~~~~~
This course is concerned with the numerical solution of matrix problems
in three standard categories:
systems of linear equations,
best approximation by least squares,
eigenvalues, singular values, and corresponding vectors.
Basic considerations relevant to a variety of numerical problems will
be explored for those three categories. Among these considerations are
matrix factorizations and canonical forms,
perturbation theory and condition-numbers,
effects of finite precision and range upon algorithms,
difficulties exacerbated by gargantuan dimensionality,
analyzing an algorithm's speed, and
mathematical engineering of numerical software.
Ample software exists to solve problems in those standard categories,
but much of that software is still afflicted by failure modes. For
instance, although eigenvalues of both of the 4-by-4 matrices
( 0 0 0 -1 ) ( 0 1 0 0 )
( 1 0 0 0 ) and ( 1 0 -h 0 ) with h = 2 sin t
( 0 1 0 2-h*h ) ( 0 h 0 1 ) and
( 0 0 1 0 ) ( 0 0 1 0 ) 0 < t < 1/2^22
are the same and easy to compute by hand, MATLAB versions 3.5m and
4.2c.1 balk at both of them. Open problems that persist even among
otherwise well-established solution techniques supply food for thought.
Annotated Survey of Relevant Readings:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Computer Solution of Linear Algebraic Systems, G. Forsythe and C.
Moler, Prentice Hall, 1967. Easy-to-read introduction to numerical
linear algebra.
Fundamentals of Matrix Computations, David Watkins, Wiley, 1991.
Very readable beginning graduate level textbook.
Matrix Computations, G. Golub and C. Van Loan, 2nd ed. Johns Hopkins
Press, 1989. The standard compendium of dense matrix computations. A
third edition is in press.
Templates for the Solution of Linear Systems: Building Blocks for
Iterative Methods, R. Barrett et al. SIAM 1994. Software and text
also available on the WWW at
http://www.netlib.org/templates/index.html.
Introduction to Matrix Computations, G. Stewart, Academic Press.
Dated introduction to numerical linear algebra covering basic material
well.
The Algebraic Eigenvalue Problem, J. Wilkinson, Clarendon Press, 1965.
The first comprehensive presentation of numerical linear algebra from
the modern error-analytic point of view, and beautifully written.
Rounding Errors in Algebraic Processes, J. Wilkinson, Prentice Hall,
1963. The first presentation of rounding error analysis for linear
and polynomial equations.
A Survey of Error Analysis, W. Kahan, pp. 239 ... in Information
Processing 71 ( Proc. IFIP Congress 1971 ) North Holland, 1972.
A short bemusing account of the anomalies that afflicted computer
arithmetics in the 1970s. For the state of affairs now see
http://http.cs.berkeley.edu/~wkahan/ieee754status/ieee754.ps
Accuracy and Stability of Numerical Algorithms, N.J. Higham, SIAM,
1996. The best account of contemporary error analysis, but long.
Advanced Functions Handbook for the Hewlett-Packard 15C, Appendix on
the Accuracy of Nymerical Calculations, and Section 4 on Using Matrix
Operations, 1982. The shortest introduction to contemporary error
analysis.
Perturbation Theory for Linear Operators, T. Kato, Prentice Hall.
Comprehensive account of analytic perturbation theory for eigenvalues
and eigenvectors; chapter 2 covers the finite dimensional case, which
is one of the topics of this course.
Solving Least Squares Problems, C. Lawson and R. Hanson, Prentice Hall,
1974. Survey of methods for linear unconstrained and constrained least
squares problems. A new book on the same subject by A. Bjorck has
just been published by SIAM.
The Symmetric Eigenvalue Problem, B. Parlett, Prentice Hall. A second
edition is expected soon from Oxford Univ. Press. Best treatment of
algebraic and analytic theory and algorithms for symmetric matrices.
LINPACK User's Guide, J. Dongarra, C. Moler, J. Bunch, G. Stewart,
SIAM, 1979. User's manual for the state of the 1970's art in linear
equation solving software; precursor of LAPACK.
EISPACK User's Guide, Vols 1,2, (Published as Lecture Notes in
Computer Science, Vols 6, 51), Springer. User's manual for state of
the 1970's art in eigensystem software, precursor to LAPACK.
Handbook for Matrix Computations, T.F. Coleman & C. Van Loan, SIAM
1988. A cookbook guide to the use of LINPACK and MATLAB v. 3.5 .
Numerical Recipes in Fortran ( or in C ), the Art of Scientific
Computing, 2nd. ed., W.H. Press, S.A. Teukolsky, W.V. Vetterling,
B.P. Flannery, Cambridge Univ. Press, 1992. The second edition of
this cookbook is much better than the first but still idiosyncratic,
and sometimes careless about theoretical details like limits to a
recipe's domain of validity.