1. NCCU Academic Hub
  2. Publications
  3. College of Science
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 在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 (日期) 1990en_US
dc.date (日期) 1989en_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) B2002005451en_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/#B2002005451en_US
dc.title (題名) 在Transputer系統上發展平行疊代法解線性互補問題zh_TW
dc.title (題名) parallel Iterative Methods for Linear Complementarity Problem on Transputeren_US
dc.type (資料類型) thesisen_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