A robust conjugate-gradient algorithm which minimizes L-functions

A new conjugate-gradient algorithm which minimizes a function of n variables is given. The algorithm performs n orthogonal searches in each stage and hence has the property that it is robust, i.e. it will not easily fail on functions which have a large number of variables (n ? 10) nor on functions which have ‘ridge-like’ properties. A general class of functions called L-functions, which includes the class of quadratic functions as a special case, is defined, and it is shown that the algorithm has the property that it will converge to the minimum of an L-function in n (or less) 1-dimensional minimizations and (n ? 1) (or less) 1-dimensional pseudo-minimizations. Numerical experiments are included for systems of the second to the fortieth order, and based on these experiments, (assuming that the gradients are calculated numerically), the new algorithm appears to be more robust than Powell's [10], Fletcher-Powell's [11], and Jacobson-Oksman's [14] methods, faster than Rosenbrock's [9] method, and especially effective on high dimensional problems.     

Real-time recognition of two-dimensional tapes by cellular automata

We introduce an n-dimensional cellular automaton (n-BCA) which accepts (n + 1)-dimensional tapes in real time. Here we regard an (n + 1)-dimensional tape as a time sequence of n-dimensional tapes, and we say that an (n + 1)-dimensional tape is accepted by an n-BCA if a final-state configuration of the acceptor belongs to a predetermined set of n-dimensional words. We state some features of the sets of 2-dimensional tapes accepted by deterministic 1-BCA's (1-DBCA's), including closure properties. For the unary input alphabet, we obtain that 1-DBCA's can recognize every set of tapes each of which has length represented by a polynomial in its width. For an arbitrary input alphabet, we obtain that the class of languages each of which consists of all the ith rows of 2-dimensional tapes accepted by a 1-DBCA coincides with the class of context-sensitive languages. For n ? 2, we show that a language not containing the empty word is recursively enumerable if and only if it is the set of top rows of (n + 1)-dimensional tapes accepted by an n-DBCA.     

Computing the relative neighborhood graph in the L1 and L∞ metrics

The Relative Neighborhood Graph (RNG) of a set of nk-dimensional points connects “relatively close” neighbors: two points are connected by an edge if they are at least as close to each other as to any other point. Toussaint recently investigated the properties of the RNG in the Euclidean metric and proposed algorithms for its computation. This note examines one of the open problems listed by Toussaint: the extension of the analysis to non-Euclidean metrics. It is shown that Bentley's range query data structures may be used to improve the speed of the best known RNG algorithm in the L_∞ (for k ? 2) and L₁ (for k = 2) metrics.     

Stationary deterministic flows in discrete systems 1

We consider a deterministic system whose state space is the n-dimensional first orthant. It may be considered as a network of (deterministic) queues, a Karp-Miller vector addition system, a Petri net, a complex computer system, etc. Weak assumptions are then made concerning the asymptotic or limiting behaviour of the instants at which events are observed across a cut in the system: these instants may be considered as ‘arrival’ or ‘departure’ instants. Thus, like in operational analysis, we deal with deterministic and observable properties and we need no stochastic assumptions or restrictions (such as independence, identical distributions, etc.). We consider however asymptotic or stationary properties, as in conventional queuing analysis. Under our assumptions a set of standard theorems are proved: concerning arrival and departure instant measures, concerning ‘birth and death’ type equations, and concerning Little's formula. Our intention is to set the framework for a new approach to performance modelling of computer systems in a context close to that used in actual measurements, but taking into account infinite time behaviour in order to take advantage of the useful mathematical properties of asymptotic results.     

GC 1 multisided Bézier surfaces

This paper presents a new method for generating a tangent-plane continuous (GC¹) multisided surface with an arbitrary number of sides. The method generates piecewise biquintic tensor product Bézier patches which join each other with G¹-continuity and which interpolate the given vector-valued first order cross-derivative functions along the boundary curves. The problem of the twist-compatibility of the surface patches at the center points is solved through the construction of normal-curvature continuous starlines and by the way the twists of surface patches are generated. This avoids the inter-relationship among the starlines and the twists of surface patches at the center points. The generation of the center points and the starlines has many degrees of freedom which can be used to modify and improve the quality of the resulting surface patches. The method can be used in various geometric modeling applications such as filling n-sided holes, smoothing vertices of polyhedral solids, blending multiple surfaces, and modeling surface over irregular polyhedral line and curve meshes.     

Transfinite surface interpolation with interior control

There are various techniques to design complex free-form shapes with general topology. In contrast to the approaches based on trimmed surfaces and control polyhedra, in curve network-based design feature curves can be directly created and edited in 3D. Multi-sided patches interpolate this curve network with slopes given by associated tangent ribbons. The patches are smoothly connected and yield a natural and predictable surface model. This paper focuses on special design techniques to adjust the interior of transfinite patches when further shape control is needed. While the boundary constraints are retained, additional vertices, curves and even interior control surfaces are supplemented to gain more design freedom. The main idea is to apply different distance-based blending functions with special parameterizations over non-regular, n-sided domains. This concept can be naturally extended to create one- and two-sided patches as well. Shape variations will be demonstrated by a few simple examples.     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

Finite automata with multiplication

A finite automaton with multiplication (FAM) is a finite automaton with a register which is capable of holding any positive rational number. The register can be multiplied by any of a fixed number of rationals and can be tested for value 1. Closure properties and decision problems for various types of FAM's (e.g. two-way, one-way, nondeterministic, deterministic) are investigated. In particular, it is shown that the languages recognized by two-way deterministic FAM's are of tape complexity log n and time complexity n³. Some decision problems related to vector addition systems are also studied.     

Approximating reachable sets for a class of linear control systems†

We present a technique for overestimating the reachable set from the origin for a class of n-dimensional linear control systems. The proposed ‘box’ method is based upon decomposing the system into one and two-dimensional subsystems for which bounds on the new variables can readily be found. Using these bounds enables the construction of a n-dimensional parallelepiped containing the reachable set of the original system. Examples of this procedure are given as well as a comparison to an overapproximation afforded by a Lyapunov approach.     

Piecewise cubic monotone interpolation with assigned slopes

An algorithm to construct a monotonicity preserving cubicC ¹ interpolant without modification of the assigned slopes is proposed. AnO(h ⁴) convergence result is obtained when exact function and derivative values are available andO(h ^p ) convergence can be obtained withp=min(4,q) forO(h ^q ) accurate function and derivative values. Numerical experiments carried out on data coming from functions with very different behaviours are presented. The results show that the method can interpolate monotone data in a visually pleasing way, even for data which present rapid variations.     

Routing Permutations on Hypercube Machines with Half-Duplex Links

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω⁻¹ in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps.     

Product location,allocation and server home base location for an order picking line with multiple servers

In this paper, we are interested in several interrelated control issues for a ‘pick to order’ (or, ‘strict’ order picking) picking line which stores N=nk types of products in n bins, each with k shelves. To fill each order, a container is transported past the various locations containing products, and the appropriate quantity of each product is removed from its respective storage location and put into the order container using an ‘out and back’ picking strategy. Each of several pickers is assigned a set or ‘zone’ of products. We are interested in the concurrent problems of: (1) product location, (2) picker home base location, and (3) allocating products to each picker so that the expected order cycle time is minimized. We provide easily implemented algorithms to solve these problems and are able to show that the results apply for several alternate picking strategies. For fixed product locations, we develop an efficient dynamic programming algorithm which determines the optimal product allocation and server locations.     

G2 Surface Interpolation Over General Topology Curve Networks

The basic idea of curve network‐based design is to construct smoothly connected surface patches, that interpolate boundaries and cross‐derivatives extracted from the curve network. While the majority of applications demands only tangent plane (G¹) continuity between the adjacent patches, curvature continuous connections (G²) may also be required. Examples include special curve network configurations with supplemented internal edges, “master‐slave” curvature constraints, and general topology surface approximations over meshes. The first step is to assign optimal surface curvatures to the nodes of the curve network; we discuss different optimization procedures for various types of nodes. Then interpolant surfaces called parabolic ribbons are created along the patch boundaries, which carry first and second derivative constraints. Our construction guarantees that the neighboring ribbons, and thus the respective transfinite patches, will be G² continuous. We extend Gregory's multi‐sided surface scheme in order to handle parabolic ribbons, involving the blending functions, and a new sweepline parameterization. A few simple examples conclude the paper.     

On the ultimate convex hull algorithm in practice

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) ‘throw-away’ algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the ‘ultimate’ ones in theory, they are of little practical value from the point of view of running time.     

DPDA's in ‘atomic normal form’ and applications to equivalence problems

In this paper, we introduce a new normal form for DPDA's, the ‘Atomic Normal Form’. As an application, using also the concept of ‘address language’ due to Gorn [19, 20], we give alternate and more direct proofs of results of Courcelle [3, 4] relating recursion schemes and DPDA's. Address languages enable us to encode trees even when they are not locally finite. As a consequence, the decidability of a new class of schemes corresponding to the ‘stateless DPDA's’ of [26] is obtained.     

The number of registers required for evaluating arithmetic expressions

We study the number of registers required for evaluating arithmetic expressions. This parameter of binary trees appears in various computer science problems as well as in numerous natural sciences applications where it is known as the Strahler number.We give several enumeration results describing the distribution of the number of registers for trees of size n. The average number of registers has the asymptotic expansion log₄n + D(log₄n) + 0(1); here, function D is periodic of period one, and its Fourier expansion can be explicitly determined in terms of Riemann's zeta function and Euler's gamma function.     

Intrinsically universal n-dimensional quantum cellular automata

Several non-axiomatic approaches have been taken to define Quantum Cellular Automata (QCA); Partitioned QCA (PQCA) are the most canonical. Here we show any QCA can be put into PQCA form. Our construction reconciles the non-axiomatic definitions of QCA, showing that they can all simulate one another, thus they are all equivalent to the axiomatic definition. A simple n-dimensional QCA capable of simulating all others to arbitrary precision is described, where the initial configuration and the evolution of any QCA can be encoded within the initial configuration of the intrinsically universal QCA. Several steps then correspond to one step of the simulated QCA, achieved via a non-trivial reduction of the problem to universality in quantum circuits. Results are formalised by defining generalised n-dimensional intrinsic simulation, preserving topology in that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. Implications are discussed.     

Approximate conversion of a rational boundary gregory patch to a nonuniform B-spline surface

A rational boundary Gregory patch is characterized by the facts that anyn-sided loop can be smoothly interpolated and that it can be smoothly connected to an adjacent patch. Thus, it is well-suited to interpolate complicated wire frames in shape modeling. Although a rational boundary Gregory patch can be exactly converted to a rational Bézier patch to enable the exchange of data, problems of high degree and singularity tend to arise as a result of conversion. This paper presents an algorithm that can approximately convert a rational boundary Gregory patch to a bicubic nonuniform B-spline surface. The approximating surface hasC ¹ continuity between its inner patches.     

Stability and model selection in k-means clustering

Clustering stability methods are a family of widely used model selection techniques for data clustering. Their unifying theme is that an appropriate model should result in a clustering which is robust with respect to various kinds of perturbations. Despite their relative success, not much is known theoretically on why or when do they work, or even what kind of assumptions they make in choosing an ‘appropriate’ model. Moreover, recent theoretical work has shown that they might ‘break down’ for large enough samples. In this paper, we focus on the behavior of clustering stability using k-means clustering. Our main technical result is an exact characterization of the distribution to which suitably scaled measures of instability converge, based on a sample drawn from any distribution in ? ⁿ satisfying mild regularity conditions. From this, we can show that clustering stability does not ‘break down’ even for arbitrarily large samples, at least for the k-means framework. Moreover, it allows us to identify the factors which eventually determine the behavior of clustering stability. This leads to some basic observations about what kind of assumptions are made when using these methods. While often reasonable, these assumptions might also lead to unexpected consequences.     

Parallel loop generation and scheduling

Loop tiling is an efficient loop transformation, mainly applied to detect coarse-grained parallelism in loops. It is a difficult task to apply n-dimensional non-rectangular tiles to generate parallel loops. This paper offers an efficient scheme to apply non-rectangular n-dimensional tiles in non-rectangular iteration spaces, to generate parallel loops. In order to exploit wavefront parallelism efficiently, all the tiles with equal sum of coordinates are assumed to reside on the same wavefront. Also, in order to assign parallelepiped tiles on each wavefront to different processors, an improved block scheduling strategy is offered in this paper.