计算数学与科学工程计算及其在中国的若干发展 (迎接ICM2002特约文章)

本文论述了计算数学与科学工程计算的重要性，回顾了近50年来这一学科在中国的发展，特别是冯康的杰出贡献，介绍了国家重点基础研究发展规划相关项目的研究课题。     

The Optical Implementation of High Efficiency Packed Redundant Binary Number Addition Based on Boolean Polarization－encoded Logic Algebra

Ｔｈｅ　Ｏｐｔｉｃａｌ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　Ｈｉｇｈ　Ｅｆｆｉｃｉｅｎｃｙ　Ｐａｃｋｅｄ　Ｒｅｄｕｎｄａｎｔ　Ｂｉｎａｒｙ　Ｎｕｍｂｅｒ　Ａｄｄｉｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｂｏｏｌｅａｎ　Ｐｏｌａｒｉｚａｔｉｏｎ－ｅｎｃｏｄｅｄ　Ｌ...     

Solving Large Quadratic Assignment Problems in Parallel

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.     

"大互联网梅森素数寻求(GIMPS)"研究计划进展

梅森素数是一种特殊的素数,它的研究与寻求一直是数论研究的代表性问题之一.寻求梅森素数之路艰辛曲折,其计算复杂性对现代计算能力极具挑战.计算机网络技术的发展,特别是能使虚拟组织共享计算资源的全球分布计算技术,使得寻求速度大大加快.本文综述寻求梅森素数的最新进展及历史进程,并介绍寻求梅森数所用的分布计算技术.     

Plane-parallel biaxial plates as polarization interferometers

Plane-parallel biaxial plates as polarization interferometers. Knowing the refractive indices and the directions of the rays inside a birefringent crystal, it is possible to calculate the positions of the images formed, when a non-parallel light beam incides on it.We part from general expressions for images in plane-parallel plates of any type of medium and we use vectorial expressions for the incident and refractive rays and waves in both interfaces.From them, we obtained the interference patterns which are observed when the plate is placed between two crossed polarizers. This experimental device constitutes a polarization interferometer. In order to find the shape of the interference patterns, we superposed the wave's fronts emerging from the images determining, in this way, the phase difference curves of phase constant on a screen.     

A Subtree-Partitioning Algorithm for Inducing Parallelism in Network Simplex Dual Updates

This paper reports on thedevelopment of a very efficient method for partitioning the networksimplex basis subtree in which dual values must be updated duringa pivot. The partitioning procedure may be concurrently executedby multiple processes. The resulting rapid decomposition of thesubtree allows an arbitrary number of processes to be utilized inthe actual dual update. This approach alleviates a primary limitationof the most efficient parallel network simplex implementationpublished to date. The new code performs at least as well as theprevious implementation on medium-scale problems and reduces averagesolution time by over 34% on large-scale problems.     

Allocating modelling resources in distributed model management systems

Due to the growing popularity of distributed computing systems and the increased level of modelling activity in most organizations, significant benefits can be realized through the implementation of distributed model management systems (DMMS). These systems can be defined as a collection of logically related modelling resources distributed over a computer network. In several ways, functions of DMMS are isomorphic to those of distributed database systems. In general, this paper examines issues viewed as central to the development of distributed model bases (DMB). Several criteria relevant to the overall DMB design problem are discussed. Specifically, this paper focuses on the problem of distributing decision models and tools (solvers), henceforth referred to as theModel Allocation Problem (MAP), to individual computing sites in a geographically dispersed organization. In this research, a 0/1 integer programming model is formulated for the MAP, and an efficient dual ascent heuristic is proposed. Our extensive computational study shows in most instances heuristic-generated solutions which are guaranteed to be within 1.5–7% of optimality. Further, even problems with 420 integer and 160,000 continuous variables took no more than 60 seconds on an IBM 3090-600E computer.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

双路可编程光学多重成像并行二值逻辑处理器

基于多重成像原理，在本文中提出一种光学并行图像逻辑处理系统。对输入图案用两个正像和两个补偿进行编码。通过光调制器控制，可以实现逻辑操作的实时可编程。而且，该系统可以通过控制一组四个偏振片的状态实现独立的双输出逻辑通道，每一个输出通道各有十六种逻辑功能。文中也给出了实验结果。     

一类多步并行Runge—Kutta公式

本文构造了一类适合在多处理机系统上实现的并行Ｒｕｎｇｅ－Ｋｕｔｔａ公式，对于其中的具体公式证明了收敛性，给出它的稳定区域，数值例子表明，该公式可以有效地求解常微分方程初值问题。