Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
From MaRDI portal
Publication:3891677
DOI10.1137/0208040zbMath0446.65015OpenAlexW2032980094WikidataQ62638424 ScholiaQ62638424MaRDI QIDQ3891677
Achim Bachem, Ravindran Kannan
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6f1d7d966a2a24183919e3da3b7ade68e6c33118
Related Items
A polyhedral homotopy algorithm for real zeros, Generalised cone complexes and tropical moduli in polymake, Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy, The hidden number problem with small unknown multipliers: cryptanalyzing MEGA in six queries and other applications, A Formal Proof of the Computation of Hermite Normal Form in a General Setting, Feasible rounding approaches for equality constrained mixed-integer optimization problems, Computing \(J\)-ideals of a matrix over a principal ideal domain, Solving systems of linear equations over polynomials, Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\), Note on shortest and nearest lattice vectors, The union of balls and its dual shape, Computing a matrix symmetrizer exactly using modified multiple modulus residue arithmetic, Lattice based extended formulations for integer linear equality systems, Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients, CW Complexes for Complex Algebraic Surfaces, The determination of canonical forms for lattice quadrature rules, Codeterminantal graphs, Real data-integer solution problems within the Blum-Shub-Smale computational model, Total dual dyadicness and dyadic generating sets, An \(NC^ 2\) algorithm for testing similarity of matrices, On efficient sparse integer matrix Smith normal form computations, An algorithmic approach to the \(q\)-summability problem of bivariate rational functions, On graphs with 2 trivial distance ideals, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, From Feynman rules to conserved quantum numbers. I, Twisted \(\Gamma \times \mathbb T^n\)-equivariant degree with \(n\)-parameters: computational formulae and applications, A feasible rounding approach for mixed-integer optimization problems, Block-structured integer programming: can we parameterize without the largest coefficient?, Local computation of homology variations over a construction process, Unnamed Item, Lattice polly cracker cryptosystems, On the discrete logarithm problem in finite fields of fixed characteristic, An interpolating sequent calculus for quantifier-free Presburger arithmetic, Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient, On groups presented by inverse-closed finite confluent length-reducing rewriting systems, The co-discovery of conservation laws and particle families, Constraint Satisfaction Problems over Numeric Domains, Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices, A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x\)], On isomorphism testing of a class of 2-nilpotent groups, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, Which new RSA-signatures can be computed from certain given RSA- signatures!, Finding cut-offs in leaderless rendez-vous protocols is easy, Enumerating Projections of Integer Points in Unbounded Polyhedra, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Proving nonreachability by modulo-invariants, Identifying lens spaces in polynomial time, The ultradiscrete Toda lattice and the Smith normal form of bidiagonal matrices, A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x\)-lattices], Enumeration of cospectral and coinvariant graphs, Unification algorithms cannot be combined in polynomial time, Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix, A decision algorithm for linear sentences on a PFM, Computing the volume, counting integral points, and exponential sums, Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra, Additive edge labelings, Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices, Reduction of Smith normal form transformation matrices, Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems, Short Bases of Lattices over Number Fields, A Generalized Sampling Theorem for Locally Compact Abelian Groups, An Interpolating Sequent Calculus for Quantifier-Free Presburger Arithmetic, Computation of cubical homology, cohomology, and (co)homological operations via chain contraction, A simplex algorithm for rational cp-factorization, Fast computation of Hermite normal forms of random integer matrices, Unnamed Item, Integer programming with 2-variable equations and 1-variable inequalities, Computational complexity and 3-manifolds and zombies, A Digital Signature Scheme Based on CVP ∞, Orientable quadratic equations in free metabelian groups, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Improvement of Lattice-Based Cryptography Using CRT, A Rigorous Subexponential Algorithm For Computation of Class Groups, Unnamed Item, How to integrate a polynomial over a simplex, A note on solving linear Diophantine systems by usingL3-reduction algorithm, Hermite and Smith normal form algorithms over Dedekind domains, An application of the Hermite normal form in integer programming, ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS, Exact Semidefinite Programming Bounds for Packing Problems, On the Infrastructure of the Principal Ideal Class of an Algebraic Number Field of Unit Rank One, Computing simplicial representatives of homotopy group elements, Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems, Decision problems in quadratic function fields of high genus, Integer Farkas Lemma, Multivariate periodic wavelet analysis, Binary Component Decomposition Part I: The Positive-Semidefinite Case, Best-case and worst-case sparsifiability of Boolean CSPs, Distance ideals of graphs, On polynomial-time solvable linear Diophantine problems, The sandpile group of a polygon flower, Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm, Attacks on Secure Logging Schemes, Frontiers of sphere recognition in practice, A comparative study of algorithms for computing the Smith normal form of an integer matrix†, Complexity questions in number theory, Total weak unimodularity: Testing and applications, Unification algorithms cannot be combined in polynomial time., A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix, Recognizing badly presented \(Z\)-modules, Parallel algorithms for matrix normal forms, A discrete structure with the minimal set, Deciding Orthogonality in Construction-A Lattices, Homology of cellular structures allowing multi-incidence
