Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

Factorizations of root-based polynomial compositions

Let denote the finite field of order q=p^r, p a prime and r a positive integer, and let f(x) and g(x) denote monic polynomials in of degrees m and n, respectively. Brawley and Carlitz (Discrete Math. 65 (1987) 115–139) introduce a general notion of root-based polynomial composition which they call the composed product and denote by fg. They prove that fg is irreducible over if and only if f and g are irreducible with gcd(m,n)=1. In this paper, we extend Brawley and Carlitz's work by examining polynomials which are composed products of irreducibles of non-coprime degrees. We give an upper bound on the number of distinct factors of fg, and we determine the possible degrees that the factors of fg can assume. We also determine when the bound on the number of factors of fg is met.     

Oscillation criteria for second-order nonlinear differential equations with integrable coefficient

In this paper, we consider the second-order nonlinear differential equation

[a(t)|y′(t)|^σ−1y′(t)|′+q(t)f(y(t))=r(t)

where σ > 0 is a constant, a C(R, (0, ∞)), q C(R, R), f C(R, R), xf(x) > 0, f′(x) ≥ 0 for x ≠ 0. Some new sufficient conditions for the oscillation of all solutions of (*) are obtained. Several examples which dwell upon the importance of our results are also included.     

MEROMORPHIC FUNCTIONS SHARING TWO FINITE SETS

Let S1 ＝ {∞} and S2 ＝ {w: Ps(w)＝ 0}, Ps(w) being a uniqueness polynomial under some restricted conditions. Then, for any given nonconstant meromorphic function f, there exist at most finitely many nonconstant meromorphic functions g such that f-1(Si) ＝ g-1(Si)(i ＝ 1,2), where f-1(Si) and g-1(Si) denote the pull-backs of Si considered as a divisor, namely, the inverse images of Si counted with multiplicities, by f and g respectively.     

A stability property of the stochastic heat equation

In this paper we consider continuity properties of a stochastic heat equation of the form ∂u(t,x)/∂t = ∂²u(t,x)/∂x² + f(u(t,x))W_x,t. We prove that the solutions of this equation depend continuously on the function f and give some new estimates for this connection.     

Odd subgraphs and matchings

Let G be a graph and f : V(G)→{1,3,5,…}. Then a subgraph H of G is called a (1,f)-odd subgraph if deg_H(x){1,3,…,f(x)} for all xV(H). If f(x)=1 for all xV(G), then a (1,f)-odd subgraph is nothing but a matching. A (1,f)-odd subgraph H of G is said to be maximum if G has no (1,f)-odd subgraph K such that |K|>|H|. We show that (1,f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1,f)-odd subgraph, which is similar to that for the order of a maximum matching.     

Synthetic realization approach to fuzzy global optimization via gamma algorithm

A new approach is proposed for global optimization problems with fuzzy cost functions and fuzzy box and equality constraints. It allows one to avoid complex operations with fuzzy sets and the use of various subjective indices of choice. To resolve the contradiction between economically better solutions with low possibility of realization and a little poorer solution with higher possibility of realization, the synthetic realization is defined as certain fixed -level cut for all membership functions. Consideration of such realizations guarantees a level of credibility not less than given (0, 1] for all globally optimal solutions. Then, so defined -cuts are rectified to cut off realizations with possibility less than and to retain higher possibility realizations which are assigned credibility μ = 1 for the whole interval of possible realizations. This construction results in a set-valued band of credibility not less than for a given fuzzy cost function f̃(x) which band has crisp Lipschitz continuous lower- and upper-value functions f_*(x), f*(x) such that f_*(x) ≤ f̃(x) ≤ f*(x) for all x X̃ Rⁿ. Then, the gamma algorithm is applied to obtain the interval global optimal solution f̄₀(x) = [f⁰_*(x), f*₀(x)]. To further simplify the computations, the fuzziness in the feasible set X̃ is transferred to the function value space transforming X̃ into the crisp unit cube in Rⁿ₊ common for all fuzzy optimization problems in Rⁿ with box and equality constraints.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Decompositions of positive self-dual boolean functions

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f_c such that f_c(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a non-dominated (ND) coterie if and only if f_c is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f₁,f₂,…, f_k. In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f₁, and f₂, and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.     

The derivative of a continuous nonconstant function

Using elementary ideas and techniques, we prove (Theorem 2) that for a nonconstant differentiable function , a < b, the set S(f) = {x ε [a, b] : f'(x) ≠ 0} cannot be negligible. This result remains valid if f fails to be differentiable on a countable subset of [a, b].     

On oscillation of second order neutral type delay differential equations

Oscillation criteria are obtained by using the so called H-method for the second order neutral type delay differential equations of the form

(r(t)ψ(x(t))z^′(t))^′+q(t)f(x(σ(t)))=0, tt₀,

where z(t)=x(t)+p(t)x(τ(t)), r, p, q, τ, σ, C([t₀,∞),R) and f,ψC(R,R).

The results of the paper contains several results obtained previously as special cases. Furthermore, we are also able to fix an error in a recent paper related to the oscillation of second order nonneutral delay differential equations.     

Probabilistic version of the method of feasible directions

A probabilistic version of the method of feasible directions (MFD) for solving nonlinear programming (NLP) problems of the type min{f(x): f_j(x)0,j=1,2,…,m} is presented. Randomization is applied to modify the algorithm and a global convergence Theorem is used in the analysis of convergence. Some numerical experiments on problems with known solutions serve to compare this method with the traditional deterministic versions.     

A note on a property of a weak self-similar perfect set

Let S be a compact, weak self-similar perfect set based on a system of weak contractions f_j, j=1,…,m each of which is characterized by a variable contraction coefficient _j(l) as d(f_j(x),f_j(y)) _j(l)d(x,y), d(x,y)<l, l>0. If the relation ∑^m_j=1j(l₀)<1 holds at at least one point l₀, then every nonempty compact metric space is a continuous image of the set S.     

Profile minimization on triangulated triangles

Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑_vV(G){f(v)−min_xN[v] f(x)} is as small as possible, where N[v]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle T_l is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles T_l with side-length l.     

On extensions of the domain invariance theorem

If f maps continuously a compact subset X of Rⁿ into Rⁿ and x is a point whose distance from the boundary ∂X is greater than double diameter of the fibres of the points in f(∂X) then f(x) is in the interior of f(X). This theorem extends some results due to Borsuk and Sitnikov.     

An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

Integral methods for computing solutions of a class of singular two-point boundary value problems

In this paper, we establish three iteration methods to compute solutions for a class of (weakly) singular two-point boundary value problems (xy^′)^′=f(x,y), where x(0,1) and <2. We obtain the sufficient conditions for existence of a unique solution on . Finally, we given some numerical examples.     

Topological entropy of a graph map

Let G be a graph and f : G → G be a continuous map. Denote by h(f), P(f), AP(f), R(f)and ω(x, f) the topological entropy of f, the set of periodic points of f, the set of almost periodic points of f, the set of recurrent points of f and the ω-limit set of x under f, respectively. In this paper,we show that the following statements are equivalent:(1) h(f) 0.(2) There exists an x ∈ G such that ω(x, f) ∩ P(f) = ? and ω(x, f) is an infinite set.(3) There exists an x ∈ G such that ω(x, f)contains two minimal sets.(4) There exist x, y ∈ G such that ω(x, f)-ω(y, f) is an uncountable set and ω(y, f) ∩ω(x, f) = ?.(5) There exist an x ∈ G and a closed subset A ? ω(x, f) with f(A) ? A such that ω(x, f)-A is an uncountable set.(6) R(f)-AP(f) = ?.(7) f |P(f)is not pointwise equicontinuous.     

The existence of linear factors in the direct sum of forms and in the tensor product of forms

The tensor product f⊗g of two forms of degree r has a linear factor if and only if both fand g have a linear factor and the sum of the multiplicities of these factors is larger than r. In fact, if (V,ϕ) and (Wθ) are symmetric spaces corresponding to fand g with linear factors U and T respectively the sum of whose multiplicities is larger than r, then the linear factor of (V,ϕ)⊗(Wθ)is U⊗W+V⊗T. Conversely, each linear factor of (V,ϕ)⊗(Wθ)is of this form. Additionally, the direct sum of two nondegenerate symmetric spaces has a linear factor if and only if each is one dimensional and isomorphic to the negative of the other.     

Starlikeness of Hadamard product of certain analytic functions

An interesting criterion was given by Lashin (A.Y. Lashin, Some convolution properties of analytic functions, Appl. Math. Lett. 18 (2005) 135–138) to be starlike for convolution of analytic functions f, g such that Re[f^′(z)],Re[g^′(z)]β,,β<1 in the unit disc U. In this paper we shall improve this criterion.