Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

An adaptive Huber method for non-linear systems of weakly singular second kind Volterra integral equations

Numerical methods for systems of weakly singular Volterra integral equations are rarely considered in the literature, especially if the equations involve non-linear dependencies between unknowns and their integrals. In the present work an adaptive Huber method for such systems is proposed, by extending the method previously formulated for single weakly singular second kind Volterra equations. The method is tested on example systems of integral equations involving integrals with kernels K(t, τ) = (t − τ)^−1/2, K(t, τ) = exp[−λ(t − τ)](t − τ)^−1/2 (where λ > 0), and K(t, τ) = 1. The magnitude of the errors, and practical accuracy orders, observed for IE systems, are comparable to those for single IEs. In cases when the solution vector is not differentiable at t = 0, the estimation of errors at t = 0 is found somewhat less reliable for IE systems, than it was for single IEs. The stability of the IE systems solved appears to be sufficient, in practice, for the numerical stability of the method.     

Numerical similarity reductions of the (1+3)-dimensional Burgers equation

We consider the (1+3)-dimensional Burgers equation u_t = u_xx + u_yy + u_zz + uu_x which has considerable interest in mathematical physics. Lie symmetries are used to reduce it to certain ordinary differential equations. We employ numerical methods to solve a number of these ordinary differential equations.     

A mechanical system containing weakly coupled subsystems

The concept of a mechanical system (model), containing coupled subsystems (MSCCS) is introduced. Examples of such a system are the Sun–planets–satellites system, a system of interacting moving objects, a system of translationally and rotationally moving celestial bodies, chains of coupled oscillators, Sommerfeld pendulums, spring systems, etc. The MSCCS subsystems and the entire system are analysed, and problems related to the investigation of the oscillations, bifurcation, stability, stabilization and resonance are stated. A solution of the oscillations problem is given for a class of MSCCS, described by reversible mechanical systems. It is proved that the autonomous MSCCS retains its family of symmetrical periodic motions (SPMs) under parametric perturbations, while in the periodic MSCCS a family of SPMs bifurcates by producing two families of SPMs. The two-body problem and the N-planet problem are investigated as applications. The generating properties of the two-body problem are established. For the N-planet problem it is proved that an (N + 1)-parametric family of orbits exists, close to elliptic orbits of arbitrary eccentricity, the family being parametrized by energy integral constant, and a syzygy of planets occurs.     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.     

Galerkin finite element approximation of symmetric space-fractional partial differential equations

In this paper, symmetric space-fractional partial differential equations (SSFPDE) with the Riesz fractional operator are considered. The SSFPDE is obtained from the standard advection-dispersion equation by replacing the first-order and second-order space derivatives with the Riesz fractional derivatives of order 2β ∈ (0, 1) and 2α ∈ (1, 2], respectively. We prove that the variational solution of the SSFPDE exists and is unique. Using the Galerkin finite element method and a backward difference technique, a fully discrete approximating system is obtained, which has a unique solution according to the Lax-Milgram theorem. The stability and convergence of the fully discrete schemes are derived. Finally, some numerical experiments are given to confirm our theoretical analysis.     

Optimal manufacturer’s replenishment policies in the EPQ model under two levels of trade credit policy

In 2007, Huang proposed the optimal retailer’s replenishment decisions in the EPQ model under two levels of trade credit policy, in which the supplier offers the retailer a permissible delay period M, and the retailer in turn provides its customer a permissible delay period N (with N < M). In this paper, we extend his EPQ model to complement the shortcoming of his model. In addition, we relax the dispensable assumptions of N < M and others. We then establish an appropriate EPQ model to the problem, and develop the proper theoretical results to obtain the optimal solution. Finally, a numerical example is used to illustrate the proposed model and its optimal solution.     

Distributive equations of implications based on nilpotent triangular norms

In this paper, we explore the distributive equations of implications, both independently and along with other equations. In detail, we consider three classes of equations. (1) By means of the section of I, we give out the sufficient and necessary conditions of solutions for the distributive equation of implication I(x, T(y, z)) = T(I(x, y), (x, z)) based on a nilpotent triangular norm T and an unknown function I, which indicates that there are no continuous solutions satisfying the boundary conditions of implications. Under the assumptions that I is continuous except the vertical section I(0, y), y ∈ [0, 1), we get its complete characterizations. (2) We prove that there are no solutions for the functional equations I(x, T(y, z)) = T(I(x, y), I(x, z)), I(x, I(y, z)) = I(T(x, y), z). (3) We obtain the sufficient and necessary conditions on T and I to be solutions of the functional equations I(x, T(y, z)) = T(I(x, y), I(x, z)), I(x, y) = I(N(y), N(x)).     

Control parameter estimation in a semi-linear parabolic inverse problem using a high accurate method

Parabolic inverse problems have an important role in many branches of science and technology. The aim of this research work is to solve these classes of equations using a high order compact finite difference scheme. We consider the following inverse problem for finding u(x, t) and p(t) governed by u_t = u_xx + p(t)u + φ(x, t) with an over specified condition inside the domain. Spatial derivatives are approximated using central difference scheme. The time advancement of the simulation is performed using a “third order compact Runge-Kutta method”. The convergence orders for the approximation of both u and p are of o(k³ + h²) which improves the results obtained in the literature. An exact test case is used to evaluate the validity of our numerical analysis. We found that the accuracy of the results is better than that of previous works in the literature.     

A Variational Approach to Discontinuous Problems with Critical Sobolev Exponents

We employ variational techniques to study the existence and multiplicity of positive solutions of semilinear equations of the form − Δu = λh(x)H(u − a)u^q + u^2* − 1 in R^N, where λ, a > 0 are parameters, h(x) is both nonnegative and integrable on R^N, H is the Heaviside function, 2* is the critical Sobolev exponent, and 0 ≤ q < 2* − 1. We obtain existence, multiplicity and regularity of solutions by distinguishing the cases 0 ≤ q ≤ 1 and 1 < q < 2* − 1.     

Non-integrable variants of Boussinesq equation with two solitons

Three variants of the Boussinesq equation, namely, the (2 + 1)-dimensional Boussinesq equation, the (3 + 1)-dimensional Boussinesq equation, and the sixth-order Boussinesq equation are studied. The Hirota bilinear method is used to construct two soliton solutions for each equation. The study highlights the fact that these equations are non-integrable and do not admit N-soliton solutions although these equations can be put in bilinear forms.     

The common bisymmetric nonnegative definite solutions with extreme ranks and inertias to a pair of matrix equations

We in this paper consider the bisymmetric nonnegative definite solution with extremal ranks and inertias to a system of quaternion matrix equations AX = C, XB = D. We derive the extremal ranks and inertias of the common bisymmetric nonnegative definite solution to the system. The general expressions of the bisymmetric nonnegative definite solution with extremal ranks and inertias to the system mentioned above are also presented. In addition, we give a numerical example to illustrate the results of this paper.     

On two perturbation estimates of the extreme solutions to the equations X ± A*XA = Q

Two perturbation estimates for maximal positive definite solutions of equations X + A*X⁻¹A = Q and X − A*X⁻¹A = Q are considered. These estimates are proved in [Hasanov et al., Improved perturbation Estimates for the Matrix Equations X ± A*X⁻¹A = Q, Linear Algebra Appl. 379 (2004) 113-135]. We derive new perturbation estimates under weaker restrictions on coefficient matrices of the equations. The theoretical results are illustrated by numerical examples.     

Parker-Sochacki method for solving systems of ordinary differential equations using graphics processors

The Parker-Sochacki method, which is used for solving systems of ordinary differential equations, and implementation of this method on graphics processors are described. The solution to the classical N-body problem is considered as a test. The algorithm makes it possible to effectively use massive parallel graphics processors and provides acceptable accuracy with multiple time reduction, as compared to processors of a conventional architecture.     

Differential quadrature method (DQM) and Boubaker Polynomials Expansion Scheme (BPES) for efficient computation of the eigenvalues of fourth-order Sturm-Liouville problems

The differential quadrature method (DQM) and the Boubaker Polynomials Expansion Scheme (BPES) are applied in order to compute the eigenvalues of some regular fourth-order Sturm-Liouville problems. Generally, these problems include fourth-order ordinary differential equations together with four boundary conditions which are specified at two boundary points. These problems concern mainly applied-physics models like the steady-state Euler-Bernoulli beam equation and mechanicals non-linear systems identification. The approach of directly substituting the boundary conditions into the discrete governing equations is used in order to implement these boundary conditions within DQM calculations. It is demonstrated through numerical examples that accurate results for the first kth eigenvalues of the problem, where k = 1, 2, 3, … , can be obtained by using minimally 2(k + 4) mesh points in the computational domain. The results of this work are then compared with some relevant studies.     

Kolmogorov Vector Fields with Robustly Permanent Subsystems

The following results are proven. All subsystems of a dissipative Kolmogorov vector field ?_i = x_if_i(x) are robustly permanent if and only if the external Lyapunov exponents are positive for every ergodic probability measure μ with support in the boundary of the nonnegative orthant. If the vector field is also totally competitive, its carrying simplex is C¹. Applying these results to dissipative Lotka-Volterra systems, robust permanence of all subsystems is equivalent to every equilibrium x* satisfying f_i(x* > 0 whenever x_i^* = 0. If in addition the Lotka-Volterra system is totally competitive, then its carrying simplex is C¹.     

Modeling fully developed laminar flow in a helical duct with rectangular cross section and finite pitch

The mass and momentum transport equations are written in an orthogonal coordinate system using Germano’s transformation to model a laminar flow in a helical duct with a rectangular cross section and finite pitch. The system of governing equations are discretized and solved by the finite-volume numerical method. The three dimensional domain is reduced to a two dimensional slab of cells, orthogonal to the main flow direction, enforcing the fully developed state for 2π/(τ · d_h) >> 1 where τ and d_h representing the duct’s centerline torsion and its hydraulic diameter. This approximation and the use of an orthogonal grid allow a great simplification on the numerical procedure. Comparisons of the numerical solution against experimental data are drawn to assess the accuracy of the approximation.     

Convergence of rank-type equations

Convergence results are presented for rank-type difference equations, whose evolution rule is defined at each step as the kth largest of p univariate difference equations. If the univariate equations are individually contractive, then the equation converges to a fixed point equal to the kth largest of the individual fixed points of the univariate equations. Examples are max-type equations for k = 1, and the median of an odd number p of equations, for k = (p + 1)/2. In the non-hyperbolic case, conjectures are stated about the eventual periodicity of the equations, generalizing long-standing conjectures of G. Ladas.     

On the security analysis of an image scrambling encryption of pixel bit and its improved scheme based on self-correlation encryption

An image scrambling encryption scheme for pixel bits was presented by Ye [Ye GD. Image scrambling encryption algorithm of pixel bit based on chaos map. Pattern Recognit Lett 2010;31:347-54], which can be seen as one kind of typical binary image scrambling encryption considering from the bit-plain of size M × (8N). However, recently, some defects existing in the original image encryption scheme, i.e., Ye’s scheme, have been observed by Li and Lo [Li CQ, Lo KT. Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks. Signal Process 2011;91:949-54]. In the attack proposed by Li and Lo at least 3 + ⌈log₂(MN)⌉ plain images of size M × N are used to reveal the permutation matrix W = [w(i, k)] (i ∈ {1, 2, … , M}; k ∈ {1, 2, … , 8N}) which can be applied to recover the exact plain image. In the current paper, at first, one type of special plain image/cipher image is used to analyze the security weakness of the original image scrambling scheme under study. The final encryption vectors TM and TN or the decryption vectors TM′ and TN′ are revealed completely according to our attack. To demonstrate the performance of our attack, a quantified comparison is drawn between our attack and the attack proposed by Li and Lo. Compared with Li and Lo’s attack, our attack is more efficient in the general conditions. In particular, when the sizes of images satisfy the condition M = N or M ? 8N, the number of the used plain images/cipher images is at most 9, which is sharply less than 3 + ⌈log₂(MN)⌉ when M and N are of large size. To overcome the weaknesses of the original scheme, in this paper, an improved image scrambling encryption scheme is proposed. In the improved scheme, the idea of the “self-correlation” method is used to resist the chosen-plaintext attack/known-plaintext attack. The corresponding simulations and analyses illustrate that the improved encryption method has good cryptographic properties, and can overcome the weakness of the original image encryption scheme. Finally, farther improvement is briefly presented for the future work.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.