Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings

DOI10.1137/18M1190823MaRDI QIDQ5234537zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai

Publication date 27 September 2019

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11245

zbMATH Keywords

combinatorial relaxation algorithmDieudonné determinantdiscrete convex analysisEuclidean buildingL-convex functionmixed matrixnoncommutative rankskew fieldsubmodular functionuniform modular lattice

Mathematics Subject Classification ID

Skew fields, division rings (12E15) Buildings and the geometry of diagrams (51E24) Combinatorial optimization (90C27)

Abstract: In this paper, we consider the computation of the degree of the Dieudonn'e determinant of a linear symbolic matrix $A=A_0+A_1{x}_1+cdots+A_m{x}_m$, where each $A_i$ is an $nimesn$ polynomial matrix over $mathbbK[t]$ and $x_1,x_2,ldots,x_m$ are pairwise "non-commutative" variables. This quantity is regarded as a weighted generalization of the non-commutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by Fortin and Rautenauer (2004), and Ivanyos, Qiao, and Subrahmanyam (2018), we develop a framework to compute the degree of the Dieudonn'e determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for $mSL(mathbbK(t{)}^n)$. To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of L-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on $mathbbK$, and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

Recommendations

• Computing the Degree of Determinants via Combinatorial Relaxation
• A cost-scaling algorithm for computing the degree of determinants
• On the complexity of approximating extremal determinants in matrices
• On the complexity of computing determinants
• scientific article; zbMATH DE number 1305439
• Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
• On computing the degree of convexity of polyominoes
• Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares
• scientific article; zbMATH DE number 7228953
• Determinant Optimization on Binary Matrices

Cites work

• L-convexity on graph structures
• A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
• A weighted linear matroid parity algorithm
• A weighted matroid intersection algorithm
• Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
• Buildings of spherical type and finite BN-pairs
• Classical complexity and quantum entanglement
• Combinatorial optimization. Theory and algorithms
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Computing DM-decomposition of a partitioned matrix with rank-1 blocks
• Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
• Computing the Degree of Determinants via Combinatorial Relaxation
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Constructive non-commutative rank computation is in deterministic polynomial time
• Degree of Dieudonné determinant defines the order of nonlinear system
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic polynomial time algorithms for matrix completion problems
• DIEUDONNÉ DETERMINANTS FOR SKEW POLYNOMIAL RINGS
• Discrete convex analysis
• Discrete Convex Analysis
• Discrete convex functions on graphs and their algorithmic applications
• Exact bounds for steepest descent algorithms of $L$-convex function minimization
• Fast deterministic algorithms for matrix completion problems
• Generalized Wong sequences and their applications to Edmonds' problems
• scientific article; zbMATH DE number 2123131 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3711820 (Why is no real title available?)
• scientific article; zbMATH DE number 48723 (Why is no real title available?)
• scientific article; zbMATH DE number 1346448 (Why is no real title available?)
• scientific article; zbMATH DE number 798609 (Why is no real title available?)
• scientific article; zbMATH DE number 3103212 (Why is no real title available?)
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Index Reduction for Differential-algebraic Equations with Mixed Matrices
• Lattice Theory: Foundation
• Les déterminants sur un corps non commutatif
• Matrices and matroids for systems analysis
• Matroid intersection algorithms
• Non-commutative Edmonds' problem and matrix semi-invariants
• On a weighted linear matroid intersection algorithm by deg-det computation
• Operator scaling: theory and applications
• Polynomial degree bounds for matrix semi-invariants
• Rational identities and applications to algebra and geometry
• Reductive groups over a local field
• Singular spaces of matrices and their application in combinatorics
• Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—
• Systems of distinct representatives and linear algebra
• Valuated matroids
• Valuated matroids: A new look at the greedy algorithm

Cited in

(13)

• Computing the discrete compactness of orthogonal pseudo-polytopes via their nD-EVM representation
• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
• A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 2 submatrices
• Computing valuations of the Dieudonné determinants
• A cost-scaling algorithm for computing the degree of determinants
• Uniform modular lattices and affine buildings
• On a weighted linear matroid intersection algorithm by deg-det computation
• Computing the Degree of Determinants via Combinatorial Relaxation
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2 2 submatrices
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• On solving (non)commutative weighted Edmonds' problem
• Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices

This page was built for publication: Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5234537)