Successive underrelaxation (SUR) and generalised conjugate gradient (GCG) methods for hyperbolic difference equations on a parallel computer

When we consider the numerical solution of the 2-dimensional linear hyperbolic problem by implicit difference equations we need to solve a set of linear systems Ax = b with many rightband sides b, where A is large, sparse and nonsymmetric. The SUR (Successive Underrelaxation) and GCG (Generalised Conjugate Gradient) methods are used for solving the linear systems. We compare the two methods on sequential and parallel computations. Numerical results indicate that the SUR method is nearly twice as fast as the GCG method and the SUR method has an almost linear speedup.     

The 0—1 Integer Programming Problem in a finite ring with identity

We define the 0—1 Integer Programming Problem in a finite field or finite ring with identity as: given an m × n matrix A and an n × 1 vector b with entries in the ring R, find or determine the non-existence of a 0—1 vector x such that Ax = b. We give an easily implemented enumerative algorithm for solving this problem, along with conditions that spurious solutions occur with probability as small as desired. Finally, we show that the problem is NP-complete if R is the ring of integers modulo r for r ≥ 3. This result suggests that it will be difficult to improve on our algorithm.     

New results on oscillation for delay differential equations with piecewise constant argument

We introduce a new technique to obtain some new oscillation criteria for the oscillating coefficients delay differential equation with piecewise constant argument of the form x′(t) + a(t)x(t) + b(t)x({t − k}) = 0, where a(t) and b(t) are right continuous functions on [−k, ∞), k is a positive integer, and [·] denotes the greatest integer function. Our results improve and generalize the known results in the literature. Some examples are also given to demonstrate the advantage of our results.     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

Optimal and nearly optimal algorithms for approximating polynomial zeros

We substantially improve the known algorithms for approximating all the complex zeros of an n^th degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schönhage [1], Pan [2], and Neff and Reif [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable x has been scaled so as to confine the zeros of p(x) to the unit disc x : |x| ≤ 1, our algorithms (which promise to be practically effective) approximate all the zeros of p(x) within the absolute error bound 2^−b, by using order of n arithmetic operations and order of (b + n)n² Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n² Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).     

Initial-interval driven biasing of nodal concentration along a fixed curve

Element size transitioning in the construction of spatial meshes for finite element models is often controlled by biasing the concentration of nodes, towards one end or the other, along each of a set of curves in the model. A simple, common and efficient scheme to implement such nodal concentration biasing along a given curve is to require that the nodal spacings δ_i be (sequence) terms bⁱδ₀ of a geometric series. Current practice takes the parameter value b, or its equivalent, as an independent input, so that the initial nodal spacing δ₀ must be a computed output. This is the most straightforward approach, but the lack of direct control over the value δ₀ is a significant shortcoming. In an element size transitioning scenario, δ₀ is often a parameter for which the model builder/analyst has independent quantitative information. It may represent the a priori known thickness of a thin bond or weld, for example. A more rational choice for these cases, proposed by this paper, is a scheme for which δ₀ is an independent input parameter instead of b. The parameter b is computed by a convergence-guaranteed algorithm for which the existence of b as a single-valued function of its input is proven.     

A simple framework for real-time cryptographic protocol analysis with compositional proof rules

A real-time process algebra, enhanced with specific constructs for handling cryptographic primitives, is proposed to model cryptographic protocols in a simple way. We show that some security properties, such as authentication and secrecy, can be re-formulated in this timed setting. Moreover, we show that they can be seen as suitable instances of a general information flow-like scheme, called timed generalized non-deducibility on compositions (tGNDC), parametric w.r.t. the observational semantics of interest. We show that, when considering timed trace semantics, there exists a most powerful hostile environment (or enemy) that can try to compromise the protocol. Moreover, we present a couple of compositionality results for tGNDC, one of which is time dependent, and show their usefulness by means of a case study.     

Conditioned asymptotics for tail probabilities in large multiplexers

Consider a buffer whose input is a superposition of L independent identical sources, and which is served at rate sL. Recent work has shown that, under very general circumstances, the stationary tail probabilities for the queue of unfinished work Q in the buffer have the asymptotics P[Q > Lb] ≈ e^−LI(b) for large L. Here the shape function, I, is obtained from a variational expression involving the transient log cumulant generating function of the arrival process.

In this paper, we extend this analysis to cover time-dependent asymptotics for Markov arrival processes subject to conditioning at some instant. In applications we envisage that such conditioning would arise due to knowledge of the queue at a coarse-grained level, for example of the number of current active sources. We show how such partial knowledge can be used to predict future tail probabilities by use of a time dependent, conditioned shape function. We develop some heuristics to describe the time-dependent shape function in terms of a reduced set of quantities associated with the underlying arrivals process and show how to calculate them for renewal arrivals and a class of ON-OFF arrivals. This bypasses the full variational calculation of the shape function for such models.     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Some issues in performance modeling of data teletraffic

Data teletraffic is characterized by bursty arrival processes. Performance models are characterized by a desire to know under what circumstances is the probability that an arrival finds a full input buffer very small. In this paper I examine how four models proposed in the literature perform on two data sets of local area network traffic. Among my conclusion are (1) the protocol governing the data transmission may have a substantial effect on the statistical propoerties on the packet stream, (2) approximating the probability that a finit buffer of size b overflows may not be adequately approximated by the probability that an infinite buffer has at least b packets in it, and (3) a data-based estimate of large-deviation rate-function does the best job of estimating packet loss on these data sets. This method may overestimate the loss rate by several orders of magnitude, so there is room for further refinements.     

The product development process: the Wenger 1/1 Office Printer

A product that is adapted individually to a specific market segment, that is innovative, and that is constructed aesthetically, will be successful. In this process there is a triangular relationship between designer, client, company and market, where functional communication has to be ensured. Globally the market has segmented into age groups, so that aesthetic attitudes are independent of nationality. Design should distinguish a product from the mass by accentuating its individual characteristics and so enable the consumer to identify with it. Today's design determines tomorrow's quality of life. This article describes the process of product development as exampled by the Wenger 1/1 Office Printer.

The design development procedure is divided into three phases: (a) planning phase; (b) project phase; (c) realization phase. The printer market is described, and the most important product requirements defined. The design concept was that a product should be developed that combined the advantages of impact- and non-impact printing techniques with a new, market-influencing design, There were two options with regard to the Wenger 1/1; [a) mechanical and electronic parts combined in one housing; (b) mechanical and electronic parts in separate housings. In order to ensure optimal noise silencing, option (b) was chosen. The favored option was realized in a foam-rubber model, and details worked out. A 'function-model' was manufactured and tested to ensure performance and market-adjustment of the new product. The designer and the client then liaised to supervise the product through to serial manufacture.     

Attacking Fair-Exchange Protocols: Parallel Models vs. Trace Models

Most approaches to formal protocol verification rely on an operational model based on traces of atomic actions. Modulo CSP, CCS, state-exploration, Higher Order Logic or strand spaces frills, authentication or secrecy are analyzed by looking at the existence or the absence of traces with a suitable property.We introduced an alternative operational approach based on parallel actions and an explicit representation of time. Our approach consists in specifying protocols within a logic language ( AL _SP), and associating the existence of an attack to the protocol with the existence of a model for the specifications of both the protocol and the attack.In this paper we show that, for a large class of protocols such as authentication and key exchange protocols, modeling in AL _SP is equivalent - as far as authentication and secrecy attacks are considered - to modeling in trace based models.We then consider fair exchange protocols introduced by N. Asokan et al. showing that parallel attacks may lead the trusted third party of the protocol into an inconsistent state. We show that the trace based model does not allow for the representation of this kind of attacks, whereas our approach can represent them.     

Physical-layer security analysis of PSK quantum-noise randomized cipher in optically amplified links

The quantitative security of quantum-noise randomized cipher (QNRC) in optically amplified links is analyzed from the perspective of physical-layer advantage. Establishing the wire-tap channel models for both key and data, we derive the general expressions of secrecy capacities for the key against ciphertext-only attack and known-plaintext attack, and that for the data, which serve as the basic performance metrics. Further, the maximal achievable secrecy rate of the system is proposed, under which secrecy of both the key and data is guaranteed. Based on the same framework, the secrecy capacities of various cases can be assessed and compared. The results indicate perfect secrecy is potentially achievable for data transmission, and an elementary principle of setting proper number of photons and bases is given to ensure the maximal data secrecy capacity. But the key security is asymptotically perfect, which tends to be the main constraint of systemic maximal secrecy rate. Moreover, by adopting cascaded optical amplification, QNRC can realize long-haul transmission with secure rate up to Gb/s, which is orders of magnitude higher than the perfect secrecy rates of other encryption systems.     

Optimized refinable enclosures of multivariate polynomial pieces

An enclosure is a two-sided approximation of a uni- or multivariate function by a pair of typically simpler functions such that b⁻bb⁺ over the domain U of interest. Enclosures are optimized by minimizing the width max_Ub⁺−b⁻ and refined by enlarging the space . This paper develops a framework for efficiently computing enclosures for multivariate polynomials and, in particular, derives piecewise bilinear enclosures for bivariate polynomials in tensor-product Bézier form. Runtime computation of enclosures consists of looking up pre-optimized enclosures and linearly combining them with the second differences of b. The width of these enclosures scales by a factor 1/4 under midpoint subdivision.     

对三个多服务器环境下匿名认证协议的分析

设计安全高效的多服务器环境下匿名身份认证协议是当前安全协议领域的研究热点。基于广泛接受的攻击者模型,对多服务器环境下的三个代表性匿名认证协议进行了安全性分析.指出Wan等协议无法实现所声称的离线口令猜测攻击,且未实现用户匿名性和前向安全性;指出Amin等协议同样不能抵抗离线口令猜测攻击,且不能提供匿名性,对两种破坏前向安全性的攻击是脆弱的;指出Reedy等协议不能抵抗所声称的用户仿冒攻击和离线口令猜测攻击,且无法实现用户不可追踪性.突出强调这些协议失败的根本原因在于,违反协议设计的三个基本原则：公钥原则、用户匿名性原则和前向安全性原则.明确协议的具体失误之处,并提出相应修正方法.     

The perception and measurement of contrast: the influence of gaps between display elements

The influence of the luminance of the gap between display elements of flat panel displays (FPDs) on perceived contrast was investigated. Twelve black-on-white FPDs, differing systematically with respect to foreground, background, and gap luminance, were simulated in an experiment. Twelve subjects rated each simulation on u scale, measuring several aspects of image quality, and performed a search task with each simulated FPD. The aims of the research were (a) to validate and assess the reliability of the rating scale items concerning contrast; (b) to relate subjective to objective measures; (c) to find out if ratings improve if raters perform a task with the rated objects; and (d) to evaluate a metric for expressing FPD contrast that we recently proposed. It is concluded that (a) the scale items are reliable if the rated objects vary on the property under concern; several items consistently measured subjective contrast; (b) subjective and objective contrast were strongly related in a linear fashion; (c) without actually using the stimuli in a working task, raters were capable of producing reliable and valid ratings; and (d) the proposed effective luminance modulation (M_r) metric did, but ordinary luminance modulation did not correspond to perceived contrast. Based on this latter finding we recommend that an alternative contrast measurement procedure based on the (M_r) metric is further validated for wide gaps and negative polarity displays.     

Revision programming

In this paper we introduce revision programming — a logic-based framework for describing constraints on databases and providing a computational mechanism to enforce them. Revision programming captures those constraints that can be stated in terms of the membership (presence or absence) of items (records) in a database. Each such constraint is represented by a revision rule ← ₁,…,_k, where and all ga_i are of the form in(a) and out(b). Collections of revision rules form revision programs. Similarly as logic programs, revision programs admit both declarative and imperative (procedural) interpretations. In our paper, we introduce a semantics that reflects both interpretations. Given a revision program, this semantics assigns to any database B a collection (possibly empty) of P-justified revisions of B. The paper contains a thorough study of revision programming. We exhibit several fundamental properties of revision programming. We study the relationship of revision programming to logic programming. We investigate complexity of reasoning with revision programs as well as algorithms to compute P-justified revisions. Most importantly from the practical database perspective, we identify two classes of revision programs, safe and stratified, with a desirable property that they determine for each initial database a unique revision.     

Formations of minimalist mobile robots using local-templates and spatially distributed interactions

In this paper we address the problem of synthesizing simple rules and local interactions at the individual level so that pre-specified complex behavior emerges at the group level of a collection of autonomous mobile agents. Usually, the emergent collective behavior is used to perform certain spatial group-tasks. Specifically, we consider self-assembling of a group of mobile robots into grid, line, and wedge patterns. We introduce the notion of local-templates in which each mobile agent – capable of simple forward/backward movements and a clock-wise/counter clock-wise spin – actively encodes distinctive information into multiple non-overlapping sectorial regions of the surrounding environment in order to form pose-specific virtual links with similar minimalist agents in a local neighborhood. The resulting local patterns around each agent lead to the desired global formation. In order to take mobile robots closer to their biological counterparts, there is a need to further simplify the manner in which they currently perceive their surroundings, communicate with their neighbors, and compute their actions. We have built a robotic platform consisting of four wheeled-mobile robots that are christened as Kinbots. They are similar in principle to Braitenberg Vehicles and use simple perception/interaction/actuation techniques to achieve individual vehicle complexity and produce effective group behavior through cooperation. To validate the proposed approach, we demonstrate a column-formation task in computer simulations and physical experiments. We illustrate an experiment which is representative of various prominent stages in a group-formation task such as formation-achievement, maintenance, and response of formation movement to the presence of obstacles.     

Shortest path and closure algorithms for banded matrices

A fast algorithm is given for the all-pairs shortest paths problem for banded matrices having band-width b. It solves the negative-cycle problem and calculates all path lengths within the band in O(nb²) time and calculates all other path lengths in O(n²b) time.