A derivative free iterative method for finding multiple roots of nonlinear equations

For an equation f(x)=0 having a multiple root of multiplicity m>1 unknown, we propose a transformation which converts the multiple root to a simple root of H(x)=0. The transformed function H(x) of f(x) with a small >0 has appropriate properties in applying a derivative free iterative method to find the root. Moreover, there is no need to choose a proper initial approximation. We show that the proposed method is superior to the existing methods by several numerical examples.     

Small noise asymptotics for invariant densities for a class of diffusions: A control theoretic view

We consider multi-dimensional nondegenerate diffusions with invariant densities, with the diffusion matrix scaled by a small >0. The o.d.e. limit corresponding to =0 is assumed to have the origin as its unique globally asymptotically stable equilibrium. Using control theoretic methods, we show that in the ↓0 limit, the invariant density has the form ≈exp(−W(x)/²), where the W is characterized as the optimal cost of a deterministic control problem. This generalizes an earlier work of Sheu. Extension to multiple equilibria is also given.     

On the reducibility of a class of nonlinear quasi-periodic system with small perturbation parameter near zero equilibrium point

This work focuses on the reducibility of the following real nonlinear analytical quasiperiodic system:

where A is a real 2×2 constant matrix, and f(t,0,)=O() and ∂_xf(t,0,)=O() as →0. With some non-resonant conditions of the frequencies with the eigenvalues of A and without any nondegeneracy condition with respect to , by an affine analytic quasiperiodic transformation we change the system to a suitable norm form at the zero equilibrium for most of the sufficiently small perturbation parameter .     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Succinct data structures for flexible text retrieval systems

We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf*idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf*idf scores there has been no efficient data structures for arbitrary patterns.Our new data structures support these queries using small space. The space is only 2/ times the size of compressed documents plus 10n bits for a document collection of length n, for any 0<1. This is much smaller than the previous O(nlogn) bit data structures. Query time is O(m+qlogn) for listing and computing tf*idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns.     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

Existence and selection of steady bubbles in a Hele–Shaw cell

This paper concerns the existence of a steadily translating bubble in a Hele–Shaw cell for small but non-zero surface tension ². We rigorously conclude that for bubble velocity U relative to the fluid velocity at infinity in the interval (1,2), analytic symmetric solutions exist in the asymptotic limit of surface tension ²→0 if and only if the Stokes constant for a relatively simple nonlinear differential equation is zero. This Stokes constant S depends on the parameter α(0,1) corresponding to bubble size and . Earlier calculations have shown S to be zero for a discrete set of values of a.     

Asymptotic Results for Injection of Reactive Solutes from a Three-Dimensional Well

In this paper we consider some asymptotic aspects related to the profile of a reactive solute, which is injected from a well (radius  > 0) into a three-dimensional porous medium. We present a convergence result for  ↓ 0 as well as the large time behaviour. Regarding the latter we show that the solute profile evolves in a self-similar way towards a stationary distribution and we give an estimate for the rate of the convergence. This paper extends earlier work of C. J. van Duijn and M. A. Peletier (1996, J. Reine Angew. Math.479, 77–98), where the two-dimensional case was treated.     

A parallel extended GCD algorithm

A new parallel extended GCD algorithm is proposed. It matches the best existing parallel integer GCD algorithms of Sorenson and Chor and Goldreich, since it can be achieved in O(n/logn) time using at most n¹⁺ processors on CRCW PRAM. Sorenson and Chor and Goldreich both use a modular approach which consider the least significant bits. By contrast, our algorithm only deals with the leading bits of the integers u and v, with uv. This approach is more suitable for extended GCD algorithms since the coefficients of the extended version a and b, such that au+bv=gcd(u,v), are deeply linked with the order of magnitude of the rational v/u and its continuants. Consequently, the computation of such coefficients is much easier.     

Visibility queries in a polygonal region

In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n²) in time O(n²lgn) and yields a query time of O((1+min(m,|V(q)|))lg²n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg¹⁺m) for a small positive constant >0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min(|E|,mn))²) space and an additional O(m(min(|E|,mn))²) preprocessing time.     

Stability for parametric implicit vector equilibrium problems

In this paper, we consider a class of parametric implicit vector equilibrium problems in Hausdorff topological vector spaces where a mapping f and a set K are perturbed by parameters and λ, respectively. We establish sufficient conditions for the upper semicontinuity and lower semicontinuity of the solution set mapping S:Λ₁×Λ₂→2^X for such parametric implicit vector equilibrium problems.     

Optimization of a convex program with a polynomial perturbation

We consider the problem of minimizing a convex function plus a polynomial p over a convex body K. We give an algorithm that outputs a solution x whose value is within range_K(p) of the optimum value, where range_K(p)=sup_xKp(x)−inf_xKp(x). When p depends only on a constant number of variables, the algorithm runs in time polynomial in 1/, the degree of p, the time to round K and the time to solve the convex program that results by setting p=0.     

Galerkin solution of a singular integral equation with constant coefficients

Galerkin methods are used to approximate the singular integral equation

with solution φ having weak singularity at the endpoint −1, where a, b≠0 are constants. In this case φ is decomposed as φ(x)=(1−x)^α(1+x)^βu(x), where β=−α, 0<α<1. Jacobi polynomials are used in the discussions. Under the conditions fH^μ[−1,1] and k(t,x)H^μ,μ[−1,1]×[−1,1], 0<μ<1, the error estimate under a weighted L² norm is O(n^−μ). Under the strengthened conditions f^″H^μ[−1,1] and , 2α−<μ<1, the error estimate under maximum norm is proved to be O(n^2α−−μ+), where , >0 is a small enough constant.     

Trace results on domains with self-similar fractal boundaries

This work deals with trace theorems for a family of ramified bidimensional domains Ω with a self-similar fractal boundary Γ^∞. The fractal boundary Γ^∞ is supplied with a probability measure μ called the self-similar measure. Emphasis is put on the case when the domain is not a −δ domain and the fractal is not post-critically finite, for which classical results cannot be used. It is proven that the trace of a function in H¹(Ω) belongs to for all real numbers p1. A counterexample shows that the trace of a function in H¹(Ω) may not belong to BMO(μ) (and therefore may not belong to ). Finally, it is proven that the traces of the functions in H¹(Ω) belong to H^s(Γ^∞) for all real numbers s such that 0s<d_H/4, where d_H is the Hausdorff dimension of Γ^∞. Examples of functions whose traces do not belong to H^s(Γ^∞) for all s>d_H/4 are supplied.There is an important contrast with the case when Γ^∞ is post-critically finite, for which the functions in H¹(Ω) have their traces in H^s(Γ^∞) for all s such that 0s<d_H/2.     

Kolmogorov Width of Classes of Smooth Functions on the Sphere

Let ^d−1{(x₁,…,x_d) ^d:x²₁+···+x²_d=1} be the unit sphere of the d-dimensional Euclidean space ^d. For r>0, we denote by B^r_p (1p∞) the class of functions f on ^d−1 representable in the formwhere dσ(y) denotes the usual Lebesgue measure on ^d−1, and P^λ_k(t) is the ultraspherical polynomial.For 1p,q∞, the Kolmogorov N-width of B^r_p in L^q( ^d−1) is given bythe left-most infimum being taken over all N-dimensional subspaces X_N of L^q( ^d−1).The main result in this paper is that for r2(d−1)²,where A_NB_N means that there exists a positive constant C, independent of N, such that C⁻¹A_NB_NCA_N.This extends the well-known Kashin theorem on the asymptotic order of the Kolmogorov widths of the Sobolev class of the periodic functions.     

C k -solvability near the characteristic set for a class of planar complex vector fields of infinite type

This paper deals with semi-global C ^k -solvability of complex vector fields of the form ${\mathsf{L}=\partial/\partial t+x^r(a(x)+ib(x))\partial/\partial x,}This paper deals with semi-global C ^k -solvability of complex vector fields of the form L=?/?t+x^r(a(x)+ib(x))?/?x,{\mathsf{L}=\partial/\partial t+x^r(a(x)+ib(x))\partial/\partial x,}, r ≥ 1, defined on W_e=(-e,e)×S¹{\Omega_\epsilon=(-\epsilon,\epsilon)\times S^1}, ${\epsilon >0 }${\epsilon >0 }, where a and b are C ^∞ real-valued functions in (-e,e){(-\epsilon,\epsilon)}. It is shown that the interplay between the order of vanishing of the functions a and b at x = 0 influences the C ^k -solvability at Σ = {0} × S ¹. When r = 1, it is permitted that the functions a and b of L{\mathsf L}depend on the x and t variables, that is, L=?/?t+x(a(x,t)+ib(x,t))?/?x,{\mathsf{L}=\partial/\partial t+x(a(x,t)+ib(x,t))\partial/\partial x,}where (x, t) ? W_e{(x, t)\in\Omega_\epsilon}.     

On the Greatest Common Divisor of u ? 1 and v ? 1 with u and v Near S{\cal S}-units

In [2], it was shown that if a and b are multiplicatively independent integers and ɛ > 0, then the inequality gcd (aⁿ − 1,bⁿ − 1) < exp(ɛn) holds for all but finitely many positive integers n. Here, we generalize the above result. In particular, we show that if f(x),f₁(x),g(x),g₁(x) are non-zero polynomials with integer coefficients, then for every ɛ > 0, the inequality gcd (f(n)aⁿ+g(n), f₁(n)bⁿ+g₁(n)) < exp(ne){\rm gcd}\, (f(n)a^n+g(n), f_1(n)b^n+g_1(n)) < \exp(n\varepsilon) holds for all but finitely many positive integers n.     

An almost all result on q1q2 o c (mod q){q_1q_2\equiv c ({\rm mod}\, q)}

In this paper, we consider the congruence equation q₁ q₂ o c (mod q){q_1 q_2 \equiv c ({\rm mod}\, q)} with a < q₁ ￡ a+q^1/2+e{a < q_1 \leq a+q^{1/2+\epsilon}} and b < q₂ ￡ b+q^1/2+e{b < q_2 \leq b+q^{1/2+\epsilon}} and show that it has solution for almost all a and b. Then we apply it to a question of Fujii and Kitaoka as well as generalize it to more variables. At the end, we present a new way to attack the above congruence equation question through higher moments.