# U.C. Berkeley Math 221 Home Page

## Matrix Computations / Numerical Linear Algebra

*Spring 2020*

T Th, 310 Hearst Mining

### Instructor:

### Teaching Assistant:

Noble Macfarlane
Office Hours: Th 9:30-12, or by appointment, in 1049 Evans
(send email)
###
Administrative Assistants:

Ria Briggs / Tammy Chouteau
Offices: 563 / 565 Soda Hall
Phones: (510)643-1455 / (510)643-4816
Email: (to Ria) /
(to Tammy)
### Announcements:

(1/26) Office hours are cancelled on Jan 27
(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 28
(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
(Updated 26 Apr 2020. Suggestions welcome!)
###
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,
2019 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
PETSc: Portable, Extensible, Toolkit for Scientific Computation
GraphBLAS: Using Linear Algebra for Graph Algorithms
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.
The IEEE floating point standard was updated again in 2019.
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
(**Best Paper Award, at SPAA'11, invited CACM Research Highlight**)
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
"Randomized Numerical Linear Algebra: Foundations and Algorithms,"
P. G. Martinsson, J. Tropp, to appear in Acta Numerica 2020, or
arxiv.org
"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**)