Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix

DOI10.1016/j.jco.2017.03.003zbMath1372.65134arXiv1607.04176OpenAlexW2963733895MaRDI QIDQ2402419

Vincent Neiger, Wei Zhou, George Labahn

Publication date: 7 September 2017

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

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

zbMATH Keywords

algorithmdeterminantHermite normal formpolynomial matrixtriangularization method

Mathematics Subject Classification ID

Related Items (6)

p-adic algorithm for bivariate Gröbner bases ⋮ On polynomially solvable constrained input selections for fixed and switched linear structured systems ⋮ High-order lifting for polynomial Sylvester matrices ⋮ Segre-driven radicality testing ⋮ Deterministic computation of the characteristic polynomial in the time of matrix multiplication ⋮ Verification protocols with sub-linear communication for polynomial matrix operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)]
• Efficient algorithms for order basis computation
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• On the complexity of inverting integer and polynomial matrices
• Solving systems of linear equations over polynomials
• Fast projection methods for minimal design problems in linear system theory
• A reliable method for computing M-Padé approximants on arbitrary staircases
• On lattice reduction for polynomial matrices
• On the complexity of computing determinants
• High-order lifting and integrality certification
• On simultaneous row and column reduction of higher-order linear differential systems
• A deterministic algorithm for inverting a polynomial matrix
• Normal forms for general polynomial matrices
• Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs
• Efficient computation of order bases
• Computing column bases of polynomial matrices
• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• Unimodular completion of polynomial matrices
• Asymptotically Fast Triangularization of Matrices over Rings
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Computing minimal nullspace bases
• Computing hermite forms of polynomial matrices
• Normalization of row reduced matrices
• Computing the rank and a small nullspace basis of a polynomial matrix

This page was built for publication: Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix