6 фактов о методах и перспективах решения многомерных задач в вычислительной химии и физике твердого тела
Интерес к многомерным массивам возник давно. В вычислительной науке, в мультилинейной алгебре «тензор» — устоявшийся термин, который используется во многих статьях. Говоря «тензор», мы имеем в виду не некоторый объект, у которого есть верхние и нижние индексы, правила, как нужно менять верхний индекс на нижний и так далее, а просто многомерный массив. Двумерный массив — это матрица; одномерный массив — это вектор; трехмерный массив — куб. Четырехмерный, пятимерный, многомерный массив — это тензор.
1. Проблема хранения тензора
Для хранения тензора нужно очень много элементов. Представим себе, что у нас есть тензор, у которого 32 точки (таблица в 32 точки по каждому направлению) и 100 переменных. Это будет число 32100. Это число можно сравнить с числом атомов во Вселенной. Легко понять, что вы не сможете хранить эти данные на компьютере. Работать напрямую с массивами такой размерности невозможно, поэтому нужно работать с какими-то их приближениями. То есть нужно хранить не все, а небольшое количество элементов, восстанавливая остальные.
Многомерные массивы возникают в тех случаях, когда нужно представлять функцию многих переменных. У вас есть функция, которая зависит, например, от десяти переменных, и вы хотите ее приблизить на некоторой сетке, на тензорном произведении сеток. Получается многомерный куб.
2. Многомерные массивы в вычислительной химии
Первое и основное приложение многомерных массивов — это вычислительная химия. Основное уравнение вычислительной химии — это уравнение Шрёдингера, куда входит волновая функция, которая зависит от 3*n переменных, где n — это число электронов. Если ядра неподвижны, то получается уравнение, в котором 3*n независимых переменных, и это функция многих переменных, которые нужно приближать. Физик Поль Дирак сказал, что все уравнения написаны, но совершенно непонятно, как их решать. Это многомерное уравнение, которое стандартными методами решать невозможно, и нужно работать над вычислительными методами приближения такой функции многих переменных. Важно отметить, что если вам нужно приблизить функцию многих переменных и это ваше основное приложение, то метод найдется. Химики хорошо умеют приближенно решать уравнение Шрёдингера, есть целая иерархия методов, когда эта функция приближается каким-то объектом, но в этом объекте небольшое количество параметров. Если внимательно посмотреть на все методы приближения функций многих переменных, то количество различных и успешно применяемых методов не очень велико.
3. Многопараметрические задачи
Второе приложение, где возникают функции многих переменных, — это многопараметрические задачи и задачи uncertainty quantification (количественного описания неопределенности). У вас есть некоторая модель, например, самолета. В эту модель входят какие-то физические константы, параметры самолета. Они известны только приближенно: вы знаете, что параметр будет меняться в определенном диапазоне, и вы предполагаете, что он случайный. То есть вы знаете, в каком пределе он меняется, либо предполагаете, что он абсолютно случайный с каким-то средним и с какой-то дисперсией. Или, например, у вас есть поверхность, которую сложно описать правильной ломаной или гладкой кривой, и вы ее приближаете к случайной поверхности, считаете, что она немного колеблется. У вас получается задача, в которую кроме обычных неизвестных на сетке (например, миллион точек) входит еще 5, 6 или 7 параметров, и вы хотите решить вашу задачу для всех значений параметров. Как это можно сделать? Составить таблицу: этот параметр принимает 10 значений, этот 10, этот 10, этот 10. У вас получается 105 различных значений параметров. Этот огромный массив надо приблизить. Естественно, функция многих переменных — это дорогая задача. Реальный пример из жизни может быть такой: у вас есть очень хорошая, очень точная модель самолета, который включает в себя миллионы узлов. Для того чтобы рассчитать режим полета этого самолета, вам нужен вычислительный кластер. Вы загоняете в него модель, ваши пять параметров, и кластер считает их в течение нескольких часов. Но представьте себе ситуацию, когда расчет вам нужно провести при взлете самолета. Например, взлетает военный самолет, и вы знаете его массу и угол атаки. Как решить эту проблему? Вы не можете отправить данные на кластер и ждать два часа до вылета, нужна маленькая модель. Что получается: есть 5 входных параметров, черный ящик, который делает эту сложную операцию и выдает на выходе небольшое количество параметров (взлетел/не взлетел). То есть опять получается функция многих переменных.
4. Методы Монте-Карло
Есть способы решения многомерных задач, основанные на методе Монте-Карло. При использования этих методов точность высокой быть не может в силу ограничения точности функций единица на корень из n, где n — это число испытаний. Соответственно, если хотите получить три знака, надо провести миллион испытаний. Предположим, мы хотим построить малопараметрическую аппроксимацию по небольшому числу элементов. Если посмотреть внимательно, все используемые подходы основаны на разделении переменных. То есть вы пытаетесь исходную функцию от переменных приблизить в виде произведения функций от одной переменной. В таком виде вы ничего не приблизите на самом деле. Произведение функций — независимые переменные. Но, если вы возьмете сумму таких функций, класс функций становится существенно более широким, и возникает так называемый канонический формат, первый формат представления тензоров. Слева — ndэлементов, справа — d*n*r, где r — ранг представления. В чем же заключается проблема?
Проблема возникнет, если вы попытаетесь численно работать в таком формате. Вы можете попытаться поставить задачу, когда дается элемент тензора или процедура, которая позволяет вычислить любой наперед заданный элемент тензора. Посчитав один, два, пять элементов, вы пытаетесь предсказать, чему будет равно значение тензоров в новом элементе. Мы знаем, что тензор имеет канонический формат. Оказывается, построить его нельзя. Нет надежных численных алгоритмов построения такого разложения. Возникает то, что называется некорректной задачей, неустойчивостью. Есть хорошее представление, но посчитать его мы не можем. Более того, есть пример тензора размером 9х9х9, для которого неизвестно, как выглядит это разложение. Вопрос разложения для этого специального тензора имеет важное прикладное значение, тем не менее это пока не сделано.
5. Аппарат приближения многомерных массивов
Возникла идея вместо этого разложения предложить другое. В 2009 году в вычислительной математике возникли новые тензорные форматы, новые представления тензоров. В каноническом формате d*n*r, где r — это какой-то параметр, чем он больше, тем больше памяти. Новые форматы — d*n*r2 , и их можно устойчивым образом посчитать: есть алгоритмы, основанные на сингулярном разложении. Это привело к локальному взрыву в сообществе, которое занимается тензорами и вычислительными методами. Возник устойчивый, надежный, эффективный аппарат приближения многомерных массивов.
В 2010 году оказалось, что в области, совершенно несвязанной с вычислительными методами линейной алгебры, в физике твердого тела, люди использовали matrixproduct states, что было очень похоже на описанный аппарат. То есть в каком-то смысле это было переоткрытие. Аппарат уже использовался, но для вычислительной математики как общий формат представления тензоров он был мертвым, никак не мог туда попасть. Как только он возник в математике, возникла возможность соотнести то представление, которое использовалось в физике. Например, в физике анализировались твердое тело, кристаллическая решетка, семейство спинов. Волновая функция спинов зависит от его направления, получается многомерный массив 2х2х2х2х2х2… Для того чтобы найти минимальное собственное значение, энергию основного состояния, нужно было строить приближение многомерных тензоров. И люди придумали, как это делать. Оказалось, что эти форматы похожи на новые форматы, которые появились в математике. Отголоски этих представлений возникли в совершенно разных областях. Это могут быть вероятностные модели. В них есть алгоритм, который при переводе на матричный язык, на язык линейной алгебры, выглядит очень просто, но в другой области обозначались другой терминологией.
6. Методы приближения в биологии
Методы приближения тензоров сегодня активно применяются в биологии. Например, когда возникает основное кинетическое уравнение, когда у вас есть динамика популяции вирусов. Обычно они описываются обыкновенными дифференциальными уравнениями, но здесь описывается не концентрация этих вирусов, их так мало, что нужно расписать уравнение на вероятность нахождения системы в некотором состоянии. Вместо пяти переменных у вас возникает функция, которая зависит от этих пяти переменных. При ста различных типах этих вирусов у вас получается стомерная задача. В данном случае такие методы работают прекрасно. Это пример математической мотивации, то есть мотивация не была связана с каким-то конкретным приложением. Мотивация при анализе многомерных массивов была связана исключительно с вопросом: «А можем ли мы обобщить двумерные результаты?»
Мы очень хорошо умеем работать с матрицами. Возьмем две и три переменных: а и j, а и j, k. Разница кажется небольшой, а теория и алгоритм совершенно разные. Это пример того, как простая математическая мотивация привела к новым результатам и новым подходам решения разных задач. Побочный результат состоит в том, что удалось объединить различных людей, которые занимаются многомерными задачами, занимаются тензорами, но при этом их так не называют. Мы смогли обнаружить новые алгоритмы, которые удалось перевести на математический язык и сделать их общематематическим достоянием, и придумать алгоритмы, которых там не было, существенно улучшить алгоритмы, использовавшиеся в физике твердого тела. Я считаю, что решение многомерных задач — это очень интересная и перспективная тема. Вычислительная математика становится все более и более многомерной, и необходима разработка новых методов.
Источник: Постнаука
