Computing

A bounded, convex polyhedronP inR n can be defined as the intersection of a finite number of halfspaces. Frequently, such polyhedronsP form the feasible regions of optimization problems; sometimes an optimum can only be determined when all vertices ofP are known. This paper describes an algorithm to enumerate these vertices with the help of graphs and a concept by Mañas and Nedoma [2]. Using this algorithm, it will be attempted to estimate the expected number of vertices of the examples employed by Liebling [1].

This paper presents a forward recovery method for the fault-tolerant execution of parallel software systems on multicomputers such that faults are neither detected nor diagnosed until the fault prevents progress in the computation of the system. The method minimizes the communication and synchronization overhead required to verify the reliability of the system and consequently minimizes the impact of fault-tolerance on the throughput of the computation. We say the system is credible provided that the system is diagnosable and complete, where complete means that at least one copy of each process exists on a fault-free processor. We apply the method to the process structure deriving from parallel, bounded-time decision systems and show through an exact Markov analysis that the method will yield a very credible system. We then introduce a much simpler but approximate Markov model that facilitates credibility analysis over a larger range of parameters and applications.

Backward stability of Gauss-Jordan elimination is discussed. The method proposed in [4] with some modifications is used. The basic tool of this method is the graph of the algorithm and its parallel structure. The systemUx=c, whereU is ann×n upper triangular matrix, is considered for simplicity. Then estimates of the equivalent perturbations depending quadratically onn are obtained.

The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected.

The centered form for real interval functions was first defined by R. E. Moore in his bookInterval Analysis [6]. Based on numerical experiments he conjectured that the centered form converges quadratically on the width of the range interval. The conjecture was first proved by Hansen [4] and later in a more general form by Miller [5]. In this paper a centered form is developed for circular complex interval polynomials (see [3]). This form is shown to always be an improvement on the power sum evaluation in contrast to the real case. The quadratic convergence of this form on the radius of the circular complex range interval is proved and some numerical examples are presented.

Low-power embedded technology offers a roadmap for enabling deep learning (DL) applications in mobile scenarios, like future autonomous vehicles. However, the lack of breakthrough power efficiency improvements can jeopardize the realization of truly “cognitive” mobile systems that meet real-time deadlines. This work focuses on the new generation cloud-backed mobile cognition system architecture where vehicles execute DL applications with dynamic assistance from the cloud. We unveil opportunities for power-efficient inferencing at the edge through a technique that balances inference execution across the cloud and the vehicle. This level of adaptation results in significant power efficiency improvements compared to all or nothing solutions, where inferences execute either completely on the vehicle or completely in the cloud. In addition, the cloud can have an active role in helping the vehicle to improve its DL capabilities by communicating relevant model updates, with up to 63% bandwidth savings and negligible accuracy degradation when the proposed relevance-driven federated learning technique is used. Finally, the cloud-backed mobile cognition concept is extended to the case of “flying clouds” where vehicles connect to flying drones that provide services while in flight. Although their capabilities are not on par with the stationary cloud, the flying cloud reduces services’ latency significantly and enables critical functionalities.

Vector spline techniques have been developed as general-purpose methods for vector field reconstruction. However, such vector splines involve high computational complexity, which precludes applications of this technique to many problems using large data sets. In this paper, we develop a fast multipole method for the rapid evaluation of the vector spline in three dimensions. The algorithm depends on a tree-data structure and two hierarchical approximations: an upward multipole expansion approximation and a downward local Taylor series approximation. In comparison with the CPU time of direct calculation, which increases at a quadratic rate with the number of points, the presented fast algorithm achieves a higher speed in evaluation at a linear rate. The theoretical error bounds are derived to ensure that the fast method works well with a specific accuracy. Numerical simulations are performed in order to demonstrate the speed and the accuracy of the proposed fast method.