An informal introduction to a high level language with applications to interval mathematics

The main problem of interval computations is as follows:given sets of possible valuesX _i for variablesx _i, and an algorithmf:R ⁿ → R, to.estimate the rangef(X ₁, ..,X _n ) of the possible values off(x ₁, ...,x _n ). In many real-life, situations setsX _i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show:

· that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations;

· and that bag languages can be also helpfully applied to traditional interval computations (where setsX _i are intervals).

     

Optimal interval enclosures for fractionally-linear functions,and their application to intelligent control

One of the main problems of interval computations is, given a functionf(x ₁, ...,x _n ) andn intervals x₁, ..., x _n , to compute the range y=f(x₁, ..., x _n ). This problem is feasible for linear functionsf, but for generic polynomials, it is known to be computationally intractable. Because of that, traditional interval techniques usually compute theenclosure of y, i.e., an interval that contains y. The closer this enclosure to y, the better. It is desirable to describe cases in which we can compute theoptimal enclosure, i.e., the range itself. In this paper, we describe a feasible algorithm for computing the optimal enclosure forfractionally linear functionsf. Applications of this result tointelligent control are described.     

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung

In the present paper a new method is given for the numerical treatment of the initial problemsy ⁽ⁿ⁾=f(x,y,y′, ...,y ^(n?1),y ⁽ⁱ⁾ (x _o )=y _o ⁽ⁱ⁾ , i=0, 1, ...,n?1. This method is an one-step process of order four. For a class of linear differential equations the exact solution is obtained. Moreover some numerical results are presented.     

Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

On Indication of External Factors by Circuits of Functional Elements

We consider functions f(x ₁, ..., x _n , z ₁, ..., z _m ) of k-valued logic, where x ₁, ..., x _n are ordinary k-valued variables and z ₁, ..., z _m are improper k-valued variables indicating external factors. An algorithm is presented for designing a circuit of k-valued functional elements, which realizes a k-valued indicator z, z {z ₁, ..., z _m }.     

The asymptotic distribution of random clumps

When objects are scattered at random in the plane or in space, some of them overlap to form clumps. It is the object of the present paper to study the asymptotic distribution of the number of clumps of given size and topological structure generated within the following model: Ifx ₁, ...,x _n are points in ? ⁿ andU=-U?? ⁿ is a symmetric set, then the pointsx _i andx _j are said tooverlap or rather to form aU-coincidence, ifx _i ?x _j ∈U. Adjoining tox ₁, ...,x _n andU, the graphG(x ₁, ...,x _n ;U)?({1, ..., n}, {[i, j]:1≤ix _i ?x _j ∈U}), the so calledcoincidence-graph, we ask for the number of connected components of this graph isomorphic to a given graphH and call this numberL9x ₁, ...x _n ;U, H). In the paper, the asymptotic distribution ofL(...) under various assumptions about the distribution of the pointsx ₁, ...,x _n and the size ofU is studied. Depending on these assumptions, we prove that the asymptotic distribution ofL(...) is either Poisson or normal.     

A quadratic-time algorithm for smoothing interval functions

In many real-life applications, physical considerations lead to the necessity to consider the smoothest of all signals that is consistent with the measurement results. Usually, the corresponding optimization problem is solved in statistical context. In this paper, we propose a quadratic-time algorithm for smoothing aninterval function. This algorithm, givenn+1 intervals x₀, ..., x _n with 0 ∈ x₀ and 0 ∈ x _n , returns the vectorx ₀, ...,x _n for whichx ₀=x ₀=0,x _i ∈ x _i , and Σ(x _i+1?x _i )² → min.     

Choosing,Agreeing, and Eliminating in Communication Complexity

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f ₁,…,f _k and each of Alice and Bob has k inputs, x ₁,…,x _k and y ₁,…,y _k , respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,…,σ _k such that f _i (x _i , y _i ) ≠ σ _i for at least one i (i.e., their goal is to eliminate one of the 2 ^k output vectors); in the choose problem, Alice and Bob should return (i, f _i (x _i , y _i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f _i (x _i , y _i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.     

Robust algorithms that locate local extrema of a function of one variable from interval measurement results: A remark

The problem of locating local maxima and minima of a function from approximate measurement results is vital for many physical applications: inspectral analysis, chemical species are identified by locating local maxima of the spectra; inradioastronomy, sources of celestial radio emission, and their subcomponents, are identified by locating local maxima of the measured brightness of the radio sky;elementary particles are identified by locating local maxima of the experimental curves. Since measurements are never absolutely precise, as a result of the measurements, we have aclass of possible functions. If we measuref(x _i ) with interval uncertainty, this class consists of all functionsf for whichf(x _i ) ε [y _i ??, y _i +?], wherey _i are the results of measuringf(x _i ), andε is the measurement accuracy. For this class, in [2], a linear-time algorithm was described. In real life, a measuring instrument can sometimes malfunction, leading to the so-calledoutliers, i.e., measurementsy _i that can be way offf(x _i ) (and thus do not restrict the actual valuesf(x _i ) at all). In this paper, we describerobust algorithms, i.e., algorithms that find the number of local extrema in the presence of possible outliers. These algorithms solve an important practical problem, but they are not based on any new mathematical results: they simply use algorithms from [2] and [3].     

An efficient dynamic program slicing technique

An important application of the dynamic program slicing technique is program debugging. In applications such as interactive debugging, the dynamic slicing algorithm needs to be efficient. In this context, we propose a new dynamic program slicing technique that is more efficient than the related algorithms reported in the literature. We use the program dependence graph as an intermediate program representation, and modify it by introducing the concepts of stable and unstable edges. Our algorithm is based on marking and unmarking the unstable edges as and when the dependences arise and cease during run-time. We call this algorithm edge-marking algorithm. After an execution of a node x, an unstable edge (x, y) is marked if the node x uses the value of the variable defined at node y. A marked unstable edge (x, y) is unmarked after an execution of a node z if the nodes y and z define the same variable var, and the value of var computed at the node y does not affect the present value of var defined at the node z. We show that our algorithm is more time and space efficient than the existing ones. The worst case space complexity of our algorithm is O(n²), where n is the number of statements in the program. We also briefly discuss an implementation of our algorithm.     

On derivative-based global sensitivity criteria

A mathematical model f(x) given in the unit n-dimensional cube, where x = (x ₁, ..., x _n ), is considered. How can one estimate the global sensitivity of f(x) with respect to x _i ? If f(x) ∈ L ₂, global sensitivity indices help answer this question. Being less reliable, derivative-based sensitivity criteria are sometimes easier-to-compute. In this work, a new derivative-based global sensitivity criterion is compared to the respective global sensitivity index. These estimates are proven to coincide in the particular case when f(x) linearly depends on x _i . However, Monte Carlo approximations to the derivative-based criterion converge faster. Thus, the global derivative-based sensitivity criterion can prove useful when f(x) depends on x _i almost linearly. It can be also used to find nonessential variables x _i .     

Algorithm 35 an algorithm for non-smoothing contour representations of two-dimensional arrays

The FORTRAN code calculates, plots and labels approximate contour linesz(x, y)=c for data that are given as a rectangular arrayz _ik =z(x _i ,y _k ).     

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung mittels Einschrittverfahren

In the present paper a new exponentially fitted one-step method is given for the numerical treatment of the initial value problemy ⁽ⁿ⁾=f(x, y, y′, ..., y ^(n?1)),y ^(j) (x ₀)=y ₀ ^(j) j=0, 1, ...n?1. The method is given by a local linearisation off(x, y, y′, ..., y ^(n?1)). Using new functions the solution of a special linear differential equation of then-th order with constant coefficients is transformed in such a way so that it no longer contains numerical singularities. The efficiency of the method is demonstrated by several numerical stiff-examples.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

Interval methods that are guaranteed to underestimate (and the resulting new justification of Kaucher arithmetic)

One of the main objectives of interval computations is, given the functionf(x ₁, ...,x _n ), andn intervals $\bar x_1 ,...,\bar x_n$ , to compute the range $\bar y = f(\bar x_1 ,...,\bar x_n )$ . Traditional methods of interval arithmetic compute anenclosure $Y \supseteq \bar y$ for the desired interval $\bar y$ , an enclosure that is often an overestimation. It is desirable to know how close this enclosure is to the desired range interval. For that purpose, we develop a new interval formalism that produces not only the enclosure, but also theinner estimate for the desired range $\bar y$ , i.e., an interval y such that $y \subseteq \bar y$ . The formulas for this new method turn out to be similar to the formulas of Kaucher arithmetic. Thus, we get a new justification for Kaucher arithmetic.     

Checking If There Exists a Monotonic Function That Is Consistent with the Measurements: An Efficient Algorithm

In many problems in science and engineering ranging from astrophysics to geosciences to financial analysis, we know that a physical quantity y depends on the physical quantity x, i.e., y = f(x) for some function f(x), and we want to check whether this dependence is monotonic. Specifically, finitely many measurements of x_i and y = f(x) have been made, and we want to check whether the results of these measurements are consistent with the monotonicity of f(x). An efficient parallelizable algorithm is known for solving this problem when the values x_i are known precisely, while the values y_i are known with interval uncertainty. In this paper, we extend this algorithm to a more general (and more realistic) situation when both x_i and y_i are known with interval uncertainty.     

New slope methods for sharper interval functions and a note on Fischer's acceleration method

This paper presents algorithms evaluating sharper bounds for interval functionsF(X) :IR ⁿ →IR. We revisit two methods that use partial derivatives of the function, and develop four other inclusion methods using the set of slopesS _f (x, z) off atx εX with respect to somez εIR ⁿ . All methods can be implemented using tools that automatically evaluate gradient and slope vectors by using a forward strategy, so the complex management of reverse accumulation methods is avoided. The sharpest methods compute each component of gradients and slopes separately, by substituting each interval variable at a time. Backward methods bring no great advantage in the sharpest algorithms, since object-oriented forward implementations are easy and immediate. Fischer's acceleration scheme [2] was also tested with interval variables. This method allows the direct evaluation of the productf′(x) * (x?z) as a single real number (instead of working with two vectors) and we used it to computeF′(X) * (X?z) for an interval vectorX. We are led to decide against such acceleration when interval variables are involved.     

Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position

Assume that n is a positive integer with n?2. It is proved that between any two different vertices x and y of Qn there exists a path Pl(x,y) of length l for any l with h(x,y)?l?n²−1 and 2|(l−h(x,y)). We expect such path Pl(x,y) can be further extended by including the vertices not in Pl(x,y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Qn, for any vertex y∈V(Qn)−{x,z}, and for any integer l with h(x,y)?l?n²−1−h(y,z) and 2|(l−h(x,y)), there exists a hamiltonian path R(x,y,z;l) from x to z such that dR(x,y,z;l)(x,y)=l. Moreover, for any two distinct vertices x and y of Qn and for any integer l with h(x,y)?l?²n−1 and 2|(l−h(x,y)), there exists a hamiltonian cycle S(x,y;l) such that dS(x,y;l)(x,y)=l.     

Errors in reduction methods

A mathematical basis is given for comparing the relative merits of various techniques used to reduce the order of large linear and non-linear dynamics problems during their numerical integration. In such techniques as Guyan-Irons, path derivatives, selected eigenvectors, Ritz vectors, etc., the nth order initial value problem of $\text{[}\text{/.y}\text{=}\text{f(y)}$ for t > 0, y(0) given] is typically reduced to the mth order (m ? n) problem of $\text{z}\text{?}\text{= g(z)}$ for t > 0, z(0) given] by the transformation $\text{y}\text{=}\text{Pz}$ where P changes from technique to technique. This paper gives an explicit approximate expression for the reduction error e_i in terms of P and the Jacobian of f. It is shown that: (a) reduction techniques are more accurate when the time rate of change of the response y is relatively small; (b) the change in response between two successive stations contributes to the errors at future stations after the change in response is transformed by a filtering matrix H, defined in terms of P; (c) the error committed at a station propagates to future stations by a mixing and scaling matrix G, defined in terms of P, Jacobian of f, and time increment h. The paper discusses the conditions under which the reduction errors may be minimized and gives guidelines for selecting the reduction basis vector, i.e. the columns of P.