Advanced Linear Algebra: Foundations to Frontiers

Preface Preface

Linear algebra is one of the fundamental tools for computational and data scientists. This document, titled "Advanced Linear Algebra: Foundations to Frontiers" (ALAFF) is an alternative to a traditional text for a graduate course on advanced linear algebra for computing. The focus is on numerical linear algebra, the study of how theory, algorithms, and computer arithmetic interact. These materials keep the learner engaged by intertwining text, videos, exercises, and programming activities in consumable chunks.

We have used these materials in different settings. It is the primary resource for our course at UT-Austin titled "Numerical Analysis: Linear Algebra" offered through the departments of Computer Science, Mathematics, Statistics and Data Sciences, and Mechanical Engineering, as well as the Computational Science, Engineering, and Mathematics graduate program. This course is also offered as "Advanced Linear Algebra for Computing" through the UT-Austin Masters in Computer Science Online program. Finally, it is the basis for the Massive Open Onine Course (MOOC) also titled "Advanced Linear Algebra: Foundations to Frontiers" on the edX platform. It is our hope that others will repurpose the ALAFF materials for other learning settings, either in its entirety or in part.

So as not to overwhelm learners, we have taken the traditional topics of a numerical linear algebra course and organized these into three parts. Orthogonality, Solving Linear Systems, and the Algebraic Eigenvalue Problem.

• Part I: Orthogonality explores orthogonality (which includes a treatment of norms, orthogonal spaces, the Singular Value Decomposition (SVD), and solving linear least squares problems). We start with with these topics since they are prerequisite knowledge for other courses that students often pursue in parallel with (or even before) advanced linear algebra.

• Part II: Solving Linear Systems focuses on so-called direct and iterative methods while also introducing the notion of numerical stability, which quantifies and qualifies how error that is introduced in the original statement of the problem and/or roundoff that occurs in computer arithmetic impacts the correctness of a computation.

• Part III: The Algebraic Eigenvalue Problem focuses on the theory and practice of computing the eigenvalues and eigenvectors of a matrix. This is closely related to the diagonazing a matrix. Practical algorithms for solving the eigenvalue problem are extended so they can be used to compute the SVD. This part, and the course, ends with a discussion of how to achieve high performance on modern computers when performing matrix computations.

While this represents only a selection of advanced topics in linear algebra, we believe that this course leaves you equipped to pursue further related subjects.

ALAFF is part of a collection of learning artifacts that we have developed over the years.

• Linear Algebra: Foundations to Frontiers (LAFF) [27] [28] a full semester undergraduate introduction to linear algebra. For those whose linear algebra fluency is a bit rusty, this is a good resource for brushing up.

• LAFF-On Programming for Correctness [29] [30] is a six-week course that shares our techniques for systematic discovery of families of algorithms for matrix operations from which the best (e.g., highest performing) can be chosen in a context.

• LAFF-On Programming for High Performance [42] [43] is a four-week course in which matrix-matrix multiplication is used to illustrate fundamental techniques for achieving high performance on modern CPUs. In Week 12 of ALAFF, we give you a flavor of how high performance can be achieved for matrix computations.

There is a MOOC on edX associated with each of these materials. Together, they form a loosely-coupled learning experience. For more information, visit ulaff.net.

You should use the pretest we have created, "Advanced Linear Algebra: Are You Ready?", [40] to self-assess whether you are ready for ALAFF. It consists of about a dozen questions. When taking it, realize that it is not about whether you can answer those questions. Rather, you should look carefully look at the solutions to the questions, which discuss how some of the more concrete exercises translate to more abstract insights. How the topic of the question fits into ALAFF is discussed as is where to review.