Алгоритмы и применения тензорных разложений для численного решения многомерных нестационарных задач

• Автор: Долгов, Сергей Владимирович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 161 с. : ил.

Оглавление
Введение
1 Многомерные вероятностные уравнения
1.1 Модель Фарлей-Бунемановской неустойчивости в ионосфере Земли
1.1.1 Постановка задачи
1.1.2 Дискретизация по пространству и скоростям
1.1.3 Расщепление по времени
1.1.4 Начальные состояния плотности электронов и распределения
ионов
1.2 Основное кинетическое уравнение для стохастической химической кинетики
1.3 Схемы интегрирования эволюционных уравнений
1.3.1 Одновременная дискретизация в пространстве и времени
1.3.2 Нахождение стационарного решения неявным методом Эйлера
2 Представления и аппроксимации тензорными произведениями
2.1 Разделение переменных в двух и многих размерностях
2.1.1 Малоранговое разложение матрицы
2.1.2 Канонический формат и формат Таккера
2.1.3 Рекуррентные тензорные представления
2.1.4 Обозначения для работы с тензорными форматами
2.1.5 Основные операции в ТТ формате
2.2 Квантизованные тензорные аппроксимации
2.2.1 Формат QTT: Quantized Tensor Train
2.2.2 QTT-Tucker: двухуровневое разделение исходных и виртуальных переменных
2.2.3 Преобразования из ТТ в расширенный ТТ и QTT-Tucker форматы
2.2.4 Операции в формате QTT-Tucker
2.2.5 Округление в формате QTT-Tucker
3 Представления основных функций, векторов и матриц в тензорных произведениях
3.1 Тензорные представления в блочной временной схеме
3.1.1 Тензорная структура блочной пространственно-временной матрицы

3.1.2 Матрицы сдвига и конечных разностей в ОТТ формате
3.2 Матрицы перехода для ионного уравнения модели Фарлей-Бунемановской неустойчивости
3.3 Тензорные свойства основного кинетического уравнения
3.3.1 Матрица ОКУ для случая цепи каскадных реакций
3.4 Обращение дискретного оператора Лапласа и преобразование Фурье
4 Итерационные методы в тензорных форматах
4.1 Итерационные методы с приближенными тензорными операциями .
4.2 Оптимизация на элементах тензорных форматов
4.2.1 Классические итерации и методы переменных направлений .
4.2.2 Решение задач линейной алгебры с помощью оптимизации .
4.2.3 Проблема адаптация рангов и двухблочный БМШЗ
4.3 Адаптивные методы переменных направлений для решения линейных систем высоких размерностей
4.3.1 Понятие расширения формата
4.3.2 Метод неточного градиентного спуска и его анализ
4.3.3 АМЕп: комбинация градиентного спуска и переменных направлений
4.3.4 АМЕп и одноблочный БМШЗ с дополнительной переменной
4.4 Практические особенности реализации алгоритмов БМШЗ и АМЕп
4.4.1 Вычисления в локальных системах
4.4.2 Аппроксимация решения
4.4.3 Аппроксимация невязки: сингулярное разложение
4.4.4 Аппроксимация невязки: АБЭ метод
4.4.5 АМЕп алгоритм для быстрой аппроксимации матричного произведения
4.4.6 АМЕп и БМШЗ для формата ОТТ-Тискег
5 Численные эксперименты
5.1 Основное кинетическое уравнение для сетей биологических реакций
5.1.1 Каскад реакций на коротком промежутке времени: сравнение методов
5.1.2 Каскад реакций иа большом промежутке времени
5.1.3 Генетический переключатель с параметром
5.1.4 А-фаг
5.2 Моделирование Фарлей-Бунемановской неустойчивости
Заключение
Список обозначений
Литература

Введение
Объект исследования и актуальность работы
Эта диссертация посвящена численному рсшсшно многомерных задач методами тензорных разложений. Что мы подразумеваем под задачами высокой размерности, и как они возникают па практике? В линейной алгебре рассматриваются векторы и матрицы, и под “размерностью” обычно понимается размер, т.е. количество элементов в векторе. Оно может быть классифицировано как “высокое”, например по сравнению с имеющейся компьютерной памятью. Однако, под термином “многомерный” мьт понимаем нечто иное. В качестве основных приложений мы выделяем квантовые и вероятностные физические модели, такие как уравнения Фоккера-Планка, управляющее уравнение, или уравнение Шредшггера. Чтобы понять, в каком смысле они являются многомерными, начнем с иллюстрации на следующем примере.
Предположим, тгго задан не конкретный вектор, а класс, или семейство векторов, так что элементы подчиняются определенным независимым вычислительным правилам. Пусть правило для каждого элемента может давать конечное число различных значений. Все экземпляры такого класса могут быть также собраны в вектор: мы просто перечисляем все возможные комбинации реализаций. Если каждый исходный элемент может принимать п значений, число комбинации двух элементов составляет уже п ■ п = п2, и 'число реализации класса из (1 элементов принимает значение п ■ п- ■ -п = пй. Это огромное количество: всего лишь 80 элементов (требующие 640 байт для хранения их с двойной точностью) при 10 возможных значениях каждого из них дают Ю80 комбинаций - качественная оценка числа всех атомов во Вселенной. Этот простейший пример иллюстрирует тем не мепее два ключевые момента в данной работе: способ, каким мы получили огромное количество значений из относительно небольшого числа исходных элементов, будет возникать в наших основных приложениях, а концепция и понимание того, что мы можем хранить пе все Ю80 экземпляров, а только 80 векторов по 10 значений в каждом, определяющих исходные правила, будут лежать в основе вычислительных методов.
Идея пространства экземпляров, или если говорить более строго, пространства состояний, является краеугольным камнем в квантовых и стохастических моделях. Система многих тел может быть описана обыкновенными дифференциальными уравнениями, которые определяют эволюцию (1 координат позиций частиц, или других степеней свободы. Основные проблемы численного решения проистекают из нелинейной формы физических законов, по само хранение регае-

нсфизнчпому явлению: с ненулевой вероятностью возникнут отрицательные г^. Чтобы избежать такой ситуации, мы всегда будем задавать граничные условия-.
и}т{г) = 0 если любой элемент г + гт < 0. (1-18)
Эти граничные условия непротекания достаточны, чтобы бесконечномерное уравнение (1.15) было корректно в физическом и вероятностном смысле, то есть отрицательные количества веществ никогда не возникают, вероятность Ф неотрицательна, а нормировка У),. Ф(г, £) сохраняется при эволюции системы во времени (при условии, что Ф(г,0) подчиняется этим свойствам). Тем не менее, это может быть не так, если РЭР применяется непосредственно без изменения гот.
Основные свойства приближения ЕвР были установлены в |181|. Во-первых, если 0) ^ 0 н щт(*) ^ 0, то сохраняется условие ф(г, Ь) ф 0. Во-вторых, ошибка в решении контролируемо связана с потерей нормировки вероятности.
Теорема 1.2.1 ([181], Теорема 2.2). Пусть ф(г,0) = Ф(г,0) ^ 0, гит(г) ф 0. Если для некоторого е > 0 и I ф 0 выполняется
]Г^(М) >1-£,

тогда

^(М) < Ф(г,I) < ф(г91)+е, г £ (^){0,.. ., п* - 1}.

Другой вариант анализа, связанный с регулярностью функции вероятности, был приведен в [77].
Как было показано в [121], все собственные значения оператора ОКУ в (1.17) имеют неположительные вещественные части. В самом деле, каждая строчная сумма Л* — Л° равна либо —1, либо 0, и сШщ(гит) неотрицательна, так как диагональные элементы и строчные суммы матрицы /1 неположительны. По теореме Гершгорина, все собственные числа лежат в левой части комплексной плоскости. Это обеспечивает стабильность динамики ОКУ. Однако, если и и>т, и ф отличны от нуля в таких тотгках 4, что Д + г ф , все собственные значения имеют строго отрицательные действительные части, и норма решения ф{£) уменьшается со временем. Это приводит к накоплению ошибки как показано в теореме 1.2.1, и свидетельствует о необходимости подбора достаточно большого щ, чтобы отброшенная часть ф была ничтожно мала.
Несложно восстановить сохранение нормировки и для конечного уравнения |122|. Все, что для этого требуется, это изменить функцию скорости следующим образом:
и)т(г) = 0 если любой + г ф пь, к = 1,..., <1, (1-19)
т.е. накладывая дополнительные граничные условия, помимо естественных (1.18). Теперь, следуя [122], можно заметить, что
£ ют{г - гт)ф^ - гт) = £ ют{г)ф(г) = £>"*(«Ж*),
г i+zrn■ г
и следовательно ет(Л2”' — Л°) Фац(гот)^ = 0, где е суть вектор из всех единиц, соответствующий суммированию по всем допустимым г.