求解线性丢番图方程组的ABS方法与WinABS03的研究
|
摘要
1984年，Abaffy、Broyden及Spedicato共同研究开发了一类用于求解线性方程组与非线性方程组的投影算法—ABS算法。随后二十多年的发展ABS算法扩展到可以求解最小二乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。线性丢番图方程组的求解是实际应用中经常遇到的一类问题，在物流、运输中起着重要的作用，从而对线性丢番图方程解的探讨变得尤为必要。本文在ABS的框架下系统的研究线性丢番图方程组的解法。
本文的研究工作分三个部分，首先介绍了ABS算法的研究进展和ABS软件的概况，其次对线性丢番图方程组的解法作了系统的阐述，最后给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法并介绍了在ABS软件方面的部分工作。所取得的成果如下：
1．第二章，我们系统的分析了当前求解单个线性丢番图方程的方法：Rosser算法和Forterbacher算法，求解线性丢番图方程组的的方法：EMAS算法和Contejean算法。
2．第三章在ABS算法的基础上给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法，讨论了相应的ABS性质，并讨论了复杂性分析及其应用。
3．第四章改进了WinABS01的输入界面，网页介绍和安装技术研制的结果，给出了新的ABS软件—WinABS03和ABSDLL03的使用解释
In 1984, Abaffy, Broyden and Spedicato developed a kind of projection algorithms for linear and nonlinear equations - ABS algorithms. Throughout the following twenty years, ABS algorithms have been extended to solve the least squares, the inequality systems, linear programming and nonlinear programming with linear constraints etc. Linear Diophantine equations appear often in modeling and practical application, which play an important part in transportation. So it is particularly necessary to find out the solution of linear diophantine equation. This paper is devoted to studying the linear diophantine equation systematically under the ABS environment.
In this thesis, three parts are considered. Firstly we outline the development of ABS algorithms and the ABS software; Secondly, the approaches for linear Diophantine equations are illuminated in detail; Finally we present the LLIU algorithm and the IILX for linear Diophantine equations, at the same time my work in ABS software is given. The main results obtained in this thesis can be summarized as follows:
1. In chapter two, we analyzed the methods for single linear Diophantine equations: Rosser algorithm and Fortenbacher algorithm; the methods for linear Diophantine equations: EMAS algorithm and Contejean algorithm.
2. In chapter three, the DLU and IILX algorithms for linear Diophantine equations are given based on the ABS algorithms. Corresponding properties, complexity and their application are discussed.
3. Chapter four improves the input interface, net page introduction and installation, the usage of WinABS03 and ABSDLL03 is presented.
本文的研究工作分三个部分，首先介绍了ABS算法的研究进展和ABS软件的概况，其次对线性丢番图方程组的解法作了系统的阐述，最后给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法并介绍了在ABS软件方面的部分工作。所取得的成果如下：
1．第二章，我们系统的分析了当前求解单个线性丢番图方程的方法：Rosser算法和Forterbacher算法，求解线性丢番图方程组的的方法：EMAS算法和Contejean算法。
2．第三章在ABS算法的基础上给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法，讨论了相应的ABS性质，并讨论了复杂性分析及其应用。
3．第四章改进了WinABS01的输入界面，网页介绍和安装技术研制的结果，给出了新的ABS软件—WinABS03和ABSDLL03的使用解释
In 1984, Abaffy, Broyden and Spedicato developed a kind of projection algorithms for linear and nonlinear equations - ABS algorithms. Throughout the following twenty years, ABS algorithms have been extended to solve the least squares, the inequality systems, linear programming and nonlinear programming with linear constraints etc. Linear Diophantine equations appear often in modeling and practical application, which play an important part in transportation. So it is particularly necessary to find out the solution of linear diophantine equation. This paper is devoted to studying the linear diophantine equation systematically under the ABS environment.
In this thesis, three parts are considered. Firstly we outline the development of ABS algorithms and the ABS software; Secondly, the approaches for linear Diophantine equations are illuminated in detail; Finally we present the LLIU algorithm and the IILX for linear Diophantine equations, at the same time my work in ABS software is given. The main results obtained in this thesis can be summarized as follows:
1. In chapter two, we analyzed the methods for single linear Diophantine equations: Rosser algorithm and Fortenbacher algorithm; the methods for linear Diophantine equations: EMAS algorithm and Contejean algorithm.
2. In chapter three, the DLU and IILX algorithms for linear Diophantine equations are given based on the ABS algorithms. Corresponding properties, complexity and their application are discussed.
3. Chapter four improves the input interface, net page introduction and installation, the usage of WinABS03 and ABSDLL03 is presented.
引文
[1] J.Abaffy, C.G.Broyden, E.Spedicato. A class of direct methods for linear equations. Nume. Math.,1984, 45:361-376.
[2] J.Abaffy, E.Spedicato. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. EllisHorwood, Chichester, 1989.
[3] J.Abaffy, Galántai A. Cojugate direction methods for linear and nonlinear systems of algebraic equations. Colloquia Mathematica Societatis János Bolyai 50, Numerical Methods, Miskolc, North-Holland(Stoyan g. editor), 1987, 481-502.
[4] J.Abaffy. A.Galántai, E.Spedicato. The local convergence of ABS methods for nonlinear algebraic equations. Numerische Mathematik, 1987, 51: 429-439, ALso as QDMSIA 14/87.
[5] 张立卫，冯恩民，夏尊铨．优化中的ABS算法引论．大连理工大学出版社，1999．
[6] E.Spedicato, Xia Z, and Zhang L. The implicit LX method of the ABS class, OMS, 1997, 8:99-110, Also as QDMSIA 2/96.
[7] M.T.Vespucci. An ABS implicit Gauss-Cholesky code for ND matrices, Manual 1/68, Progetto Finalizzato Sistemi Informaticie Calcolo Parallelo, IAC, Roma, 1991.
[8] M.Bertocchi, E.Spedicato. A vectorized FORTRAN code of the implicit Gauss-Cholesy algorithm of the ABS class. Manual 1/34, IAC, Rome,1990. J.Abaffy, C.G.Broyden,
[9] M.Bertocchi, E.Spedicato, M.T.Vespucci. A vectorized FORTRAN code of the implicit QR algorithm of the ABS class, Manual 1/56, IAC, Rome, 1991.
[10] E.Bodon, Del Popolo A., Luksan L. and E.Spedicato. Computational experiments with ABS algorithms for overdetermined linear systems, QDMSIA, 2000, 19.
[11] E.Bodon, A.Del Popolo, Luksan L. and E.Spedicato. Computational experiments with ABS algorithms for KKT linear systems, QDMSIA, 2000, 20.
[12] W.A.Blankinship. A new version of the Euclidean algorithm. Amer Math. Monthly, 1963, 70:742-745.
[13] R.Weinslock. Greatest common divisor of several integers and an associated integer diophantine equation. Amer. Math. Monthly, 1960, 67:664-667.
[14] Rosser J.B. A method of computing exact inverses of matrices with integer coefficient. J. Res. Nat. Bur, 1952, 49:349-358.
[15] A.Schrijver. Theory of Linear and Integer programming. John Wiley and Sons, 1986.
[16] Esmaeili H, Mahdavi-Amiri N and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90:101-115.
[17] E. Egervary-Aufloesung eines homogenes linearen diophantinen Gleichengsystemen mit Hilf von Projektormatrizen. Publ. Math. Debrecen, 1955-56, 4:481-483.
[18] E.Egervary. On rank-diminishing operations and their applications to the solution of linear equations. ZAMP, 1960, 9:376-386.
[19] E.Contejean and H.Devie. An efficient incremental algorithm for solving systems of linear
Diophantine equations. Information and Computation, 1994, 113:143-172.
[20] Ajili.Farid, Contejean.Evelyne. Avoiding slack variables in the solving of linear diophantine equations and inequations. Theoretical Computer Science, 1997, 173:183-208.
[21] M.Clausen, and A.Fortenbacher. Efficient solution of linear Diophantine equations. J. Symbolic Comput, 1989, 8(1&2):201-216.
[22] G.H.Bradley. Algorithm and bound for the greatest common divisor of n integers. Community ACM, 1970, 13:433-436.
[23] 薛方，郑辉，范小寅．线性丢番图方程组的一个数值解法．数学通报，1994，10：45-47．
[24] D.Goldford and M.J.Todd. Linear Programm in: Optimization by ewhauser Rinnooy Kar and Todd (Handbooks in OR and MS Volumn 1). 1989.73-170.
[25] M-H Li. On Integer Solution of Exponential Diophantine Equations. Chinese Science Abstracts Series A, 1995, 14(2):5--6.
[26] B.Mauro, V.Maria Elena. Behavior decompositions and two_sided diophantine equations, Automatics, 2001, 37:1387-1395.
[27] Petho.A, Tichy.R.F, On Two-parametric Quartic Families of Diophantine problem. Journal of Symbolic Computation, 1998, 26:151-171.
[28] A. Dujella. An Absolute Bound for the Size of Diophantine m-Tuple. Journal of Number Theory, 2001, 89(1):126--150.
[29] S.A. Arif, Abu. Muriefah, S. Fadwa. On the Diophantine Equation x~2+q~(2k+1)=y~n. Journal of Number Theory, 2002, 95(1):95--100.
[30] J.Springer. Exact solution of general integer systems of linear equations, ACM transactions on Mathematical Software, 1986,12:51-61.
[31] Huang H. Y. A direct method for the general solution of a system of linear equations. JOTA, 1975, 16: 429-445.
[32] Bodon E. Numerical results on the ABS algorithms on upper banded systems of linear least squares. QDMSIA, 1993, 18/92.
[33] Bodon E. Biconjugate algorithms in the ABS class Ⅰ: alternative formulation and theoretical properties. QDMSIA, 1989, 3/89
[34] 李兴．《隐式LU、LX算法误差分析及ABS软件》(硕士毕业论文)，2003．
[35] F.Miguel, Tomás.Ana Paula. A Fast Method for Finding the Basis of Non-negative Solutions to a Linear Diophantine Equation. Journal of Symbolic Computation, 1995, 19:507-526.
[36] J.Abaffy, M.Bertocchi, A.Torrieor. Analysis of a subclass of nonsingular M-matrices and its economic applications, QDMSIA, 1992, 22/91.
[37] E.Spedicato, Xia Z. and Zhang L. ABS algorithms for linear equations and applications to optimization, in G. Winter Althaus and Spedicato(eds.), Algorithms for Lasrge Scale Linear algebraic Systems: Applications in Science and Engineering, Series C: Mathematical and Physical Sciences--Vol 508, Kluwer Academic Publishers, The Netherlands, 1998. 291-319.
[38] E.Spedicato, Xia Z. and Zhang L.. ABS algorithms for linear equations and optimization. Journal
of Computational and Applied Mathematics, 2000, 124:155-170
[39] Xia Z.Q. Derivation of some linear transformations via the ABS algorithm. 1992, ABSC1, 95-110.
[40] Xia Z., Zhang L. ABS algorithms for solving linearly constrained optimization problems via the active set strategy. Ricerca Operativa, 2003, 31:98-100.
[41] Xia Z., Liu Y. and Zhang L. Application of a representation of ABS updating matrices tO linearly constrained optimization Ⅰ. Northeast Operational Research, 1992, 7:1-9.
[42] Xia Z. An efficient ABS algorithm for linearly constrained optimization 1994, QDMSIA, 15/94.
[43] 周奇兵．《V1.0／2001 ABS软件的研制》(硕士毕业论文)，2000．
[44] 刘莹．《ABS SOFTWARE研究的新进展，ABSDLL01&WinABS01》(硕士毕业论文)，2001．
[45] Pottier, L. Minimal solutions of linear diophantine systems: Bounds and algorithms. in "proceedings, Fourth International Conference on Rewriting Techniques and Applications, Como, Italy," 1991, 162-173.
[46] Domenjoud, E, Dutils pour la deduction automatique dans les theories associatives- commutatives, Thèse de doctorat de l'université de Nancy Ⅰ.
[47] E.Spedicato. A class of Direct methods for linear systems: generalization, nonsingular representation and other tales, Report SQFMAT 21/82, IAC, Rome, 1982.
[48] S.Morita, H.M.Salkin. Using the Blankinship algorithm to find the general solution of a linear Diophantine equation. Acts Inf., 1980, 13:379-382.
[1] J.Abaffy, C.G.Broyden, E.Spedicato. A class of direct methods for linear equations. Nume. Math.,1984, 45:361-376.
[2] J.Abaffy, E.Speclicato. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. EllisHorwood, Chichester, 1989.
[5] 张立卫，冯恩民，夏尊铨．优化中的ABS算法引论．大连理工大学出版社，1999．
[6] E.Spedicato, Xia Z, and Zhang L. The implicit LX method of the ABS class, OMS, 1997, 8:99-110, Also as QDMSIA 2/96.
[16] Esmaeili H, Mahdavi-Amiri N and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90:101-115.
[19] E.Contejean and H.Devie. An efficient incremental algorithm for solving systems of linear Diophantine equations. Information and Computation, 1994, 113:143-172.
[20] Ajili.Farid, Contejean.Evelyne. Avoiding slack variables in the solving of linear diophantine equations and inequations. Theoretical Computer Science, 1997, 173:183-208.
[23] 薛方，郑辉，范小寅．线性丢番图方程组的一个数值解法．数学通报，1994，10：45-47．
[34] 李兴．《隐式LU、LX算法误差分析及ABS软件》(硕士毕业论文)，2003．
[38] E.Spedicato, Xia Z. and Zhang L.. ABS algorithms for linear equations and optimization. Journal of Computational and Applied Mathematics, 2000, 124: 155-170.
[44] 刘莹．《ABS SOFTWARE研究的新进展，ABSDLL01&WinABS01》(硕士毕业论文)，2001．
[2] J.Abaffy, E.Spedicato. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. EllisHorwood, Chichester, 1989.
[3] J.Abaffy, Galántai A. Cojugate direction methods for linear and nonlinear systems of algebraic equations. Colloquia Mathematica Societatis János Bolyai 50, Numerical Methods, Miskolc, North-Holland(Stoyan g. editor), 1987, 481-502.
[4] J.Abaffy. A.Galántai, E.Spedicato. The local convergence of ABS methods for nonlinear algebraic equations. Numerische Mathematik, 1987, 51: 429-439, ALso as QDMSIA 14/87.
[5] 张立卫，冯恩民，夏尊铨．优化中的ABS算法引论．大连理工大学出版社，1999．
[6] E.Spedicato, Xia Z, and Zhang L. The implicit LX method of the ABS class, OMS, 1997, 8:99-110, Also as QDMSIA 2/96.
[7] M.T.Vespucci. An ABS implicit Gauss-Cholesky code for ND matrices, Manual 1/68, Progetto Finalizzato Sistemi Informaticie Calcolo Parallelo, IAC, Roma, 1991.
[8] M.Bertocchi, E.Spedicato. A vectorized FORTRAN code of the implicit Gauss-Cholesy algorithm of the ABS class. Manual 1/34, IAC, Rome,1990. J.Abaffy, C.G.Broyden,
[9] M.Bertocchi, E.Spedicato, M.T.Vespucci. A vectorized FORTRAN code of the implicit QR algorithm of the ABS class, Manual 1/56, IAC, Rome, 1991.
[10] E.Bodon, Del Popolo A., Luksan L. and E.Spedicato. Computational experiments with ABS algorithms for overdetermined linear systems, QDMSIA, 2000, 19.
[11] E.Bodon, A.Del Popolo, Luksan L. and E.Spedicato. Computational experiments with ABS algorithms for KKT linear systems, QDMSIA, 2000, 20.
[12] W.A.Blankinship. A new version of the Euclidean algorithm. Amer Math. Monthly, 1963, 70:742-745.
[13] R.Weinslock. Greatest common divisor of several integers and an associated integer diophantine equation. Amer. Math. Monthly, 1960, 67:664-667.
[14] Rosser J.B. A method of computing exact inverses of matrices with integer coefficient. J. Res. Nat. Bur, 1952, 49:349-358.
[15] A.Schrijver. Theory of Linear and Integer programming. John Wiley and Sons, 1986.
[16] Esmaeili H, Mahdavi-Amiri N and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90:101-115.
[17] E. Egervary-Aufloesung eines homogenes linearen diophantinen Gleichengsystemen mit Hilf von Projektormatrizen. Publ. Math. Debrecen, 1955-56, 4:481-483.
[18] E.Egervary. On rank-diminishing operations and their applications to the solution of linear equations. ZAMP, 1960, 9:376-386.
[19] E.Contejean and H.Devie. An efficient incremental algorithm for solving systems of linear
Diophantine equations. Information and Computation, 1994, 113:143-172.
[20] Ajili.Farid, Contejean.Evelyne. Avoiding slack variables in the solving of linear diophantine equations and inequations. Theoretical Computer Science, 1997, 173:183-208.
[21] M.Clausen, and A.Fortenbacher. Efficient solution of linear Diophantine equations. J. Symbolic Comput, 1989, 8(1&2):201-216.
[22] G.H.Bradley. Algorithm and bound for the greatest common divisor of n integers. Community ACM, 1970, 13:433-436.
[23] 薛方，郑辉，范小寅．线性丢番图方程组的一个数值解法．数学通报，1994，10：45-47．
[24] D.Goldford and M.J.Todd. Linear Programm in: Optimization by ewhauser Rinnooy Kar and Todd (Handbooks in OR and MS Volumn 1). 1989.73-170.
[25] M-H Li. On Integer Solution of Exponential Diophantine Equations. Chinese Science Abstracts Series A, 1995, 14(2):5--6.
[26] B.Mauro, V.Maria Elena. Behavior decompositions and two_sided diophantine equations, Automatics, 2001, 37:1387-1395.
[27] Petho.A, Tichy.R.F, On Two-parametric Quartic Families of Diophantine problem. Journal of Symbolic Computation, 1998, 26:151-171.
[28] A. Dujella. An Absolute Bound for the Size of Diophantine m-Tuple. Journal of Number Theory, 2001, 89(1):126--150.
[29] S.A. Arif, Abu. Muriefah, S. Fadwa. On the Diophantine Equation x~2+q~(2k+1)=y~n. Journal of Number Theory, 2002, 95(1):95--100.
[30] J.Springer. Exact solution of general integer systems of linear equations, ACM transactions on Mathematical Software, 1986,12:51-61.
[31] Huang H. Y. A direct method for the general solution of a system of linear equations. JOTA, 1975, 16: 429-445.
[32] Bodon E. Numerical results on the ABS algorithms on upper banded systems of linear least squares. QDMSIA, 1993, 18/92.
[33] Bodon E. Biconjugate algorithms in the ABS class Ⅰ: alternative formulation and theoretical properties. QDMSIA, 1989, 3/89
[34] 李兴．《隐式LU、LX算法误差分析及ABS软件》(硕士毕业论文)，2003．
[35] F.Miguel, Tomás.Ana Paula. A Fast Method for Finding the Basis of Non-negative Solutions to a Linear Diophantine Equation. Journal of Symbolic Computation, 1995, 19:507-526.
[36] J.Abaffy, M.Bertocchi, A.Torrieor. Analysis of a subclass of nonsingular M-matrices and its economic applications, QDMSIA, 1992, 22/91.
[37] E.Spedicato, Xia Z. and Zhang L. ABS algorithms for linear equations and applications to optimization, in G. Winter Althaus and Spedicato(eds.), Algorithms for Lasrge Scale Linear algebraic Systems: Applications in Science and Engineering, Series C: Mathematical and Physical Sciences--Vol 508, Kluwer Academic Publishers, The Netherlands, 1998. 291-319.
[38] E.Spedicato, Xia Z. and Zhang L.. ABS algorithms for linear equations and optimization. Journal
of Computational and Applied Mathematics, 2000, 124:155-170
[39] Xia Z.Q. Derivation of some linear transformations via the ABS algorithm. 1992, ABSC1, 95-110.
[40] Xia Z., Zhang L. ABS algorithms for solving linearly constrained optimization problems via the active set strategy. Ricerca Operativa, 2003, 31:98-100.
[41] Xia Z., Liu Y. and Zhang L. Application of a representation of ABS updating matrices tO linearly constrained optimization Ⅰ. Northeast Operational Research, 1992, 7:1-9.
[42] Xia Z. An efficient ABS algorithm for linearly constrained optimization 1994, QDMSIA, 15/94.
[43] 周奇兵．《V1.0／2001 ABS软件的研制》(硕士毕业论文)，2000．
[44] 刘莹．《ABS SOFTWARE研究的新进展，ABSDLL01&WinABS01》(硕士毕业论文)，2001．
[45] Pottier, L. Minimal solutions of linear diophantine systems: Bounds and algorithms. in "proceedings, Fourth International Conference on Rewriting Techniques and Applications, Como, Italy," 1991, 162-173.
[46] Domenjoud, E, Dutils pour la deduction automatique dans les theories associatives- commutatives, Thèse de doctorat de l'université de Nancy Ⅰ.
[47] E.Spedicato. A class of Direct methods for linear systems: generalization, nonsingular representation and other tales, Report SQFMAT 21/82, IAC, Rome, 1982.
[48] S.Morita, H.M.Salkin. Using the Blankinship algorithm to find the general solution of a linear Diophantine equation. Acts Inf., 1980, 13:379-382.
[1] J.Abaffy, C.G.Broyden, E.Spedicato. A class of direct methods for linear equations. Nume. Math.,1984, 45:361-376.
[2] J.Abaffy, E.Speclicato. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. EllisHorwood, Chichester, 1989.
[5] 张立卫，冯恩民，夏尊铨．优化中的ABS算法引论．大连理工大学出版社，1999．
[6] E.Spedicato, Xia Z, and Zhang L. The implicit LX method of the ABS class, OMS, 1997, 8:99-110, Also as QDMSIA 2/96.
[16] Esmaeili H, Mahdavi-Amiri N and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90:101-115.
[19] E.Contejean and H.Devie. An efficient incremental algorithm for solving systems of linear Diophantine equations. Information and Computation, 1994, 113:143-172.
[20] Ajili.Farid, Contejean.Evelyne. Avoiding slack variables in the solving of linear diophantine equations and inequations. Theoretical Computer Science, 1997, 173:183-208.
[23] 薛方，郑辉，范小寅．线性丢番图方程组的一个数值解法．数学通报，1994，10：45-47．
[34] 李兴．《隐式LU、LX算法误差分析及ABS软件》(硕士毕业论文)，2003．
[38] E.Spedicato, Xia Z. and Zhang L.. ABS algorithms for linear equations and optimization. Journal of Computational and Applied Mathematics, 2000, 124: 155-170.
[44] 刘莹．《ABS SOFTWARE研究的新进展，ABSDLL01&WinABS01》(硕士毕业论文)，2001．