Enclosing Solutions of Singular Interval Systems Iteratively

Richardson splitting applied to a consistent system of linear equations Cx = b with a singular matrix C yields to an iterative method x^k+1 = Ax^k + b where A has the eigenvalue one. It is known that each sequence of iterates is convergent to a vector x^* = x^* (x⁰) if and only if A is semi-convergent. In order to enclose such vectors we consider the corresponding interval iteration with (|[A]|) = 1 where |[A]| denotes the absolute value of the interval matrix [A]. If |[A]| is irreducible we derive a necessary and sufficient criterion for the existence of a limit of each sequence of interval iterates. We describe the shape of and give a connection between the convergence of ( ) and the convergence of the powers of [A].Dedicated to Professor G. Mae on the occasion of his 65^th birthday     

Quantum Orlicz Spaces in Information Geometry

Let H₀ be a selfadjoint operator such that Tr is of trace class for some , and let denote the set of ε-bounded forms, i.e., for some 0 $$" align="middle" border="0"> . Let χ := Span . Let denote the underlying set of the quantum information manifold of states of the form . We show that if Tr ,

Crash failure detection in asynchronous agent communication languages

Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language ( - ) presented in this paper addresses this issue dealing with crash failures of agents. - provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open MAS. We present a formal semantics for - and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies a set of well defined knowledge-level programming requirements. To illustrate the language features we show how - can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net one.     

Image Analysis and Reconstruction using a Wavelet Transform Constructed from a Reducible Representation of the Euclidean Motion Group

Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation score as a local orientation representation of an image, . The mapping is a wavelet transform corresponding to a reducible representation of the Euclidean motion group onto and oriented wavelet . This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a robust manner. Furthermore, by geometrical examination of the Euclidean motion group , which is the domain of our orientation scores, we deduce that an operator Φ on orientation scores must be left invariant to ensure that the corresponding operator on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them. Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics of the considered image class leads to an auto-associative behavior of the system. The Netherlands Organization for Scientific Research is gratefully acknowledged for financial support. This work has been supported by EC Grant IST-2003-004176 COSPAL.     

Population Variance under Interval Uncertainty: A New Algorithm

In statistical analysis of measurement results, it is often beneficial to compute the range V of the population variance when we only know the intervals of possible values of the x_i. In general, this problem is NP-hard; a polynomialtime algorithm is known for the case when the measurements are sufficiently accurate, i.e., when for all In this paper, we show that we can efficiently compute V under a weaker (and more general) condition .     

Deriving escape analysis by abstract interpretation

Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain as an abstract interpretation of concrete states, which we then refine into an abstract domain which is more concrete than and, hence, leads to a more precise escape analysis than . We provide optimality results for both and , in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications.     

Solving Underdetermined Systems with Interval Methods

In this paper, we use the concepts of {1} - and {2} -inverse of a matrix to construct such a Krawczyk-like operator as

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.     

Dynamic Ordering for Asynchronous Backtracking on DisCSPs

An algorithm that performs asynchronous backtracking on distributed , with dynamic ordering of agents is proposed, . Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of . The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard . The algorithm with three different ordering heuristics is compared to standard on randomly generated . A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order by a large factor in run-time and improve the network load.     

A Time-Splitting Spectral Method for the Generalized Zakharov System in Multi-Dimensions

The generalized Zakharov system (ZS) couples a dispersive field E (scalar or vectorial) and nondispersive fields with a propagating speed of . In this paper, we extend our one-dimensional time-splitting spectral method (TSSP) for the generalized ZS into higher dimension. A main new idea is to reformulate the multi-dimensional wave equations for the nondispersive fields into a first-order system using a change of variable defined in the Fourier space. The proposed scheme TSSP is unconditionally stable, second-order in time and spectrally accurate in space. Moreover, in the subsonic regime, it allows numerical capturing of the subsonic limit without resolving the small parameters . Numerical examples confirm these properties of this method     

Conditions for Instability of One Class of Nonlinear Nonautomomous Dynamic Systems

Consideration was given to the conditions for instability of the equilibrium states of a nonlinear nonautonomous dynamic systems obeying an ordinary vector differential equation of arbitrary order whose right-hand side satisfies the following conditions: (i) for any t 0, div 0$$ " align="middle" border="0"> almost everywhere on the set H that is a neighborhood of the equilibrium point of the system and (ii) at any point . The equilibrium states of such systems can be both stable and unstable. For one class of these systems, sufficient instability conditions were given, which enables one to carry out studies using only the information about the right-hand side of the system.