Computing Determinant Degree via Discrete Convex Optimization

computing degree of determinant via discrete n.w
1 / 34
Embed
Share

Explore the intersection of non-commutative combinatorial optimization and linear algebra through the lens of Edmonds' problem. Delve into the algebraic interpretation of bipartite matching and the concept of free skew fields. Understand the challenges and complexities of handling elements in these fields while aiming for efficient rank computation. Discover the connection to circuit complexity and explore polynomial time algorithms to compute ranks.

  • Determinant Degree
  • Convex Optimization
  • Linear Algebra
  • Combinatorial Optimization
  • Non-Commutative
rayaanacharya
kynsiebr Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Computing degree of determinant via discrete convex optimization over Euclidean building Hiroshi Hirai University of Tokyo hirai@mist.i.u-tokyo.ac.jp Workshop: Recent Development in Optimization 2 GRIPS, Roppongi, Tokyo, 2018/10/13 1

  2. Contents non-commutative combinatorial optimization v.s. linear algebra Submodularity + Discrete convexity 1. Background: Edmonds problem and recent development 2. Motivation + contribution of this work 2

  3. Edmonds Problem Edmonds 1967 Can we compute the rank of linear symbolic matrix ? = ?0+ ?1?1+ ?2?2+ + ???? in polynomial time ? ?1,?2, ,??: variables ?0,?1, ,??: ? ? matrices over field ? ?: matrix over ?[?1,?2, ,??] ?(?1,?2, ,??) 3

  4. Motivation Algebraic Interpretation of Bipartite Matching 1 2 3 4 1 1 ?12 1 ?23 ?24 ?21 2 2 2 ? = ?32 3 3 3 ?41 4 4 4 ? = (?,?;?) = ?? ??????? # maximum matching of ? = rank ? det ? = ??? ? ?? ? min-max formula ( K nig-Egerv ry ) polynomial time algorithm 4

  5. ? ? ?? Linear matroid intersection ----- ? = ???? ?=1 ? ? ???? ?) ?? Linear matroid matching ----- ? = (???? ?=1 min-max theorem + polynomial time algorithm Edmonds 1970, Lov sz 1981 Open Deterministic polynomial time rank computation ? of general ? = ?0+ ?=1 ???? Randomized polynomial time algorithm (Lov sz 1979) Connection to circuit complexity (Kabanets-Impagliazzo 2004) 5

  6. Non-commutative Edmonds Problem nc- Ivanyos-Qiao-Subrahmanyam 2015 Can we compute the rank of linear symbolic matrix ? = ?0+ ?1?1+ ?2?2+ + ???? in polynomial time ? ???? ???? ?1,?2, ,??: variables ?0,?1, ,??: matrices over field ? nc-rank ?: free ring ? ?1,?2, ,?? rank Amitsur 1966 free skew field ?( ?1,?2, ,??) 6

  7. What is free skew field ?( ?1,?2,,??)? skew field = ring s.t. nonzero element has inverse ?( ?1,?2, ,??) := all rational expressions of +, , , ,??,? ? modulo ~ 1+ ?3 3 1 ? = ?2?1?2 ? ~ ? ? ?1,?2, ,?? = ? ?1,?2, ,?? ( ?, ?? Mat? ?(?) ) It is much difficult to handle elements in ? ?1,?2, ,?? than ?(?1,?2, ,??), but ... 7

  8. nc-rank in P !! Garg-Gurvits-Oliveira-Wigderson 2015 (FOCS 16): ? = Ivanyos-Qiao-Subrahmanyam 2015 (ITCS 17): ?, arbitrary Min-max theorem: Fortin-Reutenauer 2004 treatable in ? ! nc-rank ? = 2? Max. ? + ? s.t. ???? = ( ?) rank = nc-rank ? 0 ? bipartite matching linear matroid intersection rank < nc-rank min-max theorem ?,?: nonsingular over ? non-bipartite matching linear matroid matching 8

  9. Knig-Egervry from Fortin-Reutenauer ?:bipartite graph 2? Max. ? + ? ? s.t. ? ? = ( ? = ?? ?) ? 0 ? 1 ? ?,?: nonsingular over ? permutation matrices = 2? #maximum stable set = # minimun vertex cover 9

  10. Algorithms for nc-rank Garg-Gurvits-Oliveira-Wigderson 2015 (FOCS 16): Gurvits operator scaling Ivanyos-Qiao-Subrahmanyam 2015 (ITCS 17): Wong sequence --- vector-space analogue of augmenting path Hamada-Hirai 2017: Submodularity + convex optimization on CAT(0)-space They are beyond Euclidean convex optimization 10

  11. Submodularity View Hamada-Hirai 2017 Max. ? + ? s.t. ???? = ( ?) ? 0 ? ?,?: nonsingular Submodular optimization on the modular lattice of vector subspaces Max. dim ? + dim ? = s.t. ???,? = 0 ? ?,? ?? vector subspaces where???,? ????? 11

  12. Motivation of this work ~capture weighted combinatorial optimization problems from such non-commutative linear algebra Ex: Weighted bipartite matching ?12 1 1 2 2 ??? +: edge-weight 3 3 ?43 4 4 Max. ? ? ?? ???? s.t. ?: perfect matching 12

  13. Algebraic Interpretation of Weighted Matching ?12 4 1 2 3 1 1 ??14?14 ??12?12 1 2 2 ??21?21 ??23?23 2 ?(?) = ??32?32 3 3 3 ??43?43 ??44?44 ??41?41 4 ?43 4 4 ?? ??????????? = Max. weight of perfect matching = deg det ?(?) ??(?) deg det ? = deg ???= max ? ?(?) ? ?? ? 13

  14. Weighted Edmonds Problem Can we compute deg det of ?(?) = ?0(?) + ?1(?)?1+ + ??(?)?? in polynomial time ? ?1,?2, ,??: variable ?0(?),?1(?), ,??(?): matrices over ?[?] ?: matrix over ?[?1,?2, ,??,?] Goal: develop a non-commutative version 14

  15. Contribution Formulate weighted non-commutative Edmonds problem by using Dieudonn determinant Det. Establish a min-max theorem for deg Det with view from Discrete Convex Analysis beyond ? L-convex function on Euclidean building Algorithm: SDA ?(??) nc-rank computation, ?: max degree Special case of deg det = deg Det: weighted linear matroid intersection, mixed matrix 15

  16. How to see ?(?) = ?0(?) + ?1(?)?1+ + ??(?)?? Matrix over (skew) polynomial ring ? ? [t] Ore ring ---- ?,?, ?,?:?? = ?? 0 Matrix over Ore quotient ring ? ? (t) ? ? ?,?, ?? = ? ?,?? = ? ? 0 ? ? = Degree: deg ? ? deg ? deg ? 16

  17. How to define determinant of matrices over skew field ?: nonsingular over ? (Our case: ? = ? ? (t)) Bruhat decomposition: LU-decomposition of matrices over skew field uni-upper-triangular uni-lower-triangular ? = ? ? ? ? diagonal permutation unique Dieudonn determinant Abelization ? /[? ,? ] of ? Det ? sgn ? ?11?22 ??? mod [? ,? ] commutator group Lem: Det ?? =Det ? Det ? 17

  18. Weighted Non-commutative Edmonds Problem Can we compute deg Det of ?(?) = ?0(?) + ?1(?)?1+ + ??(?)?? in polynomial time ? ?1,?2, ,??: variables ???? ???? ?0? ,?1? , ,??? : matrices over ?[?] ?: matrix over ?( ?1,?2, ,??)(?) deg Det is well-defined since deg is zero on commutators deg (??? 1? 1) = 0 18

  19. Min-Max Theorem treatable in ?(?) ? = ?0+ ?1?1+ + ???? deg Det ? = Min. deg det ? deg det Q s.t. deg ?????? 0 ( ?, ??) ?,?: nonsingular over ?(?) 19

  20. Weak Duality deg ?????? 0 ( ?, ??) deg ????? 0 ( ??) deg Det ??? 0 deg (Det ? Det ? Det ?) 0 deg Det ? + deg Det ? + deg Det ? 0 deg Det ? deg Det ? deg Det ? = = deg det ? deg det ? 20

  21. Strong Duality + Algorithm (SDA) ??? = ???0+ ?(? 1) = ??0?0+ ??1?0?1+ + ????0?? over ?( ? ) over ? ???0: nonsingular on ?( ? ) deg Det ??? = 0 deg Det ? = deg det ? deg det ? ?,?: optimal ???0: singular on ?( ? ) We can augment ?,? ? ,? s.t. deg det ? + deg det ? > deg det ? + deg det ? 21

  22. ???0: singular on ?( ? ) nc-rank of ???0< ? ? 1? 1 ?,?: nonsingular over ? ????? =+?(? 1) 0 ? ? ? ? ? ? + ? > ? ? ? ? ??? ? ? ? deg ? ?? ????? ?? 0 ? 1?? ? ? ? deg det ? + deg det ? = (? + ? ?) + deg det ? + deg det ? > 0 ? ? ? ? ? ? , ? > 0 Long-step: use , ???? ? ??? ? 22

  23. Remarks Essence of this argument / algorithm is in combinatorial relaxation method (Murota 1990,1995) developed for computing deg det. short-step Naive iteration bound for initial ?,? = (? ??,?) ?? (?: maximum degree) We can improve this bound to ? (deg Det ? max deg (? 1-minor)) = max deg min deg of Smith-McMillan form of ? from view of discrete convex analysis beyond ? 23

  24. Special case of deg det = deg Det ? = ?0+ ?1?1+ ?2?2+ + ???? Thm [Ivanyos et al 2010] rank ??= 1 ( ? 1) rank ? = nc-rank A. bipartite matching --- ?? ??????? linear matroid intersection --- ????? mixed matrix (Murota-Iri 1985)--- ?0+ ?? ??????? ??? ?(?) = ?0(?) + ?1(?)?1+ + ??(?)?? Thm [H. 18] rank ??(?) = 1 ( ? 1) deg det ? = deg Det A. mixed polynomial matrix weighted ver. 24

  25. bipartite matching ????????????? SDA + long-step Hungarian Interpretation via Euclidean building ??? Linear matroid ???????? SDA + long-step Greedy ??? Linear matroid intersection ???????? ? SDA + long-step Lawler s primal dual Lawler 1975 Mixed polynomial matrix ?0? + ?? ??????????? SDA + optimization over ?-sublattice (apartment) combinatorial relaxation algo. Iwata-Takamatsu 2013 Iwata-Oki-Takamatsu 2017 dual of bipartite matching 25

  26. View from Discrete Convex Analysis beyond ? Dual of deg Det Dual of nc-rank Max. ? + ? Max. deg det ? + deg det Q s.t. ???? = ( ?) s.t. deg ?????? 0 ( ?, ??) 0 ? ? ?,?: nonsingular over ?(?) ?,?: nonsingular over ? = L-convex optimization on the modular lattice of free modules over PID ? ? Max. dim ? + dim ? s.t. ???,? = 0 ? ?,? ??vector subspaces Submodular optimization on the modular lattice of vector subspaces where???,? ????? 26

  27. Max. deg det ? + deg det Q s.t. deg ?????? 0 ( ?, ??) ?,?: nonsingular over ?(?) ? ? ? ? ? ? deg ? ? 0} ?? ? full-rank free ? ? -submodule of ? ?? Max. deg ? + deg ? = s.t. deg ???,? [ ,0] ( ?) ?,?: full-rank free ? ? -submodules of ? ?? where???,? ????? 27

  28. ? ?? { full-rank free ? ?-submodules of ? ?? } Euclidean building of SL(? ??) Lem: ? ?? is a uniform modular lattice, i.e., ? ?+ ? ? covers ?} is order-preserving bijection Rem [H. 17] : uniform modular lattice Euclidean building of type A 28

  29. Uniform modular lattice [H.17] ? ?+ ? ? covers ?} is order-preserving bijection Ex: ?, = min, = max, ?+= ? + ? Ex: Tree ?+ ? Rem: ? ?2 infinite regular tree 29

  30. L-convexity on uniform modular lattice Def [Murota 96] ?: ? { } is L-convex: ? ? + ? ? ? ? ? + ? ? ? ?,? ? + ? = ? ? + ? : uniform modular lattice Def [H. 17] ?: { } is L-convex: ? ? + ? ? ? ? ? + ? ? ? ?,? ?+= ? ? + ? Several DCA concepts/properties are naturally extended 30

  31. deg Det ? = Min. deg ? deg ? s.t. deg ???,? [ ,0] ( ?) ?,? ? ?? is viewed as L-convex function minimization on uniform modular lattice SDA = steepest descent algorithm for this L-convex function: ? ? : minimizer over [?, ?+] submodular optimization # iterations = ? (initial,opt) adapting Murota-Shioura 2014 31

  32. Summary Edmonds problem, rank v.s. nc-rank Weighted Edmonds problem, deg det v.s. deg Det formulation, algorithm, special case of deg det = deg Det Submodularity / discrete convexity aspect L-convexity on uniform modular lattice (= Euclidean building) 32

  33. Problems If ? = ?0??0+ ?1??1?1+ + ??????? where ??:? ? over ?, can we compute deg Det A in time polynomial in ?,?,and log max? ?? ? Representable by deg det but deg det < deg Det : Non-bipartite matching: Edmonds 1965 Matching forest: Giles 1982 Path matching: Cunningham-Geelen 1997 Linear matroid matching: Lov sz 1980, Iwata-Kobayashi 2017 Can we develop a unified theory ? 33

  34. References H. Hirai: Uniform modular lattice and Euclidean building, 2017 H. Hirai: Uniform semimodular lattice and valuated matroid, 2018 H. Hirai: Computing degree of determinant via discrete convex optimization over Euclidean building, 2018. Thank you for your attention 34

Related


No related presentations.

More Related Content