Вычислительные тензорные методы и их применения тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Оселедец, Иван Валерьевич

• Оселедец, Иван Валерьевич
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Оселедец, Иван Валерьевич

Введение

1.1 Многомерные массивы и их представления

2 Используемые обозначения и понятия.

1.3 Основные результаты работы.

Глава 1. ТТ-разложение и его свойства

1.1 Введение.

1.2 Каноническое разложение, разложение Таккера и их свойства.

1.3 Две основные леммы.

1.4 Иерархическое разложение Таккера.

1.5 Связь с тензорными сетями.

1.6 Основные свойства ТТ-разложения.

1.7 Округление в ТТ-формате.

1.8 Матрицы в ТТ-формате.

1.9 Основные операции в ТТ-формате.

1.10 Функции в ТТ-формате

1.11 Многомерный крестовый метод.

1.12 Скелетное разложение матриц и тензоров.

1.13 Выводы.

Глава 2. ОТТ-разложение и его свойства

2.1 Введение.

2.2 (^ТТ-разложение некоторых функций.

2.3 (¡¡)ТТ-представление характеристической функции симплекса.

2.4 (¡^ТТ-разложение некоторых операторов.

2.5 Связь С^ТТ-представления и вейвлет-разложения

2.6 ТТ-разложение как вычисление подпространств

2.7 Использование "\Л/ТТ для создания новых вейвлет-преобразований.

2.8 Выводы.

Введение диссертации (часть автореферата) на тему «Вычислительные тензорные методы и их применения»

3.2 Решение молекулярного уравнения Шредингера . 128

3.3 Формулировка задачи.133

3.4 Представление матрицы.135

3.5 Решение задачи на собственные значения с помощью метода DMRG.142

3.6 Численные примеры .152

3.7 Сравнение с известными подходами.156

3.8 Вычисление многих собственных значений . 158

3.9 Стохастические и многопараметрические уравнения .163

3.10 Решение линейной системы в ТТ-формате . 169

3.11 Численные эксперименты.173

3.12 Сжатие данных на примере поля температуры . . 178

Заключение 182

Литература 184

Посвящается моему дедушке, Бежаеву Ивану Осиповичу

1918-2010)

Введение

1. Многомерные массивы и их представления

Диссертация посвящена тензорам и методам работы с ними. Сразу отметим, что под тензором мы будем понимать многомерный массив (многомерную таблицу) из чисел:

A(ibi2,.,id), 1 ^ гк < пк.

При d = 1 мы имеем векторы, а при d = 2 — матрицы. Для матриц существует богатая теория, развиваемая в течение многих десятков лет и ставшая классической. Она включает в себя различные разложения (сингулярное разложение, QR-разложение, LU-разложение, собственное разложение), методы их эффективного вычисления и применения в прикладных задачах. Для тензоров не всегда существуют прямые аналоги известных матричных свойств и разложений (например, понятие ранга можно обобщить на многомерный случай несколькими способами), поэтому сама постановка задачи об эффективных малопараметрических представлениях тензоров и алгоритмах построения таких представлений является актуальной и по настоящее время.

Тензоры и их компактные представления (тензорные разложения) впервые были рассмотрены в 1927 году Хичкоком [95, 96], а идея многофакторной модели приписывается Кэт-телу в 1944 [66, 67]. Эти понятия не привлекали особого внимания вплоть до работ Таккера в 1960-х годах [134, 132, 133], Кэролла и Чанга [65] и Харшмана [92], которые все появились в литературе по «психометрике» («психометрика» — наука о применении статистических методов в психологии). В работе 1981 года Аппельлофа и Давидсона [43] тензорные разложения были впервые применены в «хемометрике» (хемометрика — наука о применении статистических методов в химии) и с тех пор активно применяются в приложениях [93, 117, 59, 60, 62, 108, 38, 102,

41, 39, 61]. Тензорным методам посвящена книга [128]. Параллельно исследованиям в психометрике и хемометрике большой интерес тензорные разложения вызывали при построении оптимальных алгоритмов вычисления билинейных форм в теории сложности, см., например, Кнута [155]. Например, алгоритм Штрассена умножения матриц размера 2x2 можно получить как тензорное разложение тензора размера 4x4x4 [129, 57]. В последние десять лет во многих областях стали применяться тензоры и их представления. В их числе:

• Обработка сигналов [147, 127, 71, 68, 75, 119, 145, 146]

• Искусственное зрение (computer vision) [139]

• Обработка данных [114, 130]

• Нейронауки [54, 76, 118, 116, 115, 63, 64]

Существует большое количество обзоров в других областях [105, 73, 94, 58, 60, 71, 103, 128, 61, 35]. Недавно появилась книга по многомерному анализу данных [106]. Для работы с тензорами и их представлениями существуют различные программные пакеты [124, 40, 107, 74, 50, 123]. Очевидно, что тензорные методы стали играть большую роль в различных прикладных областях, где и происходило основное их развитие.

Однако, во всех приложениях и подходах, упомянутых выше, тензоры получаются как набор данных. Это означает, что они могут поместиться в оперативной памяти, т.е. допустимая размерность d не может быть большой (2, 5 или максимум — 10). При численных расчетах область часто является двумерной или трехмерной, и решение (при использовании структурированных тензорных сеток) также будет двумерным или трехмерным массивом. Если задача является нестационарной, то время можно рассматривать как дополнительную размерность и говорить о четырехмерных массивах. Массивы большой размерности (>10) как полные на практике не встречаются!

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

А(11, г2, • • •, га) = )>*2(Ы> • • .хаО-а)), 1 ^ Ч ^ пку где Х]С(1]С) — некоторые одномерные сетки. Тензор в таком случае является дискретным аналогом функции. Одним из наиболее важных приложений для вычислительных тензорных методов является вычислительная химия, где функции большого числа переменных возникают естественным образом. Вычислительная химия давно стала дешевым и более эффективным методом работы химиков, чем лабораторный эксперимент. Она позволяет за существенно более короткое время и с меньшими затратами проводить анализ различных химических соединений. Пакеты квантовохимического моделирования применяются, например, при разработке новых лекарств или поиске новых материалов, когда необходимо изучить свойства огромного количества различных веществ для нахождения вещества с нужными свойствами. В таких пакетах решаются сложные многомерные задачи. Также многомерные задачи возникают в физике твердого тела при моделировании квантовых спиновых систем.

Можно с уверенностью говорить о том, что различные методы приближения массивов высокой размерности уже давно применяются во многих областях, где необходимы очень трудоемкие вычисления, в том числе с использованием суперкомпьютеров. Разные методы приближения возникали независимо друг от друга в химии, физике. Под «методами приближения» необходимо понимать некоторые малопараметрические представления функций многих переменных и связанных с ними многомерных массивов. Так как при численном решении всегда необходимо переходить к дискретным представлениям, то почти любой из методов решения многомерных задач можно интерпретировать как метод аппроксимации тензоров. Так какие же задачи решаются? В вычислительной химии основным уравнением является уравнение Шредингера. Оно имеет вид

Нг|) = (-1д + У)-ф = ЕгК (i.l) где потенциал V = V(ri,., 1>д) имеет вид v = - у~+ 1у~! 1|Ге - Rail 2^7 ЦГе-TVlP а Ra, Zq — координаты и заряды атомов, соответственно. Неизвестная функция (называемая волновой функцией г|)) зависит от 3Ne координат, где Ne — число электронов в системе. Фактически, нужно найти наименьшее собственное значение многомерного оператора, что даст энергию системы. Решение уравнения (i.l) осложняется тем, что допускаются не любые собственные значения и функции, а только те, которые удовлетворяют дополнительным условиям симметрии/антисимметрии, так называемому принципу Паули. Тем не менее, существует большое количество методов приближенного решения уравнения (i.l): метод Хартри-Фока, методы DFT, пост-Хартри-Фок методы, которые обладают различной сложностью и точностью. Результатом работы этих методов является одно число: энергия Е, а входные параметры (если считать, что заряды атомов зафиксированы) — это положение атомов, поэтому Е является их функцией:

E = E(Rb.,RNJ.

Эта функция (она носит специальное название Potential Energy Surface, или PES) играет важнейшую роль в изучении химических свойств молекулы или системы атомов. Из нее можно получить любую интересующую информацию. Например, минимумы этой функции соответствуют устойчивым конфигурациям (изомерам). Седловые точки отделяют один минимум от другого, и связаны с химическими реакциями по переходу из одного состояния в другое. Также из потенциальной поверхности можно найти колебательные спектры, и пример таких расчетов будет приведен в данной диссертации. Основная проблема состоит в том, в каком же виде можно приблизить эту функцию, чтобы с ней в дальнейшем можно было работать — необходим хороший малопараметрический формат.

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

А(а)х(а) = f(a), а = (oti,., ар). Такие задачи возникают например, когда заранее неизвестно значение коэффициентов при решении обратных задач, или при решении стохастических дифференциальных уравнений с помощью разложения Кархунена-Лоева. Если решение х(а) удается приблизить в тензорном виде, то это позволяет существенно сократить затраты: нет необходимости каждый раз заново решать систему. Фактически, решение многопараметрической задачи сводится к приближению решения для всех значений параметров с помощью решения небольшого числа задач при фиксированных значениях параметра. От параметров также могут зависеть интегралы, возникающие в конечно-элементных методах высокого порядка. Входными параметрами являются координаты вершин треугольников по которым ведется интегрирование, а для вычисления самого интеграла (при фиксированном значении параметров) требуется использование дорогостоящих квадратур. Замена такой функции на малопараметрическое приближение может позволить существенно сократить время на вычисление одного элемента.

Упомянем также о других приложениях, в которых требуется решение многомерных дифференциальных уравнений: уравнение Блэка-Шоулза в финансовой математике, уравнение Фоккера-Планка. В таких задачах размерность с1 может быть очень большой, вплоть до сотен и тысяч, и необходимо искать решение сразу в специальном тензорном виде.

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

Математическое исследование методов приближения многомерных массивов (тензоров) началось достаточно недавно - в конце 90-х - начале 2000-х годов [55, 56], и сейчас возник бурный интерес к созданию математического и алгоритмического аппарата для работы с тензорами размерности <1^3.

Первая задача, которую необходимо решить — это выбор малопараметрического представления (формата) для рассматриваемого тензора. Часто оказывается, что несмотря на то, что тензор формально задан большим числом параметров, их можно заменить с достаточной точностью гораздо меньшим числом параметров.

Существуют различные тензорные разложения. Наиболее известным является каноническое разложение, которое является дискретным аналогом классической идеи о разделении переменных. Оно имеет вид: г

А = А(11, \2,., = и1 > °0и2(12, ос). ил(га, а), (1.2) х=1 где г называется тензорным, или каноническим, рангом и гц х г матрицы = [11^(1^, а)] называется каноническими факторами, или факторными матрицами. В двумерном случае тензор становится матрицей А^,"^)» а. каноническое разложение становится скелетным:

Наилучшее приближение скелетным разложением можно получить с помощью сингулярного разложения [154]. Наилучшее приближение с фиксированным рангом существует, оно устойчиво, и для него существуют эффективные алгоритмы [154, 82]. Каноническое разложение является естественным (но не единственным) способом обобщить сингулярное разложение на многомерный случай. Однако, к сожалению, уже при с1 ^ 3 теряются важные свойства сингулярного разложения. Наилучшее приближение с фиксированным рангом может не существовать. Например, расстояние от заданного тензора до множества тензоров фиксированного ранга может быть равно нулю, а точного разложения может не существовать [150], т.е. множество тензоров фиксированного ранга не является замкнутым. На практике применение различных методов построения канонического разложения к таким тензорам приводит к тому, что алгоритмы «разваливаются»: неограниченно возрастают нормы канонических факторов . Следствием является отсутствие надёжных алгоритмов построения канонического разложения. Более того, даже если заранее известно, что хорошее каноническое приближение существует, нет надёжных алгоритмов, которые его найдут.

Тем не менее, если нам требуется компактное приближение многомерного массива, то каноническое разложение является не очень удачным кандидатом, в силу отсутствия эффективных и надёжных алгоритмов аппроксимации, и необходимо искать какие-то другие представления для многомерных массивов, т.е. другие обобщения сингулярного разложения. Конечной целью является построение разложения, которое свободно от «проклятия размерности» (нет экспоненциальной зависимости по размерности пространства d), при этом оно обладает свойствами устойчивости и для него существуют надёжные вычислительные алгоритмы, основанные на стандартных процедурах линейной алгебры, в первую очередь, на сингулярном разложении.

Вторым стандартным разложением тензоров является так называемое разложение Таккера [134]. Оно имеет вид:

А = A(ibi2,.,id) = (i.3)

G(ai,a2,.,ad) Ui (ib ai)U2(i2, a2). Ud(id, ad).

Его построение для заданного многомерного массива можно свести к последовательному вычислению сингулярного разложения модовых матриц. Например, для того чтобы получить матрицу Ui, необходимо рассмотреть матрицу Bi размера ni х (п2Пз. nd) с элементами:

Bl (ib • • • i-d) = A(ib Í2, . . . , id) и построить малоранговую аппроксимацию: bi =u1v1T где Ui имеет размеры ги х ri , а Vi — (п2Пз . nd) х ri . Тогда Ui будет первой матрицей-фактором Таккера. Аналогично вычисляются остальные матрицы U^. По тензору А строится модовая матрица В^, в которой индекс ik нумерует строки, а оставшийся (d — 1) индекс - столбцы. Столбцами матрицы U^ будут старшие левые сингулярные векторы матрицы Вк. После того как матрицы U^ посчитаны, ядро G вычисляется как умножение тензора на матрицы:

G = А х i U| х 2 UJ . х d UJ. (i.4)

Умножение тензора на матрицу А х kV определяется как тензор В, заданный как:

Ttlc

B(il, i2, • • . , jk, • • • , id) = Y > • ■ • У ^Mi-k, jk), ik=1 т.е. свёртка по Тс-ой моде.

Отметим, что в приближённом случае можно использовать урезанное сингулярное разложение, и тогда вычисление ядра по формуле (i.4) приведёт к квазиоптималъному разложению Таккера, называемому HOSVD (High Order Singular Value Decomposition) [149]. Если ek — ошибка (во фробениусовой норме) аппроксимации матрицей ранга r^ к-ой модовой матрицы, то ошибка аппроксимации разложением Таккера с помощью HOSVD удовлетворяет неравенству: hosvd ^ ^ £

2 к' к=1

Если £ — наилучшее (оптимальное) приближение во фробениусовой норме, то £к ^ £ и оценка превращается в нобуб ^ л/(1е.

В наших приложениях £ достаточно мало, и дополнительный фактор \/с1 не играет особой роли.

Итак, разложение Таккера можно получить с помощью стандартных процедур БУБ-разложения, и можно показать, что оно является устойчивым (в отличие от канонического разложения). Для задач малой размерности (в первую очередь, для трёхмерных) память, требуемая на хранение вспомогательного массива (ядра С), является небольшой, и разложение Таккера становится отличной альтернативой каноническому разложению. Однако экспоненциальная зависимость от <Х остаётся, необходимо использовать какое-то другое разложение, которое свободно от этой зависимости но при этом является легко вычислимым, устойчивым, а алгоритмы приближения имеют гарантированную точность. Такое разложение (ТТ-разложение) предложено в данной диссертации.

Заключение диссертации по теме «Вычислительная математика», Оселедец, Иван Валерьевич

2.8. Выводы

В этой главе введено С^ТТ-разложение, которое расширяет и дополняет область применимость тензорных разложений в целом и ТТ-формата в частности. Идея квантизации или тен-зоризации векторов и матриц позволяет смотреть на них как на многомерные массивы, и применять к ним тензорные разложения. Оказалось, что для класса функций удается получить оценки на С^ТТ-ранги порожденных векторов, и зависимость числа параметров становится логарифмической. Также в (ЗТТ-формате представимы различные базовые операторы, такие как оператор Лапласа. Связь С^ТТ-формата и вейвлет-разложений позволяет получить новые алгоритмы сжатия данных. Применение разработанных подходов будет рассмотрено в следующей главе.

ГЛАВА 3.

Заключение

В заключение диссертации сформулируем её основные результаты.

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

• Предложено новое представление тензоров — ТТ-формат, которое, в отличие от канонического разложения, может быть построено с помощью быстрых устойчивых алгоритмов на основе сингулярного разложения, и в отличие от разложения Таккера не содержит экспоненциального по размерности числа параметров

• Получены все базовые алгоритмы для работы с массивами в ТТ-формате: переход от полного массива к ТТ-формату с точностью (е) (алгоритм ТТ-БУБ), алгоритм округления в ТТ-формате, все операции линейной алгебры (сложение, поэлементное умножение, умножение матрицы на вектор). Показано, что все эти операции можно проводить, оставаясь в рамках ТТ-формата

• Получено многомерное обобщение скелетного разложения — формула ТТ-интерполяции, которая показывает, что тензор с малыми ТТ-рангами можно восстановить по небольшому количеству его элементов. На основе этой формулы получен многомерный крестовый метод аппроксимации тензоров.

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

• Предложена интерпретация С^ТТ-разложения как адаптивного вейвлет-преобразования, что дает возможность применять его для сжатия данных

• На основе С^ТТ-формата построен метод решения многопараметрических задач, показана его эффективность на численных экспериментах

• Получены оценки на С^ТТ-ранги полиномиальных потенциальных поверхностей квантовой молекулярной динамики, построен эффективный алгоритм нахождения минимального собственного значения, основанный на методе БМЯС, который линеен по числу степеней свободы, вычислено минимальное собственное значения потенциала Хенон-Хайлеса с числом степеней свободы вплоть до 256.

• На основе решения нестационарной задачи построен метод эффективного нахождения спектра Гамильтонианов квантовой молекулярной механики (колебательных спектров)

• С^ТТ/"\Л/ТТ разложения применены для сжатия больших массивов данных в двух примерах: решение нестационарного двумерного уравнения Навье-Стокса (задача о каверне) , где получено сжатие в 1 ООО раз с точностью 10-7, и для массива температуры, вычисленной с помощью ст-модели общей циркуляции океана, где получено сжатие в 44 раза с точностью 0.1 градус.

Публикации по теме диссертации

1] Оселедец И. В., Савостьянов Д. В. Методы разложения тензора // Матричные методы и технологии решения больших задач / ред. Е. Е. Тыртышников. — ИВМ РАН, 2005. - С. 51-64.

2] Оселедец И.В., Тыртышников Е.Е. Приближенное обращение матриц при численном решении гиперсингулярного интегрального уравнения // Ж. вынисл. матем. и матем. физ. — 2005. — Т. 45, № 2. — С. 315-326.

3] Оселедец И. В. Применение разделенных разностей и В-сплайнов для построения быстрых дискретных преобразований вейвлетовского типа на неравномерных сетках / / Матем. заметки. — 2005. — Т. 77, № 5. — С. 743-752.

4] Оселедец И. В., Савостьянов Д. В. Минимизационные методы аппроксимации тензоров и их сравнение // Ж. вычисл. матем. и матем. физ. — 2006. — Т. 46, № 10.

С. 1752-1734.

5] Оселедец И. В. Оценки снизу для сепарабельных аппроксимаций ядра Гильберта // Матем. сб. — 2007. — Т. 198, № 3. - С. 137-144.

6] Оселедец И. В. О новом тензорном разложении // ДАН.

2009. — Т. 427, № 2. - С. 168-169.

7] Оселедец И. В. О приближении матриц логарифмическим числом параметров // ДАН. — 2009. — Т. 428, № 1.

С. 23-24.

8] Оселедец И.В., Тыртышников Е.Е. Рекурсивное приближение многомерных тензоров // ДАН. — 2009. — Т. 427, № 1. - С. 14-16.

9] Замарашкин Н.Л., Оселедец И.В., Тыртышников Е.Е. Тензорная структура обратной к ленточной теплицевой матрице // ДАН. — 2009. — Т. 422, № 2. — С. 168-169.

10] Olshevsky V., Oseledets I. V., Tyrtyshnikov E. E. Tensor properties of multilevel Toeplitz and related matrices // Linear Algebra Appl. — 2006. — Vol. 412, no. 1. — P. 1-21.

11] Oseledets I. V., Tyrtyshnikov E. E. A unifying approach to the construction of circulant preconditioners // Linear Algebra Appl. — 2006. - Vol. 418, no. 2-3. — P. 435-449.

12] Olshevsky V., Oseledets I. V., Tyrtyshnikov E. E. Superfast inversion of two-level Toeplitz matrices using Newton iteration and tensor-displacement structure / / Operator Theory: Advances and Applications. — 2008. — Vol. 179. - P. 229-240.

13] Oseledets I. V., Savostianov D. V., Tyrtyshnikov E. E. Tucker dimensionality reduction of three-dimensional arrays in linear time // SI AM J. Matrix Anal. Appl. — 2008. — Vol. 30, no. 3. — P. 939-956.

14] Oseledets I. V. The integral operator with logarithmic kernel has only one positive eigenvalue // Linear Algebra Appl. — 2008. - Vol. 428, no. 7. - P. 1560-1564.

15] Oseledets I. V., Tyrtyshnikov E. E., Zamarashkin N. L. Matrix inversion cases with size-independent rank estimates // Linear Algebra Appl. — 2009. — Vol. 431, no. 5-7. - P. 558-570.

16] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E. Fast simultaneous orthogonal reduction to triangular matrices // SI AM J. Matrix Anal. Appl. — 2009. — Vol. 31, no. 2. — P. 316-330.

17] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E. Linear algebra for tensor problems // Computing. — 2009. - Vol. 85, no. 3. - P. 169-188.

18] Oseledets I. V., Tyrtyshnikov E. E. Breaking the curse of dimensionality, or how to use SVD in many dimensions // SI AM J. Sci. Comput. - 2009. - Vol. 31, no. 5. - P. 37443759.

19] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E. Cross approximation in tensor electron density computations // Numer. Linear Algebra Appl. — 2010. — Vol. 17, no. 6. - P. 935-952.

20] Oseledets I. V., Tyrtyshnikov E. E. TT-cross algorithm for the approximation of multidimensional arrays // Linear Algebra Appl. — 2010. - Vol. 432, no. 1. - P. 70-88.

21] How to find a good submatrix / S.A. Goreinov, I.V. Oseledets, D.V. Savostyanov et al. // Matrix Methods: Theory, Algorithms, Applications / Ed. by V. Olshevsky, E. Tyrtyshnikov. — World Scientific Publishing, 2010. — P. 247-256.

22] Goreinov S. A., Oseledets I. V., Savostyanov D. V. Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case: Preprint 201001. — Moscow: INM RAS, 2010. — arXiv: 1004.1986. http: //pub.inm.ras.ru.

23] Oseledets I. V. Constructive representation of functions in tensor formats: Preprint 2010-04. — Moscow: INM RAS, 2010. http://pub.inm.ras.ru.

24] Khoromskij B. N., Oseledets I. V. QTT-approximation of elliptic solution operators in high dimensions // Rus. J.

Numer. Anal. Math. Model. — 2011. — Vol. 26, no. 3. - P. 303-322.

25] Khoromskij B. N., Oseledets I. V. Quantics-TT collocation approximation of parameter-dependent and stochastic elliptic PDEs // Comput. Meth. Appl. Math. — 2010. — Vol. 10, no. 4. - P. 376-394.

26] Khoromskij B. N., Oseledets I. V. DMRG + QTT approach to high-dimensional quantum molecular dynamics: Preprint 68. — Leipzig: MPI MIS, 2010. www.mis.mpg.de/ preprints/2010/preprint201068.pdf.

27] Oseledets I. V. Tyrtyshnikov E.E. Algebraic wavelet transform via quantics tensor train decomposition // SIAM J. Scz. Comput. — 2011. — Vol. 31, no. 3. — P. 1315-1328.

28] Oseledets I. V. Approximation of 2d x 2d matrices using tensor decomposition // SIAM J. Matrix Anal. Appl. — 2010. - Vol. 31, no. 4. - P. 2130-2145.

29] Tensor structured iterative solution of elliptic problems with jumping coefficients: Preprint 55 / S. Dolgov, B. Khoromskij, I. Oseledets, E. Tyrtyshnikov. — Leipzig: MPI MIS, 2010.

30] Oseledets I. V. Tensor-train decomposition // SIAM J. Sci. Comput. — Vol. 33, no. 5. — P. 2295-2317.

31] Dolgov S. V., Oseledets I. V. Solution of linear systems and matrix inversion in the TT-format: Preprint 19 (Submitted to SIAM J. of Sci. Comput.). — Leipzig: MIS MPI, 2011. http: //www.mis.mpg.de/preprints/2011/preprint201119.pdf.

32] Oseledets I. V. DMRG approach to fast linear algebra in the TT-format // Comput. Meth. Appl. Math. — 2011. — Vol. 10, no. 3. - P. 382-393.

33] Oseledets I. V., Tyrtyshnikov E.E., Zamarashkin N.L. Tensor-train ranks of matrices and their inverses // Comput. Meth. Appl Math. — 2011. - Vol. 10, no. 3. - P. 394-403.

Список литературы диссертационного исследования доктор физико-математических наук Оселедец, Иван Валерьевич, 2012 год

1. A study of the mode-selective trans-cis isomerization in HONO using ab initio methodology. / Falk Richter, Majdi Hochlaf, Pavel Rosmus et al. //J. Chem. Phys. — 2004. - Vol. 120, no. 3. — P. 1306-17.

2. Acar E., Yener В. Unsupervised multiway data analysis: A literature survey // IEEE Transactions on Knowledge and Data Engineering. — 2009. — P. 6-20.

3. Advances in electronic structure theory: GAMESS a decade later / C.E. Dykstra, G. Frenking, K.S. Kim, G.E. Scuseeria. — Amsterdam: Elsevier, 2005.

4. Ainsworth M., Oden J. Т. A posteriori error estimation in finite element analysis // Computer Methods in Applied Mechanics and Engineering. — 1997. — Vol. 142. — P. 188.

5. Alternating asymmetric trilinear decomposition for three-way data arrays analysis / L.Q. Hu, H.L. Wu, Y.J. Ding et al. // Chemometrics and Intelligent Laboratory Systems. — 2006. Vol. 82. - P. 145-153.

6. Andersen С. M., Bro R. Practical aspects of PARAFAC modeling of fluorescence excitation-emission data // J. Chemometrics. — 2003. — Vol. 17. — P. 200-215.

7. Andersson С.A., Bro R. The N-way Toolbox for MATLAB // Chemometrics and Intelligent Laboratory Systems. — 2000. Vol. 52, no. 1. - P. 1-4.

8. Andersson C.A., Henrion R. A general algorithm for obtaining simple structure of core arrays in N-way PCA with application to fluorometric data // Computational Statistics and Data Analysis. — 1999. — Vol. 31, no. 3. — P. 255-278.

9. Anharmonic wave functions of proteins: quantum self-consistent field calculations of BPTI / A Roitberg, R. Benny Gerber, R Elber, M. Ratner // Science. — 1995.

10. Vol. 268, no. 5215. P. 1319-1322.

11. Appellof C. J., Davidson E. R. Strategies for analyzing data from video fluorometric monitoring of liquid chromatographic effluents // Analytical Chemistry. — 1981. — Vol. 53, no. 13.1. P. 2053-2056.

12. Babuska I., Nobile F., Tempone R. Worst case scenario analysis for elliptic problems with uncertainty // Numerische Mathematik. — 2005. — Vol. 101, no. 2. — P. 185-219.

13. Babuska I, Nobile Fabio, Tempone Raul. A stochastic collocation method for elliptic partial differential equations with random input data // SI AM J. Numer. Anal. — 2007.

14. Vol. 45, no. 3. — P. 1005-1034. http://link.aip.org/ link/?SNA/45/1005/1.

15. Babuska I., Strouboulis T. The finite element method and its reliability. — Oxford University Press, USA, 2001.

16. Babuska I, Tempone Raul, Zouraris Georgios E. Galerkin finite element approximations of stochastic elliptic partial differential equations // SI AM J. Numer. Anal. — no. 2. — P. 800-825.

17. Badeau R., Boyer R. Fast multilinear singular value decomposition for structured tensors // SIAM J. Matrix Anal. Appl. 2008. - Vol. 30. - P. 1008.

18. Bader B. W., Kolda T. G. Algorithm 862: MATLAB tensor classes for fast algorithm prototyping // ACM TYans. on Math. Soft. 2006. - Vol. 32, no. 4.

19. BaderB. W., Kolda T. G. Efficient MATLAB computations with sparse and factored tensors // SIAM J. Sei. Comput.2007. — Vol. 30, no. 1. P. 205-231.

20. Bader B. W., Kolda T. G. Tensor decompositions and applications: Technical Report SAND2007-6702. — Albuquerque, NM and Livermore, CA: Sandia National Lab., 2007.

21. Bebendorf M. Approximation of boundary element matrices // Numerische Mathematik. — 2000. — Vol. 86, no. 4. — P. 565-589.

22. Beckmann C. F., Smith S. M. Tensorial extensions of independent component analysis for multisubject FMRI analysis // Neuroimage. — 2005. — Vol. 25, no. 1. — P. 294311.

23. Beylkin G., Mohlenkamp M. J. Numerical operator calculus in higher dimensions // Proc. Nat. Acad. Sei. USA. — 2002.- Vol. 99, no. 16. — P. 10246-10251.

24. Beylkin G., Mohlenkamp M. J. Algorithms for numerical analysis in high dimensions // SIAM J. Sei. Comput. — 2005. Vol. 26, no. 6. - P. 2133-2159.

25. Bini D. Relations between exact and approximate bilinear algorithms. Applications // Calcolo. — 1980. — Vol. 17, no. 1. P. 87-97.

26. Blaser, M. On the complexity of the multiplication of matrices of small formats // Journal of Complexity. — 2003.1. Vol. 19, no. 1. P. 43-60.

27. Bro Richard. PARAFAC: Tutorial and applications // Chemometrics and Intelligent Lab. Syst. — 1997. — Vol. 38, no. 2. P. 149-171.

28. Bro R. Review on multiway analysis in chemistry — 20002005 // Critical reviews in analytical chemistry. — 2006.- Vol. 36, no. 3. P. 279-293.

29. Bro R., Andersson C.A., Kiers H.A.L. PARAFAC2-Part II. Modeling chromatographic data with retention time shifts // Journal of Chemometrics. — 1999. — Vol. 13, no. 3-4. P. 295-309.

30. Canonical decomposition of ictal scalp EEG reliably detects the seizure onset zone / M. de Vos, A. Vergult, L. de Lathauwer et al. // Neuro Image. — 2007. — Vol. 37, no. 3. — P. 844-854.

31. Canonical decomposition of ictal scalp eeg and accurate source localisation: Principles and simulation study / M. de Vos, L. de Lathauwer, B. Vanrumste et al. //

32. Computational Intelligence and Neuroscience. — 2007. — Vol. 2007. P. 58253.

33. Caroll J. D., Chang J. J. Analysis of individual differences in multidimensional scaling via n-way generalization of Eckart-Young decomposition // Psychometrika. — 1970. — Vol. 35. P. 283-319.

34. Cattell R.B. "Parallell proportional profiles" and other principles for determining the choice fo factors by rotation // Psychometrika. — 1944. — Vol. 9, no. 4. — P. 267-283.

35. Cattell R.B. The three basic factor-analytic research designs and their interrelations and derivatives // Psychological Bulletin. — 1952. Vol. 49, no. 5. - P. 499-520.

36. Chen B., Petropulu A.P., de Lathauwer L. Blind identification of convolutive MIMO systems with 3 sources and 2 sensors // EURASIP Journal on Applied Signal Processing. — 2002. — Vol. 5. — P. 487-496.

37. Cohen A, DeVore R, Schwab Christoph. Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs // Found. Comput. Math. — 2010. — Vol. 10. — P. 615-646.

38. Comon P. Tensor decomposition: state of the art and applications // IMA Conf. Math, in Sig. Proc., Warwick, UK. 2000.

39. Compact thermal modeling for temperature-aware design / Wei Huang, Mircea R. Stan, Kevin Skadron et al. // Annual

40. ACM IEEE Design Automation Conference. — 2004. http://portal.acm.org/citation.cfm?id=996800.

41. Coppi R., Bolasco S. Multiway data analysis. — Amsterdam, Netherlands: North-Holland Publishing Co., 1989.

42. CuBatch, a MATLAB® interface for n-mode data analysis / S. Gourvenec, G. Tomasi, C. Durville et al. // Chemometrics and Intelligent Laboratory Systems. — 2005. — Vol. 77. — P. 122-130.

43. De Lathauwer L., Vandewalle J. Dimensionality reduction in higher-order signal processing and rank-(Rl, R2,., RN) reduction in multilinear algebra // Linear Algebra Appl. — 2004. Vol. 391. - P. 31-55.

44. Decomposing EEG data into space-time-frequency components using parallel factor analysis / F. Miwakeichi, E. Martinez-Montes, P.A. Valdes-Sosa et al. // Neurolmage. — 2004. Vol. 22, no. 3. — P. 1035-1045.

45. Elman, H.C. and Miller, C.W. and Phipps, E.T. and Tuminaro, R.S. Assessment of collocation and Galerkin approach to linear diffusion equations with random data // Intern. J. for uncertainty quantification. — 2011. — Vol. 1, no. 1. — P. 19-34.

46. Espig M., Grasedyck L., Hackbusch W. Black box low tensor rank approximation using fibre-crosses // Constr. Appr. — 2009. — Vol. 30, no. 3. — P. 557-597.

47. Fannes M., Nachtergaele B., Werner R.F. Finitely correlated states on quantum spin chains // Communications in Mathematical Physics. — 1992. — Vol. 144, no. 3. P. 443-490.

48. Ford J. M., Tyrtyshnikov E. E. Combining Kronecker product approximation with discrete wavelet transforms to solve dense, function-related systems // SIAM J. Sci. Comput. — 2003. Vol. 25, no. 3. — P. 961-981.

49. Ghanem R. G., Spanos P. D. Stochastic finite elements: a spectral approach. — Courier Dover Publications, 2003.

50. Golub G., Kahan W. Calculating the singular values and pseudo-inverse of a matrix // Journal of the Society for Industrial and Applied Mathematics: Series B, Numerical Analysis. — 1965. — Vol. 2, no. 2. — P. 205-224.

51. Goreinov S. A. On cross approximation of multi-index array // Doklady Math. — 2008. — Vol. 420, no. 4. — P. 404406.

52. Goreinov S. A., Tyrtyshnikov E. E. The maximalvolume concept in approximation by low-rank matrices // Contemporary Mathematics. — 2001. — Vol. 208. — P. 4751.

53. Goreinov S. A., Tyrtyshnikov E. E., Zamarashkin N. L. Pseudo-skeleton approximations of matrices // Reports of Russian Academy of Sciences. — 1995. — Vol. 342, no. 2. — P. 151-152.

54. Goreinov S. A., Tyrtyshnikov E. E., Zamarashkin N. L. A theory of pseudo-skeleton approximations // Linear Algebra Appl. — 1997. Vol. 261. - P. 1-21.

55. Grasedyck L. Existence and computation of low Kroneckerrank approximations for large systems in tensor product structure // Computing. — 2004. — Vol. 72. — P. 247265.

56. Hackbusch Wolfgang, Khoromskij Boris N. Low-rank Kronecker-product Approximation to Multi-dimensional

57. Nonlocal Operators. Part I. Separable Approximation of Multi-variate Functions // Computing. — 2005. — dec.

58. P. 177-202. http://www.springerlink.com/content/ 74v20851143034ql.

59. Hackbusch W., Khoromskij B. N. Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. I. Separable approximation of multi-variate functions // Computing. — 2006. — Vol. 76, no. 3-4. — P. 177-202.

60. Hackbusch W., Khoromskij B. N. Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. II. HKT representation of certain operators // Computing. — 2006. — Vol. 76, no. 3-4. — P. 203-225.

61. Hackbusch W., Khoromskij B. N., Tyrtyshnikov E. E. Hierarchical Kronecker tensor-product approximations // J. Numer. Math. 2005. - Vol. 13. - P. 119-156.

62. Harshman R. A. Foundations of the Parafac procedure: models and conditions for an explanatory multimodal factor analysis // UCLA Working Papers in Phonetics. — 1970.1. Vol. 16. P. 1-84.

63. Henrion R. Body diagonalization of core matrices in three-way principal components analysis: Theoretical bounds and simulation // Journal of Chemometrics. — 1993. — Vol. 7.1. P. 477-477.

64. Henrion R. N-way principal component analysis: theory, algorithms and applications / / Chemometrics and intelligent laboratory systems. — 1994. — Vol. 25, no. 1. P. 1-23.

65. Hitchcock F. L. Multiple invariants and generalized rank of a p-way matrix or tensor // J. Math. Phys. — 1927. — Vol. 7, no. 1. P. 39-79.

66. Hitchcock F. L. The expression of a tensor or a polyadic as a sum of products //J. Math. Phys. — 1927. — Vol. 6, no. 1.- P. 164-189.

67. Hlavacek I. Uncertain input data problems and the worst scenario method // Applications of Mathematics. — 2007.- Vol. 52, no. 3. P. 187-196.

68. How to find a good submatrix / S.A. Goreinov, I.V. Oseledets, D.V. Savostyanov et al. // Matrix Methods: Theory, Algorithms, Applications / Ed. by V. Olshevsky, E. Tyrtyshnikov. — World Scientific Publishing, 2010. — P. 247-256.

69. Hiibener R., Nebendahl V., Dur W. Concatenated tensor network states. — arXiv:0904.1925vl quant-ph], 2009.

70. Kazeev V., Khoromskij B. N. Explicit low-rank QTT representation of Laplace operator and its inverse: Preprint 75. — Leipzig: MPI MIS, 2010. www.mis.mpg.de/preprints/2010/preprint201075.pdf.

71. Khoromskij B. N. On tensor approximation of Green iterations for Kohn-Sham equations // Computing and visualization in science. — 2008. — Vol. 11, no. 4-6. — P. 259-271.

72. Kiers H.A.L. A three-step algorithm for CANDECOMP/PARAFAC analysis of large data sets with multicollinearity // Journal of Chemometrics. — 1998. — Vol. 12, no. 3. P. 155-171.

73. Kiers H.A.L., Van Mechelen I. Three-way component analysis: Principles and illustrative application //

74. Psychological methods. — 2001. — Vol. 6, no. 1. — P. 84-110.

75. Knyazev A. V. Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method // SI AM Journal on Scientific Computing. — 2002. — Vol. 23, no. 2. — P. 517-541.

76. Kroonenberg P.M. Three-mode principal component analysis: Theory and applications. — DSWO press, 1983.

77. Kroonenberg P.M. Applied multiway data analysis. — Wiley-Interscience, 2008.

78. Landry W. Implementing a high performance tensor library // Scientific Programming. — 2003. — Vol. 11, no. 4. P. 273-290.

79. Leurgans S., Ross R.T. Multilinear models: applications in spectroscopy // Statistical Science. — 1992. — Vol. 7, no. 3.1. P. 289-310.

80. Loeve M. Probability Theory, Vol. I. Grad. Texts in Math.1. Springer-Verlag, 1976.

81. Loeve M. Probability Theory, Vol. II. Grad. Texts in Math.1. Springer-Verlag, 1977.

82. Lubich Christian. Prom quantum to classical molecular dynamics: reduced models and numerical analysis. — Zurich: EMS, 2008.

83. Manzhos S., Carrington Jr T. Using redundant coordinates to represent potential energy surfaces with lower-dimensional functions H J. Chem. Phys. — 2007. — Vol. 127. — P. 014103.

84. Modeling and multiway analysis of chatroom tensors / E. Acar, S.A. Camtepe, M.S. Krishnamoorthy, B. Yener // ISI. 2005. - Vol. 3495. - P. 256-268.

85. M0rup M., Hansen L.K., Arnfred S.M. ERPWAVELAB a toolbox for multi-channel analysis of time-frequency transformed event related potentials / / Journal of neuroscience methods. — 2007. — Vol. 161, no. 2. — P. 361368.

86. M0rup, M. and Hansen, L.K. and Herrmann, C.S. and Parnas, J. and Arnfred, S.M. Parallel factor analysis as an exploratory tool for wavelet transformed event-related EEG // Neurolmage. — 2006. — Vol. 29, no. 3. P. 938-947.

87. Multiway analysis of epilepsy tensors, ISMB 2007 Conference Proceedings / E. Acar, C. A. Bingol, H. Bingol et al. // Bioinformatics. — 2007. — Vol. 23.

88. Muti D., Bourennane S. Multidimensional filtering based on a tensor approach // Signal Processing. — 2005. — Vol. 85, no. 12. P. 2338-2353.

89. Nest M., Meyer Hans-Dieter. Benchmark calculations on high-dimensional Henon-Heiles potentials with the multiconfiguration time dependent Hartree (MCTDH) method // J. Chem. Phys. 2002. - Vol. 117, no. 23. - P. 10499.

90. Numerical simulation of large-scale ocean circulation based on the multicomponent splitting method / V. B. Zalesny, G. I. Marchuk, V. I. Agoshkov et al. // Russian J. Numerical Anal. Math. Modelling. — 2010. — Vol. 25, no. 6. — P. 581609.

91. Ostlund Stellan, Rommer Stefan. Thermodynamic limit of Density Matrix Renormalization // Phys. Rev. Lett. — 1995.

92. Vol. 75, no. 19. — P. 3537-3540. http://link.aps.org/ doi/10.1103/PhysRevLett.75.3537.

93. Wise B. M., Gallagher N. B., Bro R. et al. PLS Toolbox 4.0. — 2007.

94. Paatero P. The multilinear engine: a table-driven, least squares program for solving multilinear problems, including the n-way parallel factor analysis model // Journal of Computational and Graphical Statistics. — 1999. — P. 854888.

95. Partridge H., Schwenke D.W. The determination of an accurate isotope dependent potential energy surface for water from extensive ab initio calculations and experimental data // J. Chem. Phys. 1997. — Vol. 106. - P. 4618.

96. Publications of Robert Benny Gerber. //J. Phys. Chem. A.- 2009. — Vol. 113, no. 26. P. 7173-82. http://dx.doi. org/10.1021/jp902508u.

97. Rudnyi E. B., Korvink J. G. Model Order Reduction of MEMS for Efficient Computer Aided Design and System Simulation. — 2008. http://citeseerx.ist.psu.edu/ viewdoc/summary?doi=10.1.1.59.1198.

98. Sidiropoulos N.D., Bro R., Giannakis G.B. Parallel factor analysis in sensor array processing // IEEE transactions on Signal Processing. — 2000. — Vol. 48, no. 8. — P. 2377-2388.

99. Smilde A.K., Bro R., Geladi P. Multi-way analysis with applications in the chemical sciences. — Wiley, 2004.

100. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. — 1969. — Vol. 13, no. 4. — P. 354-356.

101. Sun J., Papadimitriou S., Yu P.S. Window-based tensor analysis on high-dimensional and multi-aspect streams // Proc. ICDM2006. — 2006.

102. Tensor product approximation with optimal rank in quantum chemistry / S. R. Chinnamsetty, M. Espig, W. Hackbusch et al. //J. Chem. Phys. 2007. - Vol. 127. - P. 84-110.

103. Tucker L.R. Implications of factor analysis of three-way matrices for measurement of change // Problems in measuring change. — 1963. — P. 122-137.

104. Tucker L. R. The extension of factor analysis to three-dimensional matrices // Contributions to mathematical psychology. — 1964. — P. 109-127.

105. Tucker L. R. Some mathematical notes on three-mode factor analysis // Psychometrika. — 1966. — Vol. 31. — P. 279-311.

106. Tyrtyshnikov E. E. Incomplete cross approximation in the mosaic-skeleton method // Computing. — 2000. — Vol. 64, no. 4. P. 367-380.

107. Tyrtyshnikov E. E. Tensor approximations of matrices generated by asymptotically smooth functions // Sbomik: Mathematics. — 2003. — Vol. 194, no. 6. — P. 941-954.

108. Tyrtyshnikov E. E. Kronecker-product approximations for some function-related matrices // Linear Algebra Appl. — 2004. Vol. 379. - P. 423-437.

109. Van Loan Ch. F. Tensor network computations in quantum chemistry. — www.cs.cornell.edu/cv/OtherPdf/ZeuthenCVL.pdf, 2008. www.cs.Cornell.edu/cv/OtherPdf/ZeuthenCVL.pdf.

110. Vasilescu M.A.O., Terzopoulos D. Multilinear analysis of image ensembles: Tensorfaces // Lecture Notes in Computer Science. — 2002. — P. 447-460.

111. Verfurth, R. A review of a posteriori error estimation techniques for elasticity problems // Studies in Applied Mechanics. — 1998. — Vol. 47. — P. 257-274.

112. White Steven R. Density-matrix algorithms for quantum renormalization groups // Phys. Rev. B. — 1993. — Vol. 48, no. 14. P. 10345-10356.

113. Widom H. Hankel matrices // Trans. Amer. Math. Soc. — 1966. Vol. 121, no. 1. - P. 1-35.

114. Wiener N. The homogeneous chaos // American Journal of Mathematics. — 1938. — Vol. 60, no. 4. — P. 897-936.

115. Vol. 232 of NATO Adv. Sci. Inst. Ser. E Appl. Sci. — P. 293-314.

116. Володин E.M., Русев А.В., Дианский H.A. Воспроизведение современного климата с помощью совместной модели общей циркуляции атмосферы и океана INMCM 4.0 // Известия РАН, Физика атмосферы и океана. — 2010.- Т. 26, № 4. — С. 448-466.

117. Гантмахер Ф.Р. Теория матриц. — Наука, 1966. — Vol. 7.

118. Голуб Д., Лоун В. Матричные вычисления. — Мир М., 1999.

119. Кнут Д. Искусство программирования, т. 2. Получисленные алгоритмы, 3-е изд./Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильяме», 2000.

120. Марнук Г. И. Методы вычислительной математики. — Наука, 1980.

121. Смоляк, С.А. Квадратурные и интерполяционные формулы на тензорных произведениях некоторых классов функций // Докл. АН СССР. 1964. - Т. 148, № 5. — С. 1042-1053.

122. Тыртышников Е. Е. Тензорные аппроксимации матриц, порожденных асимптотически гладкими функциями // Матем. сб. — 2003. — Т. 194, № 5. — С. 147-160.

123. Яненко H.H. Метод дробных шагов решения многомерных задач математической физики. — Издательство "Наука Сибирское отделение, 1967.