Solving systems of linear equations over polynomials
This is a generalization of an earlier work of the author and \textit{A. Bachem} [SIAM J. Comput. 8, 499-507 (1979; Zbl 0446.65015)]. In this article a polynomial-time algorithm to derive the Hermite normal form of an \(n\times n\) matrix A(x) of polynomials is given. The algorithm hinges on constructing and postmultiplying by a small multiplier matrix \(K^{(i)}\) for the ith stage of the algorithm then showing that at every stage of the algorithm the transformed matrix \(A^{(i)}\) satisfies: \(| A^{(i)}| =length\) of \(A^{(i)}\) viewed as an \(n^ 2\) vector, den (A\({}^{(i)})=\ell cm\{den (a_{11}),...,den (a_{nn})\}<(4nad)^{400n^{11}d^ 4}\), and deg (A)\(=\max \{\deg a_{ij}(x)\}\leq 2n^ 3d\) where n is the dimension of the original matrix A, a is its length, den is the denominator, \(\ell em\) is the least common multiple, and d is its degree. This algorithm is then generalized to accommodate rectangular matrices and to obtain the Smith normal form based on the algorithm given by the author and A. Bachem [loc. cit.].
- scientific article; zbMATH DE number 3890617
- A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
- Fast parallel Hermite normal form computation of matrices over $$\mathbb{F}[x]$$
- scientific article; zbMATH DE number 1254301
- Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
- Algorithms for Hermite and Smith Normal Matrices and Linear Diophantine Equations
- Algorithms for the Solution of Systems of Linear Diophantine Equations
- Fast projection methods for minimal design problems in linear system theory
- scientific article; zbMATH DE number 3532959 (Why is no real title available?)
- scientific article; zbMATH DE number 3572260 (Why is no real title available?)
- scientific article; zbMATH DE number 3269388 (Why is no real title available?)
- scientific article; zbMATH DE number 3303655 (Why is no real title available?)
- scientific article; zbMATH DE number 3336831 (Why is no real title available?)
- scientific article; zbMATH DE number 3390604 (Why is no real title available?)
- scientific article; zbMATH DE number 3401090 (Why is no real title available?)
- scientific article; zbMATH DE number 3050844 (Why is no real title available?)
- Irreducible Realizations and the Degree of a Rational Matrix
- On Computing the Exact Determinant of Matrices with Polynomial Entries
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- On the unique decodability of codes (Corresp.)
- Part I-Smith form and common divisor of polynomial matrices
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Solving linear equations using residue arithmetic — Algorithm II
- Subresultants and Reduced Polynomial Remainder Sequences
- Systems of distinct representatives and linear algebra
- The Exact Solution of Systems of Linear Equations with Polynomial Coefficients
- Transfer Equivalence of Linear Dynamical Systems
- Evaluation techniques for zero-dimensional primary decomposition
- Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients
- A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
- Computing rational forms of integer matrices
- Solving systems of polynomial equations -- a tensor approach
- Codeterminantal graphs
- Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination
- Smith forms of circulant polynomial matrices
- Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
- Solution of linear system roots and their multiplicities
- Hermite Normal Form Computation Using Modulo Determinant Arithmetic
- Solving Binary Linear Equation Systems over the Rationals and Binaries
- scientific article; zbMATH DE number 3890617 (Why is no real title available?)
- Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination
- The use of Faber polynomials to solve systems of linear equations
- On Computing the Hermite Form of a Matrix of Differential Polynomials
- Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
- scientific article; zbMATH DE number 1254242 (Why is no real title available?)
- scientific article; zbMATH DE number 1424365 (Why is no real title available?)
- Solving rank one perturbed linear diophantine systems using the Hermite normal form
- scientific article; zbMATH DE number 6403662 (Why is no real title available?)
- scientific article; zbMATH DE number 5049913 (Why is no real title available?)
- On the quasi-stability criteria of monic matrix polynomials
- A local construction of the Smith normal form of a matrix polynomial
- Affine Loop Invariant Generation via Matrix Algebra
- A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix
- A decision algorithm for linear sentences on a PFM
- Almost consistent systems of linear equations
- Parallel algorithms for matrix normal forms
This page was built for publication: Solving systems of linear equations over polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082773)
