Search results for "Hypercube"
showing 10 items of 21 documents
Strong chromatic index of products of graphs
2007
Graphs and Algorithms
Quantum search of spatial regions
2003
Can Grover's algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time O(sqrt n) for d at least 3, or O((sqrt n)(log n)^(3/2)) for d=2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include a…
SimuRed: A flit-level event-driven simulator for multicomputer network performance evaluation
2009
The interconnection network is one of the most important multicomputer components, since it has a great impact on global system performance. Many models and simulators have been proposed to evaluate network performance. This paper presents SimuRed, an event-driven flit-level, cycle-accurate simulator to evaluate different orthogonal network configurations. The core of the simulator has been designed to be expandable and portable to different situations. Some of the advantages of this simulator over other similar tools are its visual interface, its fast execution and its simplicity. Moreover, it is multiplatform and its source code versions (C++ and Java) are freely available under GNU open-…
Parallel Simulated Annealing: Getting Super Linear Speedups
2005
The study described in this paper tries to improve and combine different approaches that are able to speed up applications of the Simulated Annealing model. It investigates separately two main aspects concerning the degree of parallelism an implementation can egectively exploit at the initial andfinal periods of an execution. As for case studies, it deals with two implementations: the Job shop Scheduling problem and the poryblio selection problem. The paper reports the results of a large number of experiments, carried out by means of a transputer network and a hypercube system. They give useful suggestions about selecting the most suitable values of the intervention parameters to achieve su…
A recurrence-free variant of strassen’s algorithm on hypercube
1995
In this paper a non-recursive Strassen’s matrix multiplication algorithm is presented. This new algorithm is suitable to run on parallel environments. Two computational schemes have been worked out exploiting different parallel approaches on hypercube architecture. A comparative analysis is reported. The experiments have been carried out on an nCUBE-2 supercomputer, housed at CNUCE in Pisa, supporting the Express parallel operating system. © 1995, Taylor & Francis Group, LLC. All rights reserved.
The Lineshape of Inelastic Neutron Scattering in Relaxor Ferroelectrics
2005
We show that a microscopic reason for the steep drop of the optical phonon branch into an acoustic one (the so-called waterfall effect) in relaxor ferroelectrics may be the coupling of phonons with defects and impurities of different kinds, which is always present in relaxors. Namely, we do not specify the type of impurities but rather represent them as an ensemble of so-called two-level systems (TLS). This approach makes it possible to trace the evolution of the “waterfall” with temperature and the TLS concentration. To facilitate the planning of experiments on inelastic neutron scattering, we present a modification of the so-called Latin hypercube sampling method, which, based on some sig…
Surface tension and interfacial fluctuations in d-dimensional Ising model
2005
The surface tension of rough interfaces between coexisting phases in 2D and 3D Ising models are discussed in view of the known results and some original calculations presented in this paper. The results are summarised in a formula, which allows to interpolate the corrections to finite-size scaling between two and three dimensions. The physical meaning of an analytic continuation to noninteger values of the spatial dimensionality d is discussed. Lattices and interfaces with properly defined fractal dimensions should fulfil certain requirements to possibly have properties of an analytic continuation from d-dimensional hypercubes. Here 2 appears as the marginal value of d below which the (d-1)…
Radio k-Labelings for Cartesian Products of Graphs
2005
International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…
Latin hypercube sampling with inequality constraints
2010
International audience; In some studies requiring predictive and CPU-time consuming numerical models, the sampling design of the model input variables has to be chosen with caution. For this purpose, Latin hypercube sampling has a long history and has shown its robustness capabilities. In this paper we propose and discuss a new algorithm to build a Latin hypercube sample (LHS) taking into account inequality constraints between the sampled variables. This technique, called constrained Latin hypercube sampling (cLHS), consists in doing permutations on an initial LHS to honor the desired monotonic constraints. The relevance of this approach is shown on a real example concerning the numerical w…
Kolmogorov Superposition Theorem and Its Application to Multivariate Function Decompositions and Image Representation
2008
International audience; In this paper, we present the problem of multivariate function decompositions into sums and compositions of monovariate functions. We recall that such a decomposition exists in the Kolmogorov's superposition theorem, and we present two of the most recent constructive algorithms of these monovariate functions. We first present the algorithm proposed by Sprecher, then the algorithm proposed by Igelnik, and we present several results of decomposition for gray level images. Our goal is to adapt and apply the superposition theorem to image processing, i.e. to decompose an image into simpler functions using Kolmogorov superpositions. We synthetise our observations, before …