Alternating direction splitting for block Angular parallel optimization

We develop and compare three decomposition algorithms derived from the method of alternating directions. They may be viewed as block Gauss-Seidel variants of augmented Lagrangian approaches that take advantage of block angular structure. From a parallel computation viewpoint, they are ideally suited to a data parallel environment. Numerical results for large-scale multicommodity flow problems are presented to demonstrate the effectiveness of these decomposition algorithmims on the Thinking Machines CM-5 parallel supercomputer relative to the widely-used serial optimization package MINOS 5.4.This material is based on research supported by the Air Force Office of Scientific Research, Grants AFORS-89-0410 and F49620-1-0036, and by NSF Grants CCR-89-07671, CDA-90-24618, and CCR-93-06807. The work of the second author was supported partially by Grant 95.00732.CT01 from the Italian National Research Council (CNR).     

The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm

Four new shortest-path algorithms, two sequential and two parallel, for the source-to-sink shortest-path problem are presented and empirically compared with five algorithms previously discussed in the literature. The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of Dial et al., with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest-path algorithm. The new parallel algorithm, PS22, is based on S22 and is the best of the parallel algorithms. We also present results for three new S22-type shortest-path heuristics. These heuristics find very good (often optimal) paths much faster than the best shortest-path 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.     

A parallel algorithm for constrained concave quadratic global minimization

The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.     

Efficient Parallel Algorithms for the Minimum Cost Flow Problem

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the -relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the -relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.     

A Stochastic Approximation Frame Algorithm with Adaptive Directions

Stochastic approximation problem is to find some root or extremum of a non- linear function for which only noisy measurements of the function are available.The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm,which uses the noisy evaluation of the negative gradient direction as the iterative direction.In order to accelerate the RM algorithm,this paper gives a flame algorithm using adaptive iterative directions.At each iteration,the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions.Two feasible choices of the criterions are pro- posed and two corresponding flame algorithms are formed.Different choices of the directions under the same given switch criterion in the flame can also form different algorithms.We also proposed the simultanous perturbation difference forms for the two flame algorithms.The almost surely convergence of the new algorithms are all established.The numerical experiments show that the new algorithms are promising.     

A delay differential equation solver based on the parallel Adams algorithms

IntroductionWith the rapid development of science and technology, a lot of delay-dynamic systems invarious fields of natural and social science have arisentl]. The presented delay systems are oftenof both multiparameter and largescale, that is, so-called large systems. Considering scientificcomputation and real-time simulation, the classical serial algorithmsIZ--4] have not fulfilled therequirements for solying this kind of systems. So, it becomes quite emergent to construct thefast algorithm…     

PARALLEL ALGORITHMS OF ONE-LEG METHOD AND ITERATED DEFECT CORRECTION METHODS

The parallel algorithms of iterated defect correction methods (PIDeCM's) are constructed, which are of efficiency and high order B-convergence for general nonlinear stiff systems in ODE'S. As the basis of constructing and discussing PIDeCM's. a class of parallel one-leg methods is also investigated, which are of particular efficiency for linear systems.     

The smoothing effect of a simultaneous directions parallel method as applied to Poisson problems

By using local Fourier analysis, a simultaneous directions parallel method, which is a particular instance of the parallel fractional step algorithm, is shown to possess smoothing effects when applied to Poisson problems. The specific smoothing factor is determined and the expected factor values are found to be consistent with those obtained. The simultaneous directions approach is an advantageous alternative to other existing smoothers in the multigrid environment. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Extensions of CGS algorithms: Generalized least-square solutions

The CGS (conjugate Gram-Schmidt) algorithms of Hestenes and Stiefel are formulated so as to obtain least-square solutions of a system of equationsg(x)=0 inn independent variables. Both the linear caseg(x)=Ax–h and the nonlinear case are discussed. In the linear case, a least-square solution is obtained in no more thann steps, and a method of obtaining the least-square solution of minimum length is given. In the nonlinear case, the CGS algorithm is combined with the Gauss-Newton process to minimize sums of squares of nonlinear functions. Results of numerical experiments with several versions of CGS on test functions indicate that the algorithms are effective.The author wishes to express appreciation and to acknowledge the ideas and help of Professor M. R. Hestenes which made this paper possible.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

Parallel algorithms for solving nonlinear two-point boundary-value problems which arise in optimal control

This paper describes a collection of parallel optimal control algorithms which are suitable for implementation on an advanced computer with the facility for large-scale parallel processing. Specifically, a parallel nongradient algorithm and a parallel variablemetric algorithm are used to search for the initial costate vector that defines the solution to the optimal control problem. To avoid the computational problems sometimes associated with simultaneous forward integration of both the state and costate equations, a parallel shooting procedure based upon partitioning of the integration interval is considered. To further speed computations, parallel integration methods are proposed. Application of this all-parallel procedure to a forced Van der Pol system indicates that convergence time is significantly less than that required by highly efficient serial procedures.This research was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3418.     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0, 2] with line search, and (0, 1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43%–91% range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

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.     

Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method

A scheme for the parallel implementation of the combined branch-and-bound method and heuristic algorithms is proposed. Results of computations for the one-dimensional Boolean knapsack problem are presented that demonstrate the efficiency of the proposed approach. The main factors that affect the speedup of the solution when local optimization is used are discussed.     

基于二重网格的定常Navier-Stokes方程的局部和并行有限元算法

对二维定常的不可压缩的Navier-Stokes方程的局部和并行算法进行了研究．给出的算法是多重网格和区域分解相结合的算法,它是基于两个有限元空间:粗网格上的函数空间和子区域的细网格上的函数空间．局部算法是在粗网格上求一个非线性问题,然后在细网格上求一个线性问题,并舍掉内部边界附近的误差相对较大的解．最后,基于局部算法,通过有重叠的区域分解而构造了并行算法,并且做了算法的误差分析,得到了比标准有限元方法更好的误差估计,也对算法做了数值试验,数值结果通过比较验证了本算法的高效性和合理性．     

A parallel algorithm for partially separable non-convex global minimization: Linear constraints

The global minimization of large-scale partially separable non-convex problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of a separable concave part, an unseparated convex part, and a strictly linear part, which are all coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. An important special class of problems which can be reduced to this form are the synomial global minimization problems. Such problems often arise in engineering design, and previous computational methods for such problems have been limited to the convex posynomial case. In the current work, a convex underestimating function to the objective function is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and convex underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results obtained on the four processor Cray 2, both sequentially and in parallel on all four processors, are also presented.     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.     

Mapping enthalpy-based solidification algorithms onto vector and parallel architectures

Effective methods are required to solve three-dimensional solidification problems with fine meshes. This paper considers some of the problems associated with mapping control volume-based enthalpy algorithms onto vector processors and transputer-based parallel networks. Although vector processors may bring speedups of a factor of 5 or so, it appears that transputer-based networks have the facility to yield speedups that increase linearly with the number of transputer chips used.