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.     

Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs

We present in this article an evolutionary procedure for solving general optimization problems. The procedure combines efficiently the mechanism of a simple descent method and of genetic algorithms. In order to explore the solution space properly, periods of optimization are interspersed with phases of interaction and diversification. An adaptation of this search principle to coloring problems in graphs is discussed. More precisely, given a graphG, we are interested in finding the largest induced subgraph ofG that can be colored with a fixed numberq of colors. Whenq is larger or equal to the chromatic number ofG, then the problem amounts to finding an ordinary coloring of the vertices ofG.     

About Compact and Sequentially Compact Coincide in Topological Groups with the Axiom （A1）

This paper is concerned with the relation between the compactness and sequential compactness in a topological space or a topological group, and show that the compactness and sequential compactness coincide in a topolpgical group with the axiom (A1).     

一类无穷矩阵代数的乘法序列连续性

设λ，μ是两个序列空间并有符号弱滑脊性，（λ，μ）是变换λ进入μ的无穷矩阵算子所成的无穷矩阵代数，本文研究了这类代数的强，Mackey、弱乘法序列连续性问题。     

不可微非线性规划的 L_1-精确罚函数法

本文提出求解不可微非线性不等式约束极小化问题的 L_1-精确罚函数算法。在有关函数为半光滑的假设下,给出了收敛性结果。     

Numerical solution of minimax problems of optimal control,part 2

In a previous paper (Part 1), we presented general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We considered two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).In this paper, the transformation techniques presented in Part 1 are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer. Both the single-subarc approach and the multiple-subarc approach are employed. Three test problems characterized by known analytical solutions are solved numerically.It is found that the combination of transformation techniques and sequential gradient-restoration algorithm yields numerical solutions which are quite close to the analytical solutions from the point of view of the minimax performance index. The relative differences between the numerical values and the analytical values of the minimax performance index are of order 10^–3 if the single-subarc approach is employed. These relative differences are of order 10^–4 or better if the multiple-subarc approach is employed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

Determination of Trace Metal Species in the Suspended Matter of Riverine and Estuarine Waters

A sequential extraction technique was used to determine the chemical species of six metals (Fe, Mn, Cu, Zn, Pb, Cd) in suspended matter of the Kaoping and Tsengwen river basins. The samples were taken to cover the fresh and marine characteristics. The precision of the species determination was estimated by the relative difference between the concentration of total metal and the sum concentation of the five species. The accuracy for the measurement of total metal was examined from the recovery of metal spiking. The accuracy of the total determination is better than 94% and the precision of speciation is greater than 90%. Most of the studied metals were found in the Fe-Mn oxides and residual fractions except that Cd, Zn and Cu have significant amounts in the exchangeable, carbonate, and organic matter phases, respectively. Species other than residual fraction are generally considered as potentially available for biota in aquatic systems, and in most cases, metal pollution could be reflected from the variation of fraction distributions.     

Universality two-dimensional Kauffman model for parallel and sequential updating

Kauffman's random Boolean nets are studied on the square lattice by computer simulation comparing parallel and sequential updating of the automata. At the phase transition the fractal dimensions of time and actual damage are found to be independent of the updating method.     

关于序列覆盖s映射

本文定义了两类序列覆盖映射，讨论了度晴空间的序列覆盖ｓ映象，特别地，我们证明了空间Ｘ具有点可数弱当且仅当Ｘ是度量空间的１序列覆盖的商ｓ映象，这回答了１９７０年Ｔ．Ｈｏｓｈｉｎａ提出了一个问题。