A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

A simple approximation for the Erlang loss function

In this paper we present a simple non-iterative computational procedure for approximating the Erlang loss function B(N, ). It is applicable to the practical range 10⁻⁵<B(N, )<10⁻¹ and gives results that are within 10% of the exact values. The formula can be computed on a pocket calculator in constant time and could be used to approximately compute B(N, ) for systems of practically any size.     

State space measures of robustness of pole locations for structured and unstructured perturbations

Measures of pole location robustness for linear feedback systems are derived from a state space model of the system. The robustness tests ensure that the eigenvalues of the perturbed systems matrix A + E remain in a desired region D of the complex plane containing the eigenvalues of the nominal system matrix A. The region D may be any open set of the complex plane whatsoever. The results are expressed in terms of induced matrix norms and apply to structured perturbations of the form E = BΔC, where B and C define the structure of E, and may be nonsquare matrices. Rank one perturbations E of minimal norm and with the given structure that will cause A + E to have an eigenvalue outside of D are constructed for the cases when the matrix norm is induced by the vector 1-norm or the vector ∞-norm. The advantages of having robustness measures for several matrix norms that can be computed are illustrated with a simple example that demonstrates how the conservatism of single tests can be reduced using several tests (i.e. several matrix norms). A method for computing numerically the robustness measures for particular norms is presented. It can be used to compute, with a guaranteed degree of accuracy, the maximum of the norm of the frequency response of a system.     

On two-sided infinite fixed points of morphisms

Let Σ be a finite alphabet, and let h:Σ^* → Σ^* be a morphism. Finite and infinite fixed points of morphisms—i.e., those words w such that h(w)=w—play an important role in formal language theory. Head characterized the finite fixed points of h, and later, Head and Lando characterized the one-sided infinite fixed points of h. Our paper has two main results. First, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the “pointed” and “unpointed” cases. Second, we completely characterize the solutions to the equation h(xy)=yx in finite words.     

A simple, moderately accurate, atmospheric correction algorithm for SeaWiFS

We present a simple modification to the standard coastal zone color scanner (CZCS) atmospheric correction algorithm for application to Sea-viewing-wide field-ofview-sensor (SeaWiFS). The modification reduces the error in the water-leaving reflectance using the standard algorithm by a factor of 2–6 when the aerosol behaves as predicted by the LOWTRAN-6 models. For many aerosol models likely to approximate aerosol properties over the oceans the error in the retrieved water-leaving reflectance is predicted to be < ± 0.002 at 443 nm for an aerosol load approximately 2 to 3 times that normally occurring in a maritime atmosphere. These errors in atmospheric correction lead to an error in the pigment concentration (C), retrieved using the blue-green ratio algorithm, of < 50% for more than 75% of the aerosol models tested, whenever the algorithm retrieves a “reasonable” pigment concentration, and when 0.1 ≤ C ≤ 1 mg / m³. This accuracy may be sufficient for some applications, for example, at-sea processing to guide ships to desirable sampling locations. An important feature of this algorithm is that, unlike more sophisticated and computational intensive algorithms, aerosol models are not required to effect the actual atmospheric correction. Investigators already having the CZCS algorithm implemented on an image processing system should be able to process SeaWiFS imagery by making very simple modifications to the code.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

An algorithmic view of gene teams

Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are “not too far” in all genomes. In this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. The first one runs in O(mn log² n) and uses a divide and conquer approach based on the formal properties of gene teams. We next propose an optimization of the original algorithm, and, in order to better understand the complexity bound of the algorithms, we recast the problem in the Hopcroft's partition refinement framework. This allows us to analyze the complexity of the algorithms with elegant amortized techniques. Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

Optimizing agent-based meeting scheduling through preference estimation

Meeting scheduling is a routine task that needs to be performed quite regularly and frequently within any organization. Unfortunately, this task can be quite tedious and time-consuming, potentially requiring a several rounds of negotiations among many people on the meeting date, time and place before a meeting can finally be confirmed. The objective of our research is to create an agent-based environment within which meeting scheduling can be performed and optimized. For meeting scheduling, we define optimality as the solution that has the highest average preference level among all the possible choices. Our model tries to mimic real life in that an individual's preferences are not made public. Without complete information, traditional optimal algorithms, such as A^* will not work. In this paper, we present a novel “preference estimation” technique that allows us to find optimal solutions to negotiations problems without needing to know the exact preference models of all the meeting participants beforehand. Instead, their preferences are “estimated” and built on the fly based on observations of their responses during negotiation. Another unique contribution is the use of “preference rules” that allow preferences to change dynamical as scheduling decisions are made. This mimics changing preferences as schedule gets filled. This paper uses two negotiation algorithms to compare the effect of “preference estimation”—one that is based on negotiation through relaxation and the other that extends this with preference estimations. Simulations were then performed to compare these algorithms.     

Computerized formal solutions of dynamical systems with two degrees of freedom and an application to the Contopoulos potential—II : The near-resonance case

The article describes the periodic solutions of the Contopoulos system for the case of near-resonant frequencies (ω₂² = 1 and ω = 1 − ε²² The Lindstedt method is used throughout with all the literal algebraic manipulations being computerized so that all expansions are carried to the fourth order in the small parameter ε.

It is shown that each of the two normal modes of oscillation has a bifurcation (really trifurcation) point which moves towards the origin when the exact resonance is approached, explaining why the one-to-one resonant Contopoulos system has six modes of periodic oscillations near the origin, rather then the usual number of two.

We give a single Lindstedt-type literal expansion which is valid for the three intersecting families of periodic solutions. This expansion contains two constants, A and D, representing the direct and retrograde circulations C⁺ and C⁻ when both constants are non-zero and the vertical normal mode family when A = 0.

The verifications of the analytical results by numerical integrations are also given.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

Array-index: a plug&search K nearest neighbors method for high-dimensional data

Previous algorithms of data partitioning methods (DPMs) to find the exact K-nearest neighbors (KNN) at high dimensions are outperformed by a linear scan method [J.M. Kleinberg, Two algorithms for nearest neighbor search in high dimensions, 29th ACM Symposium on Theory of computing, 1997; R. Weber, H.-J. Schek, S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. in: Proc. of the 24th VLDB, USA, 1998]. In this paper, we present a “plug&search” method to greatly speed up the exact KNN search of existing DPMs. The idea is to linearize the data partitions produced by a DPM, rather than the points themselves, into a one-dimensional array-index, that is simple, compact and fast. Unlike most DPMs that support KNN search, which require storage space linear, or exponential [J.M. Kleinberg, Two algorithms for nearest neighbor search in high dimensions, 29th ACM Symposium on Theory of computing, 1997; M. Hagedoom, Nearest neighbors can be found efficiently if the dimension is small relative to the input size, ICDT 2003], in dimensions, the array-index requires a storage space that is linear in the number of mapped partitions.     

Reaching a goal with directional uncertainty

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle centered around the specified direction.

First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of . We prove that the maximum complexity of is O(n/⁵). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k³m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of . For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.     

Lax-stability of fully discrete spectral methods via stability regions and pseudo-eigenvalues

In many calculations, spectral discretization in space is coupled with a standard ordinary differential equation formula in time. To analyze the stability of such a combination, one would like simply to test whether the eigenvalues of the spatial discretization operator (appropriately scaled by the time step k) lie in the stability region for the o.d.e. formula, but it is well known that this kind of analysis is in general invalid. In the present paper we rehabilitate the use of stability regions by proving that a discrete linear multistep ‘method of lines’ approximation to a partial differential equation is Lax-stable, within a small algebraic factor, if and only if all of the -pseudo-eigenvalues of the spatial discretization operator lie within O() of the stability region as → 0. An -pseudo-eigenvalue of a matrix A is any number that is an eigenvalue of some matrix A + E with E ; our arguments make use of resolvents and are closely related to the Kreiss matrix theorem. As an application of our general result, we show that an explicit N-point Chebyshev collocation approximation of u_t = −xu_x on [−1, 1] is Lax-stable if and only if the time step satisfies k = O(N⁻²), although eigenvalue analysis would suggest a much weaker restriction of the form k CN⁻¹.     

Uniform and optimal schemes for stiff initial-value problems

We formulate a class of difference schemes for stiff initial-value problems, with a small parameter ε multiplying the first derivative. We derive necessary conditions for uniform convergence with respect to the small parameter ε, that is the solution of the difference scheme u_i^h satisfies |u_i^h−u(x_i)| Ch, where C is independent of h and ε. We also derive sufficient conditions for uniform convergence and show that a subclass of schemes is also optimal in the sense that |u_i^h−u(x_i)| C min (h, ε). Finally, we show that this class contains higher-order schemes.     

Hybrid stabilization of planar linear systems with one-dimensional outputs

We consider a linear control system x′=Ax+Bu with output y=Cx, where xR², u, yR, and give necessary and sufficient conditions in order that it can be stabilized by a hybrid, linear feedback, where the action of the “switch” just depends on the sign of y. We also show, on these conditions, that the use of two control functions is enough for getting the goal.     

Fast, long-lived renaming improved and simplified

In the long-lived M-renaming problem, N processes repeatedly acquire and release names ranging over {0, …, M − 1}, where M < N. It is assumed that at most k M processes concurrently request or hold names. Efficient solutions to the long-lived renaming problem can be used to improve the performance of applications in which processes repeatedly perform computations whose time complexity depends on the size of the name space containing the processes that participate concurrently. In this paper, we consider wait-free solutions to the long-lived M -renaming problem that use only read and write instructions in an asynchronous, shared-memory multiprocessor. A solution to long-lived renaming is fast if the time complexity of acquiring and releasing a name once is independent of N. We present a new fast, long-lived (k(k + 1)/2)renaming algorithm that significantly improves upon the time and space complexity of similar previous algorithms, while providing a much simpler solution. We also show that fast, long-lived (2k − 1)-renaming can be implemented with reads and writes. This result is optimal with respect to the size of the name space.