|
СЕМИНАРЫ |
Семинар лаборатории ПреМоЛаб
|
|||
|
ТЕНЗОРЫ И ВЫЧИСЛЕНИЯ Е. Е. Тыртышников Институт вычислительной математики РАН, г. Москва |
|||
Аннотация: Основными объектами полилинейной алгебры являются полилинейные формы на векторных пространствах, называемые также тензорами. При выборе базисов в этих пространствах тензор получает представление в виде некоторой d-мерной матрицы, где d - число пространств. Мы будем понимать под тензором именно d-мерную матрицу. Главная проблема при проведении вычислений с d-мерными матрицами заключается в том, что даже при значениях d порядка нескольких десятков их невозможно задавать полной совокупностью элементов. Таким образом, вычислительные методы должны строиться при некоторых существенных предположениях относительно d-мерных матриц. Выделение соответствующих достаточно общих классов тензоров, допускающих удобные для построения алгоритмов параметризации, является весьма нетривиальной задачей. Одно из возможных решений этой задачи связано с со специальными тензорными разложениями, прежде всего с разложением в так называемый тензорный поезд. Для краткости такие разложениями называют ТТ-разложениями. Их можно применять для приближенного представления многомерных данных. При этом для базовых операций с тензорами получены очень эффективные алгоритмы в ТТ-формате. Важно, что вычислительная сложность этих алгоритмов зависит от d полиномиально, а во многих случаях линейно! Разработаны и эффективные методы приближения d-мерных матриц некоторым ТТ-разложением по относительно малой части их элементов. Все это может успешно применяться при численном решении довольно трудных многомерных задач типа уравнений Фоккера-Планка, уравнений Смолуховского, при оптимизации решений дифференциальныз уравнений по параметрам. Одно из самых последних приложений - новый эвристический метод поиска глобального минимума в задачах докинга при разработке лекарственных препаратов, оказавшийся на порядок эффективнее традиционно применяемых генетических алгоритмов. ЛИТЕРАТУРА [1] I. Oseledets, E. Tyrtyshnikov, Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J. Sci. Comput., vol 31, no. 5 (2009), pp. 3744-3759. [2] I. Oseledets, E. Tyrtyshnikov, TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432 (2010), pp. 70–88. [3] I. V. Oseledets, E. E. Tyrtyshnikov, Algebraic wavelet transform via quantics tensor train decomposition, SIAM J. Sci. Comp., vol. 31, no. 3 (2011), pp. 1315-1328. [4] I. Oseledets, E. Tyrtyshnikov, N. Zamarashkin, Tensor-train ranks for matrices and their inverses, Comput. Meth. Appl. Math., Vol. 11, No. 3, pp. 375-384 (2011). [5] V. A. Kazeev, B. N. Khoromskij, E. E. Tyrtyshnikov, Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity. SIAM J. Sci. Comput. 35 (2013), no. 3, A1511–A1536. [6] Д.А.Желтков, И.В.Офёркин, Е.В.Каткова, А.В,Сулимов, В.Б.Сулимов, Е.Е.Тыртышников. TTDock: метод докинга на основе тензорных поездов, Вычислительные методы и программирование, том 14, с. 279-291 |