拟线性抛物方程组具有界面外推的并行本性差分方法

构造了拟线性抛物型方程组初边值问题的一类具有界面外推的并行本性差分格式. 为给出子区域间界面上的值或者与界面相邻点处的值,给出了两类时间外推的方式, 得到了二阶精度无条件稳定的并行差分格式. 并且不作启示性假定,证明了所构造的并行差分格式的离散向量解的存在性和 唯一性. 而且在格式的离散向量解对原始问题的已知离散数据连续依赖的意义下, 证明了并行差分格式的解按离散W^(2,1)₂(Q_Δ)范数是无条件稳定的.最后证明了具有界面外推的并行本性差分格式的离散向量解收敛到原始拟线性抛物问题的唯一广义解. 给出了数值例子,数值结果表明所构造的格式是无条件稳定的, 具有二阶精度,且具有高度并行性.     

求解刚性常微分方程的并行广义Rosenbrock方法

本文构造了求解刚性常微分方程的并行广义Rosenbrock方法（PEROWs），分析了方法的收敛性和数值稳定性。通过用Powell方法优化方法的稳定域，构造了二级四阶并行格式PEROW4，并证明该方法是A－稳定的。新方法比同级的并行Rosenbrock方法MPROW3及PRM3均高一阶，因而在计算精度上处于优势。此外，PEROW4能使得各处理机上的负载基本均衡，从而达到非常理想的加速比和并行效率。     

并行分批排序问题综述

并行分批排序是兴起于上世纪末的一类新型排序问题，它最初来源于半导体生产中的芯片测试过程，有重要的应用价值，在理论上也有重要的意义．因此，并行分批排序问题近年来受到了越来越广泛的关注，新的研究成果不断涌现．本文就并行分批排序问题的最新进展作了全面的介绍，指出了许多尚未解决的问题和许多新的研究方向，给出了丰富的参考文献，旨在把感兴趣的读者迅速带到此研究领域的前沿．     

并行多机调度问题的一种遗传算法

运用遗传算法对最小化完工时间的并行多机调度问题进行了研究，给出了最小完工时间的一个下界，由此提出了初始种群的一种构造方法，并用计算实例表明该方法适用于大规模并行多机调度问题     

不交乘积和方法的并行化计算

本文探讨了不交积和方法的并行性提取问题，提出了不交乘积和方法并行计算的基本框架，实现了一种不交乘积和算法的并行化版本，测试结果显示，算法效率获得明显提高，加速比与并行节点数近乎线性关系。     

不定常并行多分裂SOR方法的收敛性

不定常并行多分裂方法是关于解线性方程组ＡＸ＝ｂ的新的并行方法，如果引入某种松驰，这些方法的收敛性能期望得以改善。本研究了不定常并行多分裂ＳＯＲ方法及其推广。如果Ａ是一个Ｈ－矩阵，且松驰参数满足０〈ωｊ〈ω０，ｊ＝１，…，ｋ，ω０〉１。     

色散方程的一类新的并行交替分段隐格式

本文给出了一组逼近色散方程的非对称差分格式，并用这组格式和对称的Crank-Nicolson型格式构造了求解色散方程的并行交替分段差分隐格式．这个格式是无条件稳定的，能直接在并行计算机上使用．数值试验表明，这个格式有很好的精度．     

并行加工系统中的一种排序算法

通过对现有单机和相同机组并行加工系统排序问题的研究，建立了一类多机非相同机组并行加工系统的排序模型，模型的优化目标是工件排序的拖期总数为极小。由于已经证明它是一个NP问题，本提出了一个针对该问题的快速、实用的启发式排序算法，并用实例说明了算法的有效性。     

求复矩阵奇异值的复单边Jacobi型方法

Rijk于1989年较详细地讨论了实矩阵奇异值分解(SVD)的单边Jacobi法;并指出在串行环境下,单边Jacobi法与流行的Golub-Reinsch法是竞争的对手,由于Jacobi型方法具有高度并行性,因而在并行环境下,单边Jacobi法就更具吸引力了.     

关于分块松弛算子中拟边界Jacobi成份的影响

分布式存贮并行计算环境中，高效率的获取一般通过区域分解或数据分割实现大粒度并行~[4]。因此，对于有效求解偏微分方程的多重网格算法~([1]、[7]),并行计算均采用网格划分进行任务分配~[6]以实现大料度并行。通讯的主体存在于松弛算子，其并行度是影响算法并行效率高低的关键因素。     

Algorithms for solving inverse geophysical problems on parallel computing systems

For solving inverse gravimetry problems, efficient stable parallel algorithms based on iterative gradient methods are proposed. For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, a parallel matrix sweep algorithm, a square root method, and a conjugate gradient method with preconditioner are proposed. The algorithms are implemented numerically on a parallel computing system of the Institute of Mathematics and Mechanics (PCS-IMM), NVIDIA graphics processors, and an Intel multi-core CPU with some new computing technologies. The parallel algorithms are incorporated into a system of remote computations entitled “Specialized Web-Portal for Solving Geophysical Problems on Multiprocessor Computers.” Some problems with “quasi-model” and real data are solved.     

A Parallel Projection for the Multicommodity Network Model

We present an application of parallel computing techniques to the solution of a quadratic programme that arises in the resource-directive decomposition method for multicommodity problems. A sequential algorithm for the quadratic programme is discussed, and its extension to a parallel implementation is given. Computational testing of the sequential and parallel algorithms was done on the Sequent Symmetry S81 parallel computer located in the Parallel Processing Laboratory at Southern Methodist University. On several large test problems the parallel version achieved a speed-up of 10 with 12 processors.     

Parallel algorithms for a singularly perturbed parabolic problem

This article deals with iterative algorithms for domain decomposition applied to the solution of a singularly perturbed parabolic problem. These algorithms are based on finite difference domain decomposition methods and are suitable for parallel computing. Convergence properties of the algorithms are established. Numerical results for test problems are presented. © 1999 Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 389–405, 1999     

A parallel interior point algorithm for linear programming on a network of transputers

Interior Point algorithms have become a very successful tool for solving large-scale linear programming problems. The Dual Affine algorithm is one of the Interior Point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel Dual Affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorisation, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequentialFortran 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.     

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.     

Stabbers of line segments in the plane

The problem of computing a representation of the stabbing lines of a set S of segments in the plane was solved by Edelsbrunner et al. We provide efficient algorithms for the following problems: computing the stabbing wedges for S, finding a stabbing wedge for a set of parallel segments with equal length, and computing other stabbers for S such as a double-wedge and a zigzag. The time and space complexities of the algorithms depend on the number of combinatorially different extreme lines, critical lines, and the number of different slopes that appear in S.     

Distributing evolutionary computation in a networked multi-agent environment

It has become increasingly popular to employ evolutionary algorithms to solve problems in different domains, and parallel models have been widely used for performance enhancement. Instead of using parallel computing facilities or public computing systems to speed up the computation, we propose to implement parallel evolutionary computation models on networked personal computers (PCs) that are locally available and manageable. To realize the parallelism, a multi-agent system is presented in which mobile agents play the major roles to carry the code and move from machine to machine to complete the computation dynamically. To evaluate the proposed approach, we use our multi-agent system to solve two types of time-consuming applications. Different kinds of experiments were conducted to assess the developed system, and the preliminary results show its promise and efficiency.     

Decomposition Algorithms for Stochastic Programming on a Computational Grid

We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample-average approximations of problems from the literature.     

Proximal minimizations with D-functions and the massively parallel solution of linear network programs

This paper discusses the massively parallel solution of linear network programs. It integrates the general algorithmic framework of proximal minimization with D-functions (PMD) with primal-dual row-action algorithms. Three alternative algorithmic schemes are studied: quadratic proximal point, entropic proximal point, and least 2-norm perturbations. Each is solving a linear network problem by solving a sequence of nonlinear approximations. The nonlinear subproblems decompose for massively parallel computing. The three algorithms are implemented on a Connection Machine CM-2 with up to 32K processing elements, and problems with up to 16 million variables are solved. A comparison of the three algorithms establishes their relative efficiency. Numerical experiments also establish the best internal tactics which can be used when implementing proximal minimization algorithms. Finally, the new algorithms are compared with an implementation of the network simplex algorithm executing on a CRAY Y-MP vector supercomputer.     

Iterative algorithms of domain decomposition for the solution of a quasilinear elliptic problem

This paper deals with iterative algorithms for domain decomposition applied to the solution of a quasilinear elliptic problem. Two iterative algorithms are examined: the first one is the Schwarz alternating procedure and the second algorithm is suitable for parallel computing. Convergence results are established in the two-domain and multidomain decomposition cases. Some issues of parallel implementation of these algorithms are discussed.