正交降维内积及部分重新正交化

众所周知,经典的Gram-Schmidt正交化(GS)方法在计算上是不稳定的,为此提出了不少修改方案,Rice在[1]中提出了修正的Gram-Schmidt(MGS)方法,这是一个很成功的方法,尽管工作量没有改变,但此方法很稳定,本文将提出正交降维的内积法,分析其数值稳定性,然后再指出,为什么MGS方法有如此好的数值稳定性,第二节提出MGS的重新正交化方案及部分重新正交化技术,第三节提出部分正交降维内积部分重新正交化的新方案,最后对多种算法在PC-1500上作了数值试验,其结果与理论分析一致。     

问题分解和结构递归

<正> 到目前为止已出现不少好的并行算法,但至今没有一篇文章讨论并行算法的设计方法。我们想在这方面作一尝试,提出一些设计方法,并用这些技术设计一些新的并行算法。本文讨论与问题分解和结构递归有关的一类设计方法。     

问题分解和结构递归

到目前为止已出现不少好的并行算法,但这些文章都是针对具体问题的,对各类不同的问题,是否存在一些统一的并行算法设计方法,这是一个很有意义的论题,我们想在这方面作一尝试,提出一些设计方法,并用这些技术设计一些新的并行算法,本文将讨论与问题分解和结构递归有关的一类设计方法。     

复矩阵乘法的并行计算

<正> 在矩阵计算中矩阵乘法是最基本的。一个好的矩阵乘法算法往往能大量节省求解线代数问题的计算时间。如Strassen算法的问世就使线代数方程组求解、行列式求值等的运算量,从0(n~3)下降为O(n~(2.81))。不少领域中经常遇到复矩阵的乘法,而到目前为止讨论这一问题的并行算法的文章甚少。本文提出两类计算方法并讨论了各种算法的性能、并行时间复杂性及其误差分析。一、化为实短阵乘法的算法类众所周知,若A、B、C、D是实域上n阶全矩阵环中的元素,则成立互等式(A+B_i)(c+D_i):(Ac-BD)+i[(A+B)(c+D))-Ac-BD] (1)     

算术表达式求值算法的数值稳定性

设E(x_1,…,x_n)是实域上有n个不同原子的表达式,它可以包含任何四则运算.表达式E的求值过程可以用二叉树表示,这棵树称为它的分析树.一般而言,分析树不是唯一的.为了与分析树一一对应,必须在不确定的地方加上括号使之成为合适构造的表达式,记为E_w.于是E_w可递归地定义如下: 1.若E_w=x_i,x_i是某个原子,则称E_w是合适构造的;     

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

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

直接法的误差估计

解代数问题的任何算法有两个问题是人们普遍关心的。一个问题是运算中引进的舍入误差是否可归结为原始数据的扰动,如行,则需计算出这扰动量的大小。另一个问题是对算法给出的解,估计它与精确解之差。 第一个问题称为算法的数值稳定性问题。目前主要有两种讨论方法。一种是由     

现浇楼板和轻质隔墙免抹灰工艺的实践和分析

1 概述 一般认为,抹灰工程是建筑装饰工程中不可或缺的一个组成部分,如钢筋混凝土现浇楼板上要做细石混凝土找平层或水泥砂浆抹灰层,砌体墙面要做抹灰层等,这些都是常规的做法。但随着经济和技术的发展,人们提出减少抹灰和取消抹灰、改革湿作业和发展干作业的呼声日益高涨。在世界上一些先进国家,建筑施工也以干作业为主,湿作业很少,他们能够做到混凝土结构一次成活,即清水做法,没有找平层和     

并行找近似最大值的位对分技术

<正> 设K是一个数据集,其中每个元素a∈K的键是整数,都可用P位二进制a_1a_2…a_p表示。K 上的全序关系R 定义为:若a_i=b_i(1≤i≤l),a_(l+1)>b_(l+1),o≤lb。显然B=(K,R)是一个数据结构。我们考察在B 上解最大元问题。对并行找最大元,[1]已有相当好的结果。Valiant 利用图论结果得出:若处理机台数为n,每台处理机都以二元比较作为基本运算,则对n 元找最大元的并行比较次数为t_(max)(n)≥log_2log_2n-const事实上若考虑计算机的系统开销,则不论有多少台处理机可用,因问题有n 个输入,分析树高至少为log_2n。     

环介导等温扩增法检测棘颚口线虫方法的建立

棘颚口线虫是引起人体颚口线虫病最主要的病原,其引起的病例呈世界性分布。由于其复杂的生活史,以及不同生长阶段形态的变化差异,传统的形态学鉴定方法很难鉴别。为了快速、灵敏和可靠的鉴定棘颚口线虫,本研究建立了一套检测棘颚口线虫的DNA环介导等温扩增（loop-mediated isothermal amplification,LAMP）方法。根据LAMP方法原理,针对棘颚口线虫的ITS2 rDNA设计了三套特异性引物特异性识别靶基因。进行了特异性、灵敏度、稳定性和实际样品的测试。结果表明,该方法对棘颚口线虫DNA能够特异性扩增,而比对虫体DNA均无扩增;对含有棘颚口线虫ITS2目的基因片段的质粒DNA的检测限为1 fg/μL,比传统的PCR方法灵敏度高100倍;对51批次实际样品的进行检测,LAMP方法与传统的PCR测序方法结果相符。本研究设计的LAMP检测方法适用于特异性检测棘颚口线虫。