Отчетный доклад (2015)

Иван Оселедец
oseledets.github.io, i.oseledets@skoltech.ru

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

  • Доказана тензорная структура решений многомашстабной эллиптической задачи с квазипериоди- ческими коэффициентами (совместно с C. Schwab, В. Казеевым), что дает принципиально новый подход оптимальной сложности к расчету композитных структур и фотонных кристаллов.
  • Предложен новый метод расчета интегралов по траектории на основе малоранговой аппроксимации (совм. с М. Лицаревым). Метод позволяет расчитывать интегралы в размерности ∼ 10000 и быстрее стандартного метода Монте-Карло в сотни раз при одинаковой точности.
  • Предложен и реализован новый высокоточный метод приближения поверхностей потенциальной энергии на основе тензорных поездов и активных подпространств (совм. с В. Барановым). Показано, что аффинное преобразование позволяет понизить число параметров в сотни раз и получить очень компактные представления потенциальной поверхности.
  • Предложен новый подход построения приближенной факторизации Холецкого для разреженной матрицы на основе H2-матриц. На основе численных экспериментов показано, что новое представление позволяет сократить время факторизации и требуемую память в несколько раз по сравнению со стандартным пакетом CHOLMOD (совм. с Д. Сушниковой).
  • Предложен новый метод решения проблемы холодного старта в рекомендательных системах на основе выбора репрезентативных продуктов с помощью принципа максимального объема (совм. с А. Фонаревым и А. Михалевым).

В исследованиях участвовали: А. Ю. Михалев, Д. А. Сушникова (асп. ИВМ РАН), М. В. Рахуба (асп. МФТИ), М. А. Кузнецов, П. В. Харюк (асп. ВМК), Д. А. Колесников, А. Фонарев, А. Новиков, В. Баранов.

Публикации

[1] G.V. Ryzhakov, A.Yu. Mikhalev, D.A. Sushnikova, I.V. Oseledets. Numerical solution of diffraction problems using large matrix compression. In Antennas and Propagation (EuCAP), 2015 9th European Conference on, pages 1–3, April 2015.

[2] V. Baranov, I. Oseledets. Fitting high-dimensional potential energy surface using active subspace and tensor train (AS+TT) method. J. Chem. Phys., (143):17107, 2015. doi:10.1063/1.4935017.

[3] Sergey I. Kabanikhin, Nikita S. Novikov, Ivan V. Oseledets, Maxim A. Shishlenin. Fast Toeplitz linear system inversion for solving two-dimensional acoustic inverse problem. Inverse Problems, 2015. doi:10.1515/jiip-2015-0083.

[4] D. A. Kolesnikov, I. V. Oseledets. From low-rank approximation to arational Krylov subspace method for the Lyapunov equation. SIAM J. Matrix Anal. Appl., 36(4):1622–1637, 2015. doi:10.1137/140992266.

[5] M. S. Litsarev, I. V. Oseledets. Fast low-rank approximations of multidimensional integrals in ion-atomic collisions modelling. Numer. Linear Algebra Appl., 22(6):1147–1160, 2015. doi:10.1002/nla.2008.

[6] Christian Lubich, Ivan Oseledets, Bart Vandereycken. Time integration of tensor trains. SIAM J. Numer. Anal., 53(2):917–941, 2015. doi:10.1137/140976546.

[7] A. Yu. Mikhalev, I. V. Oseledets. Iterative representing set selection fo nested cross approximation. Numer. Linear Algebra Appl., 2015. doi:10.1002/nla.2021.

[8] A. Yu. Mikhalev, I. V. Oseledets. Rectangular maximum-volume submatrices and their applications. arXiv preprint 1502.07838, 2015.

[9] I. V. Oseledets, G. V. Ovchinnikov, A. M. Katrutsa. Linear complexity SimRank using iterative diagonal estimation. arXiv preprint 1502.07167, 2015.

[10] I. Ostanin, A. Mikhalev, D. Zorin, I. Oseledets. Engineering optimization with the fast boundary element method. WIT Transactions on Modelling and Simulation, 61:7, 2015. doi:10.2495/BEM380141.

[11] Igor Ostanin, Denis Zorin, Ivan Oseledets. Toward fast topological-shape optimization. arXiv preprint 1503.02383, 2015.

[12] M. V. Rakhuba, I. V. Oseledets. Fast multidimensional convolution in low-rank tensor formats via cross approximation. SIAM J. Sci. Comput., 37(2):A565–A582, 2015. doi:10.1137/140958529.

[13] M. V. Rakhuba, I. V. Oseledets. Grid-based electronic structure calculations: the tensor decomposition approach. arXiv preprint 1508.07632, 2015.

[14] Ben Usman, Ivan Oseledets. Tensor SimRank for heterogeneous information networks. arXiv preprint 1502.06818, 2015.

[15] Zhang Zheng, Xiu Yang, Ivan V. Oseledets, George Em Karniadakis, Luca Daniel. Enabling high- dimensional hierarchical uncertainty quantification by ANOVA and Tensor-Train decomposition. IEEE Trans. Comput-aided Des. Integr. Circuits Syst., 34(1):63–76, 2015. doi:10.1109/TCAD.2014.2369505.

[16] А. Ю. Михалев, И. В. Оселедец. Прямоугольные подматрицы максимального объема и их вычис- ление. ДАН, 462(1):19–20, 2015. doi:10.7868/S0869565215070087.

Научно-организационная работа

  • Руководитель гранта РНФ 14-11-00659

  • Организация 4-ой международной конференции по матричным методам в математике и прило- жениях (MMMA-2015, Сколтех, 23-28 августа 2015 года). Более 100 участников из 6 стран и 10 университетов.

  • Рецензирование в журналах Linear Algebra Appl., SIAM J. Sci. Comput., Numer. Linear Algebra Appl., SIAM J. Matrix Anal. Appl., J. Comp. Phys, SIAM J. Opt., SIAM J. Numer. Anal. Appl.,

  • Руководство аспиранткой 3 года ИВМ РАН Д. А. Сушниковой, аспиранта 1 года ИВМ РАН А. Новикова, аспирантами 2 года обучения ВМК МГУ М. А. Кузнецовым и П. В. Харюком, аспиранта 2 года МФТИ М. В. Рахубой

  • Экспертиза проектов РФФИ, Минобрнауки, РНФ.

MMMA-2015

Более 100 участников из 6 стран. 23-28 августа 2015 года.
(C. Schwab, J. White, Per-Gunnar Martinsson, A. Cichocki, В.П. Ильин, С.И. Кабанихин)

Computational Data-Intensive Science & Engineering at Skoltech

Центр вычислительных технологий Сколтеха http://crei.skoltech.ru/cdise/ продолжает развиваться: 7 групп, более 30 исследователей.

  • Единственные публикации в России на конференциям по машинному обучению и компьютерному зрению, анализу данных.
  • Взаимодействие с индустрией (Huawei, Intel, Infowatch, Русагро, КАМАЗ, Мортон).
  • Планируется расширение в 2016 году

Новая жизнь QTT-разложения в 2015 году

QTT-разложение (превращение вектора неизвестных в $2 \times 2 \times \ldots \times 2$ тензор, применение TT-разложения) может приводить к методам логарифмической сложности.

Возражения

  • Нет классов функций, для которых приближение существует
  • Не работает для областей, отличных от прямоугольной

Результаты Казеева и Шваба

Впервые доказана структура QTT-решения двумерного уравнения диффузии в криволинейной полигональной области $\Omega$ вида с оператором $$\mathcal A = -\nabla \cdot A \nabla + b^{\top} \nabla + c, $$

где $A(x)$, $b(x)$, $c(x)$ являются аналитическими в $\Omega$.

Тогда можно построить конечно-элементную дискретизацию так, что вектор коэффициентов решения приближается в QTT-формате.

Идея доказательства основана на взвешенных пространствах Соболева и структуре решения (точечные сингулярности).

Сложные области

(картинки сделаны Ларисой Маркеевой):

четырехугольник легко отобразить в квадрат простым отображением

Quadrilateral

Reference

Логически-прямоугольные сетки

(картинки сделаны Ларисой Маркеевой):

треугольник

Референс-область

Quads

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

Многомасштабные задачи

Технология распространяется на сильноосциллирующие коэффициенты! (доказательство меняется, но оно закончено).

Например, теплопроводность:

$$ \nabla \cdot (k \nabla u) = f,$$

где $k = k(\frac{x}{\delta},x)$, и $\delta$ - параметр масштаба.

В работе Оселедец, Казеев, Шваб, Рахуба мы полностью получили результат в 1д случае, обобщение на 2д в процессе.

Основа - теория осреднения Бахвалова/Панасенко, где показывается, что асимптотическое разложение принадлежит классу.

Численная иллюстрация

Простейшая задача: $$ (a u')' = 1, \quad u(1) = u(0) = 0, $$ $$a(x) = a_0(x) a_1\left(\frac{x}{\delta}\right),$$ where $a_0 = 1 + x$, $a_1 = 2/3 (1 + \cos^2(2 \pi \frac{x}{\delta})).$

Проблема

На очень мелких сетках не работают конечные разности/конечные элементы!

Для Пуассона: $$Er = \frac{\epsilon}{h^2} + h^2,$$

минимум при $h \sim {\epsilon^{1/4}},$ даже при $\epsilon = 10^{-16}, \quad h \geq 10^{-4}.$

Для многомашстабных задач нам нужны меньшие сетки, соответственно должны быть схемы дискретизации, которые работают при $n \geq 2^{60}.$

Идея у нас есть, и она прекрасно работает в 1д (на сетках вплоть до $2^{120}$) и в 2д на сетках вплоть до $2^{40} \times 2^{40},$

в чем-то похоже на метод интегральных тождеств Марчука.

Другие результаты

  • М.С. Лицарев: методы вычисления Феймановских интегралов и решение задач в неограниченных областях (J. Comp. Phys, NLA)

  • М.В. Рахуба: тензорный метод расчета электронной структуры (прошла ревизия в J. Comp. Phys., SISC)

  • В. Баранов: тензорный метод приближения поверхности потенциальной энергии (J. Chem. Phys.)

  • А. Фонарев, А. Михалев + команда из Яндекса: максвольный метод построения рекомендаций (подано на WWW)

  • Д. А. Колесников: новый рациональный Крыловский метод для решения уравнения Ляпунова (SIMAX)

  • C. Lubich, B. Vandereycken: Time integration of tensor trains (SINUM)

  • А. Михалев: Вложенный крестовый метод (ДАН, NLA)


In [2]:
from IPython.core.display import HTML
def css_styling():
    styles = open("custom.css", "r").read()
    return HTML(styles)
css_styling()


Out[2]: