Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices

DOI10.1137/0608057zbMath0655.65069OpenAlexW1971882029MaRDI QIDQ3802506

B. David Saunders, Erich L. Kaltofen, Mukkai S. Krishnamoorthy

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/00ca0706eb823573707f99fe4a1b9313c0836830

zbMATH Keywords

parallel algorithminvariant factorprobabilistic algorithmHermite normal formpolynomial matrixSmith normal formmatrix normal formpolynomial- time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel numerical computation (65Y05) Matrices over function rings in one or more variables (15A54) Canonical forms, reductions, classification (15A21)

Related Items

A compound matrix algorithm for the computation of the Smith form of a polynomial matrix, Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients, A local construction of the Smith normal form of a matrix polynomial, On the quasi-stability criteria of monic matrix polynomials, A Formal Proof of the Computation of Hermite Normal Form in a General Setting, The complexity of the characteristic and the minimal polynomial., A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x\)], A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x\)-lattices], A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix, Unification and matching modulo nilpotence, A decision algorithm for linear sentences on a PFM, Compound matrices: Properties, numerical issues and analytical computations, On Computing the Hermite Form of a Matrix of Differential Polynomials, Easy intruder deduction problems with homomorphisms, Complexity of nilpotent unification and matching problems., Parallel algorithms for matrix normal forms, Computing rational forms of integer matrices

Cites Work

• Solving systems of linear equations over polynomials
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Exact reduction of a polynomial matrix to the Smith normal form
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast parallel matrix and GCD computations
• Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal form of polynomial matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item