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

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

Arne Storjohann, George Labahn

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 matrixSmith normal formcomplexity reductionLas Vegas probabilistic algorithmnonunimodular triangularization

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity and performance of numerical algorithms (65Y20) Canonical forms, reductions, classification (15A21)

Related Items (4)

A local construction of the Smith normal form of a matrix polynomial ⋮ Matrix-based implicit representations of rational algebraic curves and applications ⋮ Fraction-free algorithm for the computation of diagonal forms matrices over Ore domains using Gröbner bases ⋮ Smith forms of circulant polynomial matrices

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

This page was built for publication: A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix