Numerical linear algebra, Skoltech, Fall 2022, general course info

About the course

• The course is about solving problems arising in computing
• Three main problems:
  • solving linear systems
  • finding eigenvalues and eigenvectors
  • computing matrix functions (matrix exponential especially)
• The methods are different for small-scale and large-scale problems:
  • using matrix decompositions
  • iterative methods

Learning outcomes

• Solve medium-scale numerical linear algebra problems (solve linear systems, compute eigenvalues and eigenvectors, solve linear least squares) using matrix factorizations
• Iterative methods for sparse/structured systems
• Find which methods are the most appropriate for the particular problem
• Find appropriate software

(Approximate) Syllabus

• Week 1: Intro and floating points arithmetics, matrices, vectors, norms, ranks.
• Week 2: Matrix decompositions 1: SVD and its applications
• Week 3: Matrix decompositions 2: Linear systems and LU, eigendecomposition
• Week 4: Matrix decompositions 3: QR and Schur + project proposal deadline
• Week 5: Sparse and structured matrices, iterative methods (part 1)
• Week 6: Iterative methods (part 2), matrix functions and advanced topics
• Week 7: Oral exam (two days)
• Week 8: Application period and project presentations

Lecture access

• Lectures can be downloaded and viewed on GitHub: https://github.com/oseledets/nla2022

• They can also be viewed online using nbviewer: http://nbviewer.jupyter.org/github/oseledets/nla2022/tree/master/

Team

Course instructor: Ivan Oseledets

TAs: Alexander Katrutsa, Gleb Mezentsev, Anna Rudenko, Egor Sevriugov, Daria Cherniuk, Daniil Merkulov, Mikhail Pautov

How do we grade

• 50% homework. Includes 3 problem sets with coding in Python and theoretical problems.
• 20% final exam - the format and rules will be announced later
• 15% Midterm test -- written test with simple problems.
• 15% term project. More details and policies about this activity will be presented later.
• 10% Bonus. Solve bonus tasks from HW.

Total maximum is 110%.

Problem sets

1. Homework is distributed in Jupyter notebooks

2. Problem sets contain both theoretical and programming tasks

3. No hand-written solutions are accepted, only Markdown and $\LaTeX$ text in the single Jupyter Notebook file is Ok.

Problem set rules

1. Solutions must be submitted on Canvas before the deadline
2. Deadlines are strict. After the deadline Canvas submission is closed. Only the last submission will be graded.
3. Deadline for every problem set will be announced at the moment of publishing
4. Problem sets will be checked for plagiarism. If noticed, the score will be divided by a number of similar works

Attendance

Attendance is not strict, but do not disappoint us. Some lectures will be in the online mode.

Exam

• Classical oral exam with a list of questions (questions from 2020)
• If you fail exam, you get zero for the course
• The list of questions such that if you can not answer any question from this list during the final exam, you will automatically get F for this course. It will be probably updated by the end of November.

Projects

• We give you time ($\approx$ one week) and points (15% of your final grade) to test studied methods in real-world problems
• We will provide some examples in the second part of this class
• For inspiration you can checkout recent conference papers (e.g. here)
• 2–5 students per team
• Start thinking about your project topics as early as possible!

Grades

1. A: 86 - 100 %
2. B: 70 - 85 %
3. C: 50 - 70 %
4. D: 30 - 50 %
5. E: 15 - 30 %
6. F: 0 - 15 %

But they can be slightly adjusted.

Python 3

• We will use Python ecosystem for programming.
• Please, follow the rules that will be given in the problem sets

Materials

Our materials:

• Lecture notes are avaliable online
• Matrix decomposition cheat sheet

If you have difficulties with basic linear algebra:

• Cheat sheet with basics
• Gilbert Strang book "Introduction to Linear Algebra"
• Gilbert Strang has recorded lectures on YouTube

Comprehensive NLA books:

• Gene H. Golub, Charles. F. Van Loan, "Matrix computations" (4th edition)
• Lloyd N. Trefethen and David Bau III, "Numerical Linear Algebra"
• Eugene. E. Tyrtyshnikov, "Brief introduction to numerical analysis"
• James W. Demmel, "Numerical Linear Algebra"

• Many applications of linear algebra you can find in "Introduction to Applied Linear Algebra" by S. Boyd and L. Vandenberghe