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.     

Classical and vector sturm—liouville problems: recent advances in singular-point analysis and shooting-type algorithms

Significant advances have been made in the last year or two in algorithms and theory for Sturm—Liouville problems (SLPs). For the classical regular or singular SLP −(p(x)u′)′ + q(x)u = λw(x)u, a < x < b, we outline the algorithmic approaches of the recent library codes and what they can now routinely achieve.

For a library code, automatic treatment of singular problems is a must. New results are presented which clarify the effect of various numerical methods of handling a singular endpoint.

For the vector generalization −(P(x)u′)′+Q(x)u = λW(x)u where now u is a vector function of x, and P, Q, W are matrices, and for the corresponding higher-order vector self-adjoint problem, we outline the equally impressive advances in algorithms and theory.     

Krylov subspace methods for eigenvalues with special properties and their analysis for normal matrices

In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)u_j, j = 0, 1,…, where u₀ is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector u_n for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x⁽ⁿ⁾₁,…,x⁽ⁿ⁾_k} with some sufficiently large n, where x^(j+1)_m = ψ(A)x^(j)_m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature.     

Numerical results for positive solutions of a superlinear elliptic equation

In this work we present a numerical approach for finding positive solutions of the type −Δu = λf(u) for x  Ω, with Dirichlet boundary condition, where f is a superlinear function of u. We will show in which range of λ, this problem achieves multiple numerical solutions and what is the behavior of the branches of solutions.     

Inverse geophysical problems for some noncompactly supported inhomogeneities

Let[²+k²n(x₁,x₃)]u(x₁,x₂,x₃)=−δ(x₁,y₁δ(x₂,y₂)δ(x₃,y₃) in R³₊. Assume that u(x₁,x₂,x₃=0,y₁,y₂=0,y₃=0,k) is measured at the plane P {x:x₃=0} for all positions of the source on the line y = (y₁,y₂ = 0,y₃ = 0), -∞ < y₁ < ∞, and receiver on the plane(x₁,x₂,x₃ − <x₁,x₂ < ∞, and for low-frequencies 0 < k <k₀, k₀ > 0 is an arbitrary small wave number. Assume thatn(x₁,x₃) is an arbitrary bounded piecewise-continuous function. The basic result is: the above low-frequency surface data determinen(x₁,x₃)uniquely.     

Uniqueness implies existence for three-point boundary value problems for dynamic equations

Shooting methods are used to obtain solutions of the three-point boundary value problem for the second-order dynamic equation, y^ΔΔ = f (x, y, y^Δ), y(x₁) = y₁, y(x₃) − y(x₂) = y₂, where f : (a, b)_T × ² → is continuous, x₁ < x₂ < x₃ in (a, b)_T, y₁, y₂ ε , and T is a time scale. It is assumed such solutions are unique when they exist.     

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.     

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.     

Oscillations in some nonlinear economic relationships

In this paper we consider a simple family of nonlinear dynamical systems generated by smooth functions. Some theorems for the existence and the uniqueness of the limit cycles of the systems are presented. If f and g are generating functions with unique limit cycles and xf(x) < xg(x), for all x ≠ 0, then according to the ‘bounding theorem’ proved in the paper, the limit cycle of the system generated by f is bounded by the limit cycle of the system generated by g. This gives us a method to estimate the amplitude of the oscillations also for systems for which we do not know the generating function exactly. As an application we extend the nonlinear business cycle model proposed by Tönu Puu (1989).     

The space localization of unbounded boundary perturbations in nonlinear heat conduction with transfer

We consider the nonlinear parabolic equation u_t = (k(u)u_x)_x + b(u)_x, where u = u(x, t, x ε R¹, t > 0; k(u) ≥ 0, b(u) ≥ 0 are continuous functions as u ≥ 0, b (0) = 0; k, b > 0 as u > 0. At t = 0 nonnegative, continuous and bounded initial value is prescribed. The boundary condition u(0, t) = Ψ(t) is supposed to be unbounded as t → +∞. In this paper, sufficient conditions for space localization of unbounded boundary perturbations are found. For instance, we show that nonlinear equation u_t = (uⁿu_x)_x + (u^β)_x, n ≥ 0, β >; n + 1, exhibits the phenomenon of “inner boundedness,” for arbitrary unbounded boundary perturbations.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

On application of the Lanczos method to solution of some partial differential equations

Let A be a square symmetric n × n matrix, φ be a vector from ⁿ, and f be a function defined on the spectral interval of A. The problem of computation of the vector u = f(A)φ arises very often in mathematical physics.

We propose the following method to compute u. First, perform m steps of the Lanczos method with A and φ. Define the spectral Lanczos decomposition method (SLDM) solution as u_m = φ Qf(H)e₁, where Q is the n × m matrix of the m Lanczos vectors and H is the m × m tridiagonal symmetric matrix of the Lanczos method. We obtain estimates for u − u_m that are stable in the presence of computer round-off errors when using the simple Lanczos method.

We concentrate on computation of exp(− tA)φ, when A is nonnegative definite. Error estimates for this special case show superconvergence of the SLDM solution. Sample computational results are given for the two-dimensional equation of heat conduction. These results show that computational costs are reduced by a factor between 3 and 90 compared to the most efficient explicit time-stepping schemes. Finally, we consider application of SLDM to hyperbolic and elliptic equations.     

A method for solving partial differential equations using differentiate trigonometric fourier series

A method for representing a function of two variables u (x, y), that is defined in the square σ = [0, π] × [0, π], is presented in the form of a combination of polynomials and differentiable trigonometric series. Such a representation enables problems to be solved in which the unknown function is defined from partial differential equations and has some partial derivatives at the border of the square domain of higher order than the order of the equation. Expansion in a trigonometric series is carried out by a system of functions mx, M = 1, 2, 3 … that is full in [0, π] and in a double series by a system of functions mx sin ifny, m, N = 1,2,3,… that is full in σ. For solving real problems, expansion by such a system of functions can be preferable to expansion by an ordinary trigonometric system of sines and cosines /1, 2/. Using the representation of a function of two variables referred to aboye the problem of the bending of an anisotropic plate with non-uniform boundary conditions is solved.     

Numerical simulation of blow-up of a 2D generalized Ginzburg-Landau equation

We study the Cauchy problem for the following generalized Ginzburg-Landau equation u_t = (ν+i)Δu − (κ+iβ)|u|^2qu + γu in two spatial dimensions for q > 1 (here , β, γ are real parameters and ν,κ > 0). A blow-up of solutions is found via numerical simulation in several cases for q > 1.     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

On the Stability of the Positive Radial Steady States for a Semilinear Cauchy Problem Involving Critical Exponents

This article is contributed to the Cauchy problem u/t = △u K(ㄧxㄧ)up in Rn x (0,T), u(x,0) =(ψ)(x) in Rn; with initial function(ψ)≠0. The stability of positive radial steady state, which are positive solutions of △u K(ㄧxㄧ)up =0, is obtained when p is critical for general K(ㄧxㄧ).     

Air traverse time in grain bins

To maintain the quality of cereal grains during storage, it is necessary to keep the grain cool and free from insects, and typical methods for dealing with these problems are considered in this paper. In particular the insect population is controlled by fumigating the grain bed with carbon dioxide gas and the grain is cooled by forcing ambient air through the bed. In both problems, the equations which describe the physical processes contain a mixture of advection and diffusion or conduction terms. This paper explores the relationship between traverse time and heat and mass transfer and gains an insight into the grain storage processes that are controlled by forced convection. When heat and mass transport is dominated by the advection terms, the equations are simplified by changing variables from the (x,y) space coordinates to (ψ,τ), where ψ is the stream function for the problem and the traverse time τ at a point in the storage bin is the time taken for the air to travel to the point from the inlet duct. The conditions are described for the equations to be independent of ψ, with the main condition being that the derivatives of the metrics g₁₁, g₁₂ and g₂₂ with respect to ψ are small enough. If the equations are independent of ψ then the dependent variable (concentration or temperature) will be constant on lines of constant traverse time τ. This relationship between traverse time and the cooling or fumigation pattern can be used in the design of storage bins since it implies that the best outlet surface is a line of constant τ.     

Impulsive effects on global existence of solutions for degenerate semilinear parabolic equations

Let q be a nonnegative real number, and λ and σ be positive constants. This article studies the following impulsive problem: for n = 1, 2, 3,…,

. The number λ^* is called the critical value if the problem has a unique global solution u for λ < λ^*, and the solution blows up in a finite time for λ > λ^*. For σ < 1, existence of a unique λ^* is established, and a criterion for the solution to decay to zero is studied. For σ > 1, existence of a unique λ^* and three criteria for the blow-up of the solution in a finite time are given respectively. It is also shown that there exists a unique T^* such that u exists globally for T> T^*, and u blows up in a finite time for T < T^*.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

Decidability of the binary infinite Post Correspondence Problem

We shall show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an infinite solution. In this context, a binary instance (h,g) consists of two morphisms h and g with a common two element domain alphabet. An infinite solution ω is an infinite word ω=a₁a₂… such that h(ω)=g(ω). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem.