A non-separable solution of the diffusion equation based on the Galerkin’s method using cubic splines

The two dimensional diffusion equation of the form is considered in this paper. We try a bi-cubic spline function of the form as its solution. The initial coefficients C_i,j(0) are computed simply by applying a collocation method; C_i,j = f(x_i, y_j) where f(x, y) = u(x, y, 0) is the given initial condition. Then the coefficients C_i,j(t) are computed by X(t) = e^tQX(0) where X(t) = (C_0,1, C_0,1, C_0,2, … , C_0,N, C_1,0, … , C_N,N) is a one dimensional array and the square matrix Q is derived from applying the Galerkin’s method to the diffusion equation. Note that this expression provides a solution that is not necessarily separable in space coordinates x, y. The results of sample calculations for a few example problems along with the calculation results of approximation errors for a problem with known analytical solution are included.     

Divisibility of determinants of power GCD matrices and power LCM matrices on finitely many quasi-coprime divisor chains

Let a, n ? 1 be integers and S = {x₁, … , x_n} be a set of n distinct positive integers. The matrix having the ath power (x_i, x_j)^a of the greatest common divisor of x_i and x_j as its i, j-entry is called ath power greatest common divisor (GCD) matrix defined on S, denoted by (S^a). Similarly we can define the ath power LCM matrix [S^a]. We say that the set S consists of finitely many quasi-coprime divisor chains if we can partition S as S = S₁ ∪ ? ∪ S_k, where k ? 1 is an integer and all S_i (1 ? i ? k) are divisor chains such that (max(S_i), max(S_j)) = gcd(S) for 1 ? i ≠ j ? k. In this paper, we first obtain formulae of determinants of power GCD matrices (S^a) and power LCM matrices [S^a] on the set S consisting of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. Using these results, we then show that det(S^a)∣det(S^b), det[S^a]∣det[S^b] and det(S^a)∣det[S^b] if a∣b and S consists of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. But such factorizations fail to be true if such divisor chains are not quasi-coprime.     

On generalized absolute Cesàro summability

In this paper, a known result on ∣C, α; δ∣_k summability factors has been generalized for ∣C, α, γ; δ∣_k summability factors. Some new results have also been obtained.     

Estimation of flows in flow networks

Let G be a directed graph with an unknown flow on each edge such that the following flow conservation constraint is maintained: except for sources and sinks, the sum of flows into a node equals the sum of flows going out of a node. Given a noisy measurement of the flow on each edge, the problem we address, which we call the Most Probable Flow Estimation problem (MPFE), is to estimate the most probable assignment of flow for every edge such that the flow conservation constraint is maintained. We provide an algorithm called ΔY-mpfe for solving the MPFE problem when the measurement error is Gaussian (Gaussian-MPFE). The algorithm works in O(∣E∣ + ∣V∣²) when the underlying undirected graph of G is a 2-connected planar graph, and in O(∣E∣ + ∣V∣) when it is a 2-connected serial-parallel graph or a tree. This result is applicable to any Minimum Cost Flow problem for which the cost function is τ_e(X_e − μ_e)² for edge e where μ_e and τ_e are constants, and X_e is the flow on edge e. We show that for all topologies, the Gaussian-MPFE’s precision for each edge is analogous to the equivalent resistance measured in series to this edge in an electrical network built by replacing every edge with a resistor reflecting the measurement’s precision on that edge.     

On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan

We present on-line algorithms to minimize the makespan on a single batch processing machine. We consider a parallel batching machine that can process up to b jobs simultaneously. Jobs in the same batch complete at the same time. Such a model of a batch processing machine has been motivated by burn-in ovens in final testing stage of semiconductor manufacturing. We deal with the on-line scheduling problem when jobs arrive over time. We consider a set of independent jobs. Their number is not known in advance. Each job is available at its release date and its processing requirement is not known in advance. This general problem with infinite machine capacity is noted 1∣p − batch, r_j, b = ∞∣C_max. Deterministic algorithms that do not insert idle-times in the schedule cannot be better than 2-competitive and a simple rule based on LPT achieved this bound [Z. Liu, W. Yu, Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics 105 (2000) 129–136]. If we are allowed to postpone start of jobs, the performance guarantee can be improved to 1.618. We provide a simpler proof of this best known lower bound for bounded and unbounded batch sizes. We then present deterministic algorithms that are best possible for the problem with unbounded batch size (i.e., b = ∞) and agreeable processing times (i.e., there cannot exist an on-line algorithm with a better performance guarantee). We then propose another algorithm that leads to a best possible algorithm for the general problem with unbounded batch size. This algorithm improves the best known on-line algorithm (i.e. [G. Zhang, X. Cai, C.K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics 48 (2001) 241–258]) in the sense that it produces a shortest makespan while ensuring the same worst-case performance guarantee.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

The domination numbers of cylindrical grid graphs

Let γ(P_m □ C_n) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P_m, the path of length m, m ? 2 and the graph C_n, the cycle of length n, n ? 3. In this paper, methods to find the domination numbers of graphs of the form P_m □ C_n with n ? 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P₅ □ C_n, n ? 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Robustness of optimal designs for correlated random variables

Suppose that Y = (Y_i) is a normal random vector with mean Xb and covariance σ²I_n, where b is a p-dimensional vector (b_j), X = (X_ij) is an n × p matrix with X_ij ∈ {−1, 1}; this corresponds to a factorial design with −1, 1 representing low or high level respectively, or corresponds to a weighing design with −1, 1 representing an object j with weight b_j placed on the left and right of a chemical balance respectively. E-optimal designs Z are chosen that are robust in the sense that they remain E-optimal when the covariance of Y_i, Y_i′ is ρ > 0 for i ≠ i′. Within a smaller class of designs similar results are obtained with respect to a general class of optimality criteria which include the A- and D-criteria.     

Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

Landau’s theorem for functions with logharmonic Laplacian

In this paper, we show the existence of Landau constant for functions with logharmonic Laplacian of the form F(z) = ∣z∣²L(z) + K(z), ∣z∣ < 1, where L is logharmonic and K is harmonic. Moreover, the problem of minimizing the area is solved     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.     

Normal Forms for Nonautonomous Differential Equations

We extend Henry Poincarés normal form theory for autonomous differential equations x=f(x) to nonautonomous differential equations x=f(t, x). Poincarés nonresonance condition λ_j−∑ⁿ_i=1 ?_iλ_i≠0 for eigenvalues is generalized to the new nonresonance condition λ_j∩∑ⁿ_i=1 ?_iλ_i=∅ for spectral intervals.     

Compositions of Polynomials with Coefficients in a Given Field

Let F ⊂ K be fields of characteristic 0, and let K[x] denote the ring of polynomials with coefficients in K. Let p(x) = ∑_k = 0ⁿa_kx^k ∈ K[x], a_n ≠ 0. For p ∈ K[x]\F[x], define D_F(p), the F deficit of p, to equal n − max{0 ≤ k ≤ n : a_k∉F}. For p ∈ F[x], define D_F(p) = n. Let p(x) = ∑_k = 0ⁿa_kx^k and let q(x) = ∑_j = 0^mb_jx^j, with a_n ≠ 0, b_m ≠ 0, a_n, b_m ∈ F, b_j∉F for some j ≥ 1. Suppose that p ∈ K[x], q ∈ K[x]\F[x], p, not constant. Our main result is that p ° q ∉ F[x] and D_F(p ° q) = D_F(q). With only the assumption that a_nb_m ∈ F, we prove the inequality D_F(p ° q) ≥ D_F(q). This inequality also holds if F and K are only rings. Similar results are proven for fields of finite characteristic with the additional assumption that the characteristic of the field does not divide the degree of p. Finally we extend our results to polynomials in two variables and compositions of the form p(q(x, y)), where p is a polynomial in one variable.