线性规划中的多项式型算法

<正> 我们考虑由具有整系数a_(ij),b_i的关于n≥2个实变元x_1,…,x_j,…,X_n的m≥2个线性不等式 a_(il)X_1+…+a_(in)X_n≤b_i i=1,2,…,m(1)所组成的系统。令 L=[sum from i,j=1 to m,n(log_2(|a_(ij)|+1))+sum from ?=1 to m(log_2(|b_i|+1)+log_2nm)]+1 是系统的输入的长度,亦即为了把(1)写成二进制形式所需要的符号0,1的个数。     

三角形Toeplitz系统的并行求逆算法

<正> 本文给出了规模为n的三角形Toepfitz 系统的一种并行求逆算法。该算法所需处理机的台数p=n,并行时间步数T_p=O(log_2~2n),从而速度倍数s_p=O(n/log_2n)。另外,我们对多项式快速除法也作了相应的并行处理,并给出了三角形T 矩阵逆的一个显示表达式。     

有限个处理器情况下算术式的并行处理范围

为了评价并行处理机执行算术表达式的速度性能,本文依据David Kuck关于算术式并行处理步骤的定理,推导出在有限个处理器情况下,并行处理的执行步骤最多为1+2d+[log_2K]+[(n-2K)/K]。     

代数方程的根具有负实部的判定

本文给出了代数方程f(x)=a_0x~n+a_1x~(n-1)+…+a_(n-1)x+a_n=0的全部根具有负实部可由不等式:a_1a_2>α_nβ_1a_0a_3,a_2a_3>α_nβ_2a_1a_4,…,a_(n-2)a_(n-1)>α_nB_(n-2)a_(n-2)a_(n-3)a_n来确定,证明了α_n的存在性和唯一性,以及最小可取数α_n~*的存在性唯一性。并对n≤8给出了α_n的数值估计。     

齐一并行排序算法

本文给出的算法,是一个适合并行处理的排序方法.它有控制规则简单,整体对称,层次结构清晰,满足递归特征等许多优点.它对n个元素排序时并行深度为1/2log_2n(log_2 n+1),并行宽度为n/2.该算法可直接应用于并行计算,用VLSI线路设计并行排序网络等方面.     

解实对称矩阵特征值并行快速Jacobi方法

<正> 本文对传统的Jacobi 变换进行变形,且在此基础上设计了快速方法。对一次扫描而言,进行变形可省2·(((n(n-1))/2)-2[(n+1)/2]+1)次矩阵乘法([x]表示≤x 的最大整数),快速方法对固定j 而言,省了一次开平方计算。一、Jacobi 变换变形对n 阶实对称矩阵A=[a_(ij)=[(?)]i,j=1,2,…n,鉴于A 的对称性,仅考虑i相似文献   

解K阶线性递归N方程组的一种实用并行算法

本文提出了解K阶线性递归N方程组的一种实用并行算法.当K相似文献   

计算K（≥2）序线性递归N方程组的一种有效并行方法

本文提出计算K(≥2)序线性递归N方程组的一种有效并行方法,当k<相似文献   

国防科技大学研究生院二○○二年硕士生入学考试离散数学试题

一、(12分)设集合A二{1,2,3,4}上的二元关系RI和R:定义如下:尺,={,(l,3>,(2,2>,(2,4>,<3,3>,<4,4)1 (l)试分别指出R,和R:所具有的性质(即是否具有自反性,反自反性,对称性,反对称性和传递性这五种性质)。 六、(10分)证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n一1,则‘是连通的。(2)试求出尺,。尺:,t(五,)和ts:(RZ)。 七、(10分)设A为非空集合,刀二{二l二为A的划分}。若令 R二{<7r,丫>}7r,记任刀且对每个“任7r皆有。任记使u〔。} 试证明R为H上的半序。 二、(8分)求合式公…     

解三对角方程的并行追赶法

针对科学计算和工程中常见的三对角方程组,本文提出了一种有效的并行解法,如果假定一次乘法或加法的时间为1个单位时间,一次除法的时间为3个单位时间,则该方法的时间复杂性为:20[N/P]+0(log_2P),其中P为并行处理机台数,N为方程组的阶数。在文献[1]中的各种并行算法,以循环奇偶约化法效率最高,在上述同样的假定下,其时间复杂性为:28[N/P]+O(log_2P),本方法比循环奇偶约化法提高效率约40％。文献[2]中提出的并行算法,在相同的假定下,其时间复杂性为:42[N/P]+0(log_2P),本方法提高效率一倍以上。     

关于ω-语言的正则性

本文给出某些类ω-正则语言的某些代数描述。用∑~ω表示字母表∑上的一切ω-字的集合。设σ=a_1…a_n…,令σ(n)=a_1…a_n。在∑~ω上定义二元关系“≤_ω”:对σ_1,σ_2∈∑~ω,σ_1≤_ωσ_2当且仅当σ_1=x_1…x_n…,σ_2=y_1x_1y_2…x_ny_(n 1)…,x_1,y_i∈∑~ω。 定义1.对σ_n∈∑~ω,n=1,…,若存在σ∈∑~ω,使σ_n(n)=σ(n),n=1,…,则称σ是序列{σ_n)的极限。     

多维列联表分析中的有关算法

一、数学模型 1.对数线性模型 一个n维列联表可用对数线性模型M来描述(一般采用分层模型):logmθ=u u_([1][θ_1]) u_([2][θ_2]) … u_([k][θ_k]) … u_([l][θ_l]),(1≤k≤l,1≤l≤n), (1)其中θ为下标集,例如在四维情况,θ可为i_1i_2i_3i_4,m_θ为n维列联表中第i_1i_2 i_n格的     

解三对角方程组的多重特解法

<正> 在并行机上求解一般三对角方程组已有不少算法。主要有四类:基于LDU分解的倍增法和逐段并行法;APG迭代;基于Cramer法则的倍增法;以及循环奇偶归约法。本文将先对上述四种算法作简要评论,然后提出特别适合并行计算的多重特解法,并与其它算法作出比较。一、对已有算法的评论 Stone于1973年提出的倍增法需求解一个二阶递推方程和二个一阶递推方程。在阵列式理论模型上算法的时间复杂性为 (1210g_2n+2)t_*(5log_2n+1)t_++4t_÷(1)这里t_*、t_+和t_÷分别为执行并行乘法、加法和除法所需的时间。对从椭圆型方程导出的     

并行多重网格算法求解高Reynolds数不可压Navier-Stokes方程

．引言在分布式存储并行计算环境中，大粒度并行是获取较高效率的唯一途径【斗网格划分将计算网格均匀地分配到各台处理机，是实现大粒度并行的最有效方法之一’‘’·具体到多重网格算法，它首先在最细网格层进行区域分解，每个子区域拥有近似相等的网格点数，然后将属于相同子区域的所有网格点分配给同一台处理机．称子区域划分边界为拟边界．考虑2维定常不可压Navier－Stokes方程其中对流扩散算子R的Reynolds数，u一（。l，。。）”为速度，P为压力．R的不．同将导致问题的不同性质．本文只讨论R＞＞0（1）或RMoo的极限情形．此时，…     

1997年4期擂台赛点评

这次擂台赛参赛选手几乎全部能正确给出该题的正确答案:1,3,9,27。该赛题自然应是用1:1杠杆的称,否则解将依赖于杠杆比例。绝大部分参赛程序采用先用枚举法列举出所有可能的砝码序列,再对该序列的各种组合进行能否称量1至40磅所有物体的检验,其中砝码可放在称的两边分别起正负作用。 大家不同程度上找到一些减少搜寻空间量的约束条件,如将砝码从小到大排为a_1,a_2,a_3,a_4则a_4=40-a_1-a_2-a_3;al必为l;a_2≤a_3≤a_4;a_2≤(40-a_1)/3=13;a_3≤(39-a_2)/2等,但大部分程序运算量仍较大。 一般而言,枚举法利用了计算机的高速运算能力解决了一些不能直接求解或本来非常困难的问题,但其运算量可能随问题规模剧烈增长,如“搜寻树”方法     

DEDS的集结与输入-输出等价

作者对有限缓冲器容量的柔性制造系统(FMS)建模,并对所建的高维模型完成了集结和保持输入-输出等价的算法.该模型和集结、输入-输出等价算法已成功地用于FMS的摄动分析. 设有M台机床,m种工件.设工件访问机床的次序不逆向,但并不要求工件必须顺序经过M台机床. 记u_i(1≤i≤M)为i机床投入运行时刻;(M+1≤i≤M+m)为(i—M)工件投料时刻;x_(ij)为j机床加工i工件的开始时刻;y_i(1≤i≤m)为i工件加工完毕时刻;(m+1≤i≤m+M)为(i—m)机床加工完毕时刻;a_(ij)为j机床加工i     

一类特殊类型数学规划的解法及其在金融业的应用

1.问题的描述 假设国际金融界有n种货币可以发生直接的兑换.用a_(ij)表示国际市场兑换率.它的含义是,i货币每单位可以换取j货币的最大数量,若i货币不能直接兑换成j货币,则取a_(ij)=0.顺便指出,a_(ij)=1.由于买入价和卖出价之间有个差价,所以通常情况下a_(ij)a_(ji)≤1.在实际问题中,a_(ij)a_(ji)往往接近于某个常数,常见的是0.995.     

在线性处理机阵列上求MCST的并行算法

本文给出一种在P个处理机线性阵列上求MCST(最小代价生成树)的并行算法,记为OLA-MCST.证明了在整个1≤P≤n范围内其时间复杂性均为O(n~2/P);特别地,当P=n时,为O(n).这是在本模型下使用n个处理机时的最优性能.     

网孔处理机阵列上最小生成树算法

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。