U.C. Berkeley Math 221 Home Page

Matrix Computations / Numerical Linear Algebra

Fall 2014

MWF 11-12, 2 Evans Hall

Instructor:

  • Jim Demmel
  • Offices:
    564 Soda Hall ("Virginia"), (510)643-5386
    831 Evans Hall
  • Office Hours - T 10:30-11:30 (changed as of Sep 16), Th 1-2, F 1-2 in 564 Soda
  • (send email)

    • Reader:

  • The reader for Ma221 is Nick Knight (send email)

    • Administrative Assistants:

  • Roxana Infante / Tammy Johnson
  • Offices: 563 / 565 Soda Hall
  • Phones: (510)643-1455 / (510)643-4816
  • Email: (to Roxana) / (to Tammy)

    • Announcements:

  • (12/1) The poster session for class projects will be Dec 11, 10-12am, in the 5th floor hallway of Soda Hall. We will supply posterboards and easels, available in the 5th floor ASPIRE Lab.
  • (11/2) The due date for Homework 9 is extended until Nov 5.
  • (10/29) I posted an updated version of Lecture 22 at 9am today.
  • (10/23) Answers for HW 5, 6 and 7 are posted at bcourses.berkeley.edu.
  • (10/12) A correction for HW 6, Question 3.17, p. 137, has been posted in the List of Errata
  • (9/30) I just posted HW 5, and answers for HW 4.
  • (9/24) I just posted a new version of the HW 2 answers on bcourses with some minor corrections. I also posted HW 3 answers.
  • (9/21) I just posted a new version of the HW 1 answers on bcourses with some minor corrections.
  • (9/17) I'd like to pass on a request from the grader to please write neatly (if you turn in hand-written homework). If the grader can't read your writing without a great effort, then you may not get all the credit you should have gotten.
  • (9/16) Starting today, my Tuesday office hours will be 10:30-11:30.
  • (9/15) Answers to Homework 1 have been posted at bcourses.berkeley.edu. Future homework answers will also be posted there.
  • (9/7) Question 1.5 is about vector norms, a topic that we will not get to until Monday's lecture. So if you prefer to wait and turn that in with the next homework, that is ok. Sorry for the late notice.
  • (9/5) We have set up an on-line question-and-answer system using Piazza, which we encourage you to use to post questions and engage in discussions.
  • (9/5) Office hours are cancelled today, due to prelims.
  • (8/29) Welcome to Ma221!

    • Handouts

  • Course Overview in pdf, including syllabus, prerequisites, pointers to other references, and grading.
  • Class Survey . Please fill this out and email it to demmel@berkeley.edu if you did not get the copy in class.
  • An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Shewchuk, is a very easy to understand description of one of the most popular iterative methods for solving A*x=b. In contrast to the terse treatment in the course text book, you might want to see Shewchuk's answer to the question "How could fifteen lines of code take fifty pages to explain?"
  • Lectures notes on Multigrid, in powerpoint.

    • Textbook

  • Applied Numerical Linear Algebra by J. Demmel, published by SIAM, 1997.
  • List of Errata for the Textbook (This will be updated during the semester. Suggestions welcome!)

    • Homework assignments

    Matlab Programs for Homework Assignments

    Lecture Notes

    Other Online Software and Documentation

  • Matlab documentation is available from several sources, most notably by typing ``help'' into the Matlab command window.
  • Netlib, a repository of numerical software and related documentation
  • Netlib Search Facility, a way to search for the software on Netlib that you need
  • GAMS - Guide to Available Math Software, another search facility to find numerical software
  • Linear Algebra Software Libraries and Collections
  • LAPACK, state-of-the-art software for dense numerical linear algebra on workstations and shared-memory parallel computers. Written in Fortran.
  • LAPACK Manual
  • LAPACKE, a C interface to LAPACK.
  • ScaLAPACK, a partial version of LAPACK for distributed-memory parallel computers.
  • ScaLAPACK manual
  • LINPACK and EISPACK are precursors of LAPACK, dealing with linear systems and eigenvalue problems, respectively.
  • SuperLU is a fast implementations of sparse Gaussian elimination for sequential and parallel computers, respectively.
  • Updated survey of sparse direct linear equation solvers, by Xiaoye Li
  • BEBOP (Berkeley Benchmarking and Optimization) is a source for automatic generation of high performance numerical codes, including OSKI, a system for producing fast implementations of sparse-matrix-vector-multiplication. (OSKI stands for Optimized Sparse Kernel Interface, and only coincidentally is also the name of the Cal Bear mascot :) ).
  • Sources of test matrices for sparse matrix algorithms
  • Matrix Market
  • University of Florida Sparse Matrix Collection
  • Templates for the solution of linear systems, a collection of iterative methods, with advice on which ones to use. The web site includes on-line versions of the book (in html and postscript) as well as software.
  • Templates for the Solution of Algebraic Eigenvalue Problems is a survey of algorithms and software for solving eigenvalue problems. The web site points to an html version of the book, as well as software.
  • MGNet is a repository for information and software for Multigrid and Domain Decomposition methods, which are widely used methods for solving linear systems arising from PDEs.
  • Resources for Parallel and High Performance Computing
  • NERSC (National Energy Research Scientific Computing Center), a DOE supercomputer center at neighboring LBL (Lawrence Berkeley National Lab), that provides supercomputer resources to problems of interest to DOE
  • XSEDE provides access to the network of high performance computing facilities operated by NSF
  • CS 267, Applications of Parallel Computers, including slides and videos of lectures on parallel linear algebra
  • ParLab Parallelism 3-Day Short Course (2014), including slides and videos of (shorter) lectures on parallel linear algebra
  • Previous versions available here
  • ACTS (Advanced CompuTational Software) is a set of software tools that make it easier for programmers to write high performance scientific applications for parallel computers.
  • PETSc: Portable, Extensible, Toolkit for Scientific Computation
  • Issues related to Computer Arithmetic and Error Analysis
  • ``Accurate and efficient expression evaluation and linear algebra,'', J. Demmel, I. Dumitriu, O. Holtz, P. Koev Acta Numerica, V. 17, May2008
  • ``Computing the Singular Value Decomposition with High Relative Accuracy,'' J. Demmel, M. Gu, S. Eisenstat, I. Slapnicar, K. Veselic, Z. Drmac, Lin. Alg. Appl., v 299, Nov 1999
  • Efficient software for very high precision floating point arithmetic
  • ARPREC
  • GMP
  • Efficient software for high precision and reproducible Basic Linear Algebra Subroutines (BLAS)
  • XBLAS
  • ReproBLAS
  • Notes on IEEE Floating Point Arithmetic, by Prof. W. Kahan
  • Other notes on arithmetic, error analysis, etc. by Prof. W. Kahan
  • Report on arithmetic error that cause the Ariane 5 Rocket Crash
  • The IEEE floating point standard was updated in 2008. Look here for a summary.
  • For a variety of papers on solving linear algebra problems with guaranteed accuracy, see Siegfried Rump's web site