Основы матричных вычислений 2020/2021 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Лекции)
(→‎О курсе)
 
(не показано 19 промежуточных версии 2 участников)
Строка 12: Строка 12:
 
! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации
 
! Группа !! Преподаватель !! Учебный ассистент || Инвайт в anytask || Чат в телеграм || Консультации
 
|-
 
|-
−
| 1 || Рахуба Максим Владимирович || Соколов Павел Павлович || hshcN22 || [https://t.me/joinchat/HLeHFXFm_LGO_mIV ссылка]
+
| 1 || Рахуба Максим Владимирович || Соколов Павел Павлович || hshcN22 ||  
 
|| Вт 16:20 - 17:40, [https://zoom.us/j/91339444964 ссылка]
 
|| Вт 16:20 - 17:40, [https://zoom.us/j/91339444964 ссылка]
 
|-
 
|-
−
| 2 || Сушникова Дарья Алексеевна ||  Токкожин Аспандияр || ETq1F00 || [https://t.me/joinchat/GOHlwXZfAu8GJdEC ссылка] || Пт 14:40 - 16:00, [https://nyu.zoom.us/j/5938043183 ссылка]
+
| 2 || Сушникова Дарья Алексеевна ||  Токкожин Аспандияр || ETq1F00 || ||  
 
|-
 
|-
−
| 3 || Высоцкий Лев Игоревич || Мануйленко Никита Сергеевич  || go4gqFC || [https://t.me/joinchat/FqKT3P3A2mipNbp4 ссылка] || Пт 14:40 - 16:00, [https://zoom.us/j/7628087647 ссылка]
+
| 3 || Высоцкий Лев Игоревич || Мануйленко Никита Сергеевич  || go4gqFC || ||  
 
|-
 
|-
−
| 4 || Высоцкий Лев Игоревич || Кувшинова Ксения Алексеевна  || dCQaAwe || [https://t.me/joinchat/HcM9dIZZlh5BH8i2 ссылка] || Пт 14:40 - 16:00, [https://zoom.us/j/7628087647 ссылка]
+
| 4 || Высоцкий Лев Игоревич || Кувшинова Ксения Алексеевна  || dCQaAwe ||
 
|-
 
|-
−
| 5 ||  Сушникова Дарья Алексеевна || Токкожин Аспандияр  || m01wCso || [https://t.me/joinchat/GNMAvPKPNvBjvmDL ссылка] || Пт 14:40 - 16:00, [https://nyu.zoom.us/j/5938043183 ссылка]
+
| 5 ||  Сушникова Дарья Алексеевна || Токкожин Аспандияр  || m01wCso ||
 
|-
 
|-
−
| 6 ||  Зароднюк Алёна Владимировна || Тяпкин Даниил Николаевич  ||HX8MApN || [https://t.me/joinchat/Gt2asQcdBR-b-BRZ ссылка] || TBA
+
| 6 ||  Зароднюк Алёна Владимировна || Тяпкин Даниил Николаевич  ||HX8MApN ||
 
|}
 
|}
  
 
=== Полезные ссылки ===
 
=== Полезные ссылки ===
  
−
Телеграм-канал курса: https://t.me/joinchat/RawBYqxQLW8wmuqz
+
Телеграм-канал курса
  
−
Телеграм-чат курса: https://t.me/joinchat/G0LRv6fhDA0rsTLd
+
Телеграм-чат курса:  
  
 
Anytask курса: https://anytask.org/course/771
 
Anytask курса: https://anytask.org/course/771
 +
 +
Папка с конспектами лекций: https://yadi.sk/d/zmEwUxsSmOW0xw
  
 
Плейлист с записями лекций: https://www.youtube.com/playlist?list=PLEwK9wdS5g0ouOxtCkrw9_niJ5IW9zm0G
 
Плейлист с записями лекций: https://www.youtube.com/playlist?list=PLEwK9wdS5g0ouOxtCkrw9_niJ5IW9zm0G
Строка 58: Строка 60:
 
* '''FFT и структурированные матрицы — 2''' (22 марта) [[https://yadi.sk/i/PpuJYikN-hRTjQ Конспект], [https://youtu.be/FC30e3fboiU Видео]]: FFT для произвольных n. Двумерное FFT. Двумерные циклические свёртки. Дискретная свёртка. Дискретное косинус-преобразование.
 
* '''FFT и структурированные матрицы — 2''' (22 марта) [[https://yadi.sk/i/PpuJYikN-hRTjQ Конспект], [https://youtu.be/FC30e3fboiU Видео]]: FFT для произвольных n. Двумерное FFT. Двумерные циклические свёртки. Дискретная свёртка. Дискретное косинус-преобразование.
 
* '''Умножение матриц и вычислительная устойчивость''' (5 апреля) [[https://yadi.sk/i/eWB0PPGRJuLhdw Конспект], [https://youtu.be/8p_2wXj09ww Видео]]: Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность.
 
* '''Умножение матриц и вычислительная устойчивость''' (5 апреля) [[https://yadi.sk/i/eWB0PPGRJuLhdw Конспект], [https://youtu.be/8p_2wXj09ww Видео]]: Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность.
 +
* '''Лекция 11''' (12 апреля) [[https://yadi.sk/i/qtqjwVYWiT1T_g Конспект], [https://youtu.be/eOcKu-dJuxg Видео]]: Матричные ряды. Теория возмущений для линейных систем. Матричная экспонента.
 +
* '''Прямые методы решения линейных систем с плотными матрицами''' (19 апреля) [[https://yadi.sk/i/5KeAH1gLuGgc2w Конспект], [https://youtu.be/LI_HqDWAPBU Видео]]: LU-разложение. Связь LU-разложения и метода исключения Гаусса. Выбор ведущего элемента. Разложение Холецкого.
 +
* '''Прямые методы для решения линейных систем с большими разреженными матрицами''' (26 апреля) [[https://yadi.sk/i/tCtJ7rmNynMuXA Конспект], [https://youtu.be/55MtLd4vfMY Видео]]: Формула Шермана-Моррисона. Разреженные матрицы. Алгоритмы поиска P. МНК для разреженных матриц.
 +
* '''Итерационные методы для решения систем линейных уравнений''' (11 мая) [[https://yadi.sk/i/Qys5n5whTUMgaQ Презентация], [https://youtu.be/lFv4IKzyFS4 Видео]]: Метод простой итерации. Градиентный спуск. Итерационный метод Чёбышева.
 +
* '''Итерационные методы для решения линейных систем — 2''' (17 мая) [[https://yadi.sk/i/HMLDY9QLW97sqA Конспект], [https://youtu.be/gTeniSq3sQA Видео]]: Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов.
 +
* '''Итерационные методы для решения линейных систем — 3''' (24 мая) [[https://disk.yandex.ru/i/LPo02NjN72t-Zw Презентация], [https://youtu.be/ejNjWukiiCk Видео]]: Сходимость CG. GMRES. Предобуславливание.
 +
* '''Методы решения частичной задачи на собственные значения''' (31 мая) [[https://yadi.sk/i/JG0o7vdqwpmXJA Конспект], [https://youtu.be/RTArMt74BpE Видео]]: EigenValue Problem как задача оптимизации. Степенной метод (power iteration). Метод Релея-Ритца. Методы Ланцоша и Арнольди.
 +
* '''Лекция 18''' (7 июня) [[https://yadi.sk/i/TQ1X7PwdU3EkCA Конспект], [https://youtu.be/iP8tJCk8bPc Видео]]: QR-алгоритм. Алгоритм для SVD. Теория возмущений.
 +
* '''Лекция 19''' (14 июня) [[https://yadi.sk/i/U1lfxkuGMx9J9A Конспект], [https://youtu.be/QYcxRdx-FlA Видео]]: Теория возмущений (окончание). Крыловские пространства для матричных функций. Оценка вычисления следа
  
 
=== Домашние задания ===
 
=== Домашние задания ===
Строка 89: Строка 100:
 
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать папку data).
 
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать папку data).
  
−
Дедлайн (строгий): '''24.03.21''' в '''23:59'''.
+
Дедлайн (строгий): 24.03.21 в 23:59.
 +
 
 +
'''Домашнее задание 4'''
 +
 
 +
[https://yadi.sk/d/PGy5uyK__-QnqA Папка с заданием]
 +
 
 +
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook (не забудьте дополнительно скачать файл cameraman.tif).
 +
 
 +
Дедлайн (строгий): 29.04.21 в 23:59.
 +
 
 +
'''Домашнее задание 5'''
 +
 
 +
[https://yadi.sk/d/INM5Vaay-0jZ5w Папка с заданием]
 +
 
 +
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. resistors.svg — справочный материал, скачивать не обязательно.
 +
 
 +
Дедлайн (строгий): 16 мая 2021 в 23:59.
 +
 
 +
'''Домашнее задание 6'''
 +
 
 +
[https://disk.yandex.ru/d/KMMdZeKvyD_HMA Папка с заданием]
 +
 
 +
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
 +
 
 +
Дедлайн (строгий): 31 мая 2021 в 23:59.
 +
 
 +
'''Домашнее задание 7'''
 +
 
 +
[https://yadi.sk/d/71sTEAGNGWiPWA Папка с заданием]
 +
 
 +
Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook.
 +
 
 +
Дедлайн (строгий): '''15 июня 2021''' в '''23:59'''.
  
 
=== Контрольная работа ===
 
=== Контрольная работа ===

Текущая версия на 19:17, 6 августа 2021

О курсе

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

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


Семинаристы:

Группа Преподаватель Учебный ассистент Инвайт в anytask Чат в телеграм Консультации
1 Рахуба Максим Владимирович Соколов Павел Павлович hshcN22 Вт 16:20 - 17:40, ссылка
2 Сушникова Дарья Алексеевна Токкожин Аспандияр ETq1F00
3 Высоцкий Лев Игоревич Мануйленко Никита Сергеевич go4gqFC
4 Высоцкий Лев Игоревич Кувшинова Ксения Алексеевна dCQaAwe
5 Сушникова Дарья Алексеевна Токкожин Аспандияр m01wCso
6 Зароднюк Алёна Владимировна Тяпкин Даниил Николаевич HX8MApN

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

Телеграм-канал курса

Телеграм-чат курса:

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

Папка с конспектами лекций: https://yadi.sk/d/zmEwUxsSmOW0xw

Плейлист с записями лекций: https://www.youtube.com/playlist?list=PLEwK9wdS5g0ouOxtCkrw9_niJ5IW9zm0G

Ещё одна папка с записями: https://eduhseru-my.sharepoint.com/:f:/g/personal/kroslovtseva_hse_ru/ErwdF_hjiM1FmbSWp56u574BK5wHfU1Nk8qwVTxsvesZ6g?e=QoBm6H

План курса

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

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

Лекции

  • Основы матричного анализа (18 января) [Конспект, Видео]: Векторные и матричные нормы. Унитарные матрицы. Разложение Шура.
  • Малоранговое приближение матриц — 1 (25 января) [Конспект, Видео]: Разделение переменных и ранг матриц. SVD.
  • Малоранговое приближение матриц — 2 (1 февраля) [Конспект, Видео]: QR-разложение. Операции с малоранговыми матрицами. Ортопроектор. Простейший рандомизированный алгоритм SVD.
  • Малоранговое приближение матриц — 3 (8 февраля) [Конспект, Видео]: ALS-алгоритм. Кронекерово произведение.
  • Малоранговая аппроксимация многомерных массивов (тензоров) (15 февраля) [Конспект, Видео]: Каноническое разложение. Разложение Таккера. HOSVD-алгоритм. Тензорные сети*.
  • Вычисление QR-разложения (22 февраля) [Конспект, Видео]: Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR.
  • Псевдообратные матрицы и метод наименьших квадратов (29 февраля) (1 марта) [Конспект, Видео]: Полноранговый случай. Общий случай. Регуляризация.
  • FFT и структурированные матрицы (9 марта) [Конспект, Видео]: Быстрое преобразование Фурье. Циркулянты. Тёплицевы матрицы.
  • FFT и структурированные матрицы — 2 (22 марта) [Конспект, Видео]: FFT для произвольных n. Двумерное FFT. Двумерные циклические свёртки. Дискретная свёртка. Дискретное косинус-преобразование.
  • Умножение матриц и вычислительная устойчивость (5 апреля) [Конспект, Видео]: Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность.
  • Лекция 11 (12 апреля) [Конспект, Видео]: Матричные ряды. Теория возмущений для линейных систем. Матричная экспонента.
  • Прямые методы решения линейных систем с плотными матрицами (19 апреля) [Конспект, Видео]: LU-разложение. Связь LU-разложения и метода исключения Гаусса. Выбор ведущего элемента. Разложение Холецкого.
  • Прямые методы для решения линейных систем с большими разреженными матрицами (26 апреля) [Конспект, Видео]: Формула Шермана-Моррисона. Разреженные матрицы. Алгоритмы поиска P. МНК для разреженных матриц.
  • Итерационные методы для решения систем линейных уравнений (11 мая) [Презентация, Видео]: Метод простой итерации. Градиентный спуск. Итерационный метод Чёбышева.
  • Итерационные методы для решения линейных систем — 2 (17 мая) [Конспект, Видео]: Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов.
  • Итерационные методы для решения линейных систем — 3 (24 мая) [Презентация, Видео]: Сходимость CG. GMRES. Предобуславливание.
  • Методы решения частичной задачи на собственные значения (31 мая) [Конспект, Видео]: EigenValue Problem как задача оптимизации. Степенной метод (power iteration). Метод Релея-Ритца. Методы Ланцоша и Арнольди.
  • Лекция 18 (7 июня) [Конспект, Видео]: QR-алгоритм. Алгоритм для SVD. Теория возмущений.
  • Лекция 19 (14 июня) [Конспект, Видео]: Теория возмущений (окончание). Крыловские пространства для матричных функций. Оценка вычисления следа

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

Выдаются каждые 2 или 3 недели.

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

Папка с заданием

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

Выдается: 18.01.21.

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

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

Папка с заданием

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

Выдается: 09.02.21.

Дедлайн (строгий): 24.02.21 в 23:59.

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

Папка с заданием

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

Дедлайн (строгий): 24.03.21 в 23:59.

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

Папка с заданием

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

Дедлайн (строгий): 29.04.21 в 23:59.

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

Папка с заданием

Задание состоит из теоретических задач в .pdf-файле и практической задачи в Jupyter Notebook. resistors.svg — справочный материал, скачивать не обязательно.

Дедлайн (строгий): 16 мая 2021 в 23:59.

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

Папка с заданием

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

Дедлайн (строгий): 31 мая 2021 в 23:59.

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

Папка с заданием

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

Дедлайн (строгий): 15 июня 2021 в 23:59.

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

Экзамен

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

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

ДЗ –– средняя оценка за домашние задания

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

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

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

Литература

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.

4) Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997.

Источник — «http://wiki.cs.hse.ru/index.php?title=Основы_матричных_вычислений_2020/2021&oldid=56192»