A cost-scaling algorithm for computing the degree of determinants

DOI10.1007/S00037-022-00227-4zbMATH Open1492.90148OpenAlexW3081136268MaRDI QIDQ2159472FDOQ2159472

Authors Hiroshi Hirai, Motoki Ikeda 

Publication date 1 August 2022

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Newton polytopepartitioned matrixnoncommutative rankedmonds' problemDieudonné determinant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: In this paper, we address computation of the degree $mathopmdegDetA$ of Dieudonn'e determinant $mathopmDetA$ of [ A = sum_{k=1}^m A_k x_k t^{c_k}, ] where $A_k$ are $nimesn$ matrices over a field $mathbbK$, $x_k$ are noncommutative variables, $t$ is a variable commuting with $x_k$, $c_k$ are integers, and the degree is considered for $t$. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that $mathopmdegDetA$ is obtained by a discrete convex optimization on a Euclidean building. We extend this framework by incorporating a cost scaling technique, and show that $mathopmdegDetA$ can be computed in time polynomial of $n,m,lo{g}_{2}C$, where $C:=ma{x}_k|c_k|$. We give a polyhedral interpretation of $mathopmdegDet$, which says that $mathopmdegDetA$ is given by linear optimization over an integral polytope with respect to objective vector $c=(c_k)$. Based on it, we show that our algorithm becomes a strongly polynomial one. We apply this result to an algebraic combinatorial optimization problem arising from a symbolic matrix having $2imes2$-submatrix structure.

Recommendations

• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Computing the Degree of Determinants via Combinatorial Relaxation
• Non-commutative Edmonds' problem and matrix semi-invariants
• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
• On a weighted linear matroid intersection algorithm by deg-det computation

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 1346448 (Why is no real title available?)
• scientific article; zbMATH DE number 1859150 (Why is no real title available?)
• A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
• 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 \times 2\) submatrices
• A weighted linear matroid parity algorithm
• A weighted matroid intersection algorithm
• Algebraic algorithms for linear matroid parity problems
• An application of simultaneous diophantine approximation in combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Computing the Degree of Determinants via Combinatorial Relaxation
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Constructive non-commutative rank computation is in deterministic polynomial time
• Discrete Convex Analysis
• Les déterminants sur un corps non commutatif
• Matrices and matroids for systems analysis
• Non-commutative Edmonds' problem and matrix semi-invariants
• Non-commutative arithmetic circuits with division
• Noncommutative rational functions, their difference-differential calculus and realizations
• On a weighted linear matroid intersection algorithm by deg-det computation
• Operator scaling: theory and applications
• Polynomial degree bounds for matrix semi-invariants
• Random pseudo-polynomial algorithms for exact matroid problems
• Singular spaces of matrices and their application in combinatorics
• Systems of distinct representatives and linear algebra
• Uniform modular lattices and affine buildings

Cited in

(6)

• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Computing the Degree of Determinants via Combinatorial Relaxation
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Computing valuations of the Dieudonné determinants
• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank

This page was built for publication: A cost-scaling algorithm for computing the degree of determinants

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