Optimal estimation of sensor biases for asynchronous multi-sensor data fusion

An important step in a multi-sensor surveillance system is to estimate sensor biases from their noisy asynchronous measurements. This estimation problem is computationally challenging due to the highly nonlinear transformation between the global and local coordinate systems as well as the measurement asynchrony from different sensors. In this paper, we propose a novel nonlinear least squares formulation for the problem by assuming the existence of a reference target moving with an (unknown) constant velocity. We also propose an efficient block coordinate decent (BCD) optimization algorithm, with a judicious initialization, to solve the problem. The proposed BCD algorithm alternately updates the range and azimuth bias estimates by solving linear least squares problems and semidefinite programs. In the absence of measurement noise, the proposed algorithm is guaranteed to find the global solution of the problem and the true biases. Simulation results show that the proposed algorithm significantly outperforms the existing approaches in terms of the root mean square error.     

Event-driven stochastic approximation

We consider a Robbins-Monro type iteration wherein noisy measurements are event-driven and therefore arrive asynchronously. We propose a modification of step-sizes that ensures desired asymptotic behaviour regardless of this aspect. This generalizes earlier results on asynchronous stochastic approximation wherein the asynchronous behaviour is across different components, but not along the same component of the vector iteration, as is the case considered here.     

Performance analysis of asynchronous parallel Jacobi

The directed acyclic graph (DAG) associated with a parallel algorithm captures the partial order in which separaT.L.cal computations are completed and how their outputs are subsequently used in further computations. Unlike in a synchronous parallel algorithm, the DAG associated with an asynchronous parallel algorithm is not predetermined. Instead, it is a product of the asynchronous timing dynamics of the machine and cannot be known in advance, as such it is best thought of as a pseudorandom variable. In this paper, we present a formalism for analyzing the performance of asynchronous parallel Jacobi’s method in terms of its DAG. We use this app.roach to prove error bounds and bounds on the rate of convergence. The rate of convergence bounds is based on the statistical properties of the DAG and is valid for systems with a non-negative iteration matrix. We supp.ort our theoretical results with a suit of numerical examples, where we compare the performance of synchronous and asynchronous parallel Jacobi to certain statistical properties of the DAGs associated with the computations. We also present some examples of small matrices with elements of mixed sign, which demonstrate that determining whether a system will converge under asynchronous iteration in this more general setting is a far more difficult problem.     

Automata transformations of prefix decidable and decidable by Buchi superwords

We show that the set of prefix decidable superwords is closed under finite automata and asynchronous automata transformations. We prove that structures of degrees of finite automata and asynchronous automata transformations contain an atom which consists of prefix decidable superwords with undecidable monadic theory (or undecidable by Buchi). Also we prove that the structure of degrees of asynchronous automata transformations contains an atom which consists of superwords with decidable monadic theory (decidable by Buchi).     

EXPERIMENTAL STUDY OF THE ASYNCHRONOUS MULTISPLITTING RELAXATION METHODS FOR THE LINEAR COMPLEMENTARITY PROBLEMS

We study the numerical behaviours of the relaxed asynchronous multisplitting methods for the linear complementarity problems by solving some typical problems from practical applications on a real multiprocessor system. Numerical results show that the parallel multisplitting relaxation methods always perform much better than the corresponding sequential alternatives, and that the asynchronous multisplitting relaxation methods often outperform their corresponding synchronous counterparts. Moreover, the two-sweep relaxed multisplitting methods have better convergence properties than their corresponding one-sweep relaxed ones in the sense that they have larger convergence domains and faster convergence speeds. Hence, the asynchronous multisplitting unsymmetric relaxation iterations should be the methods of choice for solving the large sparse linear complementarity problems in the parallel computing environments.     

On asynchronous iterations in partially ordered spaces

We extend the idea of asynchronous iterations to self-mappings of product spaces with infinitely many components. In addition to giving a rather general convergence theorem we study in some detail the case of isotone and isotonically decomposable mappings in partially ordered spaces. In particular, we obtain relationships between asynchronous iterations and the total step method and results on enclosures for fixed points. They appear to be new, even for mappings defined on a product space with only finitely many components.     

The Local Approximation Theorem in Various Coordinate Systems

We find some sufficient conditions on the local coordinate system of a Carnot–Carathéodory space of low smoothness that ensure Gromov-type estimates on the divergence of local (quasi)metrics. We also obtain these estimates for the canonical coordinate system of the second kind and various mixed coordinate systems.     

Asynchronous Richardson iterations: theory and practice

Numerical Algorithms - We consider asynchronous versions of the first- and second-order Richardson methods for solving linear systems of equations. These methods depend on parameters whose values...     

矩阵多分裂迭代法的收敛条件

本文给出了求解非奇异线性方程组的矩阵多分裂并行迭代法的一些新的收敛结果.当系数矩阵单调和多分裂序列为弱正则分裂时,得到了几个与已有的收敛准则等价的条件,并且证明了异步迭代法在较弱条件下的收敛性.对于同步迭代,给出了与异步迭代不同且较为宽松的收敛条件.     

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

     

Parallel asynchronous label-correcting methods for shortest paths

We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI.     

基于开关控制的线性奇异系统的二次状态反馈镇定问题

主要讨论基于开关控制的线性奇异系统的二次状态反馈镇定问题.利用二次反馈镇定的概念,给出了线性奇异系统基于异步开关控制的二次状态反馈镇定问题可解的两个充分条件.进一步,对于带有范数有界的不确定项的奇异线性系统,给出了其可以基于异步开关控制的二次状态反馈鲁棒镇定的可解性条件.     

Asynchronous and corrected-asynchronous finite difference solutions of PDEs on MIMD multiprocessors

A major problem in achieving significant speed-up on parallel machines is the overhead involved with synchronizing the concurrent processes. Removing the synchronization constraint has the potential of speeding up the computation, while maintaining greater computation flexibility (e.g. differences in processors speed; differences in the data input to processors). We construct asynchronous (AS) finite difference schemes for the solution of PDEs by removing the synchronization constraint. We analyze the numerical properties of these schemes. Based on the analysis, we develop corrected-asynchronous (CA) finite difference schemes which are specifically constructed for an asynchronous processing. We present asynchronous (AS) and corrected-asynchronous (CA) finite difference schemes for the multi-dimensional heat equation. Although our discussion concentrates on the Euler scheme it should serve only as a sample, as it can be extended to other schemes and other PDEs.These schemes are implemented on the shared-memory multi-userSequent Balance machine. Numerical results for one and two dimensional problems are presented. It is shown experimentally that synchronization penalty can be about 50% of run time: in most cases, the asynchronous scheme runs twice as fast as the parallel synchronous scheme. In general, the efficiency of the parallel schemes increases with processor load, with the time-level, and with the problem dimension. The efficiency of the AS may reach 90% and over, but it provides accurate results only for steady-state values. The CA, on the other hand, is less efficient but provides more accurate results for intermediate (non steady-state) values. The results show the potential of developing asynchronous finite deference schemes for steady-state as well as non steadystate problems.This research was partially supported by a grant from The Basic Research Foundation administrated by The Israel Academy of Sciences and Humanities.A reduced version of the paper was presented at the 4th SIAM Conference on Parallel Processing for Scientific Computing, Dec. 11–13, 1989, Chicago, USA.The work by this author was supported by research grant 337 of the Israeli National Council for Research and Development in the years 1990–1991.This research was supported by the National Aeronautics and Space Administration under NASA Contract No. NASI-18107 while the author was in residence at the Institute for Computer Applications in Sciences and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23665, USA.     

RELAXED ASYNCHRONOUS ITERATIONS FOR THE LINEAR COMPLEMENTARITY PROBLEM

1. IntroductionConsider the large sparse Linear Complementarity Problem (LCP):where .1I = (mkj) 6 L(R") is a gitren real matrix and q = (qk) E R" a given real vector. Thisproblem arises in many areas of scientific computing. FOr example, it arises from problemsin (linear and) contrex quadratic programming, the prob1em of finding a Nash equilibriumpoint of a bimatrix game (e.g., Cottle and Dantzig[5] and Lemke[13]), a11d also a number of freeboundary problems of fluid mechanics (e.g., Cr…     

Asynchronous exponential growth for an age dependent population equation with delayed birth process

We show that the solutions of a population equation with age structure and delayed birth process have asynchronous exponential growth (AEG). We use operator matrices and Hille-Yosida operators as well as Perron-Frobenius techniques.     

Metric properties of functions defined by partial automata

We characterize natural categories in which morphisms are defined by partial automata of the following three types: asynchronous automata, window automata, and automata synchronous over finite alphabets. We distinguish subcategories whose morphisms are defined by finite automata.     

解椭圆变分不等式问题的区域分裂与异步并行算法

本文给出了两类解椭圆变分不等式问题的区域分裂异步并行算法，证明了解在Ｈ＾１－模意义下的收敛性，并给出离散格式及算例。     

Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements

We study and compare asynchronous parallelization strategies for tabu search, and evaluate the impact on performance and solution quality of some important algorithmic design parameters: number of processors, handling of exchanged information, etc. Parallelization approaches are implemented and compared by using a tabu search algorithm for multicommodity location-allocation problems with balancing requirements.     

Synchronous motion of two vertically excited planar elastic pendula

The dynamics of two planar elastic pendula mounted on the horizontally excited platform have been studied. We give evidence that the pendula can exhibit synchronous oscillatory and rotation motion and show that stable in-phase and anti-phase synchronous states always co-exist. The complete bifurcational scenario leading from synchronous to asynchronous motion is shown. We argue that our results are robust as they exist in the wide range of the system parameters.     

A general asynchronous block iterative model with related convergence conditions

This paper formulates a general time-varying asynchronous block-iterative model. A convergence condition for asynchronous block-iterations based on this model is given, compared to existing conditions for similar and shown to be strictly weaker.