2013 2 18 1,2 1. 2. JST, ERATO,
2/ 36 2012 2012 ERATO
Given n n A 1,..., A N Find P s.t. P A 1 P,..., P A N P A 1 A 2 A N simultaneously P A 1 P P A 2 P P A N P 3/ 36
4/ 36
5/ 36
6/ 36 [Wigner 1931 ]. [de Klerk-Dobre 2011] etc [Arima-Kim-Kojima 2012] etc [Burgdorf-Klep-Povh 2011] [Aiura-Kakimura-Murota 2011] [Gutch-Krumsiek-Theis 2011] [Irving-Sorrentino 2012].
http://www.nasa.gov/centers/ames/multimedia/images/2006/crystal.html 7/ 36 [Wigner 1931 ] Hx = ϵx H = α 1 H 1 + + α N H N H 1,..., H N
http://www.dreamstime.com/stock-image-network-infection-image11173181 8/ 36 [Irving-Sorrentino 2012] x(t) = A 1 x(t 1) + + A N x(t N) x(t) t A k k A 1 A 2.
[Gatermann-Parrilo 2004], [Murota-Kanno-Kojima-Kojima 2010],... minimize C, X subject to A i, X = b i (i = 1,..., N) X O 7 days 7 mins [de Klerk-Dobre-Pasechnik 2009] 9/ 36
[Jutten-Herault 1985], [Cardoso-Soulomiac 1993],... Y 1 Y 2 Y l Given: Find: n X Y 1,..., Y l W P C P = X = W Y http://www.kindredcocktails.com/ 10/ 36
11/ 36 [Wigner 1931 ]. [de Klerk-Dobre 2011] etc [Arima-Kim-Kojima 2012] etc [Burgdorf-Klep-Povh 2011] [Aiura-Kakimura-Murota 2011] [Gutch-Krumsiek-Theis 2011] [Irving-Sorrentino 2012].
12/ 36
13/ 36 SBD = SBD =
old new numerical linear algebra Jacobi-like [Bunse-Gerstner, Byers, Mehrmann 1990] JADE [Cardoso-Souloumiacc 1993] [Theis 2007] abstract algebra one-by-one [folklore -1820] The recipe [Schur 1905] MKKKM [Murota-Kanno-Kojima-Kojima MM [Maehara-Murota 2012] 14/ 36 2010]
old new numerical linear algebra Jacobi-like [Bunse-Gerstner, Byers, Mehrmann 1990] JADE [Cardoso-Souloumiacc 1993] [Theis 2007] abstract algebra one-by-one [folklore -1820] The recipe [Schur 1905] MKKKM [Murota-Kanno-Kojima-Kojima MM [Maehara-Murota 2012] 15/ 36 2010]
16/ 36 one-by-one method [ ]. A, X. wlog. X = diag(x 1,..., x n ), AX XA = [(x j x i )a ij ] = O x x y X A X A
17/ 36 Jacobi-like method [ ] (Bunse-Gerstner, Byers, Mehrmann 1990) one-by-one minimize [ off(p AP ) + off(p BP ) ] Givens 2 2 Jacobi
18/ 36 JADE [ ] (Cardoso, Souloumiac 1993) minimize [ off(p A 1 P ) + + off(p A N P ) ] Jacobi-like method 1 = by Cardoso
JADE [ ( )] (Theis 2007) minimize [ off(p A 1 P ) + + off(p A N P ) ] = [Maehara Gutch 2010] 19/ 36
old new numerical linear algebra Jacobi-like [Bunse-Gerstner, Byers, Mehrmann 1990] JADE [Cardoso-Souloumiacc 1993] [Theis 2007] abstract algebra one-by-one [folklore -1820] Schur lemma [Schur 1905] MKKKM [Murota-Kanno-Kojima-Kojima MM [Maehara-Murota 2012] 20/ 36 2010]
A 1,..., A N G Q A j Q = A j (Q G) G Schur - G A j - A j G G Schur lemma: MKKKM, MM: one-by-one 21/ 36
22/ 36 Schur lemma (Schur 1905) Q A j Q = A j (Q G) 1. A 1,..., A N G 2. G 3. A 1,..., A N 1930 Wigner cf. Heisenberg 1925
[Murota-Kanno-Kojima-Kojima 2010] 23/ 36 Q. 3V 3V (3i + j, 3k + l) k l i j A.
24/ 36 MKKKM [Murota-Kanno-Kojima-Kojima 2010, Maehara-Murota 2011] 1. A 1,..., A N 2. 3. cf: one-by-one 1. 2. 3.
25/ 36 MKKKM [Murota-Kanno-Kojima-Kojima 2010, Maehara-Murota 2011] 1. 2. 3. cf: one-by-one 1. 2. 3.
26/ 36 MKKKM A 1,..., A N Artin-Wedderburn T := A 1,..., A N (M n1 I µ1 ) (M nl I µl ) T M n I µ one-by-one
MM [Maehara-Murota 2012] one-by-one X = diag(x 1,..., x n ), AX XA = [(x j x i )a ij ] = O x x X y A 1,..., A N X A 1,..., A N A 27/ 36
T := {X A i X X i A = O (i = 1,..., N)} 28/ 36 MM [Maehara-Murota 2012] 1. A i X XA i = O (i = 1,..., N) 2. X Artin-Wedderburn
29/ 36 MM [Maehara-Murota 2012] 1. A i X XA i ϵ (i = 1,..., N) 2. X ϵ ϵ
http://www.misojiro.t.u-tokyo.ac.jp / maehara/commdec/ 30/ 36
31/ 36 A 1 A 2 A N simultaneously P A 1 P P A 2 P P A N P state of the art: [MM 2012]
32/ 36
33/ 36 preconditioning
A i X XA i = O (i = 1,..., N) X λ i λ j [Dyson index] n n exp( n λ 2 i /4) i<j λ i λ j i.e., λ i λ j cf. λ i λ j 2 34/ 36
35/ 36 T T = T 1 T l X T with n 2 k Dyson index ToDo:
A 1 A 2 A N simultaneously P A 1 P P A 2 P P A N P state of the art: [MM 2012] ( ) 36/ 36