有限型多阶段决策问题的并行算法

有限型多阶段决策问题的并行算法 A PARALLEL ALGORITHM TO THE MULTISTAGE DECISION PROBLEM OF FINITE TYPE 郑慧娆 Zheng Huirao 1 first-author 樊戎 Fan Rong 1 费浦生 Fei Pusheng 1 武汉大学数学系 武汉大学数学系 Department of Mathematics,Wuhan University Department of Mathematics,Wuhan University 讨论了在ＭＩＭＤ并行系统上，基于嘉量原理的摹矩阵连摹乘积求多阶段有向图最优路的并行算法．给出了选择顺推方式或逆推方式计算连摹乘的一个计算过程，提出了一个分派到各台处理机的任务基本均衡的ｐ一分划算法，并详细讨论了并行计算的实现，给出了数值试验实例． in the paper we discuss a parallel algorithm to the optimum paths in a multistage directed graph based on the Jar-metric prineiple to compute the modi-matrix chain products. We suggest a procedure of choosing the forward process or the backward process to yield modi-matrix chain products,put forward a p-partitioning algorithm to make the assignment of tasks to every processor achieve load balancing as much as possible,discuss the parallel implementation in detail and show some numerical experiments. 多阶段决策 嘉量原理 摹矩阵 连摹乘井行计算 p－分划算法 multistage decision Jar-metric principle modi-matrix parallel computationof modi-matrix chain products p-partitioning algorithm O221.3 国家攀登项目,国家自然科学基金 1995-01-01 2021-04-01 1