Estimating and Validating the Cumulative Distribution of a Function of Random Variables: Toward the Development of Distribution Arithmetic

A method for estimating and validating the cumulative distribution of a function of random variables (independent or dependent) is presented and examined. The method creates a sequence of bounds that will converge to the distribution function in the limit for functions of independent random variables or of random variables of known dependencies. Moreover, an approximation is constructed from and contained in these bounds. Preliminary numerical experiments indicate that this approximation is close to the actual distribution after a few iterations. Several examples are given to illustrate the method.     

Context Switching in a Run-Time Reconfigurable System

A distinguishing feature of reconfigurable computing over rapid prototyping is its ability to configure the computational fabric on-line while an application is running. Conventional reconfigurable computing platforms utilize commodity FPGAs, which typically have relatively long configuration times. Shrinking the configuration time down to the nanosecond region opens possibilities for rapid context switching and virtualizing the computational resources. An experimental context-switching FPGA, called the CSRC, has been created by BAE Systems, and gives researchers the opportunity to explore context-switching applications. This paper presents results obtained from constructing both control-driven and data-driven context switching applications on the CSRC device, along with unique properties of the run-time and compile-time environment.     

Growing Urban Roads

We present a simple simulation of road growing dynamics that can generate global features as belt-ways and star patterns observed in urban transportation infrastructure. The road growing dynamics consist of two steps: Identifying the maximum transportation potential bewteen two locations within the city, followed by the generation of the least expensive road between these two locations. The simulation defines a previously missing component for modeling the co-evolution of urban settlement- and road systems as it can directly be coupled to existing urban settlement simulations.     

Requirements engineering needs total systems engineering

Conclusions It is asserted that current approaches and automated support for requirements engineering are not yet sufficient to build today’s and tomorrow’s complex systems. Requirements engineering, itself intricately connected to system design and system solution and not separate from either, needs to be embedded into a total systems engineering approach. This is the route to systems engineering maturity. Software and systems engineering can and should learn from each other.     

An Efficient Algorithm for Minimizing Real-Time Transition Systems

We address the problem of performing simultaneously reachability analysis and minimization of real-time transition systems represented by timed automata, i.e., automata extended with a finite set of clock variables. The transitions of the automaton may depend on the values of the clocks and may reset some of the clocks. An efficient algorithm is presented for minimizing a system with respect to a given initial partition that respects the enabling conditions of the transitions of the timed automaton. Our algorithm generates the portion of the minimized system that is reachable from a given initial configuration in time polynomial in the input and the size of the minimal reachable system.     

Distributed Job Scheduling in Rings

We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.     

An implementation of the coupled perturbed Kohn-Sham equations: perturbation due to nuclear displacements

The Coupled Perturbed Kohn-Sham equations have been implemented in the Amsterdam Density Functional program package. Our implementation differs from previous ones in many ways. This program uses density fitting to calculate the Coulomb and exchange integrals. Further, all matrix elements of the Fock type matrix and its derivatives are calculated by numerical integration. The frozen core approximation is also implemented. Our implementation is approximately 10 times faster than a finite difference algorithm, and the absolute CPU times also compare favorably with other reported implementations.     

Teaching Macroeconomics with GAMS

Our general goal in this paper is to show how to implement in GAMS standard deterministic nonlinear macro models, and stochastic linear macro models with rational expectations. We will also present basic concepts on solution methods and policy analysis for these kinds of models. As a practical illustration, we will use some well known teaching and experimental models in the macroeconomic literature.     

Statistically representative three-dimensional microstructures based on orthogonal observation sections

Techniques are described that have been used to create a statistically representative three-dimensional model microstructure for input into computer simulations using the geometric and crystallographic observations from two orthogonal sections through an aluminum polycrystal. Orientation maps collected on the observation planes are used to characterize the sizes, shapes, and orientations of grains. Using a voxel-based tessellation technique, a microstructure is generated with grains whose size and shape are constructed to conform to those measured experimentally. Orientations are then overlaid on the grain structure such that distribution of grain orientations and the nearest-neighbor relationships, specified by the distribution of relative misorientations across grain boundaries, match the experimentally measured distributions. The techniques are applicable to polycrystalline materials with sufficiently compact grain shapes and can also be used to controllably generate a wide variety of hypothetical microstructures for initial states in computer simulations. This article is based on a presentation made at the symposium “Characterization and Representation of Material Microstructures in 3-D” held October 8–10, 2002, in Columbus, OH, under the auspices of ASM International’s Phase Transformations committee.     

Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information). As applications for distance labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. The current paper considers the problem on dynamic trees, and proposes efficient distributed schemes for it. The paper first presents a labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log² n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log² n) bit labels. This label size is known to be optimal even in the static scenario. A more general labeling scheme is then introduced for the dynamic tree model, based on extending an existing static tree labeling scheme to the dynamic setting. The approach fits a number of natural tree functions, such as distance, separation level, and flow. The main resulting scheme incurs an overhead of an O(log n) multiplicative factor in both the label size and amortized message complexity in the case of dynamically growing trees (with no vertex deletions). If an upper bound on n is known in advance, this method yields a different tradeoff, with an O(log² n/log log n) multiplicative overhead on the label size but only an O(log n/log log n) overhead on the amortized message complexity. In the fully dynamic model the scheme also incurs an increased additive overhead in amortized communication, of O(log² n) messages per operation.