Решение дифференциальных уравнений эллиптического типа при помощи тензорных методов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Лариса Маркеева Борисовна

• Лариса Маркеева Борисовна
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Лариса Маркеева Борисовна

1.3.2 Решатель TT-GMRES

1.3.3 Решатель AMEn

1.4 Выводы по главе

2 Операция Z-крон

2.1 Порядок элементов в матрицах

2.2 Операция z-крон

2.3 Связь z-крона и z-нумерации

2.4 Выводы по главе

3 Постановка задачи и её дискретизация

3.1 Модельная задача и метод конечных элементов

3.2 Структура матрицы Якоби

3.3 Выводы по главе

4 QTT-решатель для двумерных дифференциальных уравнений эллиптического типа

4.1 Построение матрицы жёсткости и вектора правой части на подобласти

4.1.1 Генератор z-meshgrid в QTT-формате

4.1.2 Сборка матрицы жёсткости и вектора правой части на подобласти

4.2 Построение глобальной матрицы жёсткости и вектора правой части для исходной области

4.2.1 Согласование решений на границе подобластей

4.2.2 Построение матриц—проекторов в QTT-формате

4.2.3 Согласование по стороне в QTT-формате

4.2.4 Согласование по вершине в TT-формате

4.2.5 Построение матрицы перестановки для подобласти

4.2.6 Применение граничных условий на подобластях

4.2.7 Построение глобальной матрицы жёсткости и вектора правой части

4.3 Алгоритм построения матрицы жёсткости и вектора правой части

в QTT-формате

4.4 Эксперименты

4.5 Выводы по главе

5 Итеративный алгоритм поиска численного решения итерационным методом Дирихле в рТТ-формате для двумерных дифференциальных уравнений эллиптического типа

5.1 Метод итераций Дирихле-Дирихле

5.2 Предобуславливатель для метода итераций Дирихле-Дирихле в QTT-формате

5.3 Алгоритм поиска решения методом итераций Дирихле-Дирихле

5.4 Эксперименты

5.5 Выводы по главе

Заключение

Список иллюстраций

Список литературы

Введение диссертации (часть автореферата) на тему «Решение дифференциальных уравнений эллиптического типа при помощи тензорных методов»

Введение

В настоящей работе предлагаются методы поиска численного решения дифференциальных уравнений эллиптического типа с применением тензорных разложений.

Актуальность исследования. Диссертационная работа посвящена разработке методов численного решения дифференциальных уравнений эллиптического типа на двумерной замкнутой многоугольной области с использованием QTT-формата. Эллиптическая задача выбрана в качестве модельного примера, т. к. результаты, полученные для уравнений этого типа, легко экстраполируются на параболические дифференциальные уравнения.

В качестве структуры для хранения данных выбран квантизованый формат тензорного поезда (Quantized Tensor Train формат, QTT-формат), который является частным случаем формата тензорного поезда^^формат). Данные форматы представляют собой методы нелинейной малоранговой аппроксимации многомерных массивов [21]. Базовые матричные операции эффективно реализованы для QTT-ZTT-форматов. Также существуют программные реализации итерационных методов поиска системы линейных алгебраических уравнений (СЛАУ), использующие QTT-ZTT-форматы. Такие программные реализации называются решателями. В данной работе используются два наиболее известных решателя в QTT-формате: AMEN [8] и TT-GMRES [6]. Стоит отдельно отметить, что TT- и QTT-форматы имеют множество примеров успешного применения к задачам вычислительной физики и численного решения дифференциальных уравнений в частных производных [4], [7], [15], [24], [27].

В [14] решение представляется как непрерывная кусочно-билинейная аппроксимация на однородной декартовой сетке. В [14] было показано, что решение для такого случая сходится экспоненциально от числа степеней свободы

N в QTT-формате. Число степеней свободы — это количество элементов, используемых в QTT-представлении. Данный результат мотивировал использовать QTT-формат в рамках представленной диссертации. Так же в [14] особое внимание уделяется транспонированному QTT (transposed QTT, эквивалентно z-переставленной QTT-матрице). Транспонированный QTT эквивалентен z-переставленной QTT-матрице, которая активно используется в текущем диссертационном исследовании. z-переставленная матрица - это матрица, строки и столбцы которой переставлены в z-последовательности [19]. Помимо определения в [14] доказывается ряд свойств, и приводится теоретическое обоснование того, что транспонированный QTT предотвращает экспоненциальный рост рангов в QTT-формате. К сожалению, в [14] не был представлен алгоритм построения матрицы с индексами строк и столбцов в z-перестановке. В [14] для экспериментов берётся матрица с уже перепорченными строками и столбцами, и строится её представление в QTT-формате. В данной диссертации вводится специальная операция z-kron [18; 31], которая позволяет строить z-переставленные матрицы в QTT-формате из QTT-матриц меньшего размера. Похожая операция уже упоминалась в [23], но использовалась для других целей, и в работе не был проведён её детальный анализ. Данная диссертационная работа вводит формальное объявление операции z-kron, проводит теоретический анализ её свойств, а также проводятся численные эксперименты с участием этой операции.

Так же представляется способ построения матрицы жесткости и вектора правой части методом конечных элементов(МКЭ) с использованием операции z-kron на двумерной многоугольной замкнутой области. В рамках данного диссертационного исследования исходная область разбивается на q четырехугольных подобластей. Вычислительная сложность и сложность по памяти предложенных методов построения O((log n)a), где n = 2d — количество узлов дискретизации на стороне четырёхугольника, на которые разбивается исходная многоугольная область (n >> q), а — константа.

В результате данная работа представляет собой связующее звено между раннее полученными теоретическими результатами [14] и практическим применением QTT к задачам поиска численных решений дифференциальных уравнений.

Цель диссертационной работы.

1. Построить дискретизации и быстрые методы компактного построения дискретных операторов в тензорных форматах которые позволят находить численные решения дифференциальных уравнений эллиптического типа в QTT-формате.

2. Разработка алгоритма поиска численного решения дифференциальных уравнений эллиптического типа на многоугольнике с использованием QTT-формата.

3. Разработка алгоритма поиска решения с вычислительной сложностью, равной 0((log n)a), и аналогичной сложностью по памяти.

4. Разработка алгоритма поиска решения, который должен обеспечивать возможность работы с малым шагом дискретизации.

5. Разработка алгоритма поиска решения, который должен иметь возможность масштабирования на несколько вычислительных узлов.

Задачи работы.

1. Разработать метод построения матрицы жёсткости и вектора правой части с ограниченными константой рангами аппроксимации для многоугольной области (выпуклой и невыпуклой) с использованием QTT-формата.

2. Разработать алгоритм поиска численного решения дифференциальных уравнений эллиптического типа на многоугольной области с использованием матриц из п. 1.

3. Разработать алгоритм поиска численного решения дифференциальных уравнений эллиптического типа на многоугольной области с использованием матриц из п. 1 и возможностью масштабирования на несколько вычислительных узлов.

4. Обеспечить возможность работы с малыми шагами дискретизации для алгоритмов из п. 1-3.

5. Анализ результатов экспериментов с разработанными алгоритмами.

Научная новизна. Предложены два алгоритма построения матрицы жёсткости и вектора правой части с использованием QTT-формата в качестве структуры хранения данных. Оба алгоритма имеют O((log n)a) вычислительную сложность и сложность по памяти для построения матрицы жёсткости и вектора правой чисти. Энергия решения сходится для данных методов как err = O((exp (—Nk)), где N — число степеней свободы, k — некоторая константа. Скорость сходимости, вычислительная сложность построения матрицы жёсткости и объёмы памяти, необходимые для поиска численного решения, существенно лучше стандартных пакетов для поиска решения СЛАУ, например, FEniCS [16]. Сравнительный анализ был произведён в [18]. Так же представленные методы позволяют работать с мелкими дискретизациями, где число узлов на всей области равно 412 х q, где q - число подобластей на которые разбита исходная двумерная многоугольная область.

Также в рамках данной работы введена новая операция z-kron, которая позволяет формировать QTT-матрицы с переставленными в z-последовательности строками и столбцами. Данная операция необходима для решения проблемы экспоненциального роста рангов, который наблюдается при стандартной последовательности строк и столбцов матрицы жёсткости и вектора правой части. Данный рост наблюдается при некоторых конфигурациях подобластей, на которые разбит исходный многоугольник. Данные конфигурации будут рассмотрены подробно в основном тексте работы.

Также в рамках данной работы были доказаны некоторые ключевые свойства операции z-kron.

Практическая значимость работы. Предложенные методы позволяют находить численное решение дифференциальных уравнений эллиптического типа за O((log n)a) итераций с использованием O((log n)a) памяти для хранения матрицы жёсткости и вектора правой части. Полученный алгоритм демонстрирует экспоненциальную сходимость ошибки энергии. Все алгоритмы, предложенные в данной работе, реализованы на языке Python, опубликованы в отдельной библиотеке [17], и могут быть сразу использованы для поиска численных решений дифференциальных уравнений эллиптического типа.

Теоретическая значимость работы В диссертационной работе представлены два алгоритма поиска численного решения дифференциального уравнения эллиптического типа. Оба алгоритма строят матрицу жёсткости и вектор правой части за O((log n)a), памяти для хранения также требуется OO((log n)a). Также в работе вводится операция z-kron, и доказываются её ключевые свойства.

Основные положения, выносимые на защиту. Основными результатами настоящей работы являются два алгоритма поиска численных решений дифференциальных уравнений эллиптического типа в формате QTT. А также, теоретическое обоснование операции z-kron, демонстрация работоспособности предложенных методов и их сравнение со стандартным пакетом для поиска решения СЛАУ FEniCS. На защиту выносятся следующие положения:

1. Алгоритм поиска численных решений дифференциальных уравнений эллиптического типа в формате QTT [18];

2. Алгоритм поиска численных решений дифференциальных уравнений эллиптического типа в формате QTT, представленный в [30]. Данный алгоритм отличается от п. 1 тем, что процесс поиска решения итеративный. Предложенный алгоритм представляет собой адаптацию метода итераций Дирихле-Дирихле [28]. Каждая итерация состоит из двух этапов. На первом этапе происходит поиск решения на каждой отдельной четырёхугольной подобласти, на которую разбита исходная многоугольная область. На втором этапе производится согласование решений на границах между подобластями. Благодаря тому, что поиск решения производится независимо на каждой подобласти, вычисления могут производиться на разных вычислительных узлах параллельно;

3. Операция z-kron, её свойства и результаты экспериментов с данной операцией.

Апробация работы. Результаты, представленные в данной диссертации, имеют математическое обоснование, а также экспериментально проверены на

модельных задачах. Достоверность предлагаемых методов и результатов подтверждается публикациями в рецензируемых журналах из баз Scopus и Web of Science. Результаты диссертации представлялись и обсуждались на следующих конференциях:

1. 60-я научная конференция МФТИ, 2017, Москва, Россия;

2. Ломоносов-2019, 2019, Москва, Россия;

3. The 5th International Conference on Matrix Methods in Mathematics and applications, August 19-23, 2019, Moscow, Russia;

4. En&T-2019, 2019, Moscow, Russia;

Публикации. Основные результаты данной работы опубликованы в следующих изданиях, индексируемых Web of Science и Scopus:

1. Markeeva L., Tsybulin I., Oseledets I. QTT-isogeometric solver in two dimensions //Journal of Computational Physics. — 2020. - С. 109835.

2. Маркеева Л. Б., Цыбулин И. В. Построение z-переставленных матриц в QTT-формате // Журнал вычислительной математики и математической физики. — 2020. — Т. 60 — №.12. — C. 248-255.

3. Gusak J., Kholiavchenko M., Ponomarev E., Markeeva L., Blagoveschensky P., Cichocki A., and Oseledets I. Automated multi-stage compression of neural networks // Proceedings of the IEEE International Conference on Computer Vision Workshops. — 2019. — C. 2501-2508.

Работы, опубликованные в RSCI:

1. Маркеева Л. Б., Оселедец И. В. Эффективный алгоритм поиска численных решений уравнений эллиптического типа в QTT-формате с использованием z-kron // Труды МФТИ. — 2020. — T. 12. — №. 3(47). — C. 44-56.

Личный вклад автора. Данное диссертационное исследование представляет собой законченный труд автора. Автором данной работы были предложены два алгоритма решения дифференциальных уравнений эллиптического типа на многоугольной области (область может быть как выпуклой, так и невыпуклой) [18]. Был разработан метод построения QTT-матриц с переставленными в z-порядке [19] строками и столбцами [18; 31]. Для данных методов в рамках исследования автором совместно с И. В. Цыбулиным была введена новая операция z-kron, и доказан ряд её свойств [31]. Также автором был адаптирован метод итераций Дирихле-Дирихле для использования QTT-формата [30]. В работах [18; 30; 31] постановка задач осуществлена И. В. Оселедцем. Постановка экспериментов и реализация алгоритмов в работах [18; 30; 31] была выполнена автором, консультационную помощь оказывал И. В. Цыбулин.

Структура работы. Диссертация состоит из оглавления, введения, 5 глав, заключения, списка иллюстраций, перечня основных обозначений и списка литературы из 31 наименований. Полный объём диссертации составляет 79 страницы с 15 рисунками.

Содержание работы. В главе 1 приводятся основные определения Tensor Train (TT) и Quantized Tensor Train (QTT) форматов, операций и методов, которые их используют. В разделе 1.1 приводится определение TT-формата и возможные варианты записи тензоров в этом формате, понятие эффективного ранга (e.rank, erank), который является ключевой мерой в оценке эффективности представления матриц в TT^QTT-формате. Аналогичные понятия вводятся и для QTT-формата в главе 1.2. После TT-ZQTT-форматов в главе 1.3 рассматриваются методы решения систем линейных алгебраических уравнений в TT-формате, которые позже используются в главе 4 и 5.

В главе 2 вводится операция z-kron. В начале главы приводится мотивация для ввода данной операции. Приводится пример, как перестановка строк и столбцов в матрице в различном порядке воздействует на эффективные ранги финального QTT-представления. Далее вводятся понятия канонической нумерации и z-нумерации. В предпоследнем параграфе вводится операция z-kron, и приводится её подробное описание. В финале главы доказывается, что резуль-

татом операции z-kгon в действительности является матрица, которая аналогична результату обычного произведения Кронекера, за исключением того, что строки и столбцы результирующей матрицы упорядочены в z-нумерации.

Глава 3 посвящена постановке задачи, которая будет рассматриваться как модельная на протяжении всего диссертационного исследования, методу дискретизации этой задачи, построению матрицы жёсткости и вектора правой части. На примере треугольной области показаны, какие типы границ между подобластями могут вызвать экспоненциальный рост рангов, а какие нет. В данной работе все рассматриваемые нами области являются невырожденными многоугольниками, как выпуклыми, так и невыпуклыми. Исходная многоугольная область разбивается на множество соседствующих по стороне/вершине четырехугольников (подобластей). Согласование решения между подобластями производится в зависимости от выбранного алгоритма. Подробней об этом в главе 4 и 5.

Глава 4 описывает алгоритм поиска численного решения дифференциального уравнения эллиптического типа на двумерной области. В главе 4.1 подробно описан способ построения матрицы жёсткости и вектора правой части на четырёхугольной подобласти. Доказано, что в рассматриваемом случае якобиан является линейной функцией (что серьёзно упрощает построение матрицы жёсткости). Глава 4.1.2 подытоживает представленные раннее выкладки пошаговым алгоритмом построения матрицы жёсткости и вектора правой части для подобласти. В главе 4.2 подробно описывается сборка глобальной матрицы жёсткости для исходной области из матриц локальных матриц жёсткости, построенных на подобластях. Подробно рассматриваются способы согласования решений по стороне и вершине, возможные варианты согласования и способы согласования в QTT-формате. Глава 4.3 подробно подытоживает все предшествующие выкладки главы 4, приводя пошаговый алгоритм построения глобальной матрицы жёсткости и вектора правой части. В финале главы приводятся результаты экспериментов с использованием предложенного алгоритма. В 4.4 производится анализ сходимости энергии, анализ роста эффективных рангов матрицы жёсткости и вектора правой части, сравнение объёмов потребляемой памяти нашим алгоритмом и пакетом для численного поиска решений дифференциальных уравнений РЕшСБ.

Глава 5 описывает ещё один алгоритм поиска численного решения дифференциального уравнения эллиптического типа на двумерной области. Ключевым отличием данного алгоритма от алгоритма в главе 4 является тот факт, что данный алгоритм итеративный, и поиск решения на каждой подобласти ведётся независимо от других подобластей. Это позволяет распределить процесс решения на несколько вычислительных узлов. Глава 5.1 описывает основные этапы метода итераций Дирихле-Дирихле и структуры глобальной матрицы жёсткости и вектора правой части для этого метода. В главе 5.2 описывается построение всех необходимых предобуславливателей для метода итераций Дирихле-Дирихле в QTT-формате. Глава 5.3 описывает алгоритм на базе предшествующих выкладок главы 5 и приводит пошаговый алгоритм поиска численного решения методом итераций Дирихле-Дирихле в формате QTT. В главе 5.4 приведены эксперименты с предложенным алгоритмом. Производится анализ количества затрачиваемой памяти по сравнению с пакетом РЕшСЯ и числа требуемых итераций при заданной точности аппроксимации решения.

Последней главой является заключение, которое подводит итоги данной диссертационной работы.

Благодарности. В первую очередь огромная благодарность выражается Ивану Валерьевичу Оселедцу, научному руководителю автора. Подход Ивана Валерьевича к постановке задаче и обеспечение условий для комфортных исследований мотивировали автора к работе над диссертацией. Также автор благодарит Ивана Владимировича Цыбулина и Молчанова Андрея Эриковича за плодотворную совместную работу и неоценимую помощь в процессе создания данной диссертационной работы.

Глава 1

Тензорные разложения

Формат тензорного поезда (Tensor Train формат или TT-формат) и кван-тизованый формат тензорного поезда (Quantized Tensor Train формат, QTT-формат) - это методы нелинейной малоранговой аппроксимации многомерных массивов. Также стоит отметить, что TT- и QTT-форматы имеют множество примеров успешного применения к задачам численного решения дифференциальных уравнений в частных производных и вычислительной физики [4], [7], [15], [24], [27]. Сложность многих основных операций с тензорами в ^-/QTT-формате может быть оценена сверху как dnra, где а £ {2,3}, n — максимальное из измерений тензора, r — максимальный ранг среди ядер в TT-ZQTT-представлении. В данном разделе мы рассмотрим основные понятия, касающиеся данных форматов. Также в последнем параграфе данного раздела вводится операция z-kron. Данная операцнамя используется в наших алгоритмах поиска решения дифференциальных уравнений, чтобы предотвратить экспоненциальный рост рангов в матрице жёсткости (подробное описание данной матрицы находится в главе 3). Детальное описание реализации основных математических операций в TT-, QTT-форматах и рассмотрение их свойств можно найти в [21].

1.1 Формат Tensor Train (TT-формат)

Tensor Train формат (TT-формат) - это нелинейный метод малоранговой аппроксимации многомерных массивов (тензоров). Рассмотрим d-мерный тен-

зор Т Е Мп1х"хпа. Мы говорим, что тензор Т представлен в ТТ-формате, если его элемент представляется следующим образом:

Г1 га-1

г

Тгуга = ^ ••• ^ О1 (¿1О2 («1,^1, «2) ••• (1-1)

«1=1 а^-1=1

• • • 0(—1 (аз—2, ¿з—1, аз—1) Оз (аа-1,га), (1-2)

где 0 ^ ^ пк — 1, к Е 1, й; О^ называется ядром; £ Е 1, й. О2,..., О3-1 - трёхмерные тензоры с размерами 1 х п3- х г3-; О1, Оз — матрицы размеров п1 х г1 и гз—1 х Пз соответственно. Верхние пределы суммирования г1,... ,гз—1 в (1.1) называются рангами аппроксимации или просто рангами.

Уравнение (1.1) также можно представить как произведение матриц:

Тч..ла = О1 (¿1) О2 (¿2) • • • Оз—1 (¿3—1) Оз (¿з), (1.3)

где Ок (¿к) — матрица размера гк—1 х гк, к Е 1, й.

Объём памяти, занимаемый тензором Т, может быть оценен по следующей формуле:

з-1

5 = Г1П1 + ^ г*—1ПГ + гз—1Пз. (1.4)

¿=2

Дополнительно введём понятие эффективного ранга (е.гапк, егапк) ге, который может быть вычислен путём решения следующего уравнения:

з—1 з—1

5 = Г1П1 + Г —+ гз— 1Пз = ГеП1 + ^ Г^ + ГеПз. (1.5)

■2>

¿=2 ¿=2

Перейдём к представлению многомерных матриц в ТТ-формате. Рассмотрим многомерную матрицу М Е М(п1 х".хпа)х(т1х".хта). Элемент с индексом ¿1... ¿з; Л ... ^'з представляется в ТТ-формате в виде:

Г1 га-1

МН-Ч = ^2 ••• У1^1,Л,а1)У2(а1^2^2,а2) •••

31.-За

«1=1 аа-1=1

(1.6)

Уз—1 (аз—2, ¿з—1, ;'з—1, аз_ 1) Уз (аз—1, ¿з, jз),

где 0 ^ ^ пк — 1, 0 ^ jk ^ — 1, У при ^ Е 2, й — 1 — это четырёхмерные тензоры с размерностями г3—1 х п3- х ш3- х г3-; У и Уз — трёхмерные тензоры с размерностями п1 х т1 х г1 и гз х пз х тз соответственно.

В матричной форме выражение (1.6) может быть представлено:

Mii...id = Vi(ii, ji)V2(i2, J2) • • • Vd-i(id-i, jd-i)Vd(id, jd), (1.7)

ji...jd

где Vk(ik,jk) _ матрица размера rk-i x rk, k G 1,d, а пара ik,jk представляет собой «длинный индекс». Важно отметить, что ядра Vk могут рассматриваться как блочные матрицы размера rk-i x rk, в которых каждый блок имеет размерность nk x mk.

Из (1.6) следует, что если TT-ранг M равен 1, то M может быть представлена как кронекерово произведение матриц:

M = Mi < M2 < ... < Md-i < Md, (1.8)

где Mk - это матрицы размера nk x mk, k G 1, d.

1.2 Quantized Tensor Train Формат (QTT-формат)

QTT-формат возникает при введении «виртуальных размерностей», а именно, когда индексы исходного тензора (например, вектора) представляются n-арным кодом. Рассмотрим пример с бинарным кодированием индексов вектора v G R2d. Данный вектор может быть представлен в виде тензора V с размерностями 2 x 2 x ... x 2. TT-разложением или QTT-аппроксимацией на-

d раз

зовём ТТ-разложение или ТТ-аппроксимацию тензора V. Превращение вектора v в d-мерный тензор эквивалентно кодированию индекса этого вектора 0 ^ i ^ 2d — 1 в бинарном формате:

d

i = ii,i2, ...,id = ^2k—lik ^ (ii,i2,...,id), (1.9)

k=i

где ik G {0,1}, k G 1,d. Аналогичная идея используется для представления матрицы M G R2dx2d в QTT-формате.

Эффективный ранг для QTT-формата вычисляется решением следующего уравнения:

d—i

S = 2ri + 2 ^ r—iri + 2rd—i = 4re + 2re2 (d — 2). (1.10)

i=2

Полезной вспомогательной операцией является сильное произведение Кронекера [5] — х, которое определяется как кронекерово произведение между двумя блочными матрицами. Использование такой операции для компактного представления ТТ-разложений различных тензоров было предложено в работе

[11].

Каждое ядро в ТТ-представлении матрицы можно рассматривать, как блочную матрицу. Тогда операция х похожа на матричное произведение, но элементы блочных матриц перемножаются друг с другом с использованием кро-некерова произведения вместо классического матричного произведения. Формально х объявляется как:

а=Кхь=

Кп ... К

1г2

Кг11 . . . К

г1 г2

Например,

а=

12 3 4 12

34

х

х

¿п ... ь

1гз

ЬГ21 ... Ь

г2 гз

Кц ® ¿11 + ... + К1г2 ® Ьг21 ... Кц ® Ь1г3 + ... + К1г2 ® ь

г2гз

КП1 ® ьи + ... + КПг2 ® Ьг21 ... КП1 ® Ь1г3 + ... + Кг.г2 ® ь

JГ2Гз

(1.11)

10 01

12 21

1 0 2 0 2 1 4 2

0 1 0 2 1 2 2 4

3 0 4 0 6 3 8 4

0 3 0 ч 3 6 4 8У

1 0 2 0 2 1 4 2

0 1 0 2 1 2 2 4

3 0 4 0 6 3 8 4

0 3 0 4 3 6 4 8

(1.12)

Такая операция позволяет компактно записывать матрицы в ТТ-формате [13]. В частности, для ТТ-формата матрица может быть записана как:

М = « х ... х «з,

(1.13)

где 3 размера х Т{, с размером блока щ х ш{, где г Е 1,<1

В следующей разделе мы введем понятие z-нумерации, z-перестановки, z-последовательности. После чего введем операцию z-kгon, которая позволяет строить матрицы с переставленными в z-последовательности строками и столбцами в QTT-формате.

1.3 Решение линейных систем в ХХ-формате

Помимо стандартных алгебраических операций таких как сложение, умножение, деление и т.д. для ТТ-^ТТ-форматов также существуют алгоритмы приближенного итерационного решения систем линейных уравнений. В данном случае, и необходимо найти приближенное решение линейной системы вида

Ах = ¡,

где известно, что и правая часть, и матрица, и само решение могут быть приближены ТТ-представлением. Для каждой задачи, необходимо:

• Доказать существование малоранговой тензорной аппроксимации матрицы А и /, и предложить алгоритм построения напрямую в ТТ^ТТ формате

• Доказать существование хорошей аппроксимации решения х в ТТ^ТТ формате.

• Переформулировать исходную задачу в виде оптимизационной задачи с ограничением на ранги решения.

В работе [14] показано, что при численном решение дифференциальных уравнений эллиптического типа в полигональных областях можно построить хорошую малоранговую тензорную аппроксимацию. В частности, было показано, что решение на равномерной сетке тензорной структуры для конечно-элементной аппроксимации сходятся экспоненциально от числа степеней свободы N данной тензорной структуры. Число степеней свободы — это число параметров, определяющих QTT-представление.

В данной работе используется два наиболее популярных решателя в QTT-формате: ТТ-ОМЯЕБ и АМЕп. Подробно построение и свойства решателей в QTT-формате рассмотрены в диссертации С.В. Долгова [29].

1.3.1 Необходимые обозначения

Алгоритмы решателей, описанные в [29] используют специфические обозначение. Приведем их ниже.

• В отличии от тензорных деревьев ТТ-формат имеет процедуру рекомпре-сии или округления, которая была подробно описана в [22]:

У = %,г (х), (1.14)

индексы е и г означают следующее: пытаться получить ошибку не превосходящую е при этом ранги аппроксимации не превосходят г.

• Пусть дан ТТ-формат {хк(гк)}. Векторное ТТ-отображение раскрывает ТТ-представление в полный тензор следующим образом:

т (Х1, ...,хя) : {хк }к=р ^ хр.,,я е С ГР-1ХПР...П1 хг , где

хр,...д(гр1 . . . , гд) хр(гр) . . . хд(гд) ,

(1.15)

при 1 ^ р ^ д ^ 4. Дополнительно обозначим:

хК..4 = х е С"1-"", (1.16)

х(<к) = т(х1,...,хк-1) е сП1...Пк-1ХГк-1, (1.17)

х(>к) = т(хк+1,...,х^) е СГкХПк+'...Па. (1.18) к-я фрейм-матрица

Х=к = х(<к) ® 1Пк ® (х(>к))т е сП1"дак-1ПкГк, (1.19)

х = Х=к хк. (1.20)

• Левая развертка ядра:

x|k)(0—,Ofe) = Xk,Ofe), x|k> G xrk, (1.21)

• Энергия:

JA,b(x) = — x||A = (x, Ax) = 2Re(x, b) + const, где b = Ax*. (1.22)

• Невязка:

RA,b(x) = || Ax — by2 = JA*A,A*b(x) + const. (1.23)

1.3.2 Решатель TT-GMRES

TT-GMRES - реализация метода минимальных невязок (GMRES [25]) для TT-формата. Алгоритм 1.1 представляет собой листинг данного данного метода. В рамках текущей диссертации TT-GMRES был использован как основной решатель в главе 5.

Алгоритм 1.1 TT-GMRES [6]

Input: правая часть b, начальное приближение X0 в TT-формате, матрица A, в виде процедуры умножения на вектор, y = 7^,r(A), точность е и/или максимальный TT ранг r. Output: приближенное решение Xj : WAX-^ е.

1: Начало: вычислить z0 = 7e,r(b — Ax0), в = l|zo|vi = |t.

2: Итерации:

3: for i = 1, 2 ... m do

4: Посчитать огрубленную точность 8 = .. я. 5: w = Ts,r (Avj): новый вектор Крылова. 6: for i = 1,2,... j do

7: 8: 9: 10: 11: 12: 13:

hi

i,j

w = w — hi,jVj, {ортогонализация} end for

w = Ts,r(w), {рекомпрессия в TT-формате}.

hj+i,j =||w|1, vj+i = h-J-.

Собрать матрицу H = [hi,k], k = 1,... ,j, i = 1,

j + 1.

Найти решение редуцированной системы: yj = argmin||(5e1 — Hj

Список литературы диссертационного исследования кандидат наук Лариса Маркеева Борисовна, 2020 год

Список литературы

1. Bachmayr M. K. V. Stability of low-rank tensor representations and structured multilevel preconditioning for elliptic PDEs // Foundations of Computational Mathematics. - 2020. - c. 1-62.

2. Blacker T. S. M. Paving: A new approach to automated quadrilateral mesh generation // International journal for numerical methods in engineering. — 1991. — t. 32, № 4. — c. 811—847.

3. Brezinski C. Extrapolation algorithms and Pade approximations: a historical survey // Applied numerical mathematics. — 1996. — t. 20, № 3. — c. 299—318.

4. Chertkov A. V., Oseledets I. V., Rakhuba M. V. Robust discretization in quantized tensor train format for elliptic problems in two dimensions. — 2016. — eprint: arXiv:1612.01166.

5. De Launey W, Seberry J. The strong Kronecker product // Journal of Combinatorial Theory, Series A. — 1994. — t. 66, № 2. — c. 192—213.

6. Dolgov S. V. TT-GMRES: solution to a linear system in the structured tensor format // Russian Journal of Numerical Analysis and Mathematical Modelling. — 2013. — t. 28, № 2. — c. 149—172.

7. Dolgov S. V., Khoromskij B. N., Oseledets I. V. Fast solution of parabolic problems in the tensor train/quantized tensor train format with initial application to the Fokker-Planck equation // SIAM Journal on Scientific Computing. — 2012. — t. 34, № 6. — A3016—A3038.

8. Dolgov S. V., Savostyanov D. V. Alternating minimal energy methods for linear systems in higher dimensions // SIAM Journal on Scientific Computing. — 2014. — t. 36, № 5. — A2248—A2271.

9. Dolgov S., Khoromskij B. Simultaneous state-time approximation of the chemical master equation using tensor product formats // Numerical Linear Algebra with Applications. - 2015. - t. 22, № 2. - c. 197-219.

10. Horn R. A., Johnson C. R. Matrix analysis. — Cambridge university press, 2012.

11. Kazeev V. A., Khoromskij B. N. Low-rank explicit QTT representation of the Laplace operator and its inverse // SIAM Journal on Matrix Analysis and Applications. - 2012. - t. 33, № 3. - c. 742-758.

12. Kazeev V. A., Khoromskij B. N. Low-rank explicit QTT representation of the Laplace operator and its inverse // SIAM journal on matrix analysis and applications. - 2012. - t. 33, № 3. - c. 742-758.

13. Kazeev V., Reichmann O, Schwab C. Low-rank tensor structure of linear diffusion operators in the TT and QTT formats // Linear Algebra and its Applications. - 2013. - t. 438, № 11. - c. 4204-4221.

14. Kazeev V., Schwab C. Quantized tensor-structured finite elements for second-order elliptic PDEs in two dimensions // Numerische Mathematik. - 2018. -t. 138, № 1. -c. 133-190.

15. Khoromskij B. N. Tensor numerical methods in scientific computing. t. 19. -Walter de Gruyter GmbH & Co KG, 2018.

16. Logg A., Mardal K.-A., Wells G. Automated solution of differential equations by the finite element method: The FEniCS book. t. 84. - Springer Science & Business Media, 2012.

17. Markeeva L. QTT Laplace Lib.notpreprint. - 2017. - URL: https://github. com/RerRayne/qtt-laplace ; https://github.com/RerRayne/qtt-laplace.

18. Markeeva L, Tsybulin I., Oseledets I. QTT-isogeometric solver in two dimensions // Journal of Computational Physics. - 2020. - c. 109835.

19. Morton G. M. A computer oriented geodetic data base and a new technique in file sequencing. - 1966.

20. Oseledets I. V. TTPY : notpreprint. - 2013. - URL: https://github.com/ oseledets/ttpy ; https://github.com/oseledets/ttpy.

21. Oseledets I. V. Tensor-train decomposition // SIAM Journal on Scientific Computing. - 2011. - т. 33, № 5. - с. 2295-2317.

22. Oseledets I. V. Tensor-train decomposition // SIAM Journal on Scientific Computing. - 2011. - т. 33, № 5. - с. 2295-2317.

23. Oseledets I. V., Dolgov S. V. Solution of linear systems and matrix inversion in the TT-format // SIAM Journal on Scientific Computing. - 2012. - т. 34, № 5. - A2718-A2739.

24. Rakhuba M., Novikov A., Oseledets I. Low-rank Riemannian eigensolver for high-dimensional Hamiltonians // Journal of Computational Physics. -2019. - т. 396. - с. 718-737.

25. Saad Y., Schultz M. H. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM Journal on scientific and statistical computing. - 1986. - т. 7, № 3. - с. 856-869.

26. Strang G., Fix G. J. An analysis of the finite element method. т. 212. -Prentice-hall Englewood Cliffs, NJ, 1973.

27. Tensor train versus Monte Carlo for the multicomponent Smoluchowski coagulation equation / S. A. Matveev [и др.] // Journal of Computational Physics. - 2016. - т. 316. - с. 164-179.

28. Василевский Ю., Ольшанский М. Краткий курс по многосеточным методам и методам декомпозиции области. - М.: МАКС Пресс, 2007.

29. Долгов С. В. Алгоритмы и применения тензорных разложений для численного решения многомерных нестационарных задач : дис. ... канд. / Долгов Сергей Владимирович. - 2014. 161 с. URL: http://www. inm. ras. ru/avtoreferat/rus-phd2. pdf, 2014.

30. Маркеева Л. Б., Оселедец И. В. Эффективный алгоритм поиска численных решений уравнений эллиптического типа в QTT-формате с использованием z-kron // Журнал вычислительной математики и математической физики. - 2020. - т. 12, 3(47). - с. 44-56.

31. Маркеева Л. Б., Цыбулин И. В. Построение z-переставленных матриц в QTT-формате // Журнал вычислительной математики и математической физики. - 2020. - т. 60, № 12. - с. 248-255.