关于整数向量卷积的一个算法的时间复杂度

众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。     

对称r-循环矩阵的快速算法和并行算法

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).     

计算周期三对角矩阵行列式和逆矩阵的新算法

给出了一种计算周期三对角矩阵行列式和逆矩阵的新递推算法,它们的运算复杂度分别为O(n)和O(n2),该算法是文献[5]和[6]中相关算法的拓广.     

B样条曲面的方向导数与高效求值

1 引言 B样条曲面是几何造型中一种用途广泛的方法,在实际应用中,大量问题需要我们研究曲面的凸性与连续性,它们都归结为求曲面在任意点处关于任意方向的各阶导数的求值问题. 给定(m+M)×(n十N)个空间点f_(ij)及两个非减节点向量{u_i;0≤i≤2m+M}和{v_j;0≤j≤2n+N},则定义在[u_m,u_(m+M)]×[v_n,v_(n+N)]上的m×n次B条曲面为 f(u,v)=(sum from i=0 to m+M-1)(sum from j=0 to n+N-1)(f_(ij)N_i~m(u)N_j~n(v), (1)其中N_i~m(u)和N_j~n(v)为定义在前两节点向量上的规范B样条基函数,它们可以按严格形式递推地定义为下式     

一个求解P_*(k)阵线性互补问题的渐近O((k 1)n~3L)宽域路径跟踪算法

本文通过使用高界校正技术，给出了一个求解P*(k)阵线性互补问题的宽域路径跟踪算法，其迭代复杂性为渐近O((k＋1)L)．通过使用秩-1校正技术，其每步的计算复杂性从常规的O(n3)约减到O(n2.5)；因此，算法总的计算复杂性为渐近O((k＋1)n3L)．     

关于矩阵多项式的新快速算法

设A为n×n矩阵,对于计算矩阵多项式 f(A)=a_0I十a_1A a_2A~2 … a_mA~m (m(?)n)我们给出了工作量为O(mlogn)的快速算法,改进了文[1]和[2]的复杂性结果。     

从求1984~(1984)的个位数谈起

1984年已经来临,你知道1984~(1984)的个位数是几吗?我们虽然不可能将1984个1984逐次相乘,但是却可以探亲解决这个问题的规律。考察1984~n。其底数的个位数是4,显然1984~n的个位数即4~n的个位数,是n的函数。即n确定后1984~n的个位数也随之确定了。我们将1984~n的个位数记为f_4(n),则f_4(1)=4,f_4 (2)=6;当n继续增加时,1984~n的个位数周期性地重复出现,即f_4(n)为一周期函数,若将其周期记为T_4,则T_4=2。所以f_4(1984)=f_4(2×1991+2)=f_4(2)=6,即1984~(1984)的个位数是6。一般地,若a、b∈N,a~b的个位数也可以求     

一类更新序列的母函数

数列f={f_1,f_2,…,f_n,…}称为f-序列,如果■(1)由f产生的更新序列u={u_0,u_1,u_2,…,u_n,…}依下式定义■记f=■,如果f=1,则称更新序列u为常返的.周知,u常返的充要条件是     

一类对称正交对称矩阵反问题的最小二乘解

1 引言 本文记号R~(n×m),OR~(n×n),A~+,I_k,SR~(n×n),rank(A),||·||,A*B,BSR~(n×n)和ASR~(n×n)参见[1].若无特殊声明文中的P为一给定的矩阵且满足P∈OR~(n×n)和P=P~T. 定义1 设A=(α_(ij))∈R~(n×n).若A满足A=A~T,(PA)~T=PA则称A为n阶对称正交对称矩阵;所有n阶对称正交对称矩阵的全体记为SR_P~n.若A∈R~(n×n)满足A~T=A,(PA)~T=-PA,则称A为n阶对称正交反对称矩阵;所有n阶对称正交反对     

P_*(κ)线性互补问题基于新核函数的大步校正算法（英文）

本文研究了P*(κ)线性互补问题的大步校正原始-对偶内点算法.基于一个强凸且不同于通常的对数函数和自正则函数的新核函数,对具有严格可行初始点的该问题,算法获得的迭代复杂性√为O(1+2κ)n(log n)2lognε,该结果缩小了大步校正内点算法的实际计算与理论复杂性界之间的差距.     

求Toeplitz矩阵各阶主子式和特征值的O(n~2)算法

形如T~(n)=(T_(ij)~(n))_(n×n),T_(ij)~(n)=t_(i-j),i,j=1～n的n阶矩阵称为Toeplitz矩阵。 Toeplitz矩阵(简称T矩阵)是一类很重要的特殊矩阵,地震预报、天气预测、石油勘探等许多应用领域的数学模型中常常遇到T型矩阵,因此研究其快速算法具有很大的实用价值。1964年,W.F.Trench在对称正定的条件下给出了T矩阵求逆的O(n~2)算法。1969年,S.Zohar进一步讨论了Trench的算法,主要工作是对推导的简化以及把对称正定的条件减弱为强非奇(即各阶主子式全不为零),算法的主要思想请参阅文[1]或[2]。     

A类零壹矩阵的基的一些定理

定义1 令n≥3,A=(a_(ij))_(n×n),i=1或0,对任固定的i(1≤i≤n)存在唯一的一个j_o(1≤j_o≤h)使得a(ij)_o=1,其余的a(ij)=0(j jo,1≤j≤n),则称(0,1)一矩阵A为A型的矩阵。 显然A型矩阵在矩阵乘法运算下成为一个具有单位元的半群。 定理2 令A={A:A是n级的A型矩阵},B A,若对任A A总存在有B_1,B_2,…B_K B使得A=B_1B_2…B_K,则称S为A的一个基。     

常微分方程组的整体解及两点边值问题——Ⅰ.整体解方法

众所周知,n维向量函数u(x)的一阶常微分方程组,如在某点上只给出n_1相似文献   

一个新的逐列正交化算法

本文讨论如下的最小二乘问题:min{S(x)=F(x)~TF(x)/2,x∈R~n},其中F(x)=(f_1(x),f_2(x),…,f_m(x)~T,m≥n.上述问题的求解,除了有以Levenberg-Marquardt为代表的各种阻尼最小二乘法外,还有一类逐列正交化算法.但在现有的逐列正交化算法中,对可行性、收敛性、收敛速度讨论得很少.本文提出了一个新的算法,并证明了其可行性、收敛性和收敛速度.文中附了计算实例,表明当用各种阻尼二乘法做不下去时,应用本算法还可能作出改进.本文主要结果如下:     

顶点加权最大团问题的加权分治算法

分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656~np(n)),其中n代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656~np(n))降为O(1.3765~np(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度.     

一种新型的解分配问题的算法

在运筹学理论中,分配问题是最基本的问题之一,而现有解分配问题的算法都比较复杂,应用这些算法是不方便的。故提出一种用最短路径算法来解决分配问题的新型算法。 1.几个基本概念及其定理分配问题数学模型(P) 求使定义1如果某一个分配x=(x_(ij)),x_(ij)满足式子(1.1),则称此分配为可行分配。定义2如果一有向图中某一回路上边的长度之和小于0,则称此回路为负回路。下面用A={(1,j_1),(2,j_2),…,(n,j_n)}来表示分配问题的一个可行分配,即当x_(ij)=1     

一类积分不等式及其应用

研究了一类新的非线性延迟积分不等式φ(u(t))≤(n_1(t)+∫_o~(a(t)) f_1(s)w_1(u(s))ds)(n_2(t)+∫_o~t f_2(s)w_2)(u9(s))ds),t∈R_+得到了新的结论,推广了已有的若干结果.并举例说明其应用.     

B类零壹矩阵的基的一些定理

定义1 令n≥3,M=(m_(ij))_(n×n),m_(ij)=1或0,对任意固定的i(1≤i≤n)最多存在一个j_0(1相似文献   

幂等矩阵下Yang-Baxter-like方程解的新的显式表达式

正1引言设C~(m×n)表示m×n阶复矩阵的集合,I_n表示n阶单位矩阵.对于矩阵A∈C~(m×n),A~*表示它的共轭转置矩阵.设矩阵A∈C~(n×n),如果A~2=A,则称矩阵A为幂等矩阵;如果A~2=A=A~*,则称矩阵A为正交投影矩阵.设A∈C~(n×n)本文主要研究下面的二次矩阵方程AXA=XAX,(1.1)称之为Yang-Baxter-like方程,因为其与统计物理中分别由Yang[1]和Baxter[2]独立得到的经典Yang-Baxter方程相似.     

(X+K) mod2n运算和X(+)K运算异或差值的概率分析及其应用

对(X+ K) mod 2n运算和X(+)K运算异或差值函数的概率分布规律进行了研究,并基于穷举攻击中“大概率优先选取”原则,给出了一个解决(X+K) mod 2n和X(+)K等价问题的计算复杂度为O(n)的算法,基于此对Hawkes等人针对SNOW1.0的猜测决定攻击进行了改进,使其数据量由O(295)降为O(290),而计算复杂度由O(2224)略微提高到O(2224.482).