Abstract
ABS methods are a large class of algorithms for solving continuous and integer linear algebraic equations, and nonlinear continuous algebraic equations, with applications to optimization. Recent work by Chinese researchers led by Zunquan Xia has extended these methods also to stochastic, fuzzy and infinite systems, extensions not considered here. The work on ABS methods began almost thirty years. It involved an international collaboration of mathematicians especially from Hungary, England, China and Iran, coordinated by the university of Bergamo. The ABS method are based on the rank reducing matrix update due to Egerváry and can be considered as the most fruitful extension of such technique. They have led to unification of classes of methods for several problems. Moreover they have produced some special algorithms with better complexity than the standard methods. For the linear integer case they have provided the most general polynomial time class of algorithms so far known; such algorithms have been extended to other integer problems, as linear inequalities and LP problems, in over a dozen papers written by Iranian mathematicians led by Nezam Mahdavi-Amiri. ABS methods can be implemented generally in a stable way, techniques existing to enhance their accuracy. Extensive numerical experiments have shown that they can outperform standard methods in several problems. Here we provide a review of their main properties, for linear systems and optimization. We also give the results of numerical experiments on some linear systems. This paper is dedicated to Professor Egerváry, developer of the rank reducing matrix update, that led to ABS methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abaffy J (1979) A linearis egyenletrendszerek ltalnos megoldsnak egy modszerosztlya. Alkamazott Matematikai Lapok 5: 223–240
Abaffy J (1984) A generalization of the ABS class. In: Proceedings of the 2nd conference on automata languages and mathematical systems. University of Economics, Budapest, pp 7–11
Abaffy J, Broyden C, Spedicato E (1984) A Class of direct methods for linear equations. Numerische Mathematik 45: 361–376
Abaffy J, Spedicato E (1984) A generalization of Huang’s method for solving systems of linear algebraic equations. Bollettino Unione Matematica Italiana 3-B: 517–529
Abaffy J, Spedicato E (1989) ABS projection algorithms, mathematical techniques for linear and nonlinear equations. Ellis Horwood, Chichester
Abaffy J, Spedicato E (1990) A class of scaled direct methods for linear systems. Ann Inst Stat Math 42: 187–201
Amiri-Mahdavi N, Khorramizadeh M (2007) Integer extended ABS algorithm and possible control of intermediate results for linear Diophantine systems. Report DOI 10, Sharif University of Technology
Amiri-Mahdavi N, Khorramizadeh M (2008) On solving linear Diophantine systems using generalized Rosser’s algorithm. Bull Iran Math Soc 34: 1–25
Bertocchi M, Spedicato E (1990) Block ABS algorithms for dense linear systems in a vector processor environment. In: Proceedings of the conference on Supercomputing, Pisa, December 1989, Franco Angeli, pp 39–46
Bodon E (1989) Biconjugate algorithms in the ABS class I: alternative formulation and theoretical properties. Report DMSIA 3/89, University of Bergamo
Bodon E (1993) Numerical experiments with ABS algorithms on banded systems of linear equations. Report TR/PA/93/13, CERFACS, Toulouse
Bodon E, Luksan L, Spedicato E (2000) Computational experiments with linear ABS algorithms. Report 817, Institute of Computer Science, Academy of Sciences of Czech Republic , Prague
Bonomi M, Del Popolo A, Spedicato E (2007) ABS solution of normal equations of second kind and application to the primal-dual interior point method for linear programming. Iran J Oper Res 1: 28–34
Broyden C (1985) On the numerical stability of Huang and related methods. J Optim Theory Appl 47: 401–412
Egerváry E (1955–1956) Aufloesungen eines homogenen linearen diophantisches Gleichungsystems mit Hilf von Projektormatrizen. Public Math Debrecen. 4:481–483
Esmaeili H, Mahdavi-Amiri N, Spedicato E (2001) A class of ABS algorithms for Diophantine linear systems. Numerische Mathematik 90: 101–115
Fodor S (2001) Symmetric and nonsymmetric ABS methods for solving Diophantine systems of equations. Ann Oper Res 103: 291–314
Galántai A (2003) Projectors and Projection Methods. Kluwer, Dordrecht
Galántai A, Spedicato E (2007) ABS methods for nonlinear systems of algebraic equations. Iran J Oper Res 1: 50–73
Huang HY (1975) A direct method for the general solution of a system of linear equations. J Optim Theory Appl 16: 429–445
Li ZF (1996) Restarted and truncated versions of ABS methods for large linear systems: a basic framework. Report DMSIA 8/96, Department of Mathematics, University of Bergamo
Matiyasevich Y (1970) Enumerable sets are Diophantine. Dokl Akad Nauk SSSR 191: 279–282
Mirmia K (1996) Iterative refinement in ABS methods, Report DMSIA 32/96. University of Bergamo
Sloboda F (1978) A parallel projection methods for linear algebraic systems. Apl Mat Ceskosl Akad Ved 23: 185–198
Spedicato E (1985) On the solution of linear least squares through the ABS class for linear systems. Proceedings Giornate di Lavoro AIRO
Spedicato E, Bodon E (2002) Numerical experiments with the simplex method for the LP problem based upon Fletcher’s factors update and the ABS implicit LU and LX algorithms. Report DMSIA 02/6, University of Bergamo
Spedicato E, Xia Z (1999) ABS formulation of Fletcher implicit LU method for factorizing a matrix and solving linear equations and LP problems. Report DMSIA 1/99, University of Bergamo
Spedicato E, Zhao JX (1993) Explicit general solution of the Quasi-Newton equation with sparsity and symmetry. Optim Methods Softw 2: 311–319
Spedicato E, Xia ZQ, Zhang LW (1997) The implicit LX method of the ABS class. Optim Methods Soft 8: 99–110
Spedicato E, Bodon E, Del Popolo A, Xia ZQ (2000) ABS algorithms for linear systems and optimization: a review and bibliography. Ricerca Operativa 29(89): 39–88
Tuma M (1993) Solving sparse unsymmetric sets of linear equations based on the implicit Gauss projection. Report 556, Institute Computer Science, Academy of Sciences, Prague
Xia ZQ (1994) An efficient ABS algorithm for linearly constrained optimization. Report DMSIA 15/94, University of Bergamo
Zhang LW (1995) An algorithm for the least Euclidean norm solution of a linear system of inequalities via the Huang ABS algorithm and the Goldfarb-Idnani strategy. Report DMSIA 2/95, University of Bergamo
Zhang ZW, Zhu M (1995) Solving a least change problem under the weak secant condition by an ABS approach. Report MA 95-20, City University, Hong Kong
Author information
Authors and Affiliations
Corresponding author
Additional information
There are now probably over 400 papers on ABS methods. A partial list up to 1999 of about 350 papers was published by Spedicato et al. (2000) in the journal Ricerca Operativa. Here we give only the handful of references most related to the content of this review paper.
Rights and permissions
About this article
Cite this article
Emilio, S., Elena, B., Zunquan, X. et al. ABS methods for continuous and integer linear equations and optimization. Cent Eur J Oper Res 18, 73–95 (2010). https://doi.org/10.1007/s10100-009-0128-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-009-0128-9