极小化完工时间和的有界批调度问题

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.     

n-单形的m阶等分点集与零多项式的判定

通过递归方法定义了N-单形的m阶等分点集.证明了n元m次多项式f为零多项式的充要条件是:f在任意n-单形的m阶等分点处的取值为0.然后将这一结果应用到插值方法的适定点问题和几何定理机器证明的数值并行法.     

最优(m,n,4,1)光正交签名码的进一步结果

为支持高速多址网络中二维图像的传输,Kitayama首次提出码分多址并行图像传输系统的概念.作为码分多址并行图像传输系统的首选光地址码,光正交签名码(OOSPC)是一族具有良好相关性的Hamming重量为k的m×n(0,1)-矩阵.用Θ(m,n,k,λ)表示所有参数为(m,n,k,λ)的OOSPC中码字容量可能的最大值,则称码字容量为Θ(m,n,k,λ)的(m,n,k,λ)-OOSPC是最优的.本文将针对满足下列条件之一的正整数m和n:(1)mn≡8,16(mod 24),gcd(m,n,2)=2,且mn≡16(mod 32)和gcd(m,n,4)=2不同时成立,其中m和n的所有奇素因子均模6余1;(2)mn≡0(mod 24)且gcd(m,n,6)=2,证明Θ(m,n,4,1)=|mn-1/12|,即构造码字容量为|mn-1/12|的最优(m,n,4,1)-OOSPC.     

分布式系统上并行矩阵乘法

1．引言矩阵乘法是最简单的数学问题,同时由于其计算量大而通常被用来对计算机的浮点运算速度进行测试,尤其是对于并行计算机,其并行效率的好坏可通过这个简单的问题反应出来,如果在这个问题上都不能取得很好的效果,对于其它问题就更不可能．此外,为了提高计算性能,对求解数值代数中的问题最终会归结到有矩阵乘法的计算,如LAPACK,ScaLAPACK等,因此有效地并行计算矩阵乘法在实际应用中是非常重要的．矩阵乘法是做C＝A×B,其中A是m×k阵,B是k×n阵,C是m×n阵．设矩阵A,B可以分成p×p块矩阵,即A＝（Ai,j）p×p,B＝（B…     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

并行推理机RAP/LOP-PIM及其优化并行编译器的设计与实现

本文重点论述并行推理机RAP/LOP-PIM及其优化并行编译器的设计与实现.首先,我们简要介绍并行执行模型RAP/LOP.然后给出基于RAP/LOP模型的并行抽象机和相应的体系结构.接着论述并行编译器的优化实现技术.最后通过模拟实验对系统性能进行了评估.     

同时求多项式全部零点的一族快速并行迭代和区间迭代(Ⅱ)

本文对[1]所提出的一族同时求多项式全部零点的并行迭代兼区间迭代加以进一步的发展。首先,作为纯粹的并行迭代法,我们在§2把每步并行迭代扩展为q个并行子步,这样得到的并行迭代法对只有单零点的多项式的全部零点的收敛是q(p 1)阶的。值得注意的是,在这里阶的提高大大超过了每步计算代价的增加,例如,当q=2时,每步     

一类刚性大系统的并行组合方法

本文针对一类分解的刚性大系统提出一种并行组合方法（ＰＣＭ）,该方法将系统分割的并行化方法与并行化方法相结合,采用并行显式Ｒｕｎｇｅ－ｋｕｔｔａ（ＲＫ）方法求解非刚性子系统,采用并行Ｒｏｓｅｎｂｒｏｃｋ方法求解刚性子系统,文中讨论了方法的相容阶、并对方法的收敛性进行了分析,数值结果表明该方法对于分解的刚性大系统的求解是实用和有效的。     

服务台可并行服务的排队系统研究

本文研究服务台可以同时并行服务多个顾客的排队系统.目前这一类新的排队问题在实践中经常出现,但却缺乏相应的理论模型,实际决策都是凭经验进行的.针对这一现状,本文首先构建相应的并行排队模型,使得服务台数量、可并行服务的最大顾客数量等重要决策变得科学化.进一步,针对并行排队模型比较复杂、求解比较困难的情况,构建相应的分散排队模型与集中排队模型,它们的求解简单方便,其结果可以有效的逼近原并行排队模型的最优解.     

解非线性方程组的并行多重分裂区间AOR方法

解线性方程组与非线性方程组的并行分裂算法是适合于并行计算的一类很有效算法,Frommer和Mayer将它用于求解线性区间方程组。本文将并行多重分裂方法与求解非线性方程组的区间松弛法结合,得到了一类适合并行计算的区间松弛法,称为并行多重分裂区间AOR方法(简称PMI—AOR方法)。文中构造的并行多重分裂Krawczyk型区间     

块循环矩阵求逆的一种快速富里叶变换(FFT)算法

本文详细讨论块循环阵求逆的一种快速富里叶变涣(FFT)算法,该算法结构简洁,并行化程度较高。对于N(N=mn)阶块循环阵,运用该算法求逆所需运算量仅为O(N log_2N),比其它一般方法要少得多。作为特殊情形,取m=1,我们便得到文[1,3]中提出的循环阵求逆的一种FFT算法。     

并行求解三对角线性方程组的顺逆消去分割方法

本文对IBM公司H.H.WANG的并行求解三对角线性方程组的分割方法提出了改进的方法——顺逆消去分割方法。主要改进之处是在主对角线从顶向下顺方向分块并行消去诸f的同时,从底向上逆方向分块并行消去诸g.它与H.H.WANG的并行分割方法相比,标量运算总数不增加。向量运算总数大约减少30％以上。     

波浪中多船近距离并行航行的水动力干扰研究

采用三维势流理论及多体动力学理论建立了波浪中近距离并行航行多船波浪作用力及运动响应的计算模型.为考虑航速效应对船体间自由面的影响,采用三维移动脉动源Green(格林)函数来模拟船间的辐射波及绕射波.采用该数学模型求解了零航速及有航速情形下两船近距离并行时的流体动力项及运动响应,和模型试验结果比较验证了方法的可靠性.将该方法推广至三船并行航行的情形,重点分析了三船并行时水动力干扰和两船并行时水动力干扰的差异.     

奇异线性方程组的并行多分裂迭代法

改进了奇异M-矩阵的线性方程组的并行多分裂法的一些最近结果,给出了并行多分裂迭代方法的一些收敛性的理论结果。     

矩形区域上非线性变分不等式的并行SOR格式及其全局收敛性

数值方法的并行化是近些年随计算机并行性能的开发而兴起的研究方向之一。众所周知,逐次超松弛迭代(简记为SOR)是解方程组及其它数学问题简单而又实用的数值算法。八十年代末及九十年代初,Mangasarian及De.Leone等人将此算法的并行格式用于求解线     

一种并行结构优化方法

本文提出一种并行结构优化方法,其主要操作均在单元内进行,不需组装总刚和求解系统方程,具有步骤简单,占内存少,计算量小和易于编程的特点。本方法可用在微型机上作结构优化设计,并且特别适用于新一代并行计算机系统。一、前言计算机系统已得到迅速的发展,突出的特点是微型化(microminaturization)和并行化(parallelization)。微型计算机以其低廉的价格和良好的环境适应性为广大工业部门和研究单位所青睐,并行计算机也以其超高速计算能力而得到普遍关注,并在国际上有了相当的应用。并行计算机大致可分为四类:单指令流多数据流(SIMD);多指令流单数据流     

并行求解三对角线性方程组的分段消元法

本文针对实际并行机系统提出并行求解三对角线性方程组的分段消元法。对于规模大于并行处理机台数的三对角方程组,该算法无须作任何修改即可直接应用。算法复杂性分析表明,分段消元法的有效适用范围很广。文中,我们还给出了分段消元法有定义的一个充分条件,并且将该算法推广应用于拟三对角线性方程的并行求解。     

弹性接触问题参数变分原理的有限元并行算法*

本文基于弹性接触问题的参数变分原理的有限元解法,利用并行计算机的特性和并行处理结构,建立了相应的并行算法.该算法从刚度阵的生成和组集,静凝聚过程,求应力过程等多方面实现了并行化.该算法在西安交通大学ELXSI-6400并行计算机上程序实现,计算结果表明能有效地节省计算时间,是一种分析接触问题的有效的并行算法.     

Navier-Stokes方程的一种并行两水平有限元方法

基于区域分解技巧,提出了一种求解定常Navier-Stokes方程的并行两水平有限元方法．该方法首先在一粗网格上求解Navier-Stokes方程,然后在细网格的子区域上并行求解粗网格解的残差方程,以校正粗网格解．该方法实现简单,通信需求少．使用有限元局部误差估计,推导了并行方法所得近似解的误差界,同时通过数值算例,验证了其高效性．     

Burgers方程的区域分裂并行格式

1引言 Burgers方程可作为N-S方程的简单形式,这是因为它不仅具有N-S方程的一些特性,而且数值求解方法也相近,因此,对Burgers方程的数值方法的研究具有一定的实际意义.为了在并行计算机上求解Burgers方程,已有不少文章提出了并行差分格式,如组显式方法([1]-[4])、交替分段隐格式[5],这些格式均可归结为交替型的并行格式.