On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).     

Outer Interval Solution of the Eigenvalue Problem under General Form Parametric Dependencies

The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝ^n×n for the general case where the matrix elements a_ij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λ_μ, x^(μ)), μ = 1, ..., n, is suggested for the case where λ_μ is a simple eigenvalue. It is based on the use of an affine interval approximation of a_ij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real or complex eigenvalue, respectively.     

Una nuova rappresentazione asintotica dei polinomi ultrasferici

In this paper we obtain a new asymptotic formula for the ultraspherical polynomialP _n ^(λ) (x), asn→∞, with an error term which isO (n ^λ−5 ) uniformly in the interval −1+δ≤x≤1−δ,δ>0. Very accurate approximations for the zeros ofP _n ^(λ) (x) are also derived from the preceding formula.

---

---

Lavoro eseguito nell'ambito del Gruppo Nazionale per l'Informatica Matematica del C. N. R..     

On the Quadratic Convergence of the Levenberg-Marquardt Method without Nonsingularity Assumption

Recently, Yamashita and Fukushima [11] established an interesting quadratic convergence result for the Levenberg-Marquardt method without the nonsingularity assumption. This paper extends the result of Yamashita and Fukushima by using _k=||F(x_k)||, where [1,2], instead of _k=||F(x_k)||² as the Levenberg-Marquardt parameter. If ||F(x)|| provides a local error bound for the system of nonlinear equations F(x)=0, it is shown that the sequence {x_k} generated by the new method converges to a solution quadratically, which is stronger than dist(x_k,X^*)0 given by Yamashita and Fukushima. Numerical results show that the method performs well for singular problems.     

Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators. Part I. Separable Approximation of Multi-variate Functions

The Kronecker tensor-product approximation combined with the -matrix techniques provides an efficient tool to represent integral operators as well as certain functions F(A) of a discrete elliptic operator A in ℝ ^d with a high spatial dimension d. In particular, we approximate the functions A ⁻¹ and sign(A) of a finite difference discretisation A∈ℝ ^{N × N} with a rather general location of the spectrum. The asymptotic complexity of our data-sparse representations can be estimated by (n ^p log ^q n), p = 1, 2, with q independent of d, where n=N ^{1/ d} is the dimension of the discrete problem in one space direction. In this paper (Part I), we discuss several methods of a separable approximation of multi-variate functions. Such approximations provide the base for a tensor-product representation of operators. We discuss the asymptotically optimal sinc quadratures and sinc interpolation methods as well as the best approximations by exponential sums. These tools will be applied in Part II continuing this paper to the problems mentioned above.     

Low-rank Kronecker-product Approximation to Multi-dimensional Nonlocal Operators. Part II. HKT Representation of Certain Operators

This article is the second part continuing Part I [16]. We apply the -matrix techniques combined with the Kronecker tensor-product approximation to represent integral operators as well as certain functions F(A) of a discrete elliptic operator A in a hypercube (0,1) ^d ∈ ℝ ^d in the case of a high spatial dimension d. We focus on the approximation of the operator-valued functions A ^{− σ} , σ>0, and sign (A) for a class of finite difference discretisations A ∈ ℝ ^{N × N} . The asymptotic complexity of our data-sparse representations can be estimated by (n ^p log ^q n), p = 1, 2, with q independent of d, where n=N ^{1/ d} is the dimension of the discrete problem in one space direction.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

On the convergence rate of two projection methods for variational inequalities in ℝ n

This paper presents a study on the convergence rate of two projection methods for solving the variational inequality problemh∈K, 〈C(h),f-h〉 ≥ 0, ∀f∈K, whereK is a closed convex subset of ℝ ⁿ ,C is a mapping fromK to ℝ ⁿ and <.,.> denotes the inner product in ℝ ⁿ . The first method, proposed by Dafermos [6] for the case whenC is continuously differentiable and strongly monotone, generates a sequence{f ⁱ } inK which is geometrically convergent to the unique solutionh∈K of the variational inequality; i.e., there exists a constant λ≡]0,1[ such that for all i, ∥f ⁱ⁺¹ −h∥ _G ≤λ ∥f ⁱ −h∥, whereG is a symmetric positive definite matrix and ∀f≡ℝ ⁿ . The second method, proposed by Bertsekas and Gafni [8] for the case whenK is polyhedral andC is of the formC=A ⁱ TA, whereA is anm×n matrix andT: ℝ ^m →ℝ ^m is Lipschitz continuous and strongly monotone, generates a sequence{f ⁱ } inK which converges to a solutionh≡K of the variational inequality and satisfies the following estimate: ∥f ⁱ⁺¹ −h∥ _G ≤qβ ⁱ , whereq>0 and β≡]0,1[. We examine the dependence of the constants λ and β on the parameters of the methods and establish that, except for particular cases, these constants do not assume those values which guarantee a rapid convergence of the methods. This work was extracted from the degree thesis [9] (Supervisor: A Laratta), Dipartimento di Matematica, Università di Modena.     

Diagonal polynomials and diagonal orders on multidimensional lattices

HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x ₁+···+x _n whenx=(x ₁, …,x _n) inR ⁿ. A mapf:R ⁿ →R is call adiagonal function of dimensionn iff|N ⁿ is a bijection ontoN and, for allx, y inN ⁿ, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2 ⁿ⁻² inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd _n of such functions is much greater than 2 ⁿ⁻² forn>3. These combinatorial ideas also give an inductive procedure to constructd _n+1 diagonal orderings of {1, …,n}.     

A note on a problem on ω-limit sets of N–dimensional skew-product maps

In 2003, Balibrea et al. stated the problem of finding a skew-product map G on 𝕀³ holding ω _G ={0}×𝕀²=ω _G (x, y, z) for any (x, y, z)∈𝕀³, x≠0. We present a method for constructing skew-product maps F on 𝕀 ⁿ⁺¹ holding ω _F ={0}×𝕀 ⁿ =ω _F (x ₁, x ₂, …, x _n+1), (x ₁, x ₂, …, x _n+1)∈𝕀 ⁿ⁺¹, x ₁≠0.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Wavelet solution of variable order pseudodifferential equations

Sobolev spaces H ^m(x)(I) of variable order 0<m(x)<1 on an interval I⊂ℝ arise as domains of Dirichlet forms for certain quadratic, pure jump Feller processes X _t ∈ℝ with unbounded, state-dependent intensity of small jumps. For spline wavelets with complementary boundary conditions, we establish multilevel norm equivalences in H ^m(x)(I) and prove preconditioning and wavelet matrix compression results for the variable order pseudodifferential generators A of X.     

Approximating Buy-at-Bulk and Shallow-Light <Emphasis Type="Italic">k</Emphasis>-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ⁺ and a distance cost r:E→ℝ⁺. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ _e∈H b(e)+∑ _t∈T−s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log ³ n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log ² n),O(log ⁴ n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 677–686, 2006). A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006. M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02. M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

Random 2 XORSAT Phase Transition

We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y=0 or x ⊕ y=1. Formula of size m on n Boolean variables are chosen uniformly at random from among all ((n(n-1)) || (m)){n(n-1)\choose m} possible choices. When c<1/2 and as n tends to infinity, the probability p(n,m=cn) that a random 2-XOR formula is satisfiable, tends to the threshold function exp (c/2)⋅(1−2c)^1/4. This gives the asymptotic behavior of random 2-XOR formula in the SAT/UNSAT subcritical phase transition. In this paper, we first prove that the error term in this subcritical region is O(n ⁻¹). Then, in the critical region c=1/2, we prove that p(n,n/2)=Θ(n ^−1/12). Our study relies on the symbolic method and analytical tools coming from generating function theory which also enable us to describe the evolution of n^1/12 p(n,\fracn2(1+mn^-1/3))n^{1/12}\ p(n,\frac{n}{2}(1+\mu n^{-1/3})) as a function of μ. Thus, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of 2-XORSAT transition.