學術產出-Theses
Article View/Open
Publication Export
-
題名 在Transputer系統上發展平行疊代法解線性互補問題
parallel Iterative Methods for Linear Complementarity Problem on Transputer作者 陳順吉 貢獻者 楊建民
陳順吉日期 1990
1989上傳時間 3-May-2016 14:17:33 (UTC+8) 摘要 本論文條發展平行疊代法( Parallel Iterative Methods ),以求取數學規畫( Mathematical Programming )中之線性互補問題( Linear Complementarity Problem,LCP ) 的數值解。發展線性互補問題的平行疊代法，有助於人們應用平行或超級電腦快速計算的能力，有效解決大型科學計算( large-scale scientific computing)的問題，而這些問題廣泛的存在於國防軍事、工程、經濟及管理科學的領域之中。 參考文獻 [1] B. H. Ahn [1981]. "Computation of Asymmetric Linear Complementarity Problem by Iterative Method",Journal of Optimization Theory and Applications 33.pp. 175-185. [2] M. Aganagic [1978]. "Iterative Methods for Linear Complementarity Problems," Technical Report SOL 78-10 Systems Optimization Laboratory. Department of Operations Research. Stanford University. [3] D. P. Bertsekas [1983]. "Distributed Asynchronous Computation of Fixed Point". Mathematical Programming 27. Pp. 107-120. [4] G. M. Baudet [1978]. "Asynchronous Iterative Methods for Multiprocessors", Journal of the Association for Computing Machinery 22, PP. 226-244. [5] C. W. Cryer [1971]. "The Solution of a Quadratic Programming Problem Using Systematic Overrelaxation," SIAM Control 9. pp. 385-392. [6] R. W. CottIe, G. H. Golub and R. S. Sacher [1978], "On the Solution of Large Structured Linear Complementarity Problems: The Block Partitioned Case", Applied Mathematics and Optimization 4. PP. 347-363. [7] Y. C. Cheng [1981], "Iterative Methods for Solving Linear Complementarity and Linear Programming Problems", Ph.D. dissertation, Department of Computer Science, University of Wisconsin (Madison Wisconsin). [8] Y. C. Cheng [1984], "On the Gradient-Projection Method for Solving the Nonsymmetric Linear Complementarity Problem",Journal of Optimization Theory and Applications 43, PP. 527-541. [9] G. B. Dantzig [1963], Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey. [10] G. B. Dantzig, M. A. H. Dempster and M. J. Kallio (Eds.) [1981], Large-Scale Linear Programming, Vol. 1. Proceedings of a IIASA workshop 2-6 June 1980, International Institute for Applied Systems Analysis, Laxenburg, Austria. [11] B. C. Eaves [1971], "On Quadratic Programming",Management Science 17, Pp. 698-711. [12] C. Hildreth [1957], A Quadratic Programming Procedure, Naval Research Logistics Quarterly 4, pp. 79-85,Erratum, ibid, p.361. [13] R. W. Hockney [1985]. "MIMD Computing In the USA – 1984”, Parallel Computing 2, PP. 119-136. [14] N. Karmarkar [1984], "A New Polynomial-Time Algorithm for Linear Programming," Combinatorica 4, Pp. 375-395. [15] H. T. Kung [1976], "Synchronized and Asynchronous Parallel Algorithms for Multiprocessors", in J. F. Traub ed., Algorithms and Complexity: New Directions and Recent Results (Academic Press) pp. 153-200. [16] Y. Y. Lin and J. S. Pang [1987]. "Iterative Methods for Large Convex Quadratic Programs: A Survey", SIAM Journal on Control and Optimization 25.pp. 383-411. [17] O. L. Mangasarian [1977]. "Solution of Symmetric Linear Complementarity Problems by Iterative Methods". Journal of Optimization Theory and Applications 22. pp.465-485. [18] O. L. Mangasarian [1981]. "Iterative Solution of Linear Programs." SIAM Journal on Numerical Analysis 18.pp.606-614. [19] O. L. Mangasarian [1984a], "Normal Solutions of Linear Programs." Mathematical Programming Study 22. pp.206-216. [20] O. L. Mangasarian [1984b], "Sparsity Preserving SOR Algorithms for Separable Quadratic and Linear Programming Problem," Computers and Operations Research . Vol. 11. pp. 105-112. [21] O. L. Mangasarian and R. De Leone [1986a]. "Parallel Successive Overrelaxation Methods for Symmetric Linear Complementarity Problems and Linear Programs". Mathematics Research Center Report #2947. University of Wisconsin (Madison. Wisconsin). [22] D. P. O`Leary and R. E. White [1985]. "Multi-splittings of Matrices and Parallel Solution of Linear Systems", SIAM Journal on Algebraic and Discrete Mathematics 6, pp. 630-640. [23] J. M. Ortega and W. C. Rheinboldt [1970], Iterative Solution of Nonlinear Equations in Several Variables. Academic Press. [24] J. M. Ortega and R. G. Voigt [1985]. "Solution of Partial Differerntial Equations on Vector and Parallel Computers". SIAM Review Vol 27. No.2. pp. 149-213. [25] J. S. Pang [1982]. "On the Convergence of a Basic Iterative Method for the Implicit Complementarity Problem", Journal of Optimization Theory and Applications 37. pp. 149-162. [26] J. S. Pang [1984a],"Necessary and Sufficient Conditions for the Convergence of Iterative Methods for the Linear Complementarity Problem", Journal of Optimization Theory and Applications 42, Pp. 1-18. [27] J. S. Pang [1986a], "More Results on the Convergence of Iterative Methods for the Symmetric Linear Complementarity Problem", Journal of Optimization Theory and Applications 49, pp. 107-134. [28] J. S. Pang and J. M. Yang [1987a], "Two-stage Parallel Iterative Methods for the Symmetric Linear Complementarity Problem," to appear in Annals of Operations Research: Parallel Optimization on Novel Computer Architectures (1988). [29] J. S. Pang and J. M. Yang [1987c], “Computational Experience with Solving Linear Programs by Iterative Methods on CRAY Supercomputers", Proceedings of the Third Science and Engineering Symposium, Minneapolis, Minnesota (1987). [30] Michael J. Quinn [1987],"Design efficient Algorithms for Parallel Computer", McGraw-Hill Series In Supercomputer and Artificial Intelligence. [31] F. Robert [1969], "Blocs-H-Matrices et Convergence des Methodes Iterative Classiques par Blocs", Linear Algebra and its Applications 2, Pp. 223-265. [32] S. M. Robinson [1980],"Strongly Regular Generalized Equations," Mathematics of Operations Research 5, Pp. 43-62. [33] T. H. Shiau [1984]. "An Iterative Scheme for Linear Complementarity Problems," Technical Report #2737, Mathematices Research Center. University of Wisconsin-Madison. [34] J. Traub [1964]. Iterative Methods for the Solution of Equations, Prentice Hall. Englewood Cliffs, New Jersey. [35] R. Varga [1968]."Matrix Iterative Analysis",Prentice-Hall, Englewood Cliffs. [36] J. M. Yang [1987], "Parallel Iterative Methods for Complementarity and Linear Programming Problems" Ph.D. dissertation. School of Management Science, University of Texas at Dallas. [37] J.M. Yang and Tai-Sheng Chang [1988], " Semi-Asynchronous two-stage Iterative Methods for the Symmetric Linear Complementarity Problem", Contributed Paper for the 13th International Symposium on Mathematical Programming Tokyo, Japan . [38] THE TRANSPUTER APPLICATION NOTEBOOK Architecture and Software INMOS [1989] [39] James M Ortega [1972]. " Numerical analysis ; a second course ", New York , Academic Press . 描述 碩士
國立政治大學
應用數學系資料來源 http://thesis.lib.nccu.edu.tw/record/#B2002005451 資料類型 thesis dc.contributor.advisor 楊建民 zh_TW dc.contributor.author (Authors) 陳順吉 zh_TW dc.creator (作者) 陳順吉 zh_TW dc.date (日期) 1990 en_US dc.date (日期) 1989 en_US dc.date.accessioned 3-May-2016 14:17:33 (UTC+8) - dc.date.available 3-May-2016 14:17:33 (UTC+8) - dc.date.issued (上傳時間) 3-May-2016 14:17:33 (UTC+8) - dc.identifier (Other Identifiers) B2002005451 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/90186 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description.abstract (摘要) 本論文條發展平行疊代法( Parallel Iterative Methods ),以求取數學規畫( Mathematical Programming )中之線性互補問題( Linear Complementarity Problem,LCP ) 的數值解。發展線性互補問題的平行疊代法，有助於人們應用平行或超級電腦快速計算的能力，有效解決大型科學計算( large-scale scientific computing)的問題，而這些問題廣泛的存在於國防軍事、工程、經濟及管理科學的領域之中。 zh_TW dc.description.tableofcontents 第一章 導論. . . . . . . . . . . . . . . . . . . . . . . . ..1 第二章Transputer和Occam . . . . . . . . . . . . . . . . .. 5 § 2-1 Transputer 的基本概念. . . . . . . . . . . . . . . . ..5 § 2-2 Occam 語言 . . . . . . . . . . . . . . . .. 9 § 2-3 通訊( Communication ) . . . . . . . . . . . . . . . . .. 17 第三章 線性互補問題. . . . . . . . . . . . . . . . ..22 § 3-1 簡介. . . . . . . . . . . . . . . . ..22 § 3-2 二階段同步疊代法. . . . . . . . . . . . . . . . ..24 § 3-3 二階段半非同步疊代法. . . . . . . . . . . . . . . . ..27 § 3-4 非同步疊代法. . . . . . . . . . . . . . . . .. 29 第四章 非同步法的收斂理論. . . . . . . . . . . . . . . . .. 32 第五章 演算法之執行與結果分析. . . . . . . . . . . . . . . . . . . . . . . . . . . 38 § 5-1 演算法之執行. . . . . . . . . . . . . . . .. 38 § 5-2 結果分析. . . . . . . . . . . . . . . . .. 42 第六章 結論 . . . . . . . . . . . . . . . . ..45 參考文獻. . . . . . . . . . . . . . . . ..46 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#B2002005451 en_US dc.title (題名) 在Transputer系統上發展平行疊代法解線性互補問題 zh_TW dc.title (題名) parallel Iterative Methods for Linear Complementarity Problem on Transputer en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] B. H. Ahn [1981]. "Computation of Asymmetric Linear Complementarity Problem by Iterative Method",Journal of Optimization Theory and Applications 33.pp. 175-185. [2] M. Aganagic [1978]. "Iterative Methods for Linear Complementarity Problems," Technical Report SOL 78-10 Systems Optimization Laboratory. Department of Operations Research. Stanford University. [3] D. P. Bertsekas [1983]. "Distributed Asynchronous Computation of Fixed Point". Mathematical Programming 27. Pp. 107-120. [4] G. M. Baudet [1978]. "Asynchronous Iterative Methods for Multiprocessors", Journal of the Association for Computing Machinery 22, PP. 226-244. [5] C. W. Cryer [1971]. "The Solution of a Quadratic Programming Problem Using Systematic Overrelaxation," SIAM Control 9. pp. 385-392. [6] R. W. CottIe, G. H. Golub and R. S. Sacher [1978], "On the Solution of Large Structured Linear Complementarity Problems: The Block Partitioned Case", Applied Mathematics and Optimization 4. PP. 347-363. [7] Y. C. Cheng [1981], "Iterative Methods for Solving Linear Complementarity and Linear Programming Problems", Ph.D. dissertation, Department of Computer Science, University of Wisconsin (Madison Wisconsin). [8] Y. C. Cheng [1984], "On the Gradient-Projection Method for Solving the Nonsymmetric Linear Complementarity Problem",Journal of Optimization Theory and Applications 43, PP. 527-541. [9] G. B. Dantzig [1963], Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey. [10] G. B. Dantzig, M. A. H. Dempster and M. J. Kallio (Eds.) [1981], Large-Scale Linear Programming, Vol. 1. Proceedings of a IIASA workshop 2-6 June 1980, International Institute for Applied Systems Analysis, Laxenburg, Austria. [11] B. C. Eaves [1971], "On Quadratic Programming",Management Science 17, Pp. 698-711. [12] C. Hildreth [1957], A Quadratic Programming Procedure, Naval Research Logistics Quarterly 4, pp. 79-85,Erratum, ibid, p.361. [13] R. W. Hockney [1985]. "MIMD Computing In the USA – 1984”, Parallel Computing 2, PP. 119-136. [14] N. Karmarkar [1984], "A New Polynomial-Time Algorithm for Linear Programming," Combinatorica 4, Pp. 375-395. [15] H. T. Kung [1976], "Synchronized and Asynchronous Parallel Algorithms for Multiprocessors", in J. F. Traub ed., Algorithms and Complexity: New Directions and Recent Results (Academic Press) pp. 153-200. [16] Y. Y. Lin and J. S. Pang [1987]. "Iterative Methods for Large Convex Quadratic Programs: A Survey", SIAM Journal on Control and Optimization 25.pp. 383-411. [17] O. L. Mangasarian [1977]. "Solution of Symmetric Linear Complementarity Problems by Iterative Methods". Journal of Optimization Theory and Applications 22. pp.465-485. [18] O. L. Mangasarian [1981]. "Iterative Solution of Linear Programs." SIAM Journal on Numerical Analysis 18.pp.606-614. [19] O. L. Mangasarian [1984a], "Normal Solutions of Linear Programs." Mathematical Programming Study 22. pp.206-216. [20] O. L. Mangasarian [1984b], "Sparsity Preserving SOR Algorithms for Separable Quadratic and Linear Programming Problem," Computers and Operations Research . Vol. 11. pp. 105-112. [21] O. L. Mangasarian and R. De Leone [1986a]. "Parallel Successive Overrelaxation Methods for Symmetric Linear Complementarity Problems and Linear Programs". Mathematics Research Center Report #2947. University of Wisconsin (Madison. Wisconsin). [22] D. P. O`Leary and R. E. White [1985]. "Multi-splittings of Matrices and Parallel Solution of Linear Systems", SIAM Journal on Algebraic and Discrete Mathematics 6, pp. 630-640. [23] J. M. Ortega and W. C. Rheinboldt [1970], Iterative Solution of Nonlinear Equations in Several Variables. Academic Press. [24] J. M. Ortega and R. G. Voigt [1985]. "Solution of Partial Differerntial Equations on Vector and Parallel Computers". SIAM Review Vol 27. No.2. pp. 149-213. [25] J. S. Pang [1982]. "On the Convergence of a Basic Iterative Method for the Implicit Complementarity Problem", Journal of Optimization Theory and Applications 37. pp. 149-162. [26] J. S. Pang [1984a],"Necessary and Sufficient Conditions for the Convergence of Iterative Methods for the Linear Complementarity Problem", Journal of Optimization Theory and Applications 42, Pp. 1-18. [27] J. S. Pang [1986a], "More Results on the Convergence of Iterative Methods for the Symmetric Linear Complementarity Problem", Journal of Optimization Theory and Applications 49, pp. 107-134. [28] J. S. Pang and J. M. Yang [1987a], "Two-stage Parallel Iterative Methods for the Symmetric Linear Complementarity Problem," to appear in Annals of Operations Research: Parallel Optimization on Novel Computer Architectures (1988). [29] J. S. Pang and J. M. Yang [1987c], “Computational Experience with Solving Linear Programs by Iterative Methods on CRAY Supercomputers", Proceedings of the Third Science and Engineering Symposium, Minneapolis, Minnesota (1987). [30] Michael J. Quinn [1987],"Design efficient Algorithms for Parallel Computer", McGraw-Hill Series In Supercomputer and Artificial Intelligence. [31] F. Robert [1969], "Blocs-H-Matrices et Convergence des Methodes Iterative Classiques par Blocs", Linear Algebra and its Applications 2, Pp. 223-265. [32] S. M. Robinson [1980],"Strongly Regular Generalized Equations," Mathematics of Operations Research 5, Pp. 43-62. [33] T. H. Shiau [1984]. "An Iterative Scheme for Linear Complementarity Problems," Technical Report #2737, Mathematices Research Center. University of Wisconsin-Madison. [34] J. Traub [1964]. Iterative Methods for the Solution of Equations, Prentice Hall. Englewood Cliffs, New Jersey. [35] R. Varga [1968]."Matrix Iterative Analysis",Prentice-Hall, Englewood Cliffs. [36] J. M. Yang [1987], "Parallel Iterative Methods for Complementarity and Linear Programming Problems" Ph.D. dissertation. School of Management Science, University of Texas at Dallas. [37] J.M. Yang and Tai-Sheng Chang [1988], " Semi-Asynchronous two-stage Iterative Methods for the Symmetric Linear Complementarity Problem", Contributed Paper for the 13th International Symposium on Mathematical Programming Tokyo, Japan . [38] THE TRANSPUTER APPLICATION NOTEBOOK Architecture and Software INMOS [1989] [39] James M Ortega [1972]. " Numerical analysis ; a second course ", New York , Academic Press . zh_TW
