CMDA 3606 is a course devoted to variations on the equation $Ax=b$.
Not only do we see how such equations arise from static equilibrium problems
in circuits and structures; we will also consider a variety of *inverse problems*,
for example, associated with image deblurring.
Course topics include modeling linear systems; the singular value decomposition;
matrix approximation, PCA, and recommender systems;
regularized least squares probelms and imaging applications;
solving large-scale linear systems via Krylov methods;
unconstrained nonlinear optimization.

## Classes: |
Monday/Wednesday, 2:30-3:45pm, McBryde 308 |

## Instructor: |
Mark Embree, embree@vt.edu, 575 McBryde |

## Office Hours: |
Monday 4-5:30pm, Tuesday 4-5:30pm, Friday 12:30-1:30pm, or by appointment |

## Piazza: |
The course Piazza page provides a forum for class discussions. |

Summary of the course; review for final exam.

Thank you all for a great semester!

Nonlinear optimization: Overview of constrained optimization

Lagrange multipliers, quadratic programming and the Karush-Kuhn-Tucker matrices

*You do not need to know details of these ideas for the final exam:
this lecture just provided an overview of these important techniques.*

Reading: Chapters 12 and 16 of Nocedal and Wright, *Numerical Optimization*.

Nonlinear optimization: Newton's method for multivariable optimization

Reading: Chapter 2 (see also Chapter 6 for details) of Nocedal and Wright, *Numerical Optimization*.

Problem Set 11 is due on **Thursday**, April 26.

Nonlinear optimization: Line search algorithms

General descent directions and the Wolfe conditions for stepsize selection

Reading: Chapter 2 and Section 3.1 of Nocedal and Wright, *Numerical Optimization*.

Problem Set 11 is due on **Thursday**, April 26.

Introduction to nonlinear optimization

Line search algorithms: steepest descent

Reading: Chapter 2 of Nocedal and Wright, *Numerical Optimization*.

Problem Set 11 is due on **Thursday**, April 26.

The GMRES algorithm: restarting and smoothing

Preconditioning: Solve $(PAQ)y=Pb$ with $x = Qy$ to improve GMRES convergence.

Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).

Problem Set 10 is due on **Thursday**, April 19.

The GMRES algorithm and its convergence

Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).

Problem Set 9 is due on **Thursday**, April 12.

MATLAB code for Problem 3: blur2d.m,
hokiebird.mat,
mystery_plate.mat.

Problem Set 10 is due on **Thursday**, April 19.

Introduction to iterative methods for $Ax=b$, the GMRES algorithm

Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).

Problem Set 9 is due on **Thursday**, April 12.

MATLAB code for Problem 3: blur2d.m,
hokiebird.mat,
mystery_plate.mat.

Exam 2 was proctored during the class period.

Problem Set 9 is due on **Thursday**, April 12.

MATLAB code for Problem 3: blur2d.m,
hokiebird.mat,
mystery_plate.mat.

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).

Regularized least squares problems: image deblurring in two dimensions

See the books
Hansen, Nagy, and O'Leary
and by Hansen
for many more details.

Exam 2 will be held in class on Wednesday, April 4.

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).

Regularized least squares problems: Tikhonov regularization, deblurring in one dimension

See the books
Hansen, Nagy, and O'Leary
and by Hansen
for many more details.

Problem Set 8 is due on Thursday, March 29.

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).

Regularized least squares problems: truncated SVD and Tikhonov regularization

Problem Set 8 is due on Thursday, March 29.

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).

Empirical principal component analysis (PCA)

MATLAB PCA demo: wine_pca.m and supporting data wine_data.m
from the UCI Machine Learning Database.

Problem Set 8 is due on Thursday, March 29.

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).

Principal component analysis (PCA)

Problem Set 7 is due on Thursday, March 22.

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).

Singular Value Decomposition: pseudoinverse, matrix norms, low-rank approximation

Problem Set 6 is due on Thursday, March 15.

Problem Set 7 is due on Thursday, March 22.

Lenny Smith (London School of Economics) will present in the CMDA Distinguished Speaker Series on Pi Day (March 14), 4-5pm in NCB 260.

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).

Singular Value Decomposition (full, reduced, and dyadic versions)

Problem Set 5 is due on Thursday, March 1.

Lenny Smith (London School of Economics) will present in the CMDA Distinguished Speaker Series on Pi Day (March 14), 4-5pm in NCB 260.

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).

Introduction to the Singular Value Decomposition (full rank case)

Problem Set 5 is due on Thursday, March 1.

Exam 1 was proctored during the class period.

Problem Set 5 is due on **Thursday**, March 1.

Review of eigenvalues and eigenvectors

All eigenvalues of a symmetric matrix are real.

All eigenvectors of a symmetric matrix associated with distinct eigenvalues are orthogonal.

Practice Exam 1: Note that Exam 1 will take place during class on February 21.

Reading: course notes, Chapter 5: Orthogonality (draft).

Gram-Schmidt orthogonalization and $QR$ factorization.

MATLAB demos: projex1.m and projex2.m (use plotline3.m, plotplane3.m).

Eigenvalue valentine: be_mine.m

Problem Set 4 is due on Wednesday, February 14.

Practice Exam 1: Note that Exam 1 will take place during class on February 21.

Reading: course notes, Chapter 5: Orthogonality (draft).

Least squares theory: the solution is unique provided ${\cal N}(A)=\{0\}$.

The *pseudoinverse* $A^+ = (A^TA)^{-1} A^T$.

Introduction to projectors: matrices for which $P^2 = P$.

The matrix $AA^+$ is a projector.

Problem Set 4 is due on Wednesday, February 14.

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).

Examples of least squares problems

The equation $(A^TA)x = A^Tb$ always has a solution.

Problem Set 4 is due on Wednesday, February 14.

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).

The Fundamental Theorem of Linear Algebra

Introduction to least squares problems

Problem Set 3 is due on Wednesday, February 8.

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).

Review of span, linear dependence, basis, dimension, rank, orthgonality

MATLAB codes for plotting lines and planes in
2d (plotline2.m, plotplane2.m)
and 3d (plotline3.m, plotplane3.m).

Problem Set 3 is due on Wednesday, February 8.

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).

Subspaces, column space, null space.

Problem Set 2: Problem 3 will be postponed until the next problem set. The updated problem set is available here.

Reading: course notes, Chapter 3: Simple Structures at Equilibrium (draft).

Modeling two-dimensional structures at equilibrium: potential for a null space.

Note: CMDA Computing Consultants are available to help with MATLAB. See the schedule for details.

Reading: course notes, Chapter 2: Linear Systems from Resistor Networks (draft).

Reading: course notes, Chapter 3: Simple Structures at Equilibrium (draft).

Circuit modeling.

Modeling one-dimensional structures at equilibrium.

Review of the course contract and discussion of notes/book options.

Reading: course notes, Chapter 1: Introduction.

Reading: course notes, Chapter 2: Linear Systems from Resistor Networks (draft).

Introduction to circuit modeling.

Posted 22 April 2018. Due **Thursday** 26 April 2018.

hw11.pdf: assignment

Posted 14 April 2018. Due **Thursday** 19 April 2018.

hw10.pdf: assignment

Posted 7 April 2018. Due **Thursday** 12 April 2018.

hw9.pdf: assignment

MATLAB code for Problem 3: blur2d.m,
hokiebird.mat,
mystery_plate.mat.

Posted 23 March 2018. Due **Thursday** 29 March 2018.

hw8.pdf: assignment

MATLAB code for Problem 3: coke_upc.m,
mystery_upc.p.

Posted 17 March 2018. Due **Thursday** 22 March 2018.

hw7.pdf: assignment

MATLAB code for Problem 2: hello.m

Posted 8 March 2018. Due **Thursday** 15 March 2018.

hw6.pdf: assignment

MATLAB code for Problem 5: supreme_court.mat, cow.mat, planck.mat

Posted 23 February 2018. Due **Thursday** 1 March 2018.

hw5.pdf: assignment

MATLAB code for Problem 5: hw5.mat

Posted 8 February 2018. Due 14 February 2018.

hw4.pdf: assignment

MATLAB code for Problem 4: bridge.p, bridge_A.mat

Posted 1 February 2018. Due 8 February 2018.

hw3.pdf: assignment

MATLAB codes for plotting lines and planes in
2d (plotline2.m, plotplane2.m)
and 3d (plotline3.m, plotplane3.m)

Posted 25 January 2018. Due 31 January 2018.

hw2.pdf: assignment

Posted 18 January 2018. Due 24 January 2018.

hw1.pdf: assignment

Download a copy of the electronic version of the course contract and tentative schedule.

Final course grades will be thus allocated:

40%: problem sets

40%: midterm exams (21 February and 4 April, in class)

20%: final exam (9 May, 10:05am-12:05pm)

Virginia Tech's Honor Code applies to all work in this course. Students must uphold the highest ethical standards, abiding by our Honor Code: "As a Hokie, I will conduct myself with honor and integrity at all times. I will not lie, cheat, or steal, nor will I accept the actions of those who do."
From the Office for Undergraduate Academic Integrity:
"Students enrolled in this course are responsible for abiding by the Honor Code. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code. For additional information about the Honor Code, please visit:
www.honorsystem.vt.edu."

We will not closely follow any one textbook; the instructor will provide notes for
much of the course.
The following books, all freely available online to Virginia Tech students,
provide helpful background information.

- Uri M. Ascher and Chen Greif,
*A First Course in Numerical Methods*, SIAM, 2011.

*This book provides background information for many of the topics addressed in tihs course.*

- Jorge Nocedal and Stephen J. Wright,
*Numerical Optimization*, 2nd ed., Springer, 2006.

*This book will be especially helpful for the last third of the course.*

- Per Christian Hansen, James G. Nagy, and Dianne P. O'Leary,
*Deblurring Images: Matrices, Spectra, and Filtering*, SIAM, 2006.

*This book will be especially helpful for the second third of the course.*

- Per Christian Hansen,
*Discrete Inverse Problems: Insight and Algorithms*, SIAM, 2010.

*This book will be especially helpful for the second third of the course.*

Any student with special needs or circumstances requiring accommodation in this course is encouraged to contact the instructor during the first week of class, as well as Virginia Tech's SSD Office. We will ensure that these needs are appropriately addressed.