一类半线性双曲系统的状态观测问题

本文考虑一类半线性双曲系统的状态观测问题,给出了一个(求解)算法并证明了其在某种相当强的意义上的有效性.     

具有磁场效应的非线性Schrdinger方程组的拟谱方法

考察一类具有磁场效应的非线性Ｓｃｈｒｏｄｉｎｇｅｒ方程组的周期初值问题，构造了全离散的Ｆｏｕｒｉｅｒ拟谱格式，利用有界延拓法，证明了其格式的收敛性与稳定性，并给出了误差估计及其算法分析，为对此模型的数值分析提供了理论基础和一个有效的算法．最后，通过数值例子，检验了理论结果的可信性．     

A generalized eigenmode algorithm for reducible regular matrices over the max-plus algebra with applications to the Metro-bus public transport system in Mexico city

In this paper, an algorithm for computing a generalized eigenmode of reducible regular matrices over the max-plus algebra is applied to the Metro-bus public transport system in Mexico city. A timed event Petri net model is constructed from the data table that characterizes the transport system. A max-plus recurrence equation, with a reducible and regular matrix, is associated with the transport system timed event Petri net. Next, given the reducible and regular matrix, the problem consists of giving an algorithm which will tell us how to compute its generalized eigenmode over the max plus algebra. The solution to the problem is achieved by studying some type of recurrence equations. In fact, by transforming the reducible regular matrix into its normal form, and considering a very specific recurrence equation, an explicit mathematical characterization is obtained, upon which the algorithm is constructed. The generalized eigenmode obtained sets a timetable for the transport system.     

The pivot and probe algorithm for solving a linear program

In [7] we defined acandidate constraint as one which, for at least one pivot step, contains a potential pivot, discovered that most constraints are never candidate, and devised a modification of the simplex method in which only constraints which are currently candidates are updated. In this paper we present another way to take advantage of this fact. We begin by solving a relaxed linear program consisting of the constraints of the original problem which are initially candidates. Its solution gives an upper bound to the value of the original problem. We also introduce the idea of a probe, that is, a line segment joining two vectors for the primal problem, one of which is primal feasible, and use it to identify a most violated constraint; at the same time this gives a lower bound to the objective value of the original problem. This violated constraint is added to the relaxed problem which is solved again, which gives a new upper bound etc. We present computational experience indicating that time savings of 50–80% over the simplex method can be obtained by this method, which we call PAPA, the Pivot and Probe Algorithm. This report was prepared as part of the activities of the Management Science Research Group, Carnegie-Mellon University, under Contract No. N00014-75-C-0621 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or part is permitted for any purpose of the U.S. Government.     

Proof of algorithms by general snapshots

A constructive approach to the question of proofs of algorithms is to consider proofs that an object resulting from the execution of an algorithm possesses certain static characteristics. It is shown by an elementary example how this possibility may be used to prove the correctness of an algorithm written in ALGOL 60. The stepping stone of the approach is what is called General Snapshots, i.e. expressions of static conditions existing whenever the execution of the algorithm reaches particular points. General Snapshots are further shown to be useful for constructing algorithms.     

Applications of the method of partial inverses to convex programming: Decomposition

A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.This research was sponsored, in part, by the Air Force Office of Scientific Research under grant 80-0195.     

An algorithm for then×n optimum assignment problem

In this paper we present an algorithm for finding an optimum assignment for ann×n matrixM inn iterations. The method uses systematic permutations on the rows ofM and is based on the properties of optimum assignments. The implementation presented in the paper requires at mostO(n ³) in time andn ²+6n memory locations for solving a densen×n problem.This work was supported by the National Science Foundation Grant NSF ENG 74-19788.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

A simple numerical technique for transient creep flows with free surfaces

A simple, but powerful iterative technique is presented for the numerical solution of the time-dependent flow of an incompressible viscous fluid with or without a free surface. The usual numerical stability restrictions related to the viscous acceleration terms are avoided using standard implicit differencing techniques. The properties and accuracy of the method are illustrated by several calculational examples.     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.