Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens

It is shown that the following modification of the Steffensen procedurex _n+1=x _n ?k _s (x _n )f(x _n ) (f[x _n ,x _n ?f(x _n )])^?1 (n=0,1,...) withk _s (x)=(1?z _s (x))^?1,z _s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])^?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds.     

On multiplication in algebraic extension fields

In this paper we characterize all algorithms for obtaining the coefficients of (Σ^n?1_i=0x_iuⁱ)(Σ^n?1_i=0y_iuⁱ) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n ? 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial.     

Monotone Einschließung von Inversen positiver Elemente durch Verfahren vom Schulz-Typ

The conditional iterationx _n+1 =sup (x _n ,x _n +x _n (e?ax _n )),y _n?1 =inf (y _n ,x _n +y _n (e?ax _n )) generating sequences (x _n ) and (y _n ) is considered in partially ordered spaces. Under certain conditions it is shown, that the inversea ^?1 of a positive elementa≧0 is monotonously enclosed in the sensex _n ≦x _n+1 ≦a ^?1 ≦y _n+1 ≦y _n and that (x _n ) and (y _n ) converge toa ^?1 quadratically.     

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.     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n?2+ [lgn], andW _k (n) = n + (k?1)lg n +O(1) for all fixed k ≥ 3. In this paper we studyW′ _k (n), the minimax complexity of selecting thek largest, when tests of the form “Isx _i the median of {x _i ,x _j ,x _t }?” are also allowed. It is proved thatW′₂(n) =n?2+ [lgn], andW′ _k (n) =n + (k?1)lg₂ n +O(1) for all fixedk≥3.     

Negation-Limited Complexity of Parity and Inverters

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x ₁,…,x _n and outputs ¬ x ₁,…,¬ x _n . We show that: (a) for n=2 ^r ?1, circuits computing Parity with r?1 NOT gates have size at least 6n?log?₂(n+1)?O(1), and (b) for n=2 ^r ?1, inverters with r NOT gates have size at least 8n?log?₂(n+1)?O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x ₁≥???≥x _n . For an arbitrary r, we completely determine the minimum size. It is 2n?r?2 for odd n and 2n?r?1 for even n for ?log?₂(n+1)??1≤r≤n/2, and it is ?3n/2??1 for r≥n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n?3r for ?log?₂(n+1)?≤r≤n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.     

Edge-pancyclicity and path-embeddability of bijective connection graphs

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2ⁿ nodes and n2ⁿ⁻¹ edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X_n, x, y) + 2 ? l ? 2ⁿ − 1 can be embedded between x and y with dilation 1 in X_n for x, y ∈ V(X_n) with x ≠ y in X_n, where X_n (n ? 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X_n) is the node set of X_n. Furthermore, by this result, we can claim that X_n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes.     

Random functions with given time correlation

First, on any sequence of real numbers (x_λ), $\text{λ ? [? Λ}{}_1\text{+ Λ] ?}\text{Z}$, the pseudo probability Pr(x, x′) of the event x_λ?[x, x′[ is defined to be the limit when Λ → ∞ of the ratio of the number of x_λ?[x, x′[ to the total number of x_λ. The a.d.f. (asymptotic distribution function) of the sequence is then defined by F(x) = Pr(? ∞, x); it possesses the properties of a d.f. (distribution function). Consequently, what is said below applies equally to a sequence of r.v. (random variables) or to a sequence of p.r.v. (pseudorandom variables) consisting of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.A weyl's polynomial ?_n(λ) is a polynomial such that one of its coefficieints other than ?(0) is irrational. Then any sequence, the fractional part of ?_n(λ), $\text{λ ? [? Λ, + Λ] ?}\text{Z}$, is asymptotically equidistributed on [0, 1].A property is given which permits the construction of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of pseudostochastically independent sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.It is known that setting Y_n = F^{(? 1)}(X_n), it is possible to transform any sequence of r.v. X_n     

Q-ary search with one lie and bi-interval queries

The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x^*∈Sn={1,2,…,n}, Paul has to find the number x^* by asking q-ary bi-interval queries and Carole is allowed to lie at most once throughout the game. The minimum worst-case number LB(n,q,1) of q-ary bi-interval queries necessary to guess the number x^* is determined exactly for all integers n?1 and q?2. It turns out that LB(n,q,1) coincides with the minimum worst-case number L(n,q,1) of arbitrary q-ary queries.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Information-theoretic characterizations of recursive infinite strings

Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the program-size complexity relative to n of its n-bit prefixes x_n. Meyer has shown that x is recursive iff ?c, ?n, K(x_n?n) ? c, and Loveland has shown that this is false if one merely stipulates that K(x_n?n) ? c for infinitely many n. We strengthen Meyer's theorem. From the fact that there are few minimal-size programs for calculating n given result, we obtain a necessary and sufficient condition for x to be recursive in terms of the absolute program-size complexity of its prefixes: x is recursive iff ?c, ?n, K(x_n) ? K(n) + c. Again Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K(x_n) ? K(n) + c for infinitely many n.     

Exact analytical expressions and numerical analysis of two-center Franck-Condon factors and matrix elements over displaced harmonic oscillator wave functions

A detailed study is undertaken, using various techniques, in deriving analytical formula of Franck-Condon overlap integrals and matrix elements of various functions of power (xl), exponential (exp(−2cx)) and Gaussian (exp(−cx²)) over displaced harmonic oscillator wave functions with arbitrary frequencies. The results suggested by previous experience with various algorithms are presented in mathematically compact form and consist of generalization. The relationships obtained are valid for the arbitrary values of parameters and the computation results are in good agreement with the literature. The numerical results illustrate clearly a further reduction in calculation times.

Program summary

Program name:FRANCKCatalogue identifier:ADXX_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXX_v1_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandProgramming language:Mathematica 5.0Computer:Pentium M 1.4 GHzOperating system:Mathematica 5.0RAM:512 MBNo. of lines in distributed program, including test data, etc.:825No. of bytes in distributed program, including test data, etc.:16 344Distribution format:tar.gzNature of problem:The programs calculate the Franck-Condon factors and matrix elements over displaced harmonic oscillator wave functions with arbitrary quantum numbers (n,n₁), frequencies (a,a₁) and displacement (d) for the various functions of power (xl), exponential (exp(−2cx)) and Gaussian (exp(−cx²)).Solution method:The Franck-Condon factors and matrix elements are evaluated using binomial coefficients and basic integrals.Restrictions:The results obtained by the present programs show great numerical stability for arbitrary quantum numbers (n,n₁), frequencies (a,a₁) and displacement (d).Unusual features:NoneRunning time:As an example, for the value of Franck-Condon Overlap Integral Inn^′(d;α,α^′)=0.004405001887372332 with n=3, n₁=2, a=4, a₁=3, d=2, the compilation time in a Pentium M 1.4 GHz computer is 0.18 s. Execution time depends on the values of integral parameters n, n^′, d, α, α^′.     

Erzeugende Funktionen bei Spline-Interpolation mit äquidistanten Knoten

Using generating functions we obtain in the case ofn+1 equidistant data points a method for the calculation of the interpolating spline functions(x) of degree 2k+1 with boundary conditionss ^(κ) (x₀)=y ₀ ^(κ) ,s ^(κ) (x _n )=y _n ^(κ) , κ=1(1)k, which only needs the inversion of a matrix of orderk. The applicability of our method in the case of general boundary conditions is also mentioned.     

Dynamic Matrix Rank with Partial Lookahead

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an n×n matrix M, we show an amortized upper bound of O(n ^ω?1) arithmetic operations per change for this problem, where ω<2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to Θ(n) locations. That is, we know up to the next Θ(n) locations (i ₁,j ₁),(i ₂,j ₂),…?, whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n ^1.575) and a lower bound of Ω(n) for this problem and later Sankowski showed an upper bound of O(n ^1.495) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.     

Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing

This paper proposes a method for finding solutions of arbitrarily nonlinear systems of functional equations through stochastic global optimization. The original problem (equation solving) is transformed into a global optimization one by synthesizing objective functions whose global minima, if they exist, are also solutions to the original system. The global minimization task is carried out by the stochastic method known as fuzzy adaptive simulated annealing, triggered from different starting points, aiming at finding as many solutions as possible. To demonstrate the efficiency of the proposed method, solutions for several examples of nonlinear systems are presented and compared with results obtained by other approaches. We consider systems composed of n   equations on Euclidean spaces ?n${?}^n$ (n variables: x₁, x₂, x₃, ? , x_n).     

On the number of roots of exp-trig polynomials

The number of roots, on an interval of lengthT, ofc′ e ^At b?0 is at most (n-1)[T ω/π]^*, wheren is the dimension ofA, b, c; ω is the largest imaginary part of eigenvalue ofA, and [x]^* denotes the smallest integerk≥x.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

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.