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

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]. Например, алгоритм Штрассена умножения матриц размера 2×2 можно получить как тензорное разложение тензора размера 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⁷ ЦГе-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³.

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

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

А = А (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 I2,. .. , 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. 37 443 759.

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 201 001. — 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.