Solution of systems of linear Diophantine equations
From MaRDI portal
Two methods to solve linear systems of Diophantine eauations are given. The first one uses \(p\)-adic considerations, and the second one is based on the Chinese remainder theorem. The complexity for a system of size \(m\times n\) is \(O(n^\beta m)\), \(\beta\) being the power in the estimation of matrix multiplication time. The complexity result is based on some theorems about quasi-Euclidean rings, also given in this paper. For the entire collection see [Zbl 0970.00027].
Recommendations
- A polynomial algorithm for solving systems of two linear diophantine equations
- Solution algorithms for systems of linear equations over residue rings
- An efficient incremental algorithm for solving systems of linear diophantine equations
- Algorithms for solving systems of linear Diophantine equations in residue rings
- Solving systems of linear diophantine equations: An algebraic approach
Cited in
(26)- An efficient incremental algorithm for solving systems of linear diophantine equations
- Solution of systems of linear equations by the \(p\)-adic method
- Multidimensional system of Diophantine equations
- On polynomial-time solvable linear Diophantine problems
- Certified dense linear system solving
- Parametric systems of linear congruences.
- Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Infinite Abelian Groups and Solving Systems of Linear Diophantine Equations
- Solving Binary Linear Equation Systems over the Rationals and Binaries
- scientific article; zbMATH DE number 3855236 (Why is no real title available?)
- Solution algorithms for systems of linear equations over residue rings
- Exact solution of general integer systems of linear equations
- A Matrix Method for Solving Linear Congruences
- Solving systems of linear diophantine equations: An algebraic approach
- scientific article; zbMATH DE number 4123806 (Why is no real title available?)
- scientific article; zbMATH DE number 1254015 (Why is no real title available?)
- scientific article; zbMATH DE number 1042590 (Why is no real title available?)
- scientific article; zbMATH DE number 800104 (Why is no real title available?)
- Solving rank one perturbed linear diophantine systems using the Hermite normal form
- General solution of systems of linear diophantine equations and inequations
- scientific article; zbMATH DE number 7510495 (Why is no real title available?)
- How can we solve a linear Diophantine equation by the basis reduction algorithm
- Sparse Solutions of Linear Diophantine Equations
- scientific article; zbMATH DE number 3106578 (Why is no real title available?)
- Symmetric and non-symmetric ABS methods for solving Diophantine systems of equations
- On one way to solve linear equations over a Euclidean ring
- A polynomial algorithm for solving systems of two linear diophantine equations
This page was built for publication: Solution of systems of linear Diophantine equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760224)
