Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

DOI10.1137/0208040zbMATH Open0446.65015DBLPjournals/siamcomp/KannanB79OpenAlexW2032980094WikidataQ62638424 ScholiaQ62638424MaRDI QIDQ3891677FDOQ3891677

Cited In (only showing first 100 items - show all)

A simplex algorithm for rational cp-factorization
A Digital Signature Scheme Based on CVP ∞
On the Infrastructure of the Principal Ideal Class of an Algebraic Number Field of Unit Rank One
A decision algorithm for linear sentences on a PFM
Twisted \(\Gamma \times \mathbb T^n\)-equivariant degree with \(n\)-parameters: computational formulae and applications
On efficient sparse integer matrix Smith normal form computations
Real data-integer solution problems within the Blum-Shub-Smale computational model
ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS
Title not available (Why is that?)
Additive edge labelings
A feasible rounding approach for mixed-integer optimization problems
An application of the Hermite normal form in integer programming
Lattice based extended formulations for integer linear equality systems
Parallel algorithms for matrix normal forms
Unification algorithms cannot be combined in polynomial time
Improvement of lattice-based cryptography using CRT
An \(NC^ 2\) algorithm for testing similarity of matrices
Fast computation of Hermite normal forms of random integer matrices
Integer programming with 2-variable equations and 1-variable inequalities
Complexity questions in number theory
Note on shortest and nearest lattice vectors
Lattice polly cracker cryptosystems
Computing the volume, counting integral points, and exponential sums
Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
An interpolating sequent calculus for quantifier-free Presburger arithmetic
An interpolating sequent calculus for quantifier-free Presburger arithmetic
A Generalized Sampling Theorem for Locally Compact Abelian Groups
Computing a matrix symmetrizer exactly using modified multiple modulus residue arithmetic
Enumerating projections of integer points in unbounded polyhedra
Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems
On the discrete logarithm problem in finite fields of fixed characteristic
Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients
Enumeration of cospectral and coinvariant graphs
Recognizing badly presented \(Z\)-modules
The union of balls and its dual shape
Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
Constraint satisfaction problems over numeric domains
A discrete structure with the minimal set
Solving systems of linear equations over polynomials
An algorithmic approach to the \(q\)-summability problem of bivariate rational functions
Total weak unimodularity: Testing and applications
On the complexity of recognizing the Hilbert basis of a linear Diophantine system
Hermite and Smith normal form algorithms over Dedekind domains
Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems
Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm
Which new RSA-signatures can be computed from certain given RSA- signatures!
A polyhedral homotopy algorithm for real zeros
On isomorphism testing of a class of 2-nilpotent groups
Multivariate periodic wavelet analysis
The co-discovery of conservation laws and particle families
From Feynman rules to conserved quantum numbers. I
Best-case and worst-case sparsifiability of Boolean CSPs
How to integrate a polynomial over a simplex
Total dual dyadicness and dyadic generating sets
Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x]\)-lattices
Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\)
A Rigorous Subexponential Algorithm For Computation of Class Groups
An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere
Short bases of lattices over number fields
Decision problems in quadratic function fields of high genus
On polynomial-time solvable linear Diophantine problems
Computation of cubical homology, cohomology, and (co)homological operations via chain contraction
Proving nonreachability by modulo-invariants
Unification algorithms cannot be combined in polynomial time.
A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix
A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
Computing simplicial representatives of homotopy group elements
Integer Farkas lemma
A note on solving linear Diophantine systems by usingL³-reduction algorithm
A comparative study of algorithms for computing the Smith normal form of an integer matrix†
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
Homology of cellular structures allowing multi-incidence
Identifying lens spaces in polynomial time
Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices
Finding cut-offs in leaderless rendez-vous protocols is easy
The degree-distance and transmission-adjacency matrices
Multidimensional integer trigonometry
Computing the unit group of a commutative finite \(\mathbb{Z}\)-algebra
Efficient algorithms for finite \(\mathbb{Z}\)-algebras
The determination of canonical forms for lattice quadrature rules
Orientable quadratic equations in free metabelian groups
Computing \(J\)-ideals of a matrix over a principal ideal domain
Generalised cone complexes and tropical moduli in polymake
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Total dual dyadicness and dyadic generating sets
Codeterminantal graphs
Reduction of Smith normal form transformation matrices
Computational complexity and 3-manifolds and zombies
The ultradiscrete Toda lattice and the Smith normal form of bidiagonal matrices
Feasible rounding approaches for equality constrained mixed-integer optimization problems
Distance ideals of graphs
The sandpile group of a polygon flower
Porous invariants for linear systems
Attacks on secure logging schemes
On graphs with 2 trivial distance ideals
The hidden number problem with small unknown multipliers: cryptanalyzing MEGA in six queries and other applications
Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices

This page was built for publication: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

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