Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Popular Matchings with Variable Job Capacities

We consider the problem of matching people to jobs, where each person ranks a subset of jobs in an order of preference, possibly involving ties. There are several notions of optimality about how to best match each person to a job; in particular, popularity is a natural and appealing notion of optimality. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not adroit popular matchings. This motivates the following extension of the popular rnatchings problem:Given a graph G; = (A boolean OR J, E) where A is the set of people and J is the set of jobs, and a list < c(1), c(vertical bar J vertical bar)) denoting upper bounds on the capacities of each job, does there exist (x(1), ... , x(vertical bar J vertical bar)) such that setting the capacity of i-th, job to x(i) where 1 <= x(i) <= c(i), for each i, enables the resulting graph to admit a popular matching. In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c is 1 or 2.

Diagnosis of dominant forcing factors for large-scale vertical velocities during active and break phases of the monsoon

An attempt to diagnose the dominant forcings which drive the large-scale vertical velocities over the monsoon region has been made by computing the forcings like diabatic heating fields,etc. and the large-scale vertical velocities driven by these forcings for the contrasting periods of active and break monsoon situations; in order to understand the rainfall variability associated with them. Computation of diabatic heating fields show us that among different components of diabatic heating it is the convective heating that dominates at mid-tropospheric levels during an active monsoon period; whereas it is the sensible heating at the surface that is important during a break period. From vertical velocity calculations we infer that the prime differences in the large-scale vertical velocities seen throughout the depth of the atmosphere are due to the differences in the orders of convective heating; the maximum rate of latent heating being more than 10 degrees Kelvin per day during an active monsoon period; whereas during a break monsoon period it is of the order of 2 degrees Kelvin per day at mid-tropospheric levels. At low levels of the atmosphere, computations show that there is large-scale ascent occurring over a large spatial region, driven only by the dynamic forcing associated with vorticity and temperature advection during an active monsoon period. However, during a break monsoon period such large-scale spatial organization in rising motion is not seen. It is speculated that these differences in the low-level large-scale ascent might be causing differences in convective heating because the weaker the low level ascent, the lesser the convective instability which produces deep cumulus clouds and hence lesser the associated latent heat release. The forcings due to other components of diabatic heating, namely, the sensible heating and long wave radiative cooling do not influence the large-scale vertical velocities significantly.

Vector control of permanent magnet synchronous motor using DSP controller

PMSM drive with high dynamic response is the attractive solution for servo applications like robotics, machine tools, electric vehicles. Vector control is widely accepted control strategy for PMSM control, which enables decoupled control of torque and flux, this improving the transient response of torque and speed. As the vector control demands exhaustive real time computations, so the present work is implemented using TI DSP 320C240. Presently position and speed controller have been successfully tested. The feedback information used is shaft (rotor) position from the incremental encoder and two motor currents. We conclude with the hope to extend the present experimental set up for further research related to PMSM applications.

Computation-Based Reliability Analysis in Real Time Applications

Reliability analysis for computing systems in aerospace applications must account for actual computations the system performs in the use environment. This paper introduces a theoretical nonhomogeneous Markov model for such applications.

Flow and heat transfer in steady laminar compressible boundary layer swirling flow in a nozzle

The axisymmetric steady laminar compressible boundary layer swirling flow of a gas with variable properties in a nozzle has been investigated. The partial differential equations governing the non-similar flow have been transformed into new co-ordinates having finite ranges by means of a transformation which maps an infinite range into a finite one. The resulting equations have been solved numerically using an implicit finite-difference scheme. The computations have been carried out for compressible swirling flow through a convergent conical nozzle. The results indicate that the swirl exerts a strong influence on the longitudinal skin friction, but its effect on the tangential skin friction and heat transfer is comparatively small. The effect of the variation of the density-viscosity product across the boundary layer is appreciable only at low-wall temperature. The results are in good agreement with those of the local-similarity method for small values of the longitudinal distance.

Spatially dependent correlation functions in the Anderson model

We report results from a first principles calculation of spatially dependent correlation functions around a magnetic impurity in metals described by the nondegenerate Anderson model. Our computations are based on a combination of perturbative scaling theory and numerical renormalization group methods. Results for the conduction election charge density around the impurity and correlation functions involving the conduction electron and impurity charge and spin densities will be presented. The behavior in various regimes including the mixed valent regime will be explored.

Mass analyser optics for wide-beam ion sources in ion implantation systems

Ion implantation systems, used for producing high-current ion beams, employ wide-beam ion sources which are rotated through 90 degrees . These sources need mass analyser optics which are different from the conventional design. The authors present results of calculation of the image distance as a function of entrance and exit angles of a sector magnet mass analyser having such a source. These computations have been performed for the magnetic deflection angles 45 degrees , 60 degrees and 90 degrees . The details of the computations carried out using the computer program MODBEAM, developed for this purpose, are also discussed.

A Computationally Efficient PWM Algorithm for Multilevel Inverters

Centred space vector PWM (CSVPWM) technique is popularly used for three level voltage source inverters. The reference voltage vector is synthesized by time-averaging of the three nearest voltage vectors produced by the inverter. Identifying the three voltage vectors, and calculation of the dwelling time for each vector are both computationally intensive. This paper analyses the process of PWM generation in CSVPWM. This analysis breaks up a three-level inverter into six different conceptual two level inverters in different regions of the fundamental cycle. Control of 3-level inverter is viewed as the control of the appropriate 2-level inverter. The analysis leads to a systematic simplification of the computations involved, finally resulting in a computationally efficient PWM algorithm. This algorithm exploits the equivalence between triangle comparison and space vector approaches to PWM generation. This algorithm does not involve any 3-phase/2-phase or 2-phase/3-phase transformation. This also does not involve any transformation from rectangular to polar coordinates, and vice versa. Further no evaluation of trigonometric functions is necessary. This algorithm also provides for the mitigation of DC neutral point unbalance, and is well suited to digital implementation. Simulation and experimental results are presented.

Unsteady laminar compressible boundary-layer flow at a three-dimensional stagnation point

Unsteady laminar compressible boundary-layer flow with variable properties at a three-dimensional stagnation point for both cold and hot walls has been studied for the case when the velocity of the incident stream varies arbitrarily with time. The partial differential equations governing the flow have been solved numerically using an implicit finite-difference scheme. Computations have been carried out for two particular unsteady free-stream velocity distributions: (i) an accelerating stream and (ii) a fluctuating stream. The results indicate that the variation of the density-viscosity product across the boundary layer, the wall temperature and the nature of stagnation point significantly affect the skin friction and heat transfer.

Aspiration-based utility functions in a planning model for timber flow management.

The study presents a theory of utility models based on aspiration levels, as well as the application of this theory to the planning of timber flow economics. The first part of the study comprises a derivation of the utility-theoretic basis for the application of aspiration levels. Two basic models are dealt with: the additive and the multiplicative. Applied here solely for partial utility functions, aspiration and reservation levels are interpreted as defining piecewisely linear functions. The standpoint of the choices of the decision-maker is emphasized by the use of indifference curves. The second part of the study introduces a model for the management of timber flows. The model is based on the assumption that the decision-maker is willing to specify a shape of income flow which is different from that of the capital-theoretic optimum. The utility model comprises four aspiration-based compound utility functions. The theory and the flow model are tested numerically by computations covering three forest holdings. The results show that the additive model is sensitive even to slight changes in relative importances and aspiration levels. This applies particularly to nearly linear production possibility boundaries of monetary variables. The multiplicative model, on the other hand, is stable because it generates strictly convex indifference curves. Due to a higher marginal rate of substitution, the multiplicative model implies a stronger dependence on forest management than the additive function. For income trajectory optimization, a method utilizing an income trajectory index is more efficient than one based on the use of aspiration levels per management period. Smooth trajectories can be attained by squaring the deviations of the feasible trajectories from the desired one.

Performance study of high operating temperature HgCdTe mid wave infrared detector through numerical modeling

The design of present generation uncooled Hg1-xCdxTe infrared photon detectors relies on complex heterostructures with a basic unit cell of type (n) under bar (+)/pi/(p) under bar (+). We present an analysis of double barrier (n) under bar (+)/pi/(p) under bar (+) mid wave infrared (x = 0.3) HgCdTe detector for near room temperature operation using numerical computations. The present work proposes an accurate and generalized methodology in terms of the device design, material properties, and operation temperature to study the effects of position dependence of carrier concentration, electrostatic potential, and generation-recombination (g-r) rates on detector performance. Position dependent profiles of electrostatic potential, carrier concentration, and g-r rates were simulated numerically. Performance of detector was studied as function of doping concentration of absorber and contact layers, width of both layers and minority carrier lifetime. Responsivity similar to 0.38 A W-1, noise current similar to 6 x 10(-14) A/Hz(1/2) and D* similar to 3.1 x 10(10)cm Hz(1/2) W-1 at 0.1 V reverse bias have been calculated using optimized values of doping concentration, absorber width and carrier lifetime. The suitability of the method has been illustrated by demonstrating the feasibility of achieving the optimum device performance by carefully selecting the device design and other parameters. (C) 2010 American Institute of Physics. doi:10.1063/1.3463379]

Studies in biogas technology. Part III. Thermal analysis of biogas plants

A thermal model for a conventional biogas plant has been developed in order to understand the heat transfer from the slurry and the gas holder to the surrounding earth and air respectively. The computations have been performed for two conditions : (i) when the slurry is at an ambient temperature of 20°C, and (ii) when it is at 35°C, the optimum temperature for anaerobic fermentation. Under both these conditions, the gas holder is the major “culprit” with regard to heat losses from the biogas plant. The calculations provide an estimate for the heat which has to be supplied by external means to compensate for the net heat losses which occur if the slurry is to be maintained at 35°C. Even if this external supply of heat is realised through (the calorific value of) biogas, there is a net increase in the biogas output, and therefore a net benefit, by operating the plant at 35°C. At this elevated temperature, the cooling effect of adding the influent at ambient temperature is not insignificant. In conclusion, the results of the thermal analysis are used to define a strategy for operating biogas plants at optimum temperatures, or at higher temperatures than the ambient.

Kinematics of pantograph masts

This paper deals with the kinematics of pantograph masts. Pantograph masts have widespread use in space application as deployable structures. They are over constrained mechanisms with degree-of-freedom, evaluated by the Grübler–Kutzback formula, as less than one. In this paper, a numerical algorithm is used to evaluate the degree-of-freedom of pantograph masts by obtaining the null space of a constraint Jacobian matrix. In the process redundant joints in the masts are obtained. A method based on symbolic computation, to obtain the closed-form kinematics equations of triangular and box shaped pantograph masts, is presented. In the process, the various configurations such masts can attain during deployment, are obtained. The closed-form solution also helps in identifying the redundant joints in the masts. The symbolic computations involving the Jacobian matrix also leads to a method to evaluate the global degree-of-freedom for these masts.

Light scattering in random media with wavelength-scale structures : astronomical and industrial applications

Light scattering, or scattering and absorption of electromagnetic waves, is an important tool in all remote-sensing observations. In astronomy, the light scattered or absorbed by a distant object can be the only source of information. In Solar-system studies, the light-scattering methods are employed when interpreting observations of atmosphereless bodies such as asteroids, atmospheres of planets, and cometary or interplanetary dust. Our Earth is constantly monitored from artificial satellites at different wavelengths. With remote sensing of Earth the light-scattering methods are not the only source of information: there is always the possibility to make in situ measurements. The satellite-based remote sensing is, however, superior in the sense of speed and coverage if only the scattered signal can be reliably interpreted. The optical properties of many industrial products play a key role in their quality. Especially for products such as paint and paper, the ability to obscure the background and to reflect light is of utmost importance. High-grade papers are evaluated based on their brightness, opacity, color, and gloss. In product development, there is a need for computer-based simulation methods that could predict the optical properties and, therefore, could be used in optimizing the quality while reducing the material costs. With paper, for instance, pilot experiments with an actual paper machine can be very time- and resource-consuming. The light-scattering methods presented in this thesis solve rigorously the interaction of light and material with wavelength-scale structures. These methods are computationally demanding, thus the speed and accuracy of the methods play a key role. Different implementations of the discrete-dipole approximation are compared in the thesis and the results provide practical guidelines in choosing a suitable code. In addition, a novel method is presented for the numerical computations of orientation-averaged light-scattering properties of a particle, and the method is compared against existing techniques. Simulation of light scattering for various targets and the possible problems arising from the finite size of the model target are discussed in the thesis. Scattering by single particles and small clusters is considered, as well as scattering in particulate media, and scattering in continuous media with porosity or surface roughness. Various techniques for modeling the scattering media are presented and the results are applied to optimizing the structure of paper. However, the same methods can be applied in light-scattering studies of Solar-system regoliths or cometary dust, or in any remote-sensing problem involving light scattering in random media with wavelength-scale structures.