Diophantine Quadratic Equation and Smith Normal Form Using Scaled Extended Integer Abaffy–Broyden–Spedicato Algorithms

E. Golpar-Raboky () and N. Mahdavi-Amiri ()
Additional contact information
E. Golpar-Raboky: Sharif University of Technology
N. Mahdavi-Amiri: Sharif University of Technology

Journal of Optimization Theory and Applications, 2012, vol. 152, issue 1, No 5, 75-96

Abstract: Abstract Classes of integer Abaffy–Broyden–Spedicato (ABS) methods have recently been introduced for solving linear systems of Diophantine equations. Each method provides the general integer solution of the system by computing an integer solution and an integer matrix, named Abaffian, with rows generating the integer null space of the coefficient matrix. The Smith normal form of a general rectangular integer matrix is a diagonal matrix, obtained by elementary nonsingular (unimodular) operations. Here, we present a class of algorithms for computing the Smith normal form of an integer matrix. In doing this, we propose new ideas to develop a new class of extended integer ABS algorithms generating an integer basis for the integer null space of the matrix. For the Smith normal form, having the need to solve the quadratic Diophantine equation, we present two algorithms for solving such equations. The first algorithm makes use of a special integer basis for the row space of the matrix, and the second one, with the intention of controlling the growth of intermediate results and making use of our given conjecture, is based on a recently proposed integer ABS algorithm. Finally, we report some numerical results on randomly generated test problems showing a better performance of the second algorithm in controlling the size of the solution. We also report the results obtained by our proposed algorithm on the Smith normal form and compare them with the ones obtained using Maple, observing a more balanced distribution of the intermediate components obtained by our algorithm.

Keywords: Smith normal form; Scaled extended integer ABS algorithms; Linear Diophantine systems; Quadratic Diophantine equation; Dirichlet’s theorem (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-011-9911-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:152:y:2012:i:1:d:10.1007_s10957-011-9911-6

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-011-9911-6

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().