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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Smith, H.J.S.: On systems of linear indeterminate equations and congruences. Philos. Trans. R. Soc. Lond. 151, 293–326 (1861)
Newman, M.: The Smith normal form. Linear Algebra Appl. 245, 367–381 (1972)
Frumkin, M.A.: An application of modular arithmetic to the construction of algorithms for solving systems of linear equations. Sov. Math. Dokl. 17, 1165–1168 (1976)
Hu, T.C.: Integer Programming and Network Flows. Addison-Wesley, Reading (1969)
Hartley, B., Hawkes, T.O.: Rings, Modules, and Linear Algebra. Chapman and Hall, London/New York (1970)
Gantmacher, F.R.: Matrix Theory, vol. 1. Chelsea, New York (1960)
Kaltofen, E., Krishnamoorthy, M.S., Saunders, B.D.: Parallel algorithms for matrix normal forms. Linear Algebra Appl. 136, 189–208 (1990)
Kailath, T.: Linear Systems. Prentice Hall, New York (1979)
Abaffy, J., Broyden, C.G., Spedicato, E.: A class of direct methods for linear equations. Numer. Math. 45, 361–378 (1984)
Abafy, J., Spedicato, E.: ABS Projection Algorithms. Mathematical Techniques for Linear and Nonlinear Equations. Ellis Horwood, Chichester (1989)
Esmaeili, H., Mahdavi-Amiri, N., Spedicato, E.: A class of ABS algorithms for Diophantine linear systems. Numer. Math. 90, 101–115 (2001)
Khorramizadeh, M., Mahdavi-Amiri, N.: Integer extended ABS algorithms and possible control of intermediate results for linear Diophantine systems. 4OR 7, 145–167 (2009)
Spedicato, E., Bodon, E., Del Popolo, A., Mahdavi-Amiri, N.: ABS methods and ABSPACK for linear systems and optimization. A review. 4OR 1, 51–66 (2003)
Spedicato, E., Bodon, E., Del Popolo, A., Xia, Z.: ABS algorithms for linear systems and optimization. A review and a bibliography. Ric. Oper. 29, 39–88 (2000)
Spedicato, E., Xia, Z., Zhang, L.: The implicit LX method of the ABS class. Optim. Methods Softw. 8, 99–110 (1997)
Adib, M., Mahdavi-Amiri, N., Spedicato, E.: Broyden’s method as an ABS algorithm. Publ. Univ. Miskolc, Ser. D Nat. Sci.. Math. 40, 3–13 (1999)
Khorramizadeh, M., Mahdavi-Amiri, N.: On solving linear Diophantine systems using generalized Rosser’s algorithm. Bull. Iran. Math. Soc. 34(2), 1–25 (2008)
Newman, M.: Integral Matrices. Academic Press, New York (1972)
Pohst, M.: Computational Algebraic Number Theory. Birkhauser, Boston (1993)
Pohst, M., Zassenhaus, H.: Algorithmic Algebraic Number Theory. Cambridge University Press, New York (1989)
Esmaeili, H., Mahdavi-Amiri, N., Spedicato, E.: Generating the integer null space and conditions for determination of an integer basis using the ABS algorithms. Bull. Iran. Math. Soc. 27, 1–18 (2001)
Chen, Z., Dang, N.Y., Xue, Y.: A general algorithm for underdetermined linear systems. In: The Proceedings of the First International Conference on ABS Algorithms, Luoyang, China, pp. 1–13 (1992)
Rosser, J.B.: A note on the linear Diophantine equation. Am. Math. Mon. 48, 662–666 (1941)
Cassels, J.W.S.: Rational Quadratic Forms. Academic Press, New York (1979)
Derbyshire, J.: Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Penguin, New York (2004)
Dirichlet, P.G.L.: Beweis des Satzes, dass jede unbegrenzte arithmetische progression, deren erstes glied und differenz ganze zahlen ohne gemeinschaftlichen factor sind, unendlich viele primzahlen enthalt. Math. Werke 1, 313–342 (1837)
Hardy, G.H., Wright, E.M. (eds.): An Introduction to the Theory of Numbers. Clarendon Press, New York (1979)
Chou, T.J., Collins, E.E.: Algorithms for the solutions of systems of linear Diophantine equations. SIAM J. Comput. 11, 686–708 (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Florian A. Potra.
The second author thanks the Research Council of Sharif University of Technology for supporting this work.
Rights and permissions
About this article
Cite this article
Golpar-Raboky, E., Mahdavi-Amiri, N. Diophantine Quadratic Equation and Smith Normal Form Using Scaled Extended Integer Abaffy–Broyden–Spedicato Algorithms. J Optim Theory Appl 152, 75–96 (2012). https://doi.org/10.1007/s10957-011-9911-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9911-6