Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices

DOI10.1137/0608057zbMath0655.65069MaRDI QIDQ3802506

Erich L. Kaltofen, B. David Saunders, 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 algorithm; invariant factor; probabilistic algorithm; Hermite normal form; polynomial matrix; Smith normal form; matrix normal form; polynomial- time complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65Y05: Parallel numerical computation

15A54: Matrices over function rings in one or more variables

15A21: Canonical forms, reductions, classification

Related Items

A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix, A decision algorithm for linear sentences on a PFM, Parallel algorithms for matrix normal forms, 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, The complexity of the characteristic and the minimal polynomial., Complexity of nilpotent unification and matching problems., 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