ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
Общие методы классической вычислительной математики, основанные на разностных схемах или методе конечных элементов, трудно или невозможно применять, когда расчетная область принадлежит пространству с числом координатных осей порядка нескольких десятков и выше. Например, взяв по 10 отсчетов на каждой оси в 30-мерном пространстве, мы уже получаем общее число точек, превосходящее число атомов во вселенной. Имеется также ряд "отрицательных" результатов, связанных с оценками аппроксимаций в многомерных пространствах. Символом трудностей, связанных с многомерными пространствами, стал неформальный термин "проклятие размерности". Тем не менее, во многих задачах из практических приложений функции многих переменных обладают важными, иногда скрытыми, свойствами и в силу этих свойств допускают весьма эффективные представления, характеризуемые вполне приемлемым число параметров. Так, для описания спиновых систем с астрономически большим числом состояний в теоретической физике давно применяются линейные тензорные сети или представления в виде произведения конечного числа матриц небольших размеров (Matrix Product States). Аналогичные представления недавно появились в вычислительной линейной алгебре как разложения многомерных матриц в тензорный поезд (TT-разложения). Важно, что вместе с новым именем появились и новые, очень эффективные вычислительные алгоритмы, которых не было в теоретической физике. Прежде всего, это методы крестовой аппроксимации многомерных матриц, заданных неявным образом, например с помощью процедуры, вычисляющей любое ее значение по требованию. Многомерные матрицы полностью определяются семейством обычных матриц, которые хорошо приближаются матрицами малого ранга. Именно это свойство является ключевым и характеризует область успешного применения тензорных поездов. Новые алгоритмы оказались настолько эффективными, что изменили само отношение к проблеме размерности и даже дали основание увеличивать число измерений искуcтвенным образом для того, чтобы задача решалась эффективнее. В частности, это очень успешно делается при решении уравнений типа Смолуховского. Классические сеточные методы в сочетании с методами представления и аппроксимации данных в формате тензорного поезда начинают успешно конкурировать с методом Монте Карло. Таким образом, во многих случаях размерность оказывается благом - настолько привлекательным, что в "маломерных" задачах возникает интерес к ее искуственному увеличению. Теперь такой подход называют тензоризацией данных. Методы тензорного поезда появились в 2009 году в Институте вычислительной математики РАН и были сразу же приняты в мире, так как действительно оказались очень эффективными. Появились также HT-разложения (в группе проф. Хакбуша в Лейпциге), дающие некоторые дополнительные возможности, но обладающие более сложной логической структурой. В докладе будет рассказано о новых вычислительных инструментах, основанных на TT- и HT-разложениях и использующих тензоризацию данных с целью увеличения числа координатных осей. Oseledets I., Tyrtyshnikov E., 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. Oseledets I., Tyrtyshnikov E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, pp. 70-88 (2010). Oseledets I., Tyrtyshnikov E., Algebraic wavelet transform via quantics tensor train decomposition, SIAM J. Sci. Comp., vol. 31, no. 3, pp. 1315-1328 (2011). Dolgov S., Tyrtyshnikov E., On evolution of solution times for the chemical master equation of the enzymatic futile cycle. Russian Journal of Numerical Analysis and Math. Modelling, vol. 30, no. 1, pp. 37-42 (2015). Matveev S.A., Smirnov A.P., Tyrtyshnikov E.E., A fast numerical method for the Cauchy problem for the Smoluchowski equation Journal of Computational Physics, Academic Press (United States), vol. 282, FEB, pp. 23-32 (2015). Oferkin I.V., Zheltkov D.A., Tyrtyshnikov E.E., Sulimov A.V., Kutov D.C., Sulimov V.B., Evaluation of the docking algorithm based on Tensor Train global optimization, Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming \& Computer Software (Bulletin SUSU MMCS), vol. 8, no. 4, pp. 83-99 (2015).