PowerPoint プレゼンテーション - misojiro.t.u-tokyo.ac.jp

PowerPoint プレゼンテーション - misojiro.t.u-tokyo.ac.jp

Euclidean Buildings in Combinatorial Optimization Hiroshi Hirai Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo JST PRESTO [email protected] Buildings, Varieties, and Applications MPI Leipzig, Germany 12 November 2019 Contents Noncommutative Edmonds problem (nc-rank) optimization on spherical building Its weighted version (degree of determinant) optimization on Euclidean building Edmonds Problem

Edmonds 1967 Can we compute the rank of linear symbolic matrix in polynomial time ? : variables matrices over field matrix over ( 1 , 2 , , ) 3 Motivation Algebraic Interpretation of Bipartite Matching 1 1 1 2

3 4 12 32 = 23 24 41 1 2 2 3 3 ( 2 3

4 4 ) 4 =( , ; ) Lem. # maximum matching of det = min-max formula ( Knig-Egervry ) polynomial time algorithm

4 Linear matroid intersection ----- = =1 Linear matroid matching -----

= ( ) =1 min-max theorem + polynomial time algorithm Edmonds 1970, Lovsz 1981 Open Deterministic polynomial time rank computation of general Randomized polynomial time algorithm (Lovsz 1979) Connection to circuit complexity (Kabanets-Impagliazzo 2004) 5 Non-commutative Edmonds Problem Ivanyos-Qiao-Subrahmanyam 2015 ncCan we compute the rank of linear symbolic matrix in polynomial time ? : variables nc-rank rank

= holds for bipartite matching, linear matroid intersection matrices over field matrix over free ring > holds for non-bipartite matching, linear matroid matching,... Amitsur 1966 free skew field 6 What is free skew field ? skew field = ring s.t. nonzero element has inverse := all rational expressions of modulo

if p,q defined () It is much difficult to handle elements in than , but ... 7 nc-rank in P Garg-Gurvits-Oliveira-Wigderson 2015 (FOCS16): Gurvits operator scaling Ivanyos-Qiao-Subrahmanyam 2015 (ITCS17): arbitrary Wong sequence --- vector-space analogue of augmenting path Hamada-H. 2017: arbitrary but bit-size issue for Submodular optimization on the lattice of vector subspaces spherical building of type A + CAT(0)-space relaxation c.f. Submodular function on a lattice : 8

Formula of nc-rank (Fortin-Reutenauer 2004) = 0 + 1 1 + 2 2+ + generalizes min-max formula for bipartite matching, etc. - = s.t. , G L ( ) 0 Max . dim +dim

( ) This is optimization over spherical building ) s . t . ( , ( ) =0 , vector subspaces where reverse of c.f. spherical building of the order complex of Hamada-Hs approach to solve Each term & the objective function are submodular on ), orthoscheme complex (Brady-McCammond 12) ) is CAT(0) (Haettel-Kielak-Schwer 15) spherical building is CAT(1)

is geodesically convex (H.18) Minimize by splitting proximal point algorithm (Bak 14) Orthoscheme Complex (Brady-McCammond 2012) : graded poset := the geometric realization of the order complex of , where each simplex is metrized by orthoschemes 3 111 2 ( ,2) 110 1 0 000 100

Thm. [Haettel-Kielak-Schwer 15(13), Chalopin-Chepoi-H-Osajda 14] : modular lattice is CAT(0) Thm. [H.18] : modular lattice is submodular : is geodesically convex 11 Weighted Edmonds problem: Motivation capture weighted combinatorial optimization problems from (non-commutative) linear algebra Ex: Weighted bipartite matching 1 12 1 2 2 edge-weight 3 4

3 43 4 Max. s.t. perfect matching 12 Algebraic Interpretation of Weighted Matching 1 12 2 2 3 3

43 4 1 1 1 12 2 14 4 3 32 12 14 32 ()= 43 44

( 2 43 44 3 4 4

Lem. Max weight of perfect matching deg det =deg () () =max 13 ) Weighted Edmonds Problem Can we compute of in polynomial time ? : variable matrices over

matrix over Goal: develop a non-commutative version 14 Contribution of [H.18] Formulate weighted non-commutative Edmonds problem by using Dieudonn determinant Det. Establish a formula for deg Det L-convex function on Euclidean building Algorithm: minimization of the L-convex func. nc-rank computation, max degree Special case of deg det = deg Det: weighted linear matroid intersection, mixed matrix 15 How to see Matrix over (skew) polynomial ring Ore ring ---- 0

Matrix over Ore quotient ring 0 Degree: 16 How to define determinant of matrices over skew field nonsingular over (Our case:) Bruhat decomposition: LU-decomposition of matrices over skew field uni-lower-triangular uni-upper-triangular = diagonal permutation unique Dieudonn determinant

Abelianization of Det sgn ( ) 11 22 mod[ , ] commutator group Lem. 17 Weighted Non-commutative Edmonds Problem Can we compute of in polynomial time ? : variables matrices over matrix over Rem. is well-defined since is zero on commutators deg ( 1 1 =0 18 Formula for deg Det ()= 0 ()+ 1() 1++ () Thm. [H. 18]

deg Det = Min . deg det deg det Q s.t. , G L ( ( )) This is optimization over Euclidean building (Proof of ; Murota 95 for deg det) deg ( ) 0( , )deg ( ) 0 ( ) deg Det 0deg(Det Det Det) 0 deg Det + deg Det +deg Det 0 deg d et deg d et 19 deg Det =Min . deg det deg det Q

s.t. , G L ( ( )) Min . deg deg s.t. lattices in where ( ) { / ( )|deg / 0 } full-rank free -submodule in Lattice Euclidean building for = simplicial complex of lattices / The lattice of all lattices in is a uniform modular lattice Def. [H.17] A uniform modular lattice := a modular lattice s.t. is an order-preserving bijection ( )+

Digression: Lattice-theoretic characterization of Euclidean buildings & tropical linear spaces Thm. [H.17] Uniform modular lattices Euclidean buildings of type A Fact: Complemented modular lattices Spherical buildings of type A Tits,Birkhoff Thm. [H.18] Uniform semimodular lattices integer-valued valuated matroids Fact: Geometric lattices simple matroids deg Det = Min . deg deg s.t. ( , ) the lattice of lattices, inclusion order its reverse Lem. [H.18] The objective function is L-convex on uniform modular lattice

Def. [H. 17] is L-convex: Original def. [Murota] : , Algorithm for deg Det ( minimization of L-convex func.) Input: 0: Choose s.t. 1: 2: Choose s.t. with maximum 0

Optimization over the link at (= spherical building) = nc-rank computation nc-nonsingular 3: If optimal; 4: If , ( ,

) ( 1 moves on the 1-skeleton of the Euclidean building ) ; go to 1 24 Remarks Essence in combinatorial relaxation method (Murota 90) for deg det, partial optimization over apartments () Bipartite matching Hungarian method Linear matroid intersection Franks weight splitting algorithm (Furue-H 2019)

Computation of deg Det for skew polynomial matrix (Oki 2019) 25 Summary Appearances of buildings in combinatorial optimization and its algebraic generalization Submodular/discrete convex optimization on buildings Lattice-theoretic approach to buildings. Appearances of buildings (type C) in multicommodity flow problems [H. 18, Ikeda-H. 19] 26 References M.Hamada and H.Hirai: Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix, arXiv H. Hirai: Uniform modular lattices and affine buildings, Adv. in Geometry H. Hirai: Uniform semimodular lattices and valuated matroids, JCTA H. Hirai: Computing the degree of determinants via discrete convex optimization over Euclidean buildings, SIAGA Papers & slides are available at http://www.misojiro.t.u-tokyo.ac.jp/~hirai/

Thank you for your attention ! 27

Recently Viewed Presentations

  • AP EURO Unit #1 - Renaissance and Reformation Lesson #2 - The ...

    AP EURO Unit #1 - Renaissance and Reformation Lesson #2 - The ...

    From its first use, there has been debate as to whether the guillotine always provided a swift death as Guillotin had hoped. With previous methods of execution intended to be painful, there was little concern about the suffering inflicted.
  • Fejlett Programozási Technikák 2.

    Fejlett Programozási Technikák 2.

    A fejlesztő által implementálható. * Hibernate- felépítés 3 rész: Java osztály Relációs adatbázisbeli táblák Leíró (descriptor) Definiálja a konverziós szabályokat A nyelvezete inkább java-centrikus 2 fajtája van: Xml file (*.xml.hbm kiterjesztés) Annotáció Sokan kézzel szerkesztik pedig XDoclet, Middlegen, AndroMDA.
  • Unit D - Living Systems Chapter 1 The biosphere of Life

    Unit D - Living Systems Chapter 1 The biosphere of Life

    Unit D - Living Systems Chapter 1 The biosphere of Life Section 1.4 Conducting a field study Summary of Terms Field Study Purpose of a Field Study Purpose: to examine abiotic and biotic factors to collect qualitative and quantitative data...
  • Numerical Expressions - Cengage

    Numerical Expressions - Cengage

    A numerical expression is an expression formed from numbers by adding, subtracting, multiplying, dividing, taking powers, taking roots, and using grouping symbols: ( ), [ ], | |, { }, and the horizontal bar as in fractions and radicals. grouping...
  • EUROPEAN IMMUNOGENETICS AND HISTOCOMPATIBILITY CONFERENCE (EFI) May 15-18,

    EUROPEAN IMMUNOGENETICS AND HISTOCOMPATIBILITY CONFERENCE (EFI) May 15-18,

    european immunogenetics and histocompatibility conference (efi) may 15-18, 2010, florence, italy [email protected] association of hla-c*06 with susceptibility to psoriatic arthritis and its clinical phenotype in romania
  • Notebook Instructions

    Notebook Instructions

    8. Foldable - Power Distribution & Relationship between branches. Power Distribution. Unitary: All the power that the government has is held by one central agency. They may create local units, but the central agency is in control. Example: Great Britain....
  • Social Stratification and Class - Windham High School

    Social Stratification and Class - Windham High School

    Social Stratification and Class Social Stratification A structural ranking of entire groups of people in which some have more power, prestige, and wealth than others. Class The group of people who share economic and social position in society. People in...
  • Aimsweb 1.0 vs. aimsweb 2.0

    Aimsweb 1.0 vs. aimsweb 2.0

    View class/student PM data. Browser Based Scoring. Print materials/ manual data entry. ... and Fall to Spring and the pattern of growth observed within each (i.e. fall to winter- faster slopes, winter to spring - slower slopes, fall to spring...