On solving linear Diophantine systems using generalized Rosser's algorithm

MaRDI QIDQ1016753zbMATH OpenFDO

Authors M. Khorramizadeh, Nezam Mahdavi-Amiri

Publication date 22 May 2009

Published in Bulletin of the Iranian Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

generalized Rosser's algorithmlinear Diophantine systems

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) The Frobenius problem (11D07) Computer solution of Diophantine equations (11Y50) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

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.

Recommendations

• An efficient algorithm for solving rank one perturbed linear Diophantine systems using Rosser's approach
• An efficient incremental algorithm for solving systems of linear diophantine equations
• A note on solving linear Diophantine systems by usingL³-reduction algorithm
• scientific article; zbMATH DE number 3900852
• A Note on the Linear Diophantine Equation

Cited in

(9)

• Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems
• Diophantine quadratic equation and Smith normal form using scaled extended integer Abaffy-Broyden-Spedicato algorithms
• Real and integer extended rank reduction formulas and matrix decompositions: A review
• An efficient algorithm for solving rank one perturbed linear Diophantine systems using Rosser's approach
• scientific article; zbMATH DE number 3099664 (Why is no real title available?)
• scientific article; zbMATH DE number 3099665 (Why is no real title available?)
• A Note on the Linear Diophantine Equation
• ABS methods for continuous and integer linear equations and optimization
• Rank reduction processes for solving linear Diophantine systems and integer factorizations: a review

This page was built for publication: On solving linear Diophantine systems using generalized Rosser's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016753)