Vandermonde行列式的快速并行算法

n阶Vandermonder行列式的求值通常需要O(n~2)次算术运算．本文从计算复杂性的角度出发，给出一种求Vandermonde行列式、合流型Vandermonde行列式、广义Vandermonde行列式的快速算法．该算法仅需O(nlog~2n)次算术运算．若在n台处理机上并行计算，该算法需并行步数O(nlog_(2~2)n)．速度倍数为s_p=O(n)．并行效率为O(1)．     

Toeplitz矩阵乘Vandermonde矩阵的快速算法

本文给出计算中应用较多的T阵乘V阵的快速方法,该算法需要O(N~2)次算术运算,较已有的算法的复杂性上界都要低。     

分块K—循环Toeplitz矩阵求逆的快速付氏变换法

1算法描述及推导 Toeplitz矩阵及Toeplitz系统的求解在谱分析、线性预测、误差控制码、自回归滤波器设计等领域内起着重要的作用~[1-3]，而分块Toeplitz矩阵在计算机的时序分析、自回归时序模型滤波中也经常出现~[4]。对一般Toeplitz矩阵求逆，其算术复杂性为O(n~2)~[5]-[6]，其中n为Toepleitz矩阵的阶，而K-循环Toeplitz矩阵的求逆，其算术复杂性可降为O(nlog_2n)，本文提供了mn附分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法，其算术复杂性为O（mnlog_2mn）.     

有理g-轮换阵之性质及g-轮换阵求逆的计算复杂性

本文利用本原多项式在有理数域上的不可约性及n次本原根的性质。证明了若(g,n)=1,则n阶有理g-轮换阵为可对角化矩阵。进一步利用快速富里叶变换(FFT)给出了g-轮换阵之求逆算法。算法的主要运算为FFT的计算,因此时间复杂性为O(n log n)。其中(g,n)表示整数,g,n,的最大公约数。     

关于有限群、环、域的判定算法

给定n元集合上的一个二元运算的乘法表(共n~2项)。判定它是不是群,过去的算法需时O(n~3)。我们给出了一个O(n~2)时间的算法。对于环和域的判定,我们也给出了O(n~2)时间的算法。这些算法的时间复杂性的阶已经不能再改进了。     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .     

关于三角形Toeplitz系统的复杂性

目前,已有结果表明,作两个n阶上(或下)三角形T矩阵的乘积以及做n阶三角形T矩阵乘n维列向量的算术运算次数,均不超过O(nlog_2n);而求n阶三角形T矩阵的逆,其工作量则不超过O(nlog_2~2n). 本文给出三角形T矩阵求逆与求解三角形Toeplitz线性方程组的快速算法.该算     

一道高考题的历史镜头

2005年北京高考试卷第14题:已知n次多项式Pn(x)=a0xn a1xn-1 … an-1x an如果在一种算法中,计算x0k(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算Pn(x0)的值共需要次运算.下面给出一种减少运算次数的算法:P0(x)=a0,Pk 1(x)=xPk(x) ak 1(k=0,1,2,…,n-1).利用该算法,计算P3(x0)的值共需要6次运算,计算Pn(x0)的值共需要次运算.这道高考题中第二小题,其思想可追溯到北宋时期的数学家贾宪.贾宪约于公元1050年写了一部《黄帝九章算术细草》,给出了高次开方法,实质上是求高次方程xn=N的根的方法—…     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

确定代数方程根位置的快速无除算法

本文提供了一个确定整系数代数方程在指定区域内根的个数的快速无除算法,此算法的复杂性为O(n²),其中n为方程的次数.为了强凋算法的稳定性,本文均用精确的整数运算.其中多项式是无平方的、首一的.     

考点11 递推数列及数列的应用

1.(天津卷,13)在数列{an}中,a1=1,a2=2,且an+2-an=1+(-1)n(n∈N*),则S100=.2.(北京卷,14)已知n次多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an.如果在一种算法中,计算xk0(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算Pn(x0)的值共需要次运算.下面给出一种减少运算次数的算法:P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1).利用该算法,计算P3(x0)的值共需要6次运算,计算Pn(x0)的值共需要次运算.3.(广东卷,14)设平面内有n条直线(n≥3),其中有且仅有两条直线互相平行,任意三条直线不过同一点.若用f(n)…     

PPR的收敛性和全面攻击导弹数据处理

本文证明了投影寻踪回归(Projection Pursuit Regression简称PPR)中岭函数为多项式形式时,PPR的L_2收敛性;对岭函数为多项式形式的投影寻踪回归给出了一种新的算法;应用这种算法对全向攻击导弹数据进行了处理,所获得的回归模型可供科研单位实际使用.     

棋盘游戏与有限域上多项式分解算法

将有限域F_2上多项式分解问题转化为一种对应的棋盘游戏,利用后者的性质设计了一个F_2上m+n-2次多项式f(x)分解为一个m-1次多项式与一个n-1次多项式的判断、分解算法,并对算法的复杂度进行了分析.算法的一个优势是,如果f(x)不能按要求分解,也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解.     

一类分数阶常微分方程初值问题的预校算法

利用Caputo导数的性质和二次多项式插值逼近,导出了分数阶二次多项式插值逼近隐式算法的完整计算公式,证明了其整体误差估计为O(hβ),β=min{2+α,3};在此基础上,构造了一类求解分数阶常微分方程初值问题的新的预校算法, 证明了其整体误差估计为 O(hγ),γ=min{2α,2+α,3},并通过数值实例得以验证.     

整系数多项式有理根的一个新求法

求整系数多项式的有理根 ,现行的高等数学书中只有一个经典的方法 ,本文给出了第二个有趣的简捷方法 ,这种方法的主要过程只需进行简单的算术运算     

F2中基于并圈法的M序列生成算法

M序列由于具有良好的统计特性经常被应用在信息安全领域.这使得寻找F₂中M序列反馈函数成为一项有意义的工作.给出了由已知M序列反馈多项式得出新的与已知函数同次数的M序列反馈多项式的新方法.主要工作如下:1)用图形简单的给出了并圈法的逆过程所实现的操作过程.2)将并圈法的逆运算与并圈法先后应用在已有M序列状态图交叉排列的两对前共轭顶点对上,得到了由已知M序列反馈多项式生成新M序列反馈多项式的算法.3)证明了上述给出算法在二阶有限域F₂中的正确性.4)用C语言实现了算法.实验结果表明当移位寄存器的阶不是很大时算法是有效的.     

Dijkstra算法的一个改进

本文得到了一种Dijkstra算法的改进算法，如果最短路问题具有n个点和m条边，那么改进算法把问题的计算复杂性从原来的O(nlogn m)降低为O(nlogn M)(M≤m)。     

一阶导数的五点数值微分公式及外推算法

通过对四次Lagrange插值多项式求导推导出一阶导数的五点数值微分公式,其截断误差为O(h~4).利用Richardson外推原理得到该公式的外推算法,K次外推后,中间节点的数值精度提高到O(h~(2(k+2))),其它节点的精度提高到O(h~(k+4)).     

偏最小二乘回归分析在均匀设计试验建模分析中的应用

本文分析了目前应用一般的最小二乘法建立均匀试验数据的二次多项式回归模型时存在的局限性,提出了应用偏最小二乘法(Partial least-square,PLS)建立二次多项式回归模型的技术,并且进一步介绍了偏最小二乘回归(PLS回归)在均匀设计中的应用。作者认为,PLS回归分析建模技术将为均匀设计的更广泛应用提供有力的技术支持。     

多重精度算术的时间复杂度分析

本文阐述并举例说明在多重精度算术中如何用实施算法所需比特运算次数来描述算法的时间复杂度。