The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

Fault-tolerant cycle-embedding of crossed cubes

The crossed cube CQ_n introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ_n is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f_e and f_v be the numbers of faulty edges and vertices in CQ_n, we show that a cycle of length l, for any 4?l?|V(CQ_n)|−f_v, can be embedded into a wounded crossed cube as long as the total number of faults (f_v+f_e) is no more than n−2, and we say that CQ_n is (n−2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n−1 faults, there is no guarantee of having a cycle of a certain length in it.     

Block Toeplitz matrices and preconditioning

We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT _n , withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T _n } are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L ², and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P _n ⁻¹ T_n}, where the sequence{P _n } is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP _n ⁻¹ T _n is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp ⁻¹ f. We also prove that the firstm eigenvalues ofP _n ⁻¹ T_n tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned matricesP _n ⁻¹ T_n are computed.     

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

Embedding fault-free cycles in crossed cubes with conditional link faults

The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2 ⁿ . The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2 ⁿ can be applied to an n-dimensional crossed cube with up to 2n−5 link faults.

The panconnectivity and the pancycle-connectivity of the generalized base-<Emphasis Type="Italic">b</Emphasis> hypercube

The interconnection network considered in this paper is the generalized base-b hypercube that is an attractive variant of the well-known hypercube. The generalized base-b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study the panconnectivity and pancycle-connectivity of the generalized base-b hypercube. We show that a generalized base-b hypercube is panconnected for b≥3. That is, for each pair of distinct vertices x and y of the n-dimensional generalized base-b hypercube GH(b,n) and for any integer l, where Dist(x,y)≤l≤N−1, there exists a path of the length l joining x and y, where N is the order of the graph GH(b,n) and Dist(x,y) is the distance between x and y. We also show that a generalized base-b hypercube is pancycle-connected for b≥3. That is, every two distinct vertices x and y of the graph GH(b,n) are contained by a cycle of every length ranging from the length of the smallest cycle that contains x and y to N.     

On the number of transitive digraphs withn labeled vertices andk arcs

A computer determination of the numberT _n,k of transitive digraphs onn labeled vertices andk arcs is obtained for 2≤n≤6,0 ≤k≤n ²-n. Furthermore some formulae are given for determiningT _n,k, ∇n for extremal values ofk (namely, 0≤k≤6 andn ² -3n+4≤k≤n ²-n). Work carried out at Fondazione Ugo Bordoni under the agreements between Fondazione Ugo Bordoni and the Istituto Superiore P. T.     

Una nuova rappresentazione asintotica dei polinomi ultrasferici

In this paper we obtain a new asymptotic formula for the ultraspherical polynomialP _n ^(λ) (x), asn→∞, with an error term which isO (n ^λ−5 ) uniformly in the interval −1+δ≤x≤1−δ,δ>0. Very accurate approximations for the zeros ofP _n ^(λ) (x) are also derived from the preceding formula.

---

---

Lavoro eseguito nell'ambito del Gruppo Nazionale per l'Informatica Matematica del C. N. R..     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

Resource scheduling with variable requirements over time

The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given two sequences of vectors A=A ₁,…,A _n and R=R ₁,…,R _m . Sequence A represents resource availability during n time intervals, where each vector A _i has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R _i has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A _i+k−1 ^j ≥R _k ^j , where A _i+k−1 ^j and R _k ^j are the jth elements of vectors A _i+k−1 and R _k , respectively. One application of this problem is I/O scheduling for multimedia presentations. The fastest known algorithm to compute the optimal solution of this problem has computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time: . We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time, our solution is within 5% of the optimal.     

Il metodo di Treffiz-Fichera per i semigruppi. potenziale di tipo potenza

A variation of the Trefftz-Fichera method is presented to compute lower bounds for the eigenvalues of a positive self-adjoint operator with discrete spectrum with grow at least in a logarithmic way as the index diverges. As suggested by Barnes et al. [2] to compute ground state, the semigroupe ^−βH, β>0, is used rather than the iterated resolvent(H+β) ⁻ⁿ,n=1,2,... As an example, the method is applied to the operatorH=−Δ+|x|^γ. inL ²(R), 1≤γ≤4.      

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

Calculating optimal addition chains

An addition chain is a finite sequence of positive integers 1 = a ₀ ≤ a ₁ ≤ · · · ≤ a _r = n with the property that for all i > 0 there exists a j, k with a _i = a _j + a _k and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains for n ≤ 2³² were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 ⁿ − 1) = l(n) + n − 1 was confirmed for many new values.     

Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

On the convergence rate of two projection methods for variational inequalities in ℝ n

This paper presents a study on the convergence rate of two projection methods for solving the variational inequality problemh∈K, 〈C(h),f-h〉 ≥ 0, ∀f∈K, whereK is a closed convex subset of ℝ ⁿ ,C is a mapping fromK to ℝ ⁿ and <.,.> denotes the inner product in ℝ ⁿ . The first method, proposed by Dafermos [6] for the case whenC is continuously differentiable and strongly monotone, generates a sequence{f ⁱ } inK which is geometrically convergent to the unique solutionh∈K of the variational inequality; i.e., there exists a constant λ≡]0,1[ such that for all i, ∥f ⁱ⁺¹ −h∥ _G ≤λ ∥f ⁱ −h∥, whereG is a symmetric positive definite matrix and ∀f≡ℝ ⁿ . The second method, proposed by Bertsekas and Gafni [8] for the case whenK is polyhedral andC is of the formC=A ⁱ TA, whereA is anm×n matrix andT: ℝ ^m →ℝ ^m is Lipschitz continuous and strongly monotone, generates a sequence{f ⁱ } inK which converges to a solutionh≡K of the variational inequality and satisfies the following estimate: ∥f ⁱ⁺¹ −h∥ _G ≤qβ ⁱ , whereq>0 and β≡]0,1[. We examine the dependence of the constants λ and β on the parameters of the methods and establish that, except for particular cases, these constants do not assume those values which guarantee a rapid convergence of the methods. This work was extracted from the degree thesis [9] (Supervisor: A Laratta), Dipartimento di Matematica, Università di Modena.     

Effect of dispersed phase viscosity on maximum droplet generation frequency in microchannel emulsification using asymmetric straight-through channels

Uniformly sized droplets of soybean oil, MCT (medium-chain fatty acid triglyceride) oil and n-tetradecane with a Sauter mean diameter of d _3,2 = 26–35 μm and a distribution span of 0.21–0.25 have been produced at high throughputs using a 24 × 24 mm silicon microchannel plate consisting of 23,348 asymmetric channels fabricated by photolithography and deep reactive ion etching. Each channel consisted of a 10-μm diameter straight-through micro-hole with a length of 70 μm and a 50 × 10 μm micro-slot with a depth of 30 μm at the outlet of each channel. The maximum dispersed phase flux for monodisperse emulsion generation increased with decreasing dispersed phase viscosity and ranged from over 120 L m⁻² h⁻¹ for soybean oil to 2,700 L m⁻² h⁻¹ for n-tetradecane. The droplet generation frequency showed significant channel to channel variations and increased with decreasing viscosity of the dispersed phase. For n-tetradecane, the maximum mean droplet generation frequency was 250 Hz per single active channel, corresponding to the overall throughput in the device of 3.2 million droplets per second. The proportion of active channels at high throughputs approached 100% for soybean oil and MCT oil, and 50% for n-tetradecane. The agreement between the experimental and CFD (Computational Fluid Dynamics) results was excellent for soybean oil and the poorest for n-tetradecane.     

The group of permutation automorphisms of a <Emphasis Type="Italic">q</Emphasis>-ary hamming code

We prove that the group of permutation automorphism of a q-ary Hamming code of length n = (q ^m − 1)/(q − 1) is isomorphic to the unitriangular group UT _m (q) if the code has a parity-check matrix composed of all columns of the form (0 ...0 1 * ... *)^T. We also show that the group of permutation automorphisms of a cyclic Hamming code cannot be isomorphic to UT _m (q). We thus show that equivalent codes can have different permutation automorphism groups.