Multiple/arbitrary precision interval computations in C-XSC

As a new feature, C-XSC provides so-called wrapper classes to some external arbitrary precision real and interval packages. Operator and function name overloading is used to give the user easy access to the arithmetic operations and mathematical functions provided by the underlying Ansi C packages. We will discuss briefly so-called staggered precision arithmetics based on exact scalar products. Such an arithmetic is available in C-XSC e.g. for multiple precision complex intervals. We also discuss the usage of the arbitrary precision arithmetic packages MPFR and MPFI, which are now accessible conveniently from within C-XSC via class interfaces. As a typical application, we will present an arbitrary precision interval Newton method to find the root(s) of a continuously differentiable function in a prescribed domain. The user only has to supply the expression for the function in the usual mathematical notation. The derivative needed in the interval Newton operator is computed using automatic differentiation based on the arbitrary precision interval operations. To demonstrate the power of the package we compute an enclosure of the zero of a model problem with guaranteed accuracy of more than 10 million decimal digits.     

A bright side of NP-hardness of interval computations: interval heuristics applied to NP-problems

It is known that interval computations are NP-hard. In other words, the solution of many important problems can be reduced to interval computations. The immediate conclusion is negative: in the general case, one cannot expect an algorithm to do all the interval computations in less than exponential running time. We show that this result also has a bright side: since there are many heuristics, for interval computations, we can solve other problems by reducing them to interval computations and applying these heuristics.     

Applications of interval computations to earthquake-resistant engineering: How to compute derivatives of interval functions fast

One of the main sources of destruction during earthquake is resonance. Therefore, the following idea has been proposed. We design special control linkages between floors that are normally unattached to the building but can be attached if necessary. They are so designed that adding them changes the building's characteristic frequency. We continuously monitor displacements within the structure, and when they exceed specified limits, the linkages are engaged in a way to control structural motion. This idea can also be applied to avoid vibrational destruction of large aerospace structures.     

On hardware support for interval computations and for softcomputing: theorems

This paper presents a rationale for providing hardware supported functions of more than two variables for processing incomplete knowledge and fuzzy knowledge. The result is in contrast to Kolmogorov's (1957) theorem in the numerical (nonfuzzy) case     

Checking security properties by model checking

A method is proposed for checking security properties in programs written in high‐level languages. The method is based on the model checking technique. The SMV tool is used. The representation of the program is a Kripke structure modelling the control flow graph enriched with security information. The properties considered are secure information flow and the absence of covert channels caused by program termination. The formulae expressing these security properties are given using the logic CTL. Copyright © 2003 John Wiley & Sons, Ltd.     

Checking timed automata for linear duration properties

It is proved in this paper that checking a timed automaton M with respect to a linear duration property D can be done by investigating only the integral timed states of M,An equivalence relation is introduced in this paper to divide the infinite number of integral timed states into finite number of equivalence classes.Based on this,a method is proposed for checking whether M satisfies D.In some cases,the number of equivalence classes is too large for a computer to mainpulate,A technique for reducing the search-space for checking linear duration propoerty is also described.This technique is more suitable for the case in this paper than those in the literature because most of those techniques are designed for reachablility analysis.     

Checking safety properties on-the-fly with the sweep-line method

The sweep-line state space method allows states to be deleted from memory during state exploration, thus alleviating the state explosion problem. Properties of the system (such as the absence of deadlocks) can then be verified on-the-fly. This paper presents an extension to the sweep-line method that allows on-the-fly checking of safety properties expressed as sequences of actions of the modelled system. This has been implemented in a prototype sweep-line library for Coloured Petri nets. We evaluate the prototype by applying it to the connection management procedures of the Datagram Congestion Control Protocol, a new Internet transport protocol. This paper was supported by Australian Research Council Discovery Grants DP0210524 and DP0559927. L. M. Kristensen was supported by the Carlsberg Foundation and the Danish Research Council for Technology and Production.     

灰色区间预测模型及其性质

针对振荡幅度大的小样本振荡序列预测问题, 构建灰色区间预测模型. 首先对原始序列的上下界序列直接建立非等间隔GM(1,1)模型, 得到取值包络带的上下包络曲线以描述系统发展的边界; 然后给出原始序列区间预测值和基本预测值的计算方法, 建立区间预测算法; 最后研究区间预测模型的灰指数规律性和时效性. 数值实验揭示, 发展系数的取值不是影响区间预测模型时效性的唯一因素; 应用实例表明, 所提出方法能够有效地提高序列的预测精度.     

区间值强模糊图的运算性质

利用经典图和模糊图定义和性质,给出了区间值模糊关系、模糊变换以及区间值强模糊图的定义,相应地定义了区间值强模糊图弱直积、半直积运算,并且证明了其弱直积、半直积运算封闭的性质。     

Optimization of computations

Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 65–94, March–April, 1994.     

Mapping computations

Let Z be a set of integers and Z ^n×n be a ring for any integer n. We define as a latter point. Hom(Z ⁿ ,Z ^m ) denotes as a homomorphism of Z ⁿ into Z ^m . For any element in Z ⁿ , we define S+T:Z ⁿ →Z ^m as . As a result, S+T become a homomorphism of Z ⁿ into Z ^m . We also define kU:Z ⁿ →Z ^m as . Consequently, kU become a homomorphism of Z ⁿ into Z ^m . Moreover, Hom (Z ⁿ ,Z ^m ) is isomorphic to Z ^n×m . A novel class of the structured matrices which is a set of elements of Hom (Z ⁿ ,Z ⁿ ) over a ring of integers with a displacement structure, referred to as a C-Cauchy-like matrix, will be formulated and presented. Using the displacement approach, which was originally discovered by Kailath, Kung, and Morf (J. Math. Anal. Appl. 68:395–407, 1979), a new superfast algorithm for the multiplication of a C-Cauchy-like matrix of the size n×n over a field with a vector will be designed. The memory space for storing a C-Cauchy-like matrix of the size n×n over a field is O(n) versus O(n ²) for a general matrix of the size n×n over a field. The arithmetic operations of a product of a C-Cauchy-like matrix and a vector is reduced dramatically to O(n) from O(n ²), which can be used to transform a latter point to another latter point such that . Moreover, the displacement structure can also be extended to a Kronecker matrix W ⊗ Z. A new class of the Kronecker-like matrices with the displacement rank r, r<n will be also discovered. The memory space for storing a Kronecker-like matrix of the size (n×1)⊗(1×n) over a field is decreased to O(rn). The arithmetic operations for a product of a Kronecker-like matrix with the displacement rank r and a vector is also accelerated to O(rn).     

Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices

We exhibit fast computational methods for the evaluation of the determinant and the characteristic polynomial of a (2k+1)-diagonal Toeplitz matrix with elements in the complex field, either for sequential or for parallel computations. A fast algorithm, to achieve one step of Newton's method, is shown to be suitable to compute the eigenvalues of such a matrix. Bounds to the eigenvalues and necessary and sufficient conditions for positive definiteness, which are easy to check, are given either for matrices with scalar elements or for matrices with blocks. In the case in which the blocks are themselves band Toeplitz matrices such conditions assume a very simple form. Dedicated to Prof. Aldo Ghizzetti on his 75 th birthday     

On certain properties of Hurwitz determinants for interval polynomials

Consider the stable interval polynomialsF _n (z)=z ⁿ +a ₁ z ^n?1 +...+a _n?1 z+a _n wherea _i are real numbers, satisfying the inequalities α _i ≤a _i ≤β _i ,i=1,2, ...,n. In this paper we prove that mind _n (a) is the same foraεD andaεD ₁, whereD=[α₁, β₁]×[α₂, β₂]×...×[α _n , β _n ],D={(γ₁, γ₂,...γ _n )∈D:γ₁=α₁∨γ₁=β₁,... γ _n =α _n ∨γ _n =β _n }d _n (a)=detH, aεD, H—Hurwitz matrix for the polynomialF _n (z).     

Liveness Checking as Safety Checking

Temporal logic is widely used for specifying hardware and software systems. Typically two types of properties are distinguished, safety and liveness properties. While safety can easily be checked by reachability analysis, and many efficient checkers for safety properties exist, more sophisticated algorithms have always been considered to be necessary for checking liveness. In this paper we describe an efficient translation of liveness checking problems into safety checking problems. A counter example is detected by saving a previously visited state in an additional state recording component and checking a loop closing condition. The approach handles fairness and thus extends to full LTL.