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

Вычислительные тензорные методы и их применения

01.01.07 — Вычислительная математика

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

005012712

1 2 26:2

Москва —

2012

005012712

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики РАН.

Научный консультант: чл-корр. РАН, д.ф.-м.н., профессор Тыртышников Евгений Евгеньевич

Официальные оппоненты: Ильин Валерий Павлович, д.ф.-м.н, профессор (Институт вычислительной математики и математической геофизики СО РАН, г.н.с.),

Гутерман Александр Эмилевич д.ф.-м.н., профессор (Механико-математический факультет МГУ, кафедра высшей алгебры),

Хазанов Владимир Борисович, д.ф.-м.н., профессор

(Санкт-Петербургский государственный морской технический университет, кафедра прикладной математики и математического моделирования).

Ведущая организация: Вычислительный центр им A.A. Дородницына РАН.

Защита состоится « 16 » марта, 20 12 г. в 15 часов на заседании диссертационного совета Д 002.045.01 в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики РАН по адресу: 119333, г. Москва, ул. Губкина, д. 8.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики РАН.

Автореферат разослан «_» февраля 200 12 г.

Учёный секретарь

диссертационного совета Д 002.045.01 д.ф.-м.н.

Г. А. Бочаров

Общая характеристика работы

Актуальность работы

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

Во всех вышеперечисленных примерах необходимо строить малопараметрические приближения для функций многих переменных и связанных с ними многомерных массивов (тензоров). При этом число координатных осей тензора может быть огромным. Например, в вычислительной химии для молекул с N электронами или атомами функции, подлежащие определению (волновые функции, потенциальные поверхности), описываются с1 = ЗN параметрами. Использование простых сеток сразу приводит к массивам с числом элементов п"1, где п — число точек по одному направлению. Экспоненциальная зависимость числа параметров от числа координатных осей носит название «проклятие размерности». Тем не менее, во многих приложениях удается найти методы представления многомерных массивов. В частности, могут использоваться специальные базисы; например, на основе радиальных базисных функций. Однако такие схемы не являются универсальными, и для каждой конкретной задачи приходится создавать свои методы.

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

ническое разложение нельзя вычислить с помощью надежных алгоритмов.

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

Исследования, отражённые в диссертации, поддерживались грантами РФФИ №Ю2-01-00590-а, 04-07-90336-в, 05-01-00721-а, 06-01-08052-офи, 08-01-00115-а, 09-01-00565-а, 09-01-12058-офи_м, 09-01-91332-ННИС)_а, 11-01-00549-а,11-01-12137-офи-м-2011, Программами ОМН-3 и ОМН-5, грантами МК-127.2009.1 и МК-140.2011.1 президента РФ молодым кандидатам наук, госконтрактами П940, П1178, П1112, 14.740.11.1067, 14.740.11.0345 в рамках ФЦП «Кадры».

Цели работы

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

Методы исследования

Методами исследования являются классические результаты матричного анализа и вычислительной линейной алгебры (сингулярное разложение, С^Е-разложение, малоранговые аппроксимации с помощью скелетного разложения матриц), мультилинейная алгебра.

Научная новизна работы

Представленные результаты являются новыми и состоят в следующем.

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

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

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

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

• Предложен и реализован новый метод сжатия данных с потерями на основе интерпретации QTT-формата как адаптивного вейвлет-преобраз-ования.

• На основе QTT-формата предложен новый быстрый метод решения многопараметрических задач.

• Получены оценки на QTT-ранги полиномиальных потенциальных поверхностей квантовой молекулярной динамики, построен линейный по числу степеней свободы алгоритм приближенного нахождения минимального собственного значения на основе метода DMRG (Density Matrix Renormalization Group).

Теоретическая и практическая ценность

Теоретическая значимость работы заключается в создании и обосновании принципиального нового математического аппарата для работы с многомерными массивами. Основой предложенного подхода является Tensor Train -

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

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

В вычислительной химии удалось получить приближенные основные состояния для потенциала Эно-Хайлеса с числом степеней свободы вплоть до 256, а также вычислить основное колебательное состояние для различных молекул более точно, чем с помощью методов, реализованных в современном квантово-химическом пакете САМЕЗБ. При решении многопараметрических и стохастических уравнений методы, основанные на ТТ-разложении, оказались в десятки раз эффективнее, чем стандартные методы (стохастический метод Галеркина и метод стохастической коллокации). Методы аппроксимации многомерных массивов были также применены для сжатия поля температуры, вычисленной с помощью сг-модели ИВМ РАН, удалось получить сжатие в 44 раза при абсолютной погрешности 0.1 градус Цельсия.

Обоснованность и достоверность результатов

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

Апробация работы

Основные результаты докладывались на следующих конференциях и семинарах.

• Международные конференции «Матричные методы и операторные уравнения» (ИВМ РАН, 2005 и 2007);

• 3-я международная конференция «Математические идеи П.Л. Чебышё-ва и их приложение к современным проблемам естествознания» (Обнинск, ИАТЭ, 2006);

• Международные конференции по линейной алгебре ILAS-13 (Амстердам, 2006), ILAS-14 (Шанхай, 2007), ILAS-17 (Пиза, 2010), ILAS-18 (Бра-уншвейг, 2011);

• Международные конференция SCPDE (Гонконг, 2008, 2010);

• Международная конференция по структурированным матрицам (Кор-тона, 2008);

• Международная конференция по численному анализу и теории операторов (Хельсинки, 2008);

• Международный симпозиум GAMM (Гданьск, 2009);

• Workshop on Advanced Computer Simulation Methods for Junior Scientists (Санкт-Петербург, 2009);

• Международные семинары GAMM-26, GAMM-27;

• Международная научная конференция «Современные проблемы вычислительной математики и математической физики» памяти А.А. Самарского (Москва, 2009);

• Международная конференция МДОЗМФ (Херсон, 2009);

• Международная конференция NOLTA-2009 (Саппоро, 2009);

• Международная конференция AIM Workshop on computational optimization for tensor decompositions (Пало Альто, 2010);

• Международная конференция «Актуальные проблемы вычислительной математики и математического моделирования» посвященная 85-летию Г.И. Марчука (Новосибирск, 2010);

• Международная конференция Tensor Methods in multi-dimensional boundary-value and eigenvalue problems (Лейпциг, 2010);

• Международная конференция TDA (Монополи, 2010);

• Международная конференция Separation of variables and applications (Ницца, 2010);

• Школа-конференция «Теория и численные методы решения обратных и некорректных задач» (Новосибирск, 2010);

• Международная конференция HDA-2011 (Бонн, 2011);

• Международный симпозиум Househ.older-18 (Тахо, 2011);

• Всероссийский симпозиум по прикладной и промышленной математике (Кисловодск, 2006, 2008).

• Всероссийские конференции «Научный сервис в сети интернет» (Абрау-Дюрсо, 2006,2007,2008,2009,2011).

• XLIX научная конференция МФТИ (Москва, 2006);

• Ломоносовские чтения (Москва, 2008);

• Тихоновские чтения (Москва, 2006,2007, 2010);

• Семинар «Вычислительные и информационные технологии в математике» (руководители в разные годы Ю.М. Нечепуренко, В.И. Лебедев, Е.Е. Тыртышников, В. И. Агошков, А. Б. Богатырев, Ю.В. Василевский);

• Семинар кафедры теории функций и функционального анализа мехмата МГУ (2009, руководитель B.C. Кашин);

• Семинар кафедры алгебры мехмата МГУ (2009, руководитель В.Н. Латышев );

• Семинар ИПМ РАН им. Бабенко (2009);

• Семинар физфака МГУ и НИВЦ МГУ (2011, руководитель А.Г. Ягола);

• Семинар кафедры химии РХТУ им. Менделеева (2011, руководитель В.Г. Цирельсон);

• Семинар кафедры физической химии химфака МГУ (2011, руководитель А.Ю. Немухин);

Публикации

Основные результаты диссертации отражены в публикациях [1-33], из них 8 работ опубликовано в отечественных рецензируемых изданиях, рекомендованных ВАК, 16 работ опубликовано в международных рецензируемых изданиях из рекомендованного ВАК списка «Web of Science: Citation Index Expanded» (база данных по естественным наукам), 3 работы — в рецензируемых международных изданиях, 1 работа — в сборнике научных трудов. 5 работ опубликовано в других научных изданиях.

Вклад автора в совместные работы заключался: в формировании постановки проблемы [1, б, 9, 13, 15, 18, 20, 22, 30, 33] предложении идеи решения [2, 6, 9, 10, 11, 12, 13, 16, 17, 18, 19, 20, 22, 24, 25, 26, 27, 31, 30, 33], теоретическом обосновании [6, 11, 12, 16, 17, 18, 27], совместном теоретическом обосновании [1, 2, 9, 10, 13, 15, 20, 24, 25, 26, 30, 33], технической реализации [2, 10, 11, 12, 16, 17, 18, 20, 24, 25, 26, 27], совместной технической реализации [13, 21, 30], постановке численных экспериментов [2, 10, И, 12, 16, 17, 18, 20, 24, 25, 26, 27].

Благодарности

Автор выражает искреннюю благодарность своему научному консультанту проф., чл.-корр РАН Е.Е. Тыртышникову за постоянную поддержку, академику РАН В.П. Дымникову за поддержку и прекрасную атмосферу, созданную в ИВМ РАН, д.ф.-м.н, проф. В.И. Агошкову, д.ф.-м.н A.B. Богатыреву, д.ф.-м.н Ю.В. Василевскому, д.ф.-м.н. Ю.М. Нечепуренко за очень полезные и стимулирующие обсуждения и предложения, повлекшие за собой существенную переработку работы, д.ф.-м.н В.Н. Хоромскому за плодотворное сотрудничество.

Диссертация посвящена памяти моего дедушки, к.ф.-м.н, генерал-майора И.О. Бежаева. (1918-2010).

Структура и объём работы

Работа состоит из введения, четырёх глав и заключения. Объём диссертации — 206 страниц. Библиография включает в себя 158 наименований. Диссертация содержит 20 рисунков и 7 таблиц.

Краткое содержание работы

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

чимость работы.

В первой главе вводится новое тензорное разложение — ТТ-разложение. ТТ-разложение лежит в основе всех разработанных в диссертации вычислительных тензорных методов. В разделе 1.1 формулируются требования к малопараметрическим представлениям тензоров (тензорным форматам). В разделе 1.2 рассматриваются два стандартных разложения тензоров: каноническое разложение и разложение Таккера, приводятся их свойства. Формулируются их недостатки и ставится основной вопрос:

можем ли мы найти такое разложение для й-мерных массивов, которое свободно от экспоненциальной зависимости от d, но при этом операции линейной алгебры и округление можно проводить с помощью устойчивых подходов на основе SVD?

В разделе 1.3 доказываются две основные леммы, которые позволяют построить такое представление.

Лемма 1 Если тензор А = [a(ii,..., id)] имеет каноническое разложение ранга г, то для любой матрицы-развёртки В = [a{T-\,Tz)]

rank В < г.

Лемма 2 Пусть тензор А = [A(i],..., г^)] имеет каноническое представление ранга г и развёртка В = [А(Х],22)] определяется «длинными индексами» Х\ и li, содержащими соответственно d\ и di исходных индексов. Рассмотрим произвольное разложение В вида

В = UVT, U = [U(Zi, а)], V = [V(I2, а)],

где U и V имеют г = rank В столбцов. Тогда Ы{Ъп а) и V{l2,oi} могут быть рассмотрены как тензоры порядка di + 1 и ¿2+1 соответственно, и для обоих тензоров существуют канонические представления ранга не выше т.

На основании этих двух лемм в разделе 1.4. строится иерархическое разложение Таккера. Пример построения приведен на рис. 1.

Предположим, что для 9-мерного массива существует (неизвестное заранее) каноническое разложение ранга г. Тогда на основании леммы 1 его можно заменить на 6-мерный и 5-мерный массивы, которые по лемме 2 имеют каноническое представление ранга не выше г. Продолжая рекурсию, получим вместо исходного 9-мерного массива семь трехмерных массивов. Для числа параметров такого представления верна следующая теорема.

6 5

/ \ / \

4 4 4 3

/\ ,/\ / \

3 3 3 3 3 3

Рис. 1

Расщепление измерений.

Теорема 1 Пусть А — d-мерный тензор с каноническим разложением ранга г. Тогда существует ТТ-разложение с

nrd+id-ZJr3 (1)

параметрами.

В разделе 1.5 все три упомянутых разложения (разложение Таккера, каноническое разложение, иерархическое разложение Таккера) рассматривается с точки зрения формализма тензорных сетей. Как частный случай иерархического разложения Таккера вводится tensor-train разложение (ТТ-разложение). Оно имеет вид

A(ii,...,id) = L G^ibtxi) G2(abi2,a2) •••

a,...,«d-1 (2)

... Gd-i[oid_2,id_ba[i_i) Gd(ad-hi-d)»

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

Теорема 2 Тензорное разложение, заданное произвольным деревом, удовлетворяющим ограничениям 1 и 2, можно представить в виде

A(ib...,id) = Y. Gl(Po,V(l)>Pl) G2(|3l,V(2),P2) ...

Pb—iPd-l _ _ (3)

... Gd-l(Pd-2)T-a(d-1)i Pd-l) Gd(Pd-1> V(d)i Pd)-

В разделе 1.6 исследуются свойства ТТ-разложения. Вводится компактная матричная форма разложения в виде произведения матриц, зависящих от параметров:

А(г,,..., ч) = G, (i, )G2(i2) • • • Gd(id), (4)

где Gic(iic) — матрица размера rk_i х rk, г о = rd = 1. Доказана теорема, связывающая ТТ-ранги с рангами матриц-разверток тензора А. Матрица Ак называется k-ой разверткой тензора А, если

Ak(ii ...ik;ik+,...id) = A(ib...,id), (5)

т.е. первые к индексов нумеруют строки Ак, а последние (d — к) — столбцы Ак.

Теорема 3 Если для каждой матрицы-развёртпки Ак с!-мерного тензора А вида (5) выполняется

гапк Ак = Гк, (6)

то существует разложение (4) с ТТ-рангами не выше гк.

Доказательство теоремы 3 конструктивно и дает алгоритм построения ТТ-разложения — ТТ-БУБ. Разложение является устойчивым, что показывает

Теорема 4 Для заданного тензора А = [/\[11,..., существует ТТ-при-ближение Т = [Т(г1,...,1д)] с ТТ-рангами гк такими, что

||A-T||f<

d—1

L

k=i

•k'

(7)

где £k — расстояние (во фробениусовой норме) от Ак до наилучшего приближения ранга тк;

£k = min ||А]с - ВЦр.

rankB<rk

В разделе 1.7 вводится и обосновывается быстрая процедура тензорного округления: для заданной точности е и заданного тензора А в ТТ-формате с рангами тк ^ г требуется найти тензор В с минимально возможными рангами такими, что ||А —B||f ^ е||В||р. Вычислительная сложность такого алгоритма

— Ofdnr3) операций. В разделе 1.8 вводится ТТ-формат для матриц и доказывается теорема о связи кронекеровских рангов матрицы с ТТ-рангами. В разделе 1.9 систематически выводятся формулы для основных арифметических операций в ТТ-формате: сложение, умножение на число, поэлементное произведение, скалярное произведение, умножение матрицы на вектор, вычисление многомерной свертки. Например, если заданы два тензора А и В одинаковых размеров в ТТ-формате:

A(ib...,id) = A,(ii)A2(i2)... Ad(id), В(ii,...,id), В,(i,)B2(i2)... Bd(id),

то их поэлементное произведение С = АоВ также представимо в ТТ-формате с ядрами

Ck(ik) = Ak(ik) <g Bk(ik).

Вазовые процедуры имеют линейную по d сложность и результат получается также в ТТ-формате. В разделе 1.10 вводится понятие функционального ТТ-разложения, получены явные формулы для FTT-представления нескольких функций многих переменных, которые в дальнейшем будут использованы для получения оценок для числа параметров QTT-формата. В разделах 1.11-1.12 получена интерполяционная формула в ТТ-формате. Доказана следующая теорема

Теорема 5 Пусть А — произвольный d-мерный тензор размера ni х ... х rid с ТТ-рангами

rk = rank Ak, Ak = A(iii2... ik; ik+i... id).

Предположим, что заданы правые индексные множества

Л = BÍP0], 01 = 1....Гк, l = k,...,d-1,

и левые индексные множества

Ik = [iiai)], CXI = 1,... ,-Pfc, l = 1,...,k-l,

так, что левые индексные множества образуют левую вложенную последовательность, и все rk х Гк подматрицы на пересечении

Ak(ak) |3k) = А^',^',... Д[й0, ..., ak, |3k = 1,... ,rk

невырождены.

Тогда тензор А может быть восстановлен по трёхмерным тензорам Ск размера Tk_i х tit х т^ с элементами

г (rv i R 1 — Л(i(a*' 1-(ак) i ^(Pk) ^СЭк}л no интерполяционной формуле «тензорных поездов»

A(M,i2,.^,id) = Ц Ci(ii,ai) C2(abi2,a2) ••• Cd_,(ad_2,id_i,ad_i) Cd(ad_i,id),

где тензорные вагоны Ск получаются из Ск при помощи умножения тензора на матрицу:

Ск = СкХ3А^\ к = 2,..., d — 1,

Ci = Ci А-|Cd = Cd.

Смысл этой теоремы состоит в том, что если известно, что тензор имеет ранг т, то его можно точно восстановить по 0{dnr2) элементам. По аналогии с двумерным случаем, предложен адаптивный многомерный крестовый метод (TT-cross) для нахождения интерполяционных индексов, упомянутых в теореме 5. Основным вычислительным инструментом алгоритма TT-cross является алгоритм поиска подматрицы максимального объема. В разделе 1.13 приведены краткие выводы.

Глава 2 посвящена QTT-разложению (quantized tensor train), которое основано на идее виртуальных уровней или квантизации. В разделе 2.1 вводится понятие квантизации и дается определение QTT-формата. При квантизации заданный массив превращается в многомерный. В качестве примера можно рассмотреть «одномерный» случай. Пусть задана некоторая функция f на отрезке [а, Ь], на котором введена равномерная сетка с 2d узлами. Тогда вектор значений этой функции представляет собой вектор, т.е. одномерный массив, длины 2d. Этот массив затем рассматривается как d мерный массив с размерами модовых индексов, равными 2 с помощью стандартного бинарного кодирования одномерного индекса любого элемента. К этому новому массиву применяется ТТ-разложение. Если получившиеся ранги малы, то получаем малопараметрическое представление с количеством параметров 2dr2. Число параметров при условии, что г ограничено сверху, растет как логарифм от полного числа элементов, что делает такое представление очень эффективным. В разделе 2.2 доказано, что многие «стандартные» функции имеют

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

В разделе 2.3 получено явное СЭТТ-представление для характеристической функции К-мерного стандартного симплекса. Такая функция возникает во многих задачах финансовой математики. Для нее показано, что С}ТТ-ранги ограничены 2К — 1 и не зависят от шага сетки. На рис. 2 приведены С^ТТ-ранги для характеристической функции К-мерного симплекса для К = 32 и п = 210 точек по каждому направлению.

Mode Рис. 2

QTT-ранги характеристической функции 32-мерного симплекса.

В разделе 2.4 приведены QTT-разложения некоторых операторов, в частности, оператора Лапласа, который играет важную роль во многих многомерных задачах (как оператор кинетической энергии). Также в разделе 2.4 доказана следующая теорема о структуре обратной к ленточной теплицевой

матрице.

Теорема 6 Пусть Т — ленточная теплицева матрица с верхней шириной ленты S) и нижней шириной ленты S2 размера N = 2й. Тогда, все QTT-ранги ограничены сверху (si + S2)2 + 1.

В разделе 2.5 выявлена аналогия между QTT-разложением и дискретными вейвлет-преобразованиями. На основе этой связи в разделе 2.6 вводится новая интерпретация QTT как нелинейного адаптивного вейвлет-преобразования с фильтрами, вычисляемыми по самой функции. Построены алгоритмы вычисления фильтров и применения преобразования. В разделе 2.7 показано, как применить WTT для создания новых вейвлет-преобразований.

Глава 3 посвящена применению разработанных в главах 1 и 2 вычислительных тензорных методов для решения практически важных многомерных задач. Раздел 3.1 посвящен перечислению таких задач в следующих областях: вычислительная химия, многопараметрические задачи, сжатие данных. В разделе 3.2 описывается формулировка задачи о решении молекулярного уравнения Шредингера, кратко вводятся основные понятия. В разделе 3.3. формулируется задача на собственные значения многомерного оператора, описывающего колебательные движения молекул. В разделе 3.4 для случая полиномиальной потенциальной поверхности, имеющего важный практический смысл при малых колебаниях, доказаны оценки на ТТ и QTT ранги вида rk = 0(f'^О, где f — число степеней свободы, as — порядок полинома. Для молекулы HONO получены QTT-представления высокой точности для потенциальной поверхности с рангами порядка 10 и относительной точностью Ю-8.

В разделе 3.5 строится оптимизационный метод нахождения минимального собственного значения матрицы, заданной в QTT формате, основаный на алгоритме Density Matrix Renormalization Group (DMRG), который много лет применялся в физике твердого тела. Оказывается, что этот алгоритм является не чем иным, как методом блочной релаксации в QTT-формате. Получены расчетные формулы для одной итерации алгоритма. В разделе 3.6 приведены численные расчеты для трехмерного потенциала и для потенциала Эно-Хайлеса с числом степеней свободы вплоть до 256. В разделе 3.7 произведено сравнение алгоритма DMRG-QTT на реальных молекулах с использованием данных, полученных с помощью пакета GAMBSS. Результаты сравнения по вычислению энергии основного колебательного состояния приведены в таблице 1. Видно, что тензорный метод систематически дает более низкое значение, а так как все рассматриваемые методы являются вариаци-

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

Таблица 1

Минимальные собственные значения для различных молекул (в см-1).

Молекула E(DIAG) E(VMP2) E(DMRG-QTT) Эксперимент

Н2СО СН3ОН С2Н4 6005.83 12264.27 11477.09 5904.54 12071.90 11298.93 5808.19 11187.57 11263.74 5643.5 10848.5 10784.7

В разделе 3.8 рассмотрено вычисление многих собственных значений с помощью решения нестационарной задачи в мнимом времени

^ = ф(о) =ф0, H = -1A + V,

и расчет спектра с помощью преобразования Фурье от автокорреляционной функции a(t) = (^(t),il>(0)). Используется схема расщепления Марчука-Яненко-Стрэнга и арифметика ТТ-формата с округлением. Результаты вычисления спектра (при разных точностях) приведены на рис. 3 и 4.

В разделе 3.9 описывается применение разработанных вычислительных методов к решению стохастических и многопараметрических задач. Рассматриваются задачи вида

£{ a)u = f,

где линейный оператор Да) зависит от некоторого случайного поля а. Случайное поле предполагается параметризованным с помощью M параметров, после чего задача рассматривается как система линейных уравнений с NpM неизвестными. Описаны стандартные подходы к решению таких задач, основанные на стохастическом методе Галеркина и методе стохастической колло-кации. В диссертации предложено использовать ТТ-разложение для приближенного представления решения. В разделе 3.10 представлен метод решения больших линейных систем, основанный на итерациях Ричардсона с «одноточечным» предобуславливателем. На каждом шаге такого метода требуется решить г систем при некоторых значениях параметров, остальные вычисления производятся с помощью быстрой ТТ-арифметики. В разделе 3.12 приведены численные эксперименты по решению скалярного уравнения диффузии

= 25

= 5

1 Ц1м......

О

10

1 0.8 0.6 0.4 0.2 0

[

ч1А

0

10

Рис. 3

Спектр для потенциала Эно-Хайлеса ^ = 2) при использовании различных рангов. По горизонтали — частота, по вертикали — амплитуда

= 25

= 5

Рис. 4

Некоторые детали спектра

с коэффициентом, зависящим от параметров. Рассмотрены четыре примера. Приведем результаты численных экспериментов для одного из них Необходимо решить уравнение диффузии с граничными условиями Дирихле на квадрате [0,1]2. Коэффициент диффузии задан в виде а(х,у) = 1 тЛМш» где £,((х) — характеристические функции четырех кругов (рис.5). Переменные уьг = 1,...,4 принадлежат интервалу [—0.99,0]. Такая задача может возникнуть, например, при решении обратной задачи о восстановлении коэффициента диффузии в некоторых подобластях: в этом случае решение многопараметрической задачи эквивалентно решению «всех» прямых задач, и эффективному представлению для многомерной параметрической зависимости в С^ТТ-формате. Для дискретизации по физической переменной взята сетка 256 х 256. Результаты расчетов приведены на рис. 6.

о-1-1-----

0 0.2 0.4 0.6 0.8 1

Рис. 5

Расчетная область: 4 круга

Стандартные методы существенно более трудоемки. Тензорный метод требует всего 100 решений линейных систем для достижения точности Ю-5. Метод стохастической коллокации требует решения в 1000 раз больше линейных систем, а стохастический метод Галеркина требует решения системы, в которой примерно 60 миллионов неизвестных.

Рис. 6

Задача «4-х кругов». Вверху: невязка в зависимости от итерации. Слева внизу: время на итерацию. Справа внизу: ранги в зависимости от итерации.

В разделе 3.12 рассмотрен пример примения '\А/ТТ-разложения для сжатия поля температуры, вычисленного с помощью сг-модели общей циркуляции океана, разработанной в ИВМ РАН. Данные представляют собой четырехмерный массив размера360x337x40x648 х№х№), в котором хранится температура в узлах широтно-долготной сетки, с 40 уровнями по высоте. Интервал по времени — 1 час. Весь массив занимает на диске объём примерно 12 гигабайт, и необходимо приблизить его с потерями, с ошибкой в С-норме не больше 0.1 градуса Цельсия. При таких условиях удалось получить сжатие примерно в 44 раза. Более подробно численные результаты приведены в таблице 2. Отметим, что время сжатия оказалось меньше, чем полное время, требуемое на чтение всего массива в оперативную память.

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

Таблица 2

Сжатие массива температуры с помощью \¥ТТ-разложения

Память Ошибка абсолютная Ошибка относительная Время сжатия

497 МВ 277 МВ 0.0392 0.0984 0.0004 0.0009 и 500 секунд и 500 секунд

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

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

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

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

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

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

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

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

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

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

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

• С2ТТ/\ЛГГТ разложения применены для сжатия поля температуры, вычисленного с помощью а-модели общей циркуляции океана ИВМ РАН, получено сжатие в 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 // SIAM 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 // SIAM J. Sci. Comput. — 2009.

- Vol. 31, no. 5. - P. 3744-3759.

[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 2010-01. — 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/preprint2010_68.pdf.

[27] Oseledets I. V. Tyrtyshnikov E.E. Algebraic wavelet transform via quantics tensor train decomposition // SIAM J. Sci. 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] Oseledets I. V. Tensor-train decomposition // SIAM J. Sci. Comput. — Vol. 33, no. 5. - P. 2295-2317.

[30] 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/ 201l/preprint201l_19.pdf.

[31] Low-rank tensor structure of solutions to elliptic problems with jumping coefficients / Sergey Dolgov, Boris N. Khoromskij, Ivan V. Oseledets, Eugene E. Tyrtyshnikov // J. Comput. Math. — 2012. — Vol. 30, no. 1. — P. 14-23.

[32] Oseledets I. V. DMEG 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 //.L. Tensor-train ranks of matrices and their inverses // Comput. Meth. Appl. Math. — 2011. — Vol. 10, no. 3. - P. 394-403.

изд. лиц. №03991 от 12.02.2001. Компьютерный набор. Подписано в печать 05.02.2012. Усл. печ. л. 1.5. Тираж 100 экз.

Институт вычислительной математики РАН. 119333, Москва, ул. Губкина, 8.

Введение

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.

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.