Two point hermite approximations for the solution of linear initial value and boundary value problems

Application of an idea originally due to Ch. Hermite allows the derivation of an approximate formula for expressing the integral ∫xixi?1y(x)dx as a linear combination of y(xi?1), y(xi), and their derivatives y(v)(xi?1) up to order v = α and y(v)(xi) up to order v = β. In addition to this integro-differential form a purely differential form of the 2-point Hermite approximation will be derived. Both types will be denoted by Hαβ-approximation. It will be shown that the well-known Obreschkoff-formulas contain no new elements compared to the much older Hαβ-method.The Hαβ-approximation will be applied to the solution of systems of ordinary differential equations of the type y'(x) = M(x)y(x) + q(x), and both initial value and boundary value problems will be treated. Function values at intermediate points x? (xi?1, xi) are obtained by the use of an interpolation formula given in this paper.An advantage of the Hαβ-method is the fact that high orders of approximation (α, β) allow an increase in step size hi. This will be demonstrated by the results of several test calculations.     

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.     

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.     

Curve generation of implicit functions by incremental computers

The conventional numerical solution of an implicit function f(x, y) = 0 is substantially complicated for calculating by any computer. We propose a new method representing the argument of the implicit function as a unary function of a parameter, t, if the continuous and unique solution of f(x, y) = 0 exists. The total differential $\text{d}\text{f}\text{d}\text{t}$ constitutes simultaneous differential equations of which the solution about x and y is unique. The Newton-Raphson method must be used to calculate the values near singular points of an implicit function and then the sign of dt has to be decided according to four special cases. Incremental computers are suitable for curve generation of implicit functions by the new method, because the incremental computer can perform more complex algorithms than the analog computer and can calculate faster than the digital computer. This method is easily applicable to curve generation in three-dimensional space.     

Efficient implementation of algorithms for approximate exponentiation

We present efficient implementations of algorithms for the following fundamental problem: Given as input three positive integers x, y and j, compute the leading j digits of xy. A special case of this problem (k=2 and j=1) was recently studied by Hirvensalo and Karhumaki [M.Hirvensalo, J.Karhumaki, Computing partial information out of uncomputable one—The first digit of n² to base 3 as an example, in: Mathematical Foundations of Computer Science, in: Lecture Notes in Computer Science, Springer-Verlag, Inc., 2002] for which they presented a polynomial time algorithm. Specifically an algorithm of bit complexity O(n²log³nloglogn) where n=|y| is the number of digits in y. But their algorithm is not efficient in practice. For example, finding the leading digit of y² where y is a 500 digit positive integer takes several hours. Hirvensalo and Karhumaki's algorithm is based on computing a rational approximation to ln2 (and a few other constants) to a high-degree of precision. Our approach is fundamentally different from theirs: we use a modified addition chain algorithm in which the multiplication is truncated to varying number of digits at various steps, followed by a self-tester that validates the truncation. Our algorithm runs several orders of magnitude faster. For example, on an input in which x and y have a few thousand digits, our program computes the leading 1000 digits in under 3 minutes. Since the approximate exponentiation has many application [B.Ravikumar, A Las Vegas randomized approximation algorithm for approximate exponentiation and its applications, in preparation] we hope that our algorithm will stimulate further research on this problem.     

A Sequential Algorithm for Generating Random Graphs

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max?=O(m ^1/4?τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max?) where $m=\frac{1}{2}\sum_{i}d_{i}We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max=O(m ^1/4−τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max) where m=\frac12?_id_im=\frac{1}{2}\sum_{i}d_{i} is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52–67, 1990) has a running time of O(m ² d _max²). Our method also gives an independent proof of McKay’s estimate (McKay in Ars Combinatoria A 19:15–25, 1985) for the number of such graphs.     

On the moore test for coupled equations

In this paper an improved Moore test for the coupled system:f(x, y)=0,g(x, y)=0 is described: x⁺ is calculated from x and y in a forward-substep, and we use x⁺ and y to compute y⁺ in a backward-substep. It is shown that, if x⁺ ? x, y⁺ ? y, then a solution of the coupled system (x*,y*) ∈ (x⁺, y⁺) exists. On this foundation, we prove convergence of a point iterative algorithm for solving coupled systems.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

A Linear Time Algorithm for L(2,1)-Labeling of Trees

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)?f(y)|≥2 if x and y are adjacent and |f(x)?f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,…,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ ^4.5 n) for more than a decade, and an O(min{n ^1.75,Δ ^1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.     

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.     

Some procedures for function approximation based on the use of sample data and their application in heuristic methods for solving practical problems

Let f(x) be a member of a set of functions over a probability space. Samples of f(x) are 2-tuples (xⁱ,f(xⁱ) where xⁱ is a sample of the random variable X and f(xⁱ) is a sample of f(x) at x = xⁱ. Some procedures and analysis are presented for the approximation of such functions by systems of orthonormal functions. The approximations are based on the data samples. The analysis includes the case of error in the measurement of f(xⁱ). The properties of the expected square error in the approximation are examined for a number of different estimators for the coefficients in the expansion and these well-behaved and easily analyzed estimators are compared to those obtained using the method of least squares. The effectiveness of different sets of basis functions, those involved in the Karhunen-Loeve expansion and others, can be compared and an approach is suggested to adaptive basis selection in order to select that basis which is most efficient in approximating the particular function under examination. The connection between results and applications are discussed in the introduction and conclusion.     

Transportation Distances on the Circle

This paper is devoted to the study of the Monge-Kantorovich theory of optimal mass transport, in the special case of one-dimensional and circular distributions. More precisely, we study the Monge-Kantorovich problem between discrete distributions on the unit circle S ¹, in the case where the ground distance between two points x and y is defined as h(d(x,y)), where d is the geodesic distance on the circle and h a convex and increasing function. This study complements previous results in the literature, holding only for a ground distance equal to the geodesic distance d. We first prove that computing a Monge-Kantorovich distance between two given sets of pairwise different points boils down to cut the circle at a well chosen point and to compute the same distance on the real line. This result is then used to obtain a dissimilarity measure between 1-D and circular discrete histograms. In a last part, a study is conducted to compare the advantages and drawbacks of transportation distances relying on convex or concave cost functions, and of the classical L ¹ distance. Simple retrieval experiments based on the hue component of color images are shown to illustrate the interest of circular distances. The framework is eventually applied to the problem of color transfer between images.     

An algorithm for the decomposition of differential polynomials in the general case

The theory of decomposition of differential polynomials (DPs) is considered. For a given differential algebraic equation $P(x,y(x), y'(x), \ldots ,y^{(n)} (x)) = 0,$ the possibility to represent the differential polynomial P as the composition P = Q(x, R, R′, ..., R ^(q)), R = R(x, y(x), ..., ^y (r)(x)) of DPs Q and R is studied. It is shown that the decomposition problem is reduced to the factorization of linear ordinary differential operators (LODOs). A generic decomposition algorithm for DPs is described based on the Vandermonde differential theorem.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Faster pairing computation on genus 2 hyperelliptic curves

In this paper, new efficient pairings on genus 2 hyperelliptic curves of the form C:y²=x⁵+ax with embedding degree k satisfying 4|k are constructed, that is an improvement for the results of Fan et al. (2008) [10]. Then a variant of Miller?s algorithm is given to compute our pairings. In this algorithm, we just need to evaluate the Miller function at two divisors for each loop iteration. However, Fan et al. had to compute the Miller function at four divisors. Moreover, compared with Fan et al.?s algorithm, the exponentiation calculation is simplified. We finally analyze the computational complexity of our pairings, which shows that our algorithm can save 2036m operations in the base field or be 34.1% faster than Fan et al.?s algorithm. The experimental result shows that our pairing can achieve a better performance.     

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.     

Geodesic methods in quantitative image analysis

Let X be a part of an image to be analysed. Given two arbitrary points x and y of X, let us define the number d_x(x, y) as follows: d_x(x, y) is the lower bound of the lengths of the arcs in X ending at points x and y, if such arcs exist, and + α if not. The function d_x is an X-intrinsic distance function, called ‘geodesic distance’. Note that if x and y belong to two disjoint connected components of X, d_x(x, y) = + α. In other words, d_x seems to be an appropriate distance function to deal with connectivity problems.In the metric space (X, d_x), all the classical morphological transformations (dilation, erosion, skeletonization, etc.) can be defined. The geodesic distance d_x also provides rigorous definitions of topological transformations, which can be performed by automatic image analysers with the help of parallel iterative algorithms.All these notions are illustrated by several examples (definition of the length of a fibre and of an effective length factor; automatic detection of cells having at least one nucleus or having one single nucleus; definitions of the geodesic center and of the ends of an object without a hole; etc.). The corresponding algorithms are described.     

Online Metric Tracking and Smoothing

We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Δ≥0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:?→?. Given a signal f ₁,f ₂,…∈X the tracker is responsible for producing a sequence a ₁,a ₂,… of elements of X that meet the proximity constraint: d(f _i ,a _i )≤Δ. To complicate matters, the tracker is on-line—the value a _i may only depend on f ₁,…,f _i —and wishes to minimize the cost of his travels, ∑c(d(a _i ,a _i+1)). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance. The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be ? ^k with the ? ₂ metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion).

We begin by studying arbitrary metric spaces with the “pay if you move” metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb _Δ)-competitive ratio, where b _Δ=max _x∈X |B _Δ(x)| is the maximum number of points appearing in any ball of radius Δ. We show that this bound is tight.

We then focus on the metric space ? with natural families of monotone cost functions c(x)=x ^p for some p≥0. We consider both the expansive case (p≥1) and the contractive case (p<1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.

     

Galois Action on Solutions of a Differential Equation

Consider a second-order differential equation of the form y″ + ay ′ + by = 0 with a, b ϵ Q(x). Kovacic's algorithm tries to compute a solution of the associated Riccati equation that is algebraic and of minimal degree over Q̄ (x). The coefficients of the monic irreducible polynomial of this solution are in C(x), where C is a finite algebraic extension of Q. In this paper we give a bound for the degree of the extension C ⊃ Q. Similar results are obtained for third-order differential equations.     

A predictor-corrector form of the numerov method for coupled equations

A new algorithm is presented for solving nonlinear second-order coupled differential equations of the form y′ = F(x,y). Modifications of the standard Numerov procedure have resulted in a rapid, noniterative, predictor-corrector form without matrix inversion and with improved accuracy. Comparisons with the usual Numerov and de Vogelaere methods are presented for the homogeneous case F(x,y) = -G(x)y often encountered in quantum scattering theory. Tests are also presented of a version with variable step size and with stabilization by orthogonalization of the solutions at internally determined. intervals.