A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix

DOI10.1016/0024-3795(95)00743-1zbMath0890.65038MaRDI QIDQ677132

George Labahn, Arne Storjohann

Publication date: 16 February 1998

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(95)00743-1

zbMATH Keywords

polynomial matrix; Smith normal form; complexity reduction; Las Vegas probabilistic algorithm; nonunimodular triangularization

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

65Y20: Complexity and performance of numerical algorithms

15A21: Canonical forms, reductions, classification

Cites Work

• Parallel algorithms for matrix normal forms
• Solving systems of linear equations over polynomials
• Fast projection methods for minimal design problems in linear system theory
• Computing Hermite and Smith normal forms of triangular integer matrices
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Probabilistic computation of integer polynomial GCDs
• Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal form of polynomial matrices
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Computational Solutions of Matrix Problems Over an Integral Domain
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item