U.C. Berkeley Math 221 Home Page

Matrix Computations / Numerical Linear Algebra

Spring 2016

MWF 12-1, 110 Wheeler Hall (starting Jan 22)

Instructor:

  • Jim Demmel
  • Offices:
    564 Soda Hall ("Virginia"), (510)643-5386
    831 Evans Hall
  • Office Hours: M 9-10, T 9-10 and F 1:30-2:30, in 564 Soda Hall
  • (send email)

    • Teaching Assistant:

  • Eric Hallman
  • Office Hours: F 9-11am, in 1058 Evans
  • Starting Tuesday Feb 16, office hours will be 1:30-3:30 Tuesdays in 1058 Evans
  • (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:

  • (4/18) The due date of Homework 12 is delayed 2 days, until Friday April 22 in class.
  • (4/17) As stated below, the project poster session will be Wednesday of RRR week, May 4, from 2-4pm in the 5th floor Soda Hall hallway. A poster can consist of standard 8.5-by-11 pieces of paper printed on a standard printer. We will supply easels, poster boards and pins that you can use to attach your posters to the poster board. If you want to print a single large poster, and need access to a suitable printer, this will need to be done at least one day earlier in the week, since many students (in other classes too) may be using it to print posters.
  • (2/17) The project poster session will be Wednesday of RRR week, May 4, from 2-4pm in the 5th floor Soda Hall hallway.
  • (2/09) Starting Tuesday, Feb 16, Eric Hallman's office hours will be Tuesdays, 1:30-3:30pm in 1058 Evans.
  • (1/22) The due date of homework 1 is postponed from Monday Jan 25 to Wednesday Jan 27.
  • (1/21) We are changing rooms (again) to a larger room, 110 Wheeler Hall, starting Friday Jan 22.
  • (1/20) Welcome to Ma221!
  • (1/20) Class Survey. Please fill out this on-line survey.
  • (1/20) Please sign up for Piazza, an on-line question-and-answer system which we encourage you to use.
  • (1/20) Homework 1 has been posted, due Jan 2527
  • (1/20) Answers to homework will be posted at bcourses.berkeley.edu.

    • Handouts

  • Course Overview in pdf, including syllabus, prerequisites, pointers to other references, and grading.
  • 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, Documentation, and Reference Material

  • 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, 2015 and 2016 version, including slides and videos of lectures on parallel linear algebra
  • ParLab Parallelism 3-Day Short Course (2013), including slides and videos of (shorter) lectures on parallel linear algebra
  • 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
  • References for 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, May 2008
  • Efficient software for very high precision floating point arithmetic
  • ARPREC
  • MPFR
  • 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, by using interval arithmetic, see Siegfried Rump's web site
  • References for Communication-Avoiding Algorithms
  • Minimizing Communication in Numerical Linear Algebra, G. Ballard, J. Demmel, O. Holtz, O. Schwartz, SIMAX, Sep 2011 (SIAM Linear Algebra Prize 2012) presents a complete proof of the communication lower bound for O(n^3) matrix multiplication and other classical linear algebra algorithms
  • Communication-Optimal Parallel and Sequential QR and LU Factorizations, J. Demmel, L. Grigori, M. Hoemmen, J. Langou, SIAM J. Sci. Comp., Feb 2012; (SIAM Activity Group (SIAG) on Supercomputing, Best Paper Prize, 2016)
  • Graph Expansion and Communication Costs of Fast Matrix Multiplication, G. Ballard, J. Demmel, O. Holtz, O. Schwartz, JACM, Dec 2012; presents the communication lower bound for Strassen-like matrix multiplication
  • Communication lower bounds and optimal algorithms for numerical linear algebra G. Ballard, E. Carson, J. Demmel, M. Hoemmen, N. Knight, O. Schwartz, Acta Numerica, 2014; survey of field, including both direct and iterative methods
  • References for Randomized Algorithms
  • "Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions," N. Halko, P. G. Martinsson, J. A. Tropp, SIAM Review 2011, or arxiv.org
  • "An Elementary Proof of a Theorem of Johnson and Lindenstrauss," S. Dasgupta, A. Gupta, Random Structures and Algorithms 2003, or here
  • "Randomized algorithms for matrices and data," M. Mahoney, arxiv.org
  • "Low Rank Approximation and Regression in Input Sparsity Time", K. Clarkson, D. Woodruff, STOC 2013 (co-winner, Best Paper Award), or arxiv.org
  • "Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression," X. Meng, M. Mahoney, arxiv.org
  • Stat 260/CS294 - Randomized Algorithms for Matrices and Data was taught by Michael Mahoney in Fall 2013.
  • Reading group on randomized numerical linear algebra, with archived slides and video presentations, was taught by Laura Grigori and James Demmel in Spring 2015
  • References for Symmetric Eigenproblem and SVD
  • ``Avoiding Communication in Successive Band Reduction'', G. Ballard, J. Demmel, N. Knight, UCB EECS Tech Report UCB/EECS-2013-131
  • ``New Fast and Accurate Jacobi SVD Algorithm, Part I and Part II,'', Z. Drmac, K. Veselic, SIAM J. Mat. Anal. Appl., v 29, 2008 (SIAM Linear Algebra Prize 2009)
  • ``Orthogonal Eigenvectors and Relative Gaps,'' I. Dhillon, B. Parlett, SIAM J. Mat. Anal. Appl. v. 25:3, Mar 2004 (SIAM Linear Algebra Prize 2006)
  • ``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, 1999
  • ``Jacobi's Method is more accurate than QR,'' J. Demmel, K. Veselic, SIAM J. Mat. Anal. Appl., v 27, 1990
  • ``Accurate singular values of bidiagonal matrices,'' J. Demmel, W. Kahan, SIAM J. Sci. Stat. Comp., v 11, 1990 (SIAM Linear Algebra Prize 1991)