A modular integer GCD algorithm

This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U−bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (−p/2,p/2) such that . When the algorithm is executed on a bit common CRCW PRAM with O(nlognlogloglogn) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/logn) time on the same number of processors.     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

智能工作站主机的MMPIS实验模型研究──一个全互连式结构MMPIS硬件环境的设计与实现

本文介绍中日国际合作开发研究的Ａ１型智能网（Ａ１型ＩＮ）智能工作站（ＩＷ）主机的并行推理硬件结构的实验模型设计与实现，给出了一种并行推理硬件支持环境实现方案和该方案在实现中若干问题的解决方法。     

Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.     

On a Question of Phillips

In [5] Phillips proved that one can obtain the additive group of any nonstandard model *? of the ring ? of integers by using a linear mod 1 function h : F ?, where F is the α-dimensional vector space over ? when α is the cardinality of *?. In this connection it arises the question whether there are linear mod 1 functions which are neither addition nor quasi-linear. We prove that this is the case.     

A New Simple Ultrahigh Speed Decoding Algorithm for BCH Code

1　Ｉｎｔｒｏｄｕｃｔｉｏｎ　　Ｍｏｄｅｒｎｄｉｇｉｔａｌｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍｓｏｆｔｅｎｒｅｑｕｉｒｅｅｒｒｏｒ ｆｒｅｅｔｒａｎｓｍｉｓｓｉｏｎ .Ｅｒｒｏｒｃｏｎｔｒｏｌｃｏｄｉｎｇｔｅｃｈｎｏｌｏｇｙｈａｓｂｅｅｎｕｓｅｄｗｉｄｅｌｙｉｎｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍ .Ａｎｄｉｔｈａｓｂｅｅｎｉｍｐｒｏｖｉｎｇｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍ ｇｒｅａｔｌｙ ,ｅｓｐｅｃｉａｌｌｙｉｎｗｉｒｅｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎｓｓ…     

具有平行平均曲率向量子流形的曲率估计与稳定性

本文估计空间形式中具有平行平均曲率向量子流形上共形度量的数量曲率上界,并利用其研究了具有常平均曲率超曲面的稳定性．     

SUN5500小型机MPI编程与蕴式并行计算的实现方法

基于SUN5500小型计算机并行开发环境，给出了消息传递模型和蕴式行模型的实现方法，通过实例分析了SUNMPI实际编程，并对选取不同模型有不同参数的运算时间进行了比较，结果表明，在SUN5500计算机上MPI模型和蕴式并行模型均能较大地提高运算速度，而且MPI在灵活性和并行程度方面更优。     

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.