A cost-scaling algorithm for computing the degree of determinants

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

Hiroshi Hirai, Motoki Ikeda

Publication date: 1 August 2022

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

Newton polytope[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Dieudonn%EF%BF%BD%EF%BF%BD+determinant&go=Go Dieudonn�� determinant]partitioned matrixnoncommutative rankedmonds' problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Discrete Convex Analysis
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Non-commutative Edmonds' problem and matrix semi-invariants
• Noncommutative rational functions, their difference-differential calculus and realizations
• Matrices and matroids for systems analysis
• An application of simultaneous diophantine approximation in combinatorial optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• A weighted matroid intersection algorithm
• A Weighted Linear Matroid Parity Algorithm
• Les déterminants sur un corps non commutatif
• Random pseudo-polynomial algorithms for exact matroid problems
• Systems of distinct representatives and linear algebra
• Title not available (Why is that?)
• Singular spaces of matrices and their application in combinatorics
• Computing the Degree of Determinants via Combinatorial Relaxation
• Polynomial degree bounds for matrix semi-invariants
• A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
• Algebraic algorithms for linear matroid parity problems
• Title not available (Why is that?)
• Uniform modular lattices and affine buildings
• Constructive non-commutative rank computation is in deterministic polynomial time
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Operator scaling: theory and applications
• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices
• On a weighted linear matroid intersection algorithm by deg-det computation

Cited In (5)

• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Computing the Degree of Determinants via Combinatorial Relaxation
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• 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

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)