On solving linear Diophantine systems using generalized Rosser's algorithm (Q1016753)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On solving linear Diophantine systems using generalized Rosser's algorithm |
scientific article |
Statements
On solving linear Diophantine systems using generalized Rosser's algorithm (English)
0 references
22 May 2009
0 references
The authors present an algorithmic solution to \(Ax=b\) based on Rosser's algorithm (for finding the general solution of a single diophantine equation \(a^T x = d\)). The main idea is to find iteratively the general solution \(x=v^k+V^k y\) for \(A_i.x=b_i\), \(i=1,\dots,k\), and then plug it into \(a_{k+1}^T x=b_{k+1}\) to find the general solution for the system \(A_i.x=b_i\), \(i=1,\dots,k+1\). This algorithm is compared to the algorithms LDSSBR by \textit{T.-W. J. Chou} and \textit{G. E. Collins} [SIAM J. Comput. 11, 687--708 (1982; Zbl 0498.65022)]. With 25 pages, the paper is very lengthy and technical for presenting a comparably straightforward idea.
0 references
linear Diophantine systems
0 references
generalized Rosser's algorithm
0 references