Матричные вычисления 20/21 — различия между версиями

Версия 14:49, 26 ноября 2020

О курсе

Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях.

Лектор: Рахуба Максим Владимирович

Лекции проходят на Покровке по вторникам в ауд. D510 (09:30 - 10:50)

Семинарист: Высоцкий Лев Игоревич

Семинары проходят онлайн по пятницам (13:00 - 14:20) Ссылка на регулярную Zoom-конференцию: https://zoom.us/j/91934043735

Ассистент курса: Фёдоров Андрей Александрович

Домашние задания необходимо присылать на почту aafedorov_2@edu.hse.ru

Полезные ссылки

Телеграм-канал курса: https://t.me/joinchat/AAAAAFkvC-gUnDmoK-YY2w

Телеграм-чат курса: https://t.me/joinchat/AiDEvBgUTMjcfkWpD8NMWA

Anytask курса: https://anytask.org/course/706

План курса

Еженедельные тесты

На каждом семинаре (начиная с первого) будет проходить короткий тест по теме последней лекции.

Лекции

1. Основы матричного анализа Записи с лекции

Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы.

2. Малоранговая аппроксимация матриц Записи с лекции

Разделение переменных и скелетное разложение. Сингулярное разложение матриц. Теорема Эккарта-Янга-Мирского. Ортопроекторы. Простейший рандомизированный алгоритм поиска малорангового приближения матриц.

3. Малоранговая аппроксимация матриц 2 Записи с лекции, Слайды (метод крестовой аппроксимации)

CUR разложение матриц. Метод крестовой аппроксимации матриц. ALS (Alternating Least Square) алгоритм для матричной факторизации.

4. Малоранговая аппроксимация тензоров Записи с лекции

Кронекерово и внешнее (тензорное) произведения. Каноническое разложение и разложение Таккера. Теорема о мультилинейном ранге тензора. HOSVD алгоритм.

5. QR разложение и метод наименьших квадратов Записи с лекции

QR разложением матриц с помощью отражений Хаусхолдера и вращений Гивенса. Метод наименьших квадратов. Решение системы нормальных уравнений с помощью QR и SVD разложений. Псевдообратная матрица Мура-Пенроуза.

6. Быстрое преобразование Фурье и структурированные матрицы Записи с лекции

Матрица Фурье и быстрое преобразование Фурье. Циркулянты и дискретная теорема свертки. Теплицевы матрицы.

7. Умножение матриц. Вычислительная устойчивость. Записи с лекции

Сложность умножения матриц. Метод Штрассена и его связь с каноническим разложением тензоров. BLAS и связанные с ним пакеты программ. Представление чисел в памяти компьютера. Вычислительная устойчивость алгоритмов. Основные аксимомы машинной арифметики. Обусловленность задач.

8. Прямые методы решения систем линейных уравнений с плотными матрицами. Записи с лекции

LU разложения, его существование и единственность. Стратегии выбора ведущего элемента: частичный и полный выборы. Разложение Холецкого.

9. Прямые методы решения систем линейных уравнений с большими разреженными матрицами. Записи с лекции

Формула Шермана-Моррисона. Форматы хранения разреженных матриц. Заполнение, ленточные матрицы. Алгоритмы поиска перестановки, минимизирующей заполнение: Катхилл-Макки, minimal degree ordering, вложенное рассечение (начало следующей лекции).

10. Итерационные методы решения систем линейных уравений 1. Записи с лекции

Метод простой итерации и его сходимость. Методы Якоби и Гаусса-Зейделя. Метод Ричардсона, выбор оптимального параметра. Метод наискорейшего спуска для функционала энергии, оценка сходимости.

11. Итерационные методы решения систем линейных уравений 2. Записи с лекции

Итерационный метод Чебышева. Оптимизация на подпространствах и подпространства Крылова.

Домашние задания

Домашнее задание 1 Папка с заданием

Задание состоит из теоретических задач в pdf файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл с видео из папки).

Выдается: 02.09.20

Дедлайн (строгий): 17.09.20 в 21:59

Домашнее задание 2 Папка с заданием

Задание состоит из теоретических задач в pdf файле и практических задач в Jupyter Notebook.

Выдается: 18.09.20

Дедлайн (строгий): 01.10.20 в 21:59

Домашнее задание 3 Папка с заданием

Задание состоит из теоретических задач в pdf файле и практических задач в Jupyter Notebook.

Выдается: 02.10.20

Дедлайн (строгий): 15.10.20 в 21:59

Домашнее задание 4 Папка с заданием

Задание состоит из теоретических задач в pdf файле и практической задачи в Jupyter Notebook.

Выдается: 05.11.20

Дедлайн (строгий): 19.11.20 в 21:59

Домашнее задание 5 Папка с заданием

Задание состоит из теоретических задач в pdf файле и практических задач в Jupyter Notebook.

Выдается: 20.11.20

Дедлайн (строгий): 03.12.20 в 21:59

Контрольная работа

Полусеместровая контрольная работа пройдет 02 ноября (понедельник) с 13:00 до 15:00 через Zoom.

Задачи для подготовки.

Контрольная работа будет состоять из задач и нескольких теоретических вопросов на знание основных концепций и теорем из курса. Например:

1) Сформулируете дискретную теорему свертки и объясните, как умножать циркулянт на вектор со сложностью O(n log n);

2) Сформулируйте ALS алгоритм с ортогонализацией в применении к поиску наилучшего малорангового приближения матрицы A во фробениусовой норме.

Экзамен

Письменный экзамен в аудитории.

Итоговая оценка за курс

Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э))

ДЗ –– средняя оценка за домашние задания Б –– средняя оценка за бонусные задачи в ДЗ ПР — средняя оценка за самостоятельные работы на семинарах КР –– оценка за контрольную работу (проводится в первой половине 2-го модуля) Э –– устный экзамен

Округление арифметическое

Автоматы не предусмотрены

Литература

1) Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations 4th Edition. The Johns Hopkins University Press. Baltimore.

2) Тыртышников, Е. Е. (2007). Методы численного анализа. Академия, Москва.

3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia.