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.     

A parallel asynchronous Newton algorithm for unconstrained optimization

A new approach to the solution of unconstrained optimization problems is introduced. It is based on the exploitation of parallel computation techniques and in particular on an asynchronous communication model for the data exchange among concurrent processes. The proposed approach arises by interpreting the Newton method as being composed of a set of iterative and independent tasks that can be mapped onto a parallel computing system for the execution.Numerical experiments on the resulting algorithm have been carried out to compare parallel versions using synchronous and asynchronous communication mechanisms in order to assess the benefits of the proposed approach on a variety of parallel computing architectures. It is pointed out that the proposed asynchronous Newton algorithm is preferable for medium and large-scale problems, in the context of both distributed and shared memory architectures.This research work was partially supported by the National Research Council of Italy, within the special project Sistemi Informatici e Calcolo Parallelo, under CNR Contract No. 90.00675.PF69.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

Algorithm composition scheme for problems in composite domains based on the difference potential method

An algorithm composition scheme for the numerical solution of boundary value problems in composite domains is proposed and illustrated using an example. The scheme requires neither difference approximations of the boundary conditions nor matching conditions on the boundary between the subdomains. The scheme is suited for multiprocessor computers.     

Local and parallel finite element method for solving the biharmonic eigenvalue problem of plate vibration

In this paper, we establish a new local and parallel finite element discrete scheme based on the shifted‐inverse power method for solving the biharmonic eigenvalue problem of plate vibration. We prove the local error estimation of finite element solution for the biharmonic equation/eigenvalue problem and prove the error estimation of approximate solution obtained by the local and parallel scheme. When the diameters of three grids satisfy H⁴ = ?(w²) = ?(h), the approximate solutions obtained by our schemes can achieve the asymptotically optimal accuracy. The numerical experiments show that the computational schemes proposed in this paper are effective to solve the biharmonic eigenvalue problem of plate vibration.     

On error estimates in the Galerkin method for hyperbolic equations

We consider the Cauchy problem in a Hilbert space for a second-order abstract quasilinear hyperbolic equation with variable operator coefficients and nonsmooth (but Bochner integrable) free term. For this problem, we establish an a priori energy error estimate for the semidiscrete Galerkin method with an arbitrary choice of projection subspaces. Also, we establish some results on existence and uniqueness of an exact weak solution. We give an explicit error estimate for the finite element method and the Galerkin method in Mikhlin form.     

A local parallel superconvergence method for the incompressible flow by coarsening projection

In this article, we investigate a local parallel superconvergence method by coarsening projection for the incompressible Stokes flow. The method is a combination of the local superconvergence technique and the given framework of local parallel method. For the smooth subdomains, the local superconvergence method is applied in a higher order finite dimensional space corresponding to an appropriate coarse mesh on interior domain. Moreover, a useful and flexible local parallel method is designed to obtain the local parallel superconvergence results of presented method, which offset theoretical limitation of the model without the smoothness of the exact solution and a priori regularity of the underlying problem over the whole domain. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1209–1223, 2015     

Pseudo-conjugate directions for the solution of the nonlinear unconstrained optimization problem on a parallel computer

Parallel algorithms and test case results for the solution of the unconstrained optimization problem are presented. The algorithms involve the use of pseudo-conjugate directions (directions which tend to become conjugate as the solution is approached). It is shown that the algorithms are both fast and robust. Although all the algorithms of this paper involve the parallel execution of linear search procedures, a critical differentiation can be made among them, depending on whether the linear searches are performed along the same direction (parallel unidirectional algorithms) or different directions (parallel multidirectional algorithms).     

Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem

This article presents a branch-and-bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm economizes the required computations by conducting the branch-and-bound search in ^p, rather than in ⁿ, where p is the number of ratios in the objective function of problem (P) and n is the number of decision variables in problem (P). To implement the algorithm, the main computations involve solving a sequence of convex programming problems for which standard algorithms are available.     

Parallel implementation of Newton’s method for solving large-scale linear programs

Parallel versions of a method based on reducing a linear program (LP) to an unconstrained maximization of a concave differentiable piecewise quadratic function are proposed. The maximization problem is solved using the generalized Newton method. The parallel method is implemented in C using the MPI library for interprocessor data exchange. Computations were performed on the parallel cluster MVC-6000IM. Large-scale LPs with several millions of variables and several hundreds of thousands of constraints were solved. Results of uniprocessor and multiprocessor computations are presented.     

Error estimates in S P for cubature formulas exact for haar polynomials in the two-dimensional case

On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for $ \left\| {\delta _N (f)} \right\|_{S_p^* } On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for with the number of nodes N ∼ 2 ^d , where d → ∞. For N ∼ 2 ^d with d → ∞, it is shown that the norm of δ _N for the formulas under study has the best convergence rate, which is equal to N ^−1/p . Original Russian Text ? K.A. Kirillov, M.V. Noskov, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 1, pp. 3–13.     

Global optimization method using adaptive and parallel ensemble of surrogates for engineering design optimization

As a robust and efficient technique for global optimization, surrogate-based optimization method has been widely used in dealing with the complicated and computation-intensive engineering design optimization problems. It’s hard to select an appropriate surrogate model without knowing the behaviour of the real system a priori in most cases. To overcome this difficulty, a global optimization method using an adaptive and parallel ensemble of surrogates combining three representative surrogate models with optimized weight factors has been proposed. The selection of weight factors is treated as an optimization problem with the desired solution being one that minimizes the generalized mean square cross-validation error. The proposed optimization method is tested by considering several well-known numerical examples and one industrial problem compared with other optimization methods. The results show that the proposed optimization method can be a robust and efficient approach in surrogate-based optimization for locating the global optimum.     

浅水波方程的一种特征-Galerkin方法及其误差估计

给出求解二维浅水波方程组的一种特征－－Galerkin方法，并给出该方法的误差估计。     

一类抛物型偏微分方程的特征中心差分方法

运用特征中心差分方法来求解一类抛物型偏微分方程.通过对网格的不均匀剖分来离散方程,得到方程的特征中心差分格式.作了H1误差估计,给出了相应的定理.数值实验表明该方法对解此类问题是高效稳定的.     

离散时间单重休假两部件并联可修系统的可靠性分析

利用离散向量Markov过程方法研究了离散时间单重休假两同型部件并联可修系统.在部件寿命服从几何分布,修理时间和修理工休假时间服从一般离散型概率分布的假定下,引入修理时间和休假时间尾概率,求得了系统的稳态可用度、稳态故障频度、待修概率、修理工空闲概率和休假概率,以及首次故障前平均时间等可靠性指标.并通过具体数值实例展示了离散向量马氏链状态转移频度的具体计算方法.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

Pointwise error estimates of the local discontinuous Galerkin method for a second order elliptic problem

In this paper we derive some pointwise error estimates for the local discontinuous Galerkin (LDG) method for solving second-order elliptic problems in (). Our results show that the pointwise errors of both the vector and scalar approximations of the LDG method are of the same order as those obtained in the norm except for a logarithmic factor when the piecewise linear functions are used in the finite element spaces. Moreover, due to the weighted norms in the bounds, these pointwise error estimates indicate that when at least piecewise quadratic polynomials are used in the finite element spaces, the errors at any point depend very weakly on the true solution and its derivatives in the regions far away from . These localized error estimates are similar to those obtained for the standard conforming finite element method.

     

Error estimates of the DtN finite element method for the exterior Helmholtz problem

A priori error estimates are established for the DtN (Dirichlet-to-Neumann) finite element method applied to the exterior Helmholtz problem. The error estimates include the effect of truncation of the DtN boundary condition as well as that of the finite element discretization. A property of the Hankel functions which plays an important role in the proof of the error estimates is introduced.     

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.     

Uniform point-wise error estimates of semi-implicit compact finite difference methods for the nonlinear Schrödinger equation perturbed by wave operator

This study is devoted to analysis of semi-implicit compact finite difference (SICFD) methods for the nonlinear Schrödinger equation (NLS) perturbed by the wave operator (NLSW) with a perturbation strength described by a dimensionless parameter ε∈(0,1]$\epsilon \in (0,1]$. Uniform l^∞$l^{\infty }$-norm error bounds of the proposed SICFD schemes are built to give immediate insight on point-wise error occurring as time increases, and the explicit dependence of the mesh size and time step on the parameter ε is also figured out. In the small ε   regime, highly oscillations arise in time with O(ε²)$O({\epsilon }^2)$-wavelength. This highly oscillatory nature in time as well as the difficulty raised by the compact FD discretization make establishing the l^∞$l^{\infty }$-norm error bounds uniformly in ε   of the SICFD methods for NLSW to be a very interesting and challenging issue. The uniform l^∞$l^{\infty }$-norm error bounds in ε   are proved to be of O(h⁴+τ)$O(h^4+\tau )$ and O(h⁴+τ^2/3)$O(h^4+{\tau }^{2/3})$ with time step τ and mesh size h for well-prepared and ill-prepared initial data. Finally, numerical results are reported to verify the error estimates and show the sharpness of the convergence rates in the respectively parameter regimes.