用“化成等差数列法”求自然数列方幂和

定理 如果Sn=1^m+2^m+3^m+…+n^m(m∈N）,那么存在g(n)=λ1n^(m+1)+λ2n^m+λ3n^(m-1)+…+λmn^2和常数k,使数列{Sn-g(n)}成为公差为k的等差数列,其中λi(i=1,2,…,m)和k由下述方程组给出：     

关于阶乘的Erds-Stewart猜想

摘要:设n是正整数;P_0=1,P_i(i=1,2,…)是第i个素数.本文证明了:方程 n!+1=P_k~aP_(k+1)~b,P_(k-1)0,b>0,仅有解(n,P_k,P_(k+1),a,b)=(1,1,2,1,0),(2,3,5,1,0),(3,5,7,0,1),(4,5,7,2,0),(5,7,11,0,2).上述结果证实了Erds和Stewart提出的一个猜想.     

一个不等式链与一个连等式

本文拟出初等代数中一个新的不等式链,并获得一连等式。设a_1,a_2,…,a_n均是正实数,n≥2,且sum from i=1 to n a_i=n。记f(k)=1 a_k a_ka_(k 1) … a_ka_(k 1)·…·a_na_1·…·a_(k-2);f_i(k)表示和f(k)(自左至右)的第i个和项,i=1,2,…,n。令S_i=sum from i=1 to n (f_i(k)/f(k)),i=1,2,…,n, 则有不等式链     

链积中参数对称的反链

设k-i为正整数,i=1,2,…,n,直积S=Ⅰ_(R_1)×Ⅰ_(R_2)×…×Ⅰ_(k_n)={x_1,x_2,…,x_n,0≤x_i≤k_i}叫做链积,对任意的在偏序“<”下为有限偏序集。r(x)=sum from i(x_i)原S的秩函数,叫做S的Whitney数记k=sum from i=1 to n(k_i,k_1=k_2=k_n=1)时,S即为布尔代数B_n。 设为S中的反链,{P_i,i=0,1,…,n}叫做反链的参数,若成立     

关于多项式系数的整除性

设 n是正整数 ,k1 ,k2 ,… ,ks 是适合 k1 +k2 +… +ks=n的非负整数 ,正整数 nk1 k2 … ks=n!k1 !k2 !… ks!称为多项式系数 .本文讨论了当n=a0 +a1 p+a2 p2 +… +arpr ,其中 p为素数且 p≤ n,0≤ ai相似文献   

关于布尔矩阵行空间基数的若干存在区间

Let B_n be the set of all n×n Boolean Matrices;R(A) denote the row space of A∈B_n,|R(A)| denote the cardinality of R(A),m,n,k,l,t,i,γ_i be positive integers,S_i,λ_i be non negative integers.In this paper,we prove the following two results: (1)Let n≥13,n-3≥k > S_l,S_(i+1)> S_i,i = 1,2,…,l-1.if k+l≤n,then for any m=2~k+2~(S_(l)) + 2~(S_(l-1))+…+ 2~(S_(1)),there exists A∈B_n,such that |R(A)|= m. (2)Let n≥13,n-3≥k>S_(n-k-1)> S_(n-k-2)>…>S_1>λ_t>λ_(t-1)>…>λ_1,2≤t≤n-k.If existγ_i(k+1≤γ_i≤n-1,i=1,2,…,t-1)γ_i<γ_...     

一类“数学问题”的统一证法

文[1]给出了不等式:已知x,y,z∈R+,m∈N+.求证:x/mx+y+z+y/x+my+z+z/x+y+mz≤3/m+2. 文[2]给出了不等式:已知xi＞0(i=1,2,…n),k＜1,求证: n∑i=1 xi/x1+x2+…+xi-1+kxi+xi+1+…+xn≥n/n+k-1. 文[3]给出了不等式:设ai＞0(i=1,2,3,…,n),p∈R,q＞0,且n∑i=1ai=A,Si=pai+q(A一ai)＞0(i=1,2,…,n),求证:     

关于多项式系数的整除性

设n是正整数,k1,k2,…+k1=n的非负整数,正整数[nk1k2…ks]=n！/k1!k2!…k5!称为多项式系数,本文讨论了当n=a0+a1p+a2p^2+…arp^r,其中p为素数且p≤n,0≤ai&;lt;p(0≤i≤r);ki=a0^(i)+a1^(i)p+…+ar^(i)p^r,其中ki≤0,∑^si=1,ki=n,0≤ak^(i)p(0≤i&;lt;s)时多项式系数的整除性问题,得出的结果推广了著名的Lucas定理^[1].     

n阶常系数线性非齐次微分方程及欧拉方程的通解的一种显式表达式

§1引言对于形如y~((n))+p_1y~((n-1))+p_2y~((n-2))+…+p_(n-1)y＇+p_ny=f(x)的微分方程[其中P_i(i=1,2,…,n)为常数],若能求出其对应齐次方程的n个特征根,则很容易写出该齐次方程的通解Y(x)的显式表达式。     

一个有趣的命题及其推论与应用

设X=(x1,x2,……,xk),记函数fi(X)=fi(x1,x2,…xk),又设f(X)为正值函数且其二阶偏导数连续(k≥2),其中i=1,2…n。将形如[(^n∑i=1)fi(X)]/n的函数称为fi(X)(i=1,2…,n)的均值函数;将^n√(^n∏i=1)fi(X)称为fi(X)(i=1,2…,n)的几何均值函数,由fi(X)(i=1,2…,n)的均值函数和fi(X)(i=1,2…,n)的几何均值函数可以得到均值不等式。     

Parallel lightweight wavelet tree,suffix array and FM-index construction

We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.     

An effective hybrid algorithm for computing symbolic determinants

A hybrid algorithm for computing the determinant of a matrix whose entries are polynomials is presented. It is based on the dimension-decreasing algorithm [22] and the parallel algorithm for computing a symbolic determinant of [19]. First, through the dimension-decreasing algorithm, a given multivariate matrix can be converted to a bivariate matrix. Then, the parallel algorithm can be applied to effectively compute the determinant of the bivariate matrix. Experimental results show that the new algorithm can not only reduce enormously the intermediate expression swell in the process of symbolic computation, but also achieve higher degree of parallelism, compared with the single parallel algorithm given in [19].     

一种迭代格式的有限元并行算法*

本文提出了一种求解有限元方程的迭代格式的并行算法.该方法在线性代数方程迭代解法的基础上,引进并行运算步骤;并且运用加权残数方法,通过选择适当的权函数,推导了该并行算法的有限元基本格式.该方法在西安交通大学BLXSI-6400并行计算机上程序实现.计算结果表明它能有效地提高运算速度,减少计算时间,是一种有效的求解大型结构有限元方程的并行算法.     

解非对称矩阵特征值问题的一种并行分治算法

１引言考虑矩阵特征值问题其中Ａ是非对称矩阵．通过正交变换（如Ｈｏｕｓｅｈｏｌｄｅｒ变换或Ｇｉｖｅｎｓ变换）,Ａ可化为上Ｈｅｓｓｅｎｂｅｒｇ形．因而,本文假设Ａ为上Ｈｅｓｓｅｎｂｅｒｇ矩阵,表示如下：不失一般性,进一步假设所有的（ｊ＝２,…,ｎ）,即认为Ａ是不可约的关于如何求解上述问题,人们进行了不懈的努力,提出了许多行之有效的算法［１－８］．其中分治算法因具有良好的并行性而引人注目．分治算法的典型代表是基于同伦连续的分治算法［２,３,４］和基于Ｎｅｗｔｏｎ迭代的分治算法［１］．本文提出一种新的分…     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.     

凸可行问题的一种强收敛算法

无限维Hilbert空间中,解凸可行问题的平行投影算法通常是弱收敛的.本文对一般的平行投影算法进行改进,设计了一种解凸可行问题的具有强收敛性的新算法.该算法主要是在原有算法基础上引入了一个参数序列,在参数序列满足一定的控制条件下保证了算法的强收敛性.为了简单证明算法的强收敛性,我们构建了一个新的积空间,然后把原空间的这种改进平行投影算法转换为积空间中的交替投影算法.这样,改进的平行投影算法的强收敛性就可以通过交替投影算法的收敛性证明得到.     

Parareal算法的均方稳定性分析

Parareal算法是一种非常有效的实时并行计算方法.与传统的并行计算方法相比,该算法的显著特点是它的时间并行性-先将整个计算时间划分成若干个子区间,然后在每个子区间内同时进行计算.Parareal算法收敛速度快,并行效率高,且易于编程实现,从2001年由Lions,Maday和Turinici等人首次提出至今,在短短...     

A simulation tool for the performance evaluation of parallel branch and bound algorithms

Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.