ИСТИНА

Принято считать, что основу вычислительной математики и методов анализа данных составляют численные методы линейной алгебры. Во второй половине 20-го века они были главной темой для сотен исследователей. К началу 21-го века область вычислений с векторами и матрицами достигла высокой степени завершенности, а перед теми, кто привел ее к этому состоянию, возник вопрос о том, что же должно стать главной темой исследований в 21-м веке. По всей видимости это должны быть многомерные матрицы, которые часто называют также тензорами. В 20-м веке тензоры изучались и применялись прежде всего в физике как средство описания изучаемых объектов. В теоретической физике специальные тензорные конструкции были открыты как модели квантовых систем. В математике тензоры привели к некоторым знаменитым результатам, например к алгоритму Штрассена умножения двух матриц порядка n быстрее, чем за n^3 операций. Но эффективных вычислительных методов на базе тензоров в 20-м веке не было. Вычислительным инструментом тензоры стали лишь в 21-м веке. Даже "простые" случаи в многомерных задачах требуют рассмотрения таких объемов данных, в которых число элементов оказывается много больше числа атомов во Вселенной. Ключевой идеей в таких задачах является изучение специальной структуры данных, методов их сжатого представления и алгоритмов, использующих специальные параметризации данных. Для многомерных матриц довольно давно известны различные тензорные разложения. Однако для разработки эффективных методов численного анализа их в принципе недостаточно. Мы рассмотрим новые представления, в которых многомерная матрица фактически заменяется некоторой последовательностью ассоциированных с ней обычных матриц. Основным предположением относительно внутренней структуры данных является то, что эти матрицы имеют малый ранг или хорошо приближаются матрицами малого ранга. Сжатое представление для многомерных матриц (тензоров) строится через хорошо изученные разложения данных матриц. В результате удается получить ряд алгоритмов, сложность которых зависит от числа измерений линейно или полиномиально! Приложения включают задачи интерполяции многомерных функций, вычисление многомерных интегралов, решение уравнений типа Фоккера-Планка и Смолуховского, моделирование спиновых систем, построение фильтров для вейвлет-преобразований и многое другое. В практике наиболее простыми и полезными оказываются методы "тензорного поезда", полученные в ИВМ РАН начиная с 2009 года, основные публикации можно найти в интернете по адресу http://pub.inm.ras.ru. Для знакомства с этими методами и некоторыми их применениями можно рекомендовать также следующие работы: [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] 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. [3] J. A. Roberts, D. V. Savostyanov D.V., E. E. Tyrtyshnikov, Superfast solution of linear convolutional Volterra equations using QTT approximation, Journal of Computational and Applied Mathematics, vol.260, pp. 434-448 (2014). Доклад основан на результатах, полученных при поддержке грантов РФФИ 13-01-12061, 12-01-91333, 11-01-00549.