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.     

Guaranteeing total balance in Metropolis algorithm Monte Carlo simulations

The condition of detailed balance has long been used as a proxy for the more difficult-to-prove condition of total balance, which along with ergodicity is required to guarantee convergence of a Markov Chain Monte Carlo (MCMC) simulation to the correct probability distribution. However, some simple-to-program update schemes such as the sequential and checkerboard Metropolis algorithms are known not to satisfy detailed balance for such common systems as the Ising model.     

Q-superlinear convergence of the iterates in primal-dual interior-point methods

Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent. Received: February 9, 2000 / Accepted: February 20, 2001?Published online May 3, 2001     

Adjustment of Residual Stresses in Unsymmetric Fiber-Reinforced Composites Using Genetic Algorithms

During the manufacturing process of multilayered fiber-reinforced composites with variable fiber orientations, residual stresses build up in these composites due to the directional expansion of single unidirectionally reinforced layers. Depending on the laminate lay-up, the inhomogeneous residual stresses, which are caused by thermal effects, moisture absorption, and chemical shrinkage, can lead to large multistable out-of-plane deformations. Instead of avoiding these curvatures, they can be advantageously used for technical applications following the near-net-shape technology. In order to adjust the deformations to the technical requirements, genetic algorithms in combination with a nonlinear calculation method have been developed, which can purposefully adapt the laminate lay-up depending on the loading and process parameters.     

A Fast, Direct Algorithm for the Lippmann–Schwinger Integral Equation in Two Dimensions

The state-of-the-art, large-scale numerical simulations of the scattering problem for the Helmholtz equation in two dimensions rely on iterative solvers for the Lippmann–Schwinger integral equation, with an optimal CPU time O(m ³ log(m)) for an m-by-m wavelength problem. We present a method to solve the same problem directly, as opposed to iteratively, with the obvious advantage in efficiency for multiple right-hand sides corresponding to distinct incident waves. Analytically, this direct method is a hierarchical, recursive scheme consisting of the so-called splitting and merging processes. Algebraically, it amounts to a recursive matrix decomposition, for a cost of O(m ³), of the discretized Lippmann–Schwinger operator. With this matrix decomposition, each back substitution requires only O(m ² log(m)); therefore, a scattering problem with m incident waves can be solved, altogether, in O(m ³ log(m)) flops.     

场景自适应的红外焦平面成像动态范围调整技术

针对红外焦平面对辐射强度较大的目标输出动态范围不足的问题,提出了一种场景自适应的红外焦平面成像动态范围调整技术。包括3个方面的内容：从图像中提取目标灰度特征,获取动态范围自适应依据;结合最小均方自适应滤波算法,对调整依据进行滤波预测后给出调节值;把灰度调节值转换成电平值,利用电平值设置红外焦平面偏置电压完成焦平面成像动态范围自适应。最后,对整体方案进行了实验验证。通过在红外焦平面成像系统中实验证明了基于场景成像动态范围自适应方法的可行性,并获得了很好的效果,成像质量有明显提高。     

逆Walsh序p值Walsh变换的演化生成及快速算法

本文利用二分演化思想和矩阵分解技术 ,重点讨论逆Walsh序三值Walsh变换的演化生成和快速算法 ,并将之推广至p值情形 .     

Conical Algorithm in Global Optimization for Optimizing over Efficient Sets

The problem of optimizing some contiuous function over the efficient set of a multiple objective programming problem can be formulated as a nonconvex global optimization problem with special structure. Based on the conical branch and bound algorithm in global optimization, we establish an algorithm for optimizing over efficient sets and discuss about the implementation of this algorithm for some interesting special cases including the case of biobjective programming problems.     

An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.