The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

Certain Aspects Related To Computation By Modified Crack Closure Integral(MCCI)

This paper presents the proper computational approach for the estimation of strain energy release rates by modified crack closure integral (MCCI). In particular, in the estimation of consistent nodal force vectors used in the MCCI expressions for quarter-point singular elements (wherein all the nodal force vectors participate in computation of strain energy release rates by MCCI). The numerical example of a centre crack tension specimen under uniform loading is presented to illustrate the approach.

Computation of Diffuse Solar Radiation

A technique for computing the spectral and angular (both the zenith and azimuthal) distribution of the solar energy reaching the surface of earth and any other plane in the atmosphere has been developed. Here the computer code LOWTRAN is used for getting the atmospheric transmittances in conjunction with two approximate procedures: one based on the Eddington method and the other on van de Hulst's adding method, for solving the equation of radiative transfer to obtain the diffuse radiation in the cloud-free situation. The aerosol scattering phase functions are approximated by the Hyeney-Greenstein functions. When the equation of radiative transfer is solved using the adding method, the azimuthal and zenith angle dependence of the scattered radiation is evaluated, whereas when the Eddington technique is utilized only the total downward flux of scattered solar radiation is obtained. Results of the diffuse and beam components of solar radiation received on surface of earth compare very well with those computed by other methods such as the more exact calculations using spherical harmonics and when atmospheric conditions corresponding to that prevailing locally in a tropical location (as in India) are used as inputs the computed values agree closely with the measured values.

Hybrid constant factor incremental delta modulators

The paper presents a new adaptive delta modulator, called the hybrid constant factor incremental delta modulator (HCFIDM), which uses instantaneous as well as syllabic adaptation of the step size. Three instantaneous algorithms have been used: two new instantaneous algorithms (CFIDM-3 and CFIDM-2) and the third, Song's voice ADM (SVADM). The quantisers have been simulated on a digital computer and their performances studied. The figure of merit used is the SNR with correlated, /?C-shaped Gaussian signals and real speech as the input. The results indicate that the hybrid technique is superior to the nonhybrid adaptive quantisers. Also, the two new instantaneous algorithms developed have improved SNR and fast response to step inputs as compared to the earlier systems.

Algorithm for incremental compaction of geometrical layouts

In this paper, a new incremental algorithm for layout compaction is proposed. In addition to its linear time performance in terms of the number of rectangles in the layout, we also describe how incremental compaction can form a good feature in the design of a layout editor. The design of such an editor is also described. In the design of the editor, we describe how arrays can be used to implement quadtrees that represent VLSI layouts. Such a representation provides speed of data access and low storage requirements.

Constant factor incremental delta modulator

This paper presents a new algorithm for the step-size change of instantaneous adaptive delta modulator. The present strategy is such that the step-size at any sampling instant can increase or decrease by either of the two constant factors or can remain the same, depending upon the combination of three or four most recent output bits. The quantizer has been simulated on a digital computer, and its performance compared with other quantizers. The figure of merit used is the SNR with gaussian signals as the input. The results indicate that the new design can give an improved SNR over a wider dynamic range and fast response to step inputs, as compared to the earlier systems.

Analysis and computation of the oil film thickness between the piston ring and cylinder liner of an internal combustion engine

A study of the essential features of piston rings in the cylinder liner of an internal combustion engine reveals that the lubrication problem posed by it is basically that of a slider bearing. According to steady-flow-hydrodynamics, viz. Image the oil film thickness becomes zero at the dead centre positions as the velocity, U = 0. In practice, however, such a phenomenon cannot be supported by consideration of the wear rates of pistion rings and cylinder liners. This can be explained by including the “squeeze” action term in the

Block- and strand-multiplexing for fast computation of a class of transforms

The transforms dealt with in this paper are defined in terms of the transform kernels which are Kroneeker products of the two or more component kernels. The signal flow-graph for the computation of such a transform is obtained with the flow-graphs for the component transforms as building blocks.

Finite field computation technique for exact solution of systems of linear equations and interval linear programming problems

An error-free computational approach is employed for finding the integer solution to a system of linear equations, using finite-field arithmetic. This approach is also extended to find the optimum solution for linear inequalities such as those arising in interval linear programming probloms.

On the computation of two-dimensional compressible flow fields by the modified local stability scheme

The modified local stability scheme is applied to several two-dimensional problems—blunt body flow, regular reflection of a shock and lambda shock. The resolution of the flow features obtained by the modified local stability scheme is found to be better than that achieved by the other first order schemes and almost identical to that achieved by the second order schemes incorporating artificial viscosity. The scheme is easy for coding, consumes moderate amount of computer storage and time. The scheme can be advantageously used in place of second order schemes.

Adiabatic quantum computation with a one-dimensional projector Hamiltonian

Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.

Computation of Thermal Stress Intensity Factors for Bimaterial Interface Cracks Using Domain Integral Method

The concept of domain integral used extensively for J integral has been applied in this work for the formulation of J(2) integral for linear elastic bimaterial body containing a crack at the interface and subjected to thermal loading. It is shown that, in the presence of thermal stresses, the J(k) domain integral over a closed path, which does not enclose singularities, is a function of temperature and body force. A method is proposed to compute the stress intensity factors for bimaterial interface crack subjected to thermal loading by combining this domain integral with the J(k) integral. The proposed method is validated by solving standard problems with known solutions.

Efficient computation of volume fractions for multi-material cell complexes in a grid by slicing

The paper presents a novel slicing based method for computation of volume fractions in multi-material solids given as a B-rep whose faces are triangulated and shared by either one or two materials. Such objects occur naturally in geoscience applications and the said computation is necessary for property estimation problems and iterative forward modeling. Each facet in the model is cut by the planes delineating the given grid structure or grid cells. The method, instead of classifying the points or cells with respect to the solid, exploits the convexity of triangles and the simple axis-oriented disposition of the cutting surfaces to construct a novel intermediate space enumeration representation called slice-representation, from which both the cell containment test and the volume-fraction computation are done easily. Cartesian and cylindrical grids with uniform and non-uniform spacings have been dealt with in this paper. After slicing, each triangle contributes polygonal facets, with potential elliptical edges, to the grid cells through which it passes. The volume fractions of different materials in a grid cell that is in interaction with the material interfaces are obtained by accumulating the volume contributions computed from each facet in the grid cell. The method is fast, accurate, robust and memory efficient. Examples illustrating the method and performance are included in the paper.

Time and Energy Complexity of Distributed Computation of a Class of Functions in Wireless Sensor Networks

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/lo- g n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

Incremental attribute evaluation through recursive procedures

Incremental semantic analysis in a programming environment based on Attribute Grammars is performed by an Incremental Attribute Evaluator (IAE). Current IAEs are either table-driven or make extensive use of graph structures to schedule reevaluation of attributes. A method of compiling an Ordered Attribute Grammar into mutually recursive procedures is proposed. These procedures form an optimal time Incremental Attribute Evaluator for the attribute grammar, which does not require any graphs or tables.