Math 221 Matrix Computation 13 Sept. 1996 ~~~~~~~~~~~~~~~~~~ MWF 9-10 in 405 Soda Hall, NOT 2 Evans. Instructor: Prof. W. Kahan, 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.