Лекция. Матрицы, тензоры, вычисления (Тыртышников) (Электронные лекции)

КАК РЕШАТЬ ЗАДАЧИ,КОТОРЫЕ НЕ РЕШАЮТСЯНА СУПЕРКОМПЬЮТЕРАХ?Евгений Евгеньевич ТыртышниковИнститут вычислительной математики Российской академии наукМосковский государственный университет им. М.В.ЛомоносоваМосковский физико-технический институтeugene.tyrtyshnikov@gmail.comМосква, 22 ноября 2016Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯРАЗМЕРНОСТЬ – ЭТО ПРОКЛЯТИЕИЛИ БЛАГО?Как задать элементы d-мерной матрицы(тензора) A = [a(i1 , . . . , id )] размера n × . . . × n?IЕсли d = 300 и n = 2, точисло этих элементов 2300 1083больше числа атомов во вселенной!Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯСПЕЦИАЛЬНЫЕ ПРЕДСТАВЛЕНИЯТЕНЗОРОВЧистый тензор (тензор ранга 1, скелетон):a(i , j , k) = u(i )v (j )w (k).Разделение переменных.Каноническое разложение – это сумма чистых тензоров:a(i , j , k) =rXu(i , α)v (j , α)w (k, α)α=1Определяется тремя матрицами:U = [u(:, 1), ..., u(:, r )],V = [v (:, 1), ..., v (:, r )], W = [w (:, 1), ..., w (:, r )].Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯКАНОНИЧЕСКОЕ РАЗЛОЖЕНИЕIПрименяется как модель для данных.

Флюоресцентнаяспектрометрия: n1 смесей, найти число веществ и ихконцентрации. Данные измерений = массив размеровn1 × n2 × n3 , n2 и n3 – для частот излучателей и приемников.Каноническое разложение дает число веществ и концентрации.IПрименяется в теории сложности – основное средство привычислении билинейных форм (Strassen, Pan, Bini и др.).IМного трудных проблем - теоретических и вычислительных!тензоры ранга < rЕвгений Евгеньевич Тыртышников→тензор ранга rМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯУМНОЖЕНИЕ 2 × 2-МАТРИЦПравило “строка на столбец” дает 8 умножений:a11 a12 b11 b12a11 b11 + a12 b21 a11 b12 + a12 b22=a21 a22 b21 b22a21 b11 + a22 b21 a21 b12 + a22 b22Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯАЛГОРИТМ ШТРАССЕНА ДЛЯ БЫСТРОГОУМНОЖЕНИЯ МАТРИЦВ 1969 Штрассен (Strassen) открыл алгоритм, в котором всего7 умножений. При умножении блочных 2 × 2-матриц алгоритмШтрассена содержит 7 умножений блоков:α1 = (a11 + a22 )(b11 + b22 )α2 = (a21 + a22 )b11α3 = a11 (b12 − b22 )α4 = a22 (b21 − b11 )α5 = (a11 + a12 )b22α6 = (a21 − a11 )(b11 + b12 )c11 = α1 + α4 − α5 + α7c12 = α3 + α5c21 = α2 + α4c22 = α1 + α3 − α2 + α6α7 = (a12 − a22 )(b21 + b22 )Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯКАНОНИЧЕСКОЕ ТЕНЗОРНОЕРАЗЛОЖЕНИЕ ДЛЯ ПОИСКА БЫСТРОГОАЛГОРИТМА УМНОЖЕНИЯ n × n МАТРИЦ c1 c2a1 a2 b1 b2=c3 c4a3 a4 b3 b4hijk =RX2ck =2n XnXhijk ai bji=1 j=1ui α vj α wkαα=1⇒ ck =RXα=1wkα n2n2XXuiα ai  vjα bj i=1j=1Теперь лишь R умножений блоков!Если n = 2, то R = 7 (Strassen, 1969).Рекурсия⇒O(nlog2 7 ) умножений для произвольного n.Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯРЕКУРСИЯ ДЛЯ БЫСТРОГО УМНОЖЕНИЯМАТРИЦИспользуя рекурсию, можно перемножить две матрицыпорядка n = 2d с затратой не более 7d = nlog2 7 и 7nlog2 7сложений-вычитаний.n = 2dn/2n/2n/2Евгений Евгеньевич Тыртышниковn/2n/2n/2n/2МАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯТЕНЗОРЫ ПОВСЮДУЕвгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯУВИДЕТЬ В ТЕНЗОРАХ МАТРИЦЫa(i1 ; i2 , i3 ) =Xa1 (α1 , i2 ; i3 ) =Xa(i1 , i2 , i3 ) =Xg1 (i1 , α1 )a1 (α1 ; i2 , i3 )g2 (α1 , i2 ; α2 )g3 (α2 ; i3 )g1 (i1 , α1 )g2 (α1 , i2 , α2 )g3 (α2 , i3 )Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯTЕНЗОРНЫЙ ПОЕЗД =MATRIX PRODUCT STATE=ЛИНЕЙНАЯ ТЕНЗОРНАЯ СЕТЬa(i1 , i2 , i3 , i4 , i5 ) =Xg1 (i1 , α1 )g2 (α1 , i2 , α2 )g3 (α2 , i3 , α3 )g4 (α3 , i4 , α4 )g5 (α4 , i3 )(i )(i )(i )(i )(i )= A1 1 A2 2 A3 3 A4 4 A5 5|{z} |{z} |{z} |{z} |{z}1×r1 r1 ×r2 r2 ×r3 r3 ×r4 r4 ×1i1α1i2α2Евгений Евгеньевич Тыртышниковi3α3i4α4МАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯi5СЛОЖЕНИЕ ТЕНЗОРОВ(i )(i )(i )a(i1 , i2 , i3 ) = A1 1 A2 2 A3 3 ,|{z} |{z} |{z}1×r1 r1 ×r2 r3 ×1i1α1i2α2i3(i )(i )1×s1 s1 ×s2 s3 ×1i1β1"i A(i2 )h2(a + b)(i1 , i2 , i3 ) = A1(i1 ) B1(i1 )Евгений Евгеньевич Тыртышников(i )b(i1 , i2 , i3 ) = B1 1 B2 2 B3 3|{z} |{z} |{z}β2i2i3#"(i )B2 2(i )A3 3(i )B3 3МАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯ#ТЕНЗОРНЫЙ ПОЕЗДспециальное представление d-мерной матрицыa(i1 .

. . id ) =Xg1 (i1 α1 )g2 (α1 i2 α2 ) . . .. . . gd−1 (αd−2 id−1 αd−1 )gd (αd−1 id )d-мерная матрица A представляется черезтрехмерные матрицы gk (αk−1 ik αk ) размераrk−1 × n × rk . Если rk 6 r , то число параметровтензорного поезда 6 dnr 2 nd .Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯКОГДА ТЕНЗОРНЫЙ ПОЕЗДРЕАЛЬНО ПОМОГАЕТ?Ak = [a(i1 .

. . ik ; ik+1 . . . id )] =iuk (i1 . . . ik ; αk ) vk (αk ; ik+1 . . . id ) = Uk Vk>Xuk (i1 . . . ik αk ) =g1 (i1 α1 ) . . . gk (αk−1 ik αk )Xvk (αk ik+1 . . . id ) =gk+1 (αk ik+1 αk+1 ) . . . gd (αk−1 id )hXНужно, чтобы все матрицы Ak были близки кматрицам малого ранга.Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯТЕНЗОРНЫЙ ПОЕЗД ДЛЯ d-МЕРНОЙМАТРИЦЫ МОЖНО ПОСТРОИТЬПО "МАЛЫМ КРЕСТАМ" В МАТРИЦАХ AkA(i1 . . . id ) =dYA(J6k−1 , ik , J>k ) [A(J6k , J>k )]−1k=1I.Oseledets, E.Tyrtyshnikov‘2009Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯИСТОРИЯ КРЕСТОВОЙ АППРОКСИМАЦИИ1985 Knuth:Semi-optimal bases for linear dependencies1995 Tyr., Goreinov, Zamarashkin:2000 Tyr.:A = CGR pseudoskeletonincomplete cross approximation with ALS maxvol2000 Bebendorf:ACA = Gaussian elimination2001 Tyr., Goreinov: maximum volume principle,quasioptimality k cross kC ≤ (r + 1)k best k22006 Mahoney et al:randomized CUR algorithm2008 Oseledets, Savostyanov, Tyr.:2009 Oseledets, Tyr.:Cross3DTT–Cross2010 J.Schneider: function-related quasioptimalityk cross kC ≤ (r + 1)2 k best kC2011 Tyr., Goreinov: quasioptimalityk cross kC ≤ (r + 1)2 k best kC2013 Ballani, Grasedyck, Kluge:HT–Cross2013 Townsend, Trefethen –- Chebfun2Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯСТРОЧНО-СТОЛБЦЕВАЯ ИНТЕРПОЛЯЦИЯМАТРИЦA11 A12A=A21 A22A11 is r × rA интерполируется по первым r строкам истолбцам: AAr = 11 A−1AAA21 11 11 12Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯОШИБКА ИНТЕРПОЛЯЦИИ AA11 A12− 11 A−1AA1112A21 11A21 A2200=0 A22 − A21 A−111 A12Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯПРИНЦИП МАКСИМАЛЬНОГО ОБЪЕМАТЕОРЕМА (Горейнов, Тыртышников‘2000)ПустьA11 A12, A11 is r × rA=A21 A22имеет максмимальный объем (определитель помодулю) среди всех r × r блоков в A, и пусть AAr = 11 A−1AA.1112A21 11Тогда||A − Ar ||C 6 (r + 1) min ||A − B||2 .rank B6r|{z}=σr +1 (A)Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯНОВОЕ ПОНЯТИЕ – РЕДУЦИРОВАННЫЙОБЪЕМVr (A) :=rYσi (A)i=1ТЕОРЕМА (А.И.Осинский – Н.Л.Замарашкин)LetAA12A = 11∈ CM×N ,A21 A22где A11 ∈ Cm×n is имеет максимальный r -редуцированныйобъем среди всех m × n подматриц и rank A11 > r .

Тогдаrrrr†||A − CA11 R||C 6 1 +σr +1 ,1+m−r +1n−r +1 AC = 11 , R = A11 A12 .A21Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯСЛЕДСТВИЕ ТЕОРЕМЫ ОРЕДУЦИРОВАННОМ ОБЪЕМЕВзяв крест, в котором на пересечении строк истолюцов находится подматрица размера(2r − 1) × (2r − 1), мы можем гарантироватьоценку||A − CA†11 R||C 6 2σr +1 (A).Достаточно выбрать подматрицу A11 смаксимальным r -редуцированным объемом.A.Osinsky, N.Zamarashlin, Pseudo-skeleton approximations withbetter accuracy estimates, submitted to LAA, 2016.Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯКВАЗИОПТИМАЛЬНОСТЬ ТЕЗОРНОГОПОЕЗДА, ПОСТРОЕННОГО ПО КРЕСТАММАКСИМАЛЬНОГО ОБЪЕМАe 1 . .

. id ) =A(idXYA(J6k−1 , ik , J>k ) [A(J6k , J>k )]†τkk=1THEOREM.e C 6 c(r ) ·||A − A||||F ||C| {z }BEST APPROXIMATION ERROR(4r )dlog2 de − 1c(r ) =(r + 1)24r − 1Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯТЕНЗОРИЗАЦИЯ ВЕКТОРОВ И МАТРИЦЛюбой вектор размера N = n1 . . . nd можно рассматривать какd-тензор, а любую N × N-матрицуa(i, j) = a(i1 . . . id , j1 . . .

jd )можно рассматривать как 2d-тензор или, а еще лучше какd-tensor размера n12 × . . . × nd2 , например такой:a(i1 j1 , . . . , id jd )Тензоризация плюс тензорный поезд(TT) позволяют радикально уменьшитьчисло параметров представления!Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯБЫСТРОЕ СУММИРОВАНИЕ ЭЛЕМЕНТОВАСТРОНОМИЧЕСКИ БОЛЬШОГО ВЕКТОРАNXa(i) =?N = 1083i=1Евгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯБЫСТРОЕ СУММИРОВАНИЕ ЭЛЕМЕНТОВАСТРОНОМИЧЕСКИ БОЛЬШОГО ВЕКТОРАd = 83i = i1 i2 . . .

idXa(i) = a(i1 , . . . , id ) =g1 (i1 , α1 )g2 (α1 , i2 , α2 ) . . . gd (αd−1 , id )α1 ,...,αd−1Xa(i1 , . . . , id ) =i1 ,...,idXĝ1 (α1 )ĝ2 (α1 , α2 ) . . . ĝd (αd−1 )α1 ,...,αd−1ĝk =XgkikЕвгений Евгеньевич ТыртышниковМАТРИЦЫ, ТЕНЗОРЫ, ВЫЧИСЛЕНИЯTT-ИНТЕГРИРОВАНИЕВычисляется d-мерный интегралZI (d) = sin(x1 + x2 + .