任意长一维DFT的MIMD并行算法

本文提出了共享与分布储计算机上任意长一维ＤＦＴ的ＭＩＭＤ并行算法，若Ｎ＝Ｏ（ｐ，ｑ），则算法需要Ｏ（「ｑ／ｐ」（３／２ｐｌｏｇｐ＋ｐ）ｐ＋３／２ｑｌｏｇｑ＋ｑ）次算术运算。其中，ｐ与Ｎ可为任意自然数，分别表示处理机台数与ＤＦＴ长度。本算法具有很高的并行效率。     

任意长度W变换的统一算法及其实现

任意长度Ｗ变换的统一算法及其实现曾泳泓，蒋增荣（国防科技大学）ＡＵＮＩＦＩＥＤＭＳＴＡＬＧＯＲＩＴＨＭＦＯＲＴＨＥＤＩＳＣＲＥＴＥＷＴＲＡＮＳＦＯＲＭＷＩＴＨＡＲＢＩＴＲＡＲＶＬＥＮＧＴＨ￥ＺｅｎｇＹｏｎｇ－ｈｏｎｇ；ＪｉａｎｇＺｅｎｇ－ｒｏｎｇ（７...     

A NOTE OF APPLICATION OF O．D．E． METHOD TO BCP ESTIMATES FOR THE POROUS MEDIUM EQUATION WITH CONVECTION

ＡＮＯＴＥＯＦＡＰＰＬＩＣＡＴＩＯＮＯＦＯ．Ｄ．Ｅ．ＭＥＴＨＯＤＴＯＢＣＰＥＳＴＩＭＡＴＥＳＦＯＲＴＨＥＰＯＲＯＵＳＭＥＤＩＵＭＥＱＵＡＴＩＯＮＷＩＴＨＣＯＮＶＥＣＴＩＯＮＬｕＧｕｏｆｕ（卢国富）（ＰｕｔｉａｎＣｏｌｌｅｅｅ，福建莆田高等专科学校，邮...     

CONFORMAL DEFORMATION OF COMPLETE SURFACE WITH NEGATIVE CURVATURE

ＣＯＮＦＯＲＭＡＬＤＥＦＯＲＭＡＴＩＯＮＯＦＣＯＭＰＬＥＴＥＳＵＲＦＡＣＥＷＩＴＨＮＥＧＡＴＩＶＥＣＵＲＶＡＴＵＲＥＺＨＯＵＤＥＴＡＮＧＭａｎｕｓｃｒｉｐｔｒｅｃｅｉｖｅｄＯｃｔｏｂｅｒ３１，１９９４．ＲｅｖｉｓｅｄＡｕｇｕｓｔ３０，１９９５．Ｄ...     

STRONG CODING THEOREM AND ASYMPTOTIC ERROR EXPONENT OF ARBITRARILY VARYING SOURCE

ＳＴＲＯＮＧＣＯＤＩＮＧＴＨＥＯＲＥＭＡＮＤＡＳＹＭＰＴＯＴＩＣＥＲＲＯＲＥＸＰＯＮＥＮＴＯＦＡＲＢＩＴＲＡＲＩＬＹＶＡＲＹＩＮＧＳＯＵＲＣＥ符方伟，沈世镒）￥ＦｉＦａｎｇｗｅｉ；ＳｈｅｎＳｉｙｉ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＮａｎｋａｉＵｎｉｖ．，Ｔ...     

A NOTE ON REGULARITY AND EXISTENCE OF SOLUTIONS FOR A CLASS OF NON－UNIFORMLY DEGENERATE ELLIPTIC EQUATIONS

ＡＮＯＴＥＯＮＲＥＧＵＬＡＲＩＴＹＡＮＤＥＸＩＳＴＥＮＣＥＯＦＳＯＬＵＴＩＯＮＳＦＯＲＡＣＬＡＳＳＯＦＮＯＮ－ＵＮＩＦＯＲＭＬＹＤＥＧＥＮＥＲＡＴＥＥＬＬＩＰＴＩＣＥＱＵＡＴＩＯＮＳ￥ＬＩＪＵＮＪＩＥ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＺｈｅｊｉａｎｇＵｎｉ...     

STRONG SUBORDINATION OF SYMMETRIC DIRICHLET FORMS

ＳＴＲＯＮＧＳＵＢＯＲＤＩＮＡＴＩＯＮＯＦＳＹＭＭＥＴＲＩＣＤＩＲＩＣＨＬＥＴＦＯＲＭＳＹＩＮＧＪＩＡＮＧＧＡＮＧＭａｎｕｓｃｒｉｐｔｒｅｃｅｉｖｅｄＭａｙ９，１９９５．ＲｅｖｉｓｅｄＭａｒｃｈ２１，１９９６．ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈ...     

NONTRIVIAL SOLUTIONS OF COMPETITIVE-DIFFUSIVE SYSTEMS WITH SMALL DIFFUSION

ＮＯＮＴＲＩＶＩＡＬＳＯＬＵＴＩＯＮＳＯＦＣＯＭＰＥＴＩＴＩＶＥ－ＤＩＦＦＵＳＩＶＥＳＹＳＴＥＭＳＷＩＴＨ　ＳＭＡＬＬＤＩＦＦＵＳＩＯＮＬｉＤａｈｕａ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＨｕａｚｈｏｎｇＵｎｉｖ．ｏｆＳｃｉ．＆Ｔｅｃｈ．，Ｗｕｈａｎ４３００７...     

A KERNEL ESTIMATOR OF A DENSITY FUNCTION IN MULTIVARIATE CASE FROM RANDOMLY CENSORED DATA

ＡＫＥＲＮＥＬＥＳＴＩＭＡＴＯＲＯＦＡＤＥＮＳＩＴＹＦＵＮＣＴＩＯＮＩＮＭＵＬＴＩＶＡＲＩＡＴＥＣＡＳＥＦＲＯＭＲＡＮＤＯＭＬＹＣＥＮＳＯＲＥＤＤＡＴＡ￥ＺｈｏｕＹｏｎｇ（周勇）（ＰｒｏｂａｂｉｌｉｔｙｌａｂｏｒａｔｏｒｙｉｎＩｎｓｔ．ｏｆＡｐｐｌ．...     

ON NECESSARY AND SUFFICIENT CONDITIONS FOR DUALS OF WAVELET FRAMES

（张泽银）（王建忠）ＯＮＮＥＣＥＳＳＡＲＹＡＮＤＳＵＦＦＩＣＩＥＮＴＣＯＮＤＩＴＩＯＮＳＦＯＲＤＵＡＬＳＯＦＷＡＶＥＬＥＴＦＲＡＭＥＳ￥ＺｈａｎｇＺｅｙｉｎ（Ｄｅｐｔ．ｏｆＭａｔｈ．，ＨｕｂａｉＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００６２，Ｃｈｉｎａ...     

Parallel Synchronous and Asynchronous Space-Decomposition Algorithms for Large-Scale Minimization Problems

Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control and Optimization, vol. 33, no. 6, pp. 1916–1925.), are presented for solving convex or nonconvex unconstrained minimization problems. The PSDM algorithms decompose the variable space into subspaces and distribute these decomposed subproblems among parallel processors. It is shown that if all decomposed subproblems are uncoupled of each other, they can be solved independently. Otherwise, the parallel algorithms presented in this paper can be used. Numerical experiments show that these parallel algorithms can save processor time, particularly for medium and large-scale problems. Up to six parallel processors are connected by Ethernet networks to solve four large-scale minimization problems. The results are compared with those obtained by using sequential algorithms run on a single processor. An application of the PSDM algorithms to the training of multilayer Adaptive Linear Neurons (Madaline) and a new parallel architecture for such parallel training are also presented.     

On Fast Computations with the Inverse to Harmonic Potential Operators via Domain Decomposition

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operations in terms of the Poincare-Steklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can be efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs are of the order O(N log^p N) and O(N log² N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations.     

N=2^t点DFT的快速卷积算法

从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. We provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(log n) using O(n/log n) processors on an . We also prove that the algorithm is the fastest possible independently of the number of processors available.     

Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function

A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.     

算术级数中的五素数平方和定理

设N是充分大的正整数满足N≡5mod 24,l和d是满足(l,d)=1的整数.A0,A>1是满足A0=600A+2000的正常数.本文证明对所有的整数0相似文献   

平行六边形区域上的快速离散傅立叶变换

In this paper, we propose a fast algorithm for computing the DGFT (Discrete Generalized Fourier Transforms) on hexagon domains [6], based on the geometric properties of the domain. Our fast algorithm (FDGFT) reduces the computation complexity of DGFT from O(N4) to O(N2 log N). In particulary, for N =2^P23^P34^P45^P56^P6, the floating point computation working amount equals to(17/2P2 16p3 135/8p4 2424/25p5 201/2P6)3N^2. Numerical examples are given to access our analysis.     

A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem

The purpose of this study is to describe a data parallel primal-dual augmenting path algorithm for the dense linear many-to-one assignment problem also known as semi-assignment. This problem could for instance be described as assigning n persons to m(n) job groups.The algorithm is tailored specifically for massive SIMD parallelism and employs, in this context, a new efficient breadth-first-search augmenting path technique which is found to be faster than the shortest augmenting path search normally used in sequential algorithms for this problem. We show that the best known sequential computational complexity of O(mn ² ) for dense problems, is reduced to the parallel complexity of O(mn), on a machine with n processors supporting reductions in O(1) time. The algorithm is easy to implement efficiently on commercially available massively parallel computers. A range of numerical experiments are performed on a Connection Machine CM200 and a MasPar MP-2. The tests show the good performance of the proposed algorithm.     

New Inexact Parallel Variable Distribution Algorithms

We consider the recently proposed parallel variable distribution(PVD) algorithm of Ferris and Mangasarian [4] for solvingoptimization problems in which the variables are distributed amongp processors. Each processor has the primary responsibility forupdating its block of variables while allowing the remainingsecondary variables tochange in a restricted fashion along some easily computable directions.We propose useful generalizationsthat consist, for the general unconstrained case, of replacing exact global solution ofthe subproblems by a certain natural sufficient descent condition, and,for the convex case, of inexact subproblem solution in thePVD algorithm. These modifications are the key features ofthe algorithm that has not been analyzed before.The proposed modified algorithms are more practical andmake it easier to achieve good load balancing among the parallelprocessors.We present a general framework for the analysis of thisclass of algorithms and derive some new and improved linear convergence resultsfor problems with weak sharp minima of order 2 and strongly convex problems.We also show that nonmonotone synchronization schemesare admissible, which further improves flexibility of PVD approach.