关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

相对化概率算法类与非确定算法类的强分离

本文提出并讨论了多项式时间概率型算法复杂度语言类与指数时间非确定型算法复杂度语言类的强分离(即带禁集证据的分离)问题,获得并证明了存在一个递归Oracle集A使得在多项式时间有界错误概率复杂度语言类BPP^A中存在NEXT_k^A禁集,这里NEXT_k^A=∪NTIME^A(2^_cnk)表示计算时间限界于O(2^_nk)的指数时间非确定型算法所接受的语言类;我们指出,Oracle集A可以一致地对k构成并列举熟知的语言类P,NP,U,R,BPP,PP,∑₂^p,∏₂^p,Δ₂^p以及交互式证明系统语言类MA,AM,IP等之间的30余种强分离关系作为本文结果的直接推论.     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

逐步聚类分析在医学研究中的应用

本文提出了一个多变量逐步聚类算法,它可应用于逐步回归所适用的范围,但在处理离散变量和连续变量,以及变量间的非线性关系上,更具有优越的性能.文中用此法研究了河南林县姚村公社49个大队食管癌和食管上皮重度增生患病率与四季饮水井中NO₃^-和NO₂^-含量的相关关系,探索食管癌的发生、发展与亚硝胺化合物前体的关系,结果表明:食管癌患病率主要与井水中夏季NO₃^-的含量,春季NO₂^-的含量有显著的“正相关”关系,而食管上皮重度增生患病率主要与井水中春季NO₂^-、NO₃^-,秋李NO₂、NO₃^-,以及冬季NO₂^-,NO₃^-的含量有显著的“正相关”关系.实践证明:本文所提出的逐步聚类分析法是医学研究中一个有效的统计方法。     

负相协随机变量的指数不等式

该文给出了一些负相协随机变量的指数不等式.这些不等式改进了由Jabbari和Azarnoosh^[4]及Oliveira^[7] 所得到的相应的结果.利用这些不等式对协方差系数为几何下降情形, 获得了强大数律的收敛速度为n^-1/2(log log n)^1/2(log n)^2.这个收敛速度接近独立随机变量的重对数律的收敛速度, 而Jabbari和Azarnoosh^[4]在上述情形下得到的收敛速度仅仅为n^-1/3(log n)^5/3.     

随机发展方程小扰动大偏差原理的统一方法

设X^ε=|X^ε(t);0≤t≤1|(ε>0)是由随机发展方程 dX^ε(t)=^ε(1/2)σ(X^ε(t))dB(t)+b(X^ε(t),ν(t))dt控制的随机过程,其中ν(t)是与Brown运动B(·)独立的随机过程。讨论了|(X^ε,ν(·));ε>0|的大偏差性质;在特殊情形下,给出了精确的速率函数,解决了Eizenberg和Freidlin所提的一个问题。此外,还得到一个一般性大偏差定理。     

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

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

ZnS∶Mn2+纳米晶钠硼硅玻璃复合体的EPR研究 *

用熔融法制备了ZnS∶Mn²⁺不同含量的钠硼硅玻璃 .发光和激发光谱测量发现Mn离子可能占据替位 (Mn²⁺) _sub和间隙 (Mn²⁺) _int两种格位 .进一步的电子顺磁共振(EPR)实验证实了这一判断 ,并从EPR谱确认了(Mn²⁺) _sub,(Mn²⁺) _int和Mn团 3种格位态的存在 .观测到g因子和超精细结构(HFS)常数随纳米晶粒径的减小而增大 .这可能是由于量子限域效应下ZnS的sp³ 和Mn的3d⁵电子态杂化和表面态所引起的 .     

稀疏复杂网络的识别

本文研究了一种给定的复杂网络结构识别问题.利用网络结构的稀疏性质,提出了一个带有l¹正则化的最小二乘模型.数值仿真表明该算法对带噪声或不带噪声的较大型网络结构的识别是非常有效的.     

一个除数为2m(2n±1)的快速除法

本文提出了一个除数为常数2^m(2ⁿ±1)形式的除法的快速算法。该算法可非常简单的直接由硬件和软件实现。AP-601高速向量计算机无冲突访问存贮系统的素数模地址变换的硬件实现,便是该算法的成功应用。文中不仅给出了算法的数学基础,也给出了某些性能指标。     

矩阵填充的硬阈值修正算法

提出了使用硬阈值进行矩阵填充的修正算法.算法通过对迭代矩阵进行对角修正来完成矩阵填充,并给出了算法的收敛性分析.最后通过数值实验比较了修正算法与硬阈值算法填充的数值结果,显示出了新算法的优越性.     

A modified candecomp algorithm for fitting the latent class model: Implementation and evaluation

In this paper an implementation is discussed of a modified CANDECOMP algorithm for fitting Lazarsfeld's latent class model. The CANDECOMP algorithm is modified such that the resulting parameter estimates are non-negative and ‘best asymptotically normal’. In order to achieve this, the modified CANDECOMP algorithm minimizes a weighted least squares function instead of an unweighted least squares function as the traditional CANDECOMP algorithm does. To evaluate the new procedure, the modified CANDECOMP procedure with different weighting schemes is compared on five published data sets with the widely-used iterative proportional fitting procedure for obtaining maximum likelihood estimates of the parameters in the latent class model. It is found that, with appropriate weights, the modified CANDECOMP algorithm yields solutions that are nearly identical with those obtained by means of the maximum likelihood procedure. While the modified CANDECOMP algorithm tends to be computationally more intensive than the maximum likelihood method, it is very flexible in that it easily allows one to try out different weighting schemes.     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

解一类Hessian矩阵亏秩的修正BFGs算法及其局部Q-超线性收敛性

本文对凸函数在极值点的Hessian矩阵是秩亏一的情况下,给出了一类求解无约束优化问题的修正BFGS算法.算法的思想是对凸函数加上一个修正项,得到一个等价的模型,然后简化此模型得到一个修正的BFGS算法.文中证明了该算法是一个具有超线性收敛的算法,并且把修正的BFGS算法同Tensor方法进行了数值比较,证明了该算法对求解秩亏一的无约束优化问题更有效.     

求总极值问题的最优性条件

郑权提出了求总极值问题的积分－水平集的概念性算法,同时给出了最优性条件。本文提出了修正的积分－水平集算法,并且给出了类似的总极值存在的最优性条件。     

Hybrid algorithm for the two-dimensional rectangular layer-packing problem

In this paper, a rectangular layer-packing algorithm (RLPA) combined with modified genetic algorithm (GA) or particle swarm optimization (PSO) algorithm is developed to solve the problem with emerging restraints, which is raised from the two-dimensional rectangular packing problem with some small rectangles that need to be packed into a fixed rectangular object. RLPA is designed from the BL algorithm and lowest horizontal line algorithm. GA and PSO are also modified to satisfy the constraint conditions. Best GA or PSO parameters are obtained by conducting experiments on some typical instances. The results are also compared, which validate the quality of the solutions and show the effectiveness of the modified algorithm.     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems

A framework and an algorithm for using modified Gram-Schmidt for constrained and weighted linear least squares problems is presented. It is shown that a direct implementation of a weighted modified Gram-Schmidt algorithm is unstable for heavily weighted problems. It is shown that, in most cases it is possible to get a stable algorithm by a simple modification free from any extra computational costs. In particular, it is not necessary to perform reorthogonalization.Solving the weighted and constrained linear least squares problem with the presented weighted modified Gram-Schmidt algorithm is seen to be numerically equivalent to an algorithm based on a weighted Householder-likeQR factorization applied to a slightly larger problem. This equivalence is used to explain the instability of the weighted modified Gram-Schmidt algorithm. If orthogonality, with respect to a weighted inner product, of the columns inQ is important then reorthogonalization can be used. One way of performing such reorthogonalization is described.Computational tests are given to show the main features of the algorithm.     

A type of modified BFGS algorithm with any rank defects and the local Q-superlinear convergence properties

A modified BFGS algorithm for solving the unconstrained optimization, whose Hessian matrix at the minimum point of the convex function is of rank defects, is presented in this paper.The main idea of the algorithm is first to add a modified term to the convex function for obtain an equivalent model, then simply the model to get the modified BFGS algorithm. The superlinear convergence property of the algorithm is proved in this paper. To compared with the Tensor algorithms presented by R. B. Schnabel (seing [4],[5]), this method is more efficient for solving singular unconstrained optimization in computing amount and complication.     

Introduction to the improved functional epsilon algorithm

This paper introduces the improved functional epsilon algorithm. We have defined this new method in principle of the modified Aitken Δ² algorithm. Moreover, we have found that the improved functional epsilon algorithm has remarkable precision of the approximation of the exact solution and there exists a relationship with the integral Padé approximant. The use of the improved functional epsilon algorithm for accelerating the convergence of sequence of functions is demonstrated. The relationship of the improved functional epsilon algorithm with the integral Padé approximant is also demonstrated. Moreover, we illustrate the similarity between the integral Padé approximant and the modified Aitken Δ² algorithm; thus we have shown that the integral Padé approximant is a natural generalisation of modified Aitken Δ² algorithm.