An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Accelerating Numerical Linear Algebra Kernels on a Scalable Run Time Reconfigurable Platform

Numerical Linear Algebra (NLA) kernels are at the heart of all computational problems. These kernels require hardware acceleration for increased throughput. NLA Solvers for dense and sparse matrices differ in the way the matrices are stored and operated upon although they exhibit similar computational properties. While ASIC solutions for NLA Solvers can deliver high performance, they are not scalable, and hence are not commercially viable. In this paper, we show how NLA kernels can be accelerated on REDEFINE, a scalable runtime reconfigurable hardware platform. Compared to a software implementation, Direct Solver (Modified Faddeev's algorithm) on REDEFINE shows a 29X improvement on an average and Iterative Solver (Conjugate Gradient algorithm) shows a 15-20% improvement. We further show that solution on REDEFINE is scalable over larger problem sizes without any notable degradation in performance.

How to run a campaign: Optimal control of SIS and SIR information epidemics

Information spreading in a population can be modeled as an epidemic. Campaigners (e.g., election campaign managers, companies marketing products or movies) are interested in spreading a message by a given deadline, using limited resources. In this paper, we formulate the above situation as an optimal control problem and the solution (using Pontryagin's Maximum Principle) prescribes an optimal resource allocation over the time of the campaign. We consider two different scenarios-in the first, the campaigner can adjust a direct control (over time) which allows her to recruit individuals from the population (at some cost) to act as spreaders for the Susceptible-Infected-Susceptible (SIS) epidemic model. In the second case, we allow the campaigner to adjust the effective spreading rate by incentivizing the infected in the Susceptible-Infected-Recovered (SIR) model, in addition to the direct recruitment. We consider time varying information spreading rate in our formulation to model the changing interest level of individuals in the campaign, as the deadline is reached. In both the cases, we show the existence of a solution and its uniqueness for sufficiently small campaign deadlines. For the fixed spreading rate, we show the effectiveness of the optimal control strategy against the constant control strategy, a heuristic control strategy and no control. We show the sensitivity of the optimal control to the spreading rate profile when it is time varying. (C) 2014 Elsevier Inc. All rights reserved.

On the measurement of the surface energy budget over a land surface during the summer monsoon

The measurement of surface energy balance over a land surface in an open area in Bangalore is reported. Measurements of all variables needed to calculate the surface energy balance on time scales longer than a week are made. Components of radiative fluxes are measured while sensible and latent heat fluxes are based on the bulk method using measurements made at two levels on a micrometeorological tower of 10 m height. The bulk flux formulation is verified by comparing its fluxes with direct fluxes using sonic anemometer data sampled at 10 Hz. Soil temperature is measured at 4 depths. Data have been continuously collected for over 6 months covering pre-monsoon and monsoon periods during the year 2006. The study first addresses the issue of getting the fluxes accurately. It is shown that water vapour measurements are the most crucial. A bias of 0.25% in relative humidity, which is well above the normal accuracy assumed the manufacturers but achievable in the field using a combination of laboratory calibration and field intercomparisons, results in about 20 W m(-2) change in the latent heat flux on the seasonal time scale. When seen on the seasonal time scale, the net longwave radiation is the largest energy loss term at the experimental site. The seasonal variation in the energy sink term is small compared to that in the energy source term.

Unsteady flow over a stretching surface with a magnetic field in a rotating fluid

The effect of the magnetic field on the unsteady flow over a stretching surface in a rotating fluid has been studied. The unsteadiness in the flow field is due to the time-dependent variation of the velocity of the stretching surface and the angular velocity of the rotating fluid. The Navier-Stokes equations and the energy equation governing the flow and the heat transfer admit a self-similar solution if the velocity of the stretching surface and the angular velocity of the rotating fluid vary inversely as a linear function of time. The resulting system of ordinary differential equations is solved numerically using a shooting method. The rotation parameter causes flow reversal in the component of the velocity parallel to the strerching surface and the magnetic field tends to prevent or delay the flow reversal. The surface shear stresses dong the stretching surface and in the rotating direction increase with the rotation parameter, but the surface heat transfer decreases. On the other hand, the magnetic field increases the surface shear stress along the stretching surface, but reduces the surface shear stress in the rotating direction and the surface heat transfer. The effect of the unsteady parameter is more pronounced on the velocity profiles in the rotating direction and temperature profiles.

Spatial distribution of aerosol black carbon over India during pre-monsoon season

Aerosol black carbon (BC) mass concentrations ([BC]), measured continuously during a multi-platform field experiment, Integrated Campaign for Aerosols gases and Radiation Budget (ICARB, March-May 2006), from a network of eight observatories spread over geographically distinct environments of India, (which included five mainland stations, one highland station, and two island stations (one each ill Arabian Sea and Bay of Bengal)) are examined for their spatio-temporal characteristics. During the period of study, [BC] showed large variations across the country, with values ranging from 27 mu g m(3) over industrial/urban locations to as low as 0.065 mu g m(-3) over the Arabian Sea. For all mainland stations, [BC] remained high compared to highland as well as island stations. Among the island stations, Port Blair (PBR) had higher concentration of BC, compared to Minicoy (MCY), implying more absorbing nature of Bay of Bengal aerosols than Arabian Sea. The highland station Nainital (NTL), in the central Himalayas, showed low values of [BC], comparable or even lower than that of the island station PBR, indicating the prevalence of cleaner environment over there. An examination of the changes in the mean temporal features, as the season advances from winter (December-February) to pre-monsoon (March-May), revealed that: (a) Diurnal variations were pronounced over all the mainland stations, with all afternoon low and a nighttime high: (b) At the islands, the diurnal variations, though resembled those over the mainlands, were less pronounced; and (c) In contrast to this, highland station showed an opposite pattern with an afternoon high and a late night or early morning low. The diurnal variations at all stations are mainly caused by the dynamics of local Atmospheric Boundary Layer (ABL), At the entire mainland as well as island stations (except HYD and DEL), [BC] showed a decreasing trend from January to May, This is attributed to the increased convective mixing and to the resulting enhanced vertical dispersal of species in the ABL. In addition, large short-period modulations were observed at DEL and HYD, which appeared to be episodic, An examination of this in the light of the MODIS-derived fire count data over India along with the back-trajectory analysis revealed that advection of BC from extensive forest fires and biomass-burning regions upwind were largely responsible for this episodic enhancement in BC at HYD and DEL.

Flow and heat transfer in a stagnation-point flow over a stretching sheet with a magnetic field

The flow and heat transfer problem in the boundary layer induced by a continuous moving surface is important in many manufacturing processes in industry such as the boundary layer along material handling conveyers, the aerodynamic extrusion of plastic sheet, the cooling of an infinite metalic plate in a cooling bath (which may also be electrolyte). Glass blowing, continuous casting and spinning of fibres also involve the flow due to a stretching surface. Sakiadis [1] was the first to study the flow induced by a semi-infinite moving wall in an ambient fluid. On the other hand, Crane [2] first studied the flow over a linearly stretching sheet in an ambient fluid. Subsequently, Crane [3] also investigated the corresponding heat transfer problem. Since then several authors [4-8] have studied various aspects of this problem such as the effects of mass transfer, variable wall temperature, constant heat flux, magnetic field etc. Recently, Andersson [9] has obtained an exact solution of the Navier-Stokes equations for the MHD flow over a linearly stretching sheet in an ambient fluid. Also Chiam [10] has studied the heat transfer with variable thermal conductivity on a stretching sheet when the velocities of the sheet and the free stream are equal.

Vertical structure and horizontal gradients of aerosol extinction coefficients over coastal India inferred from airborne lidar measurements during the Integrated Campaign for Aerosol, Gases and Radiation Budget (ICARB) field campaign

Quantitative estimates of the vertical structure and the spatial gradients of aerosol extinction coefficients have been made from airborne lidar measurements across the coastline into offshore oceanic regions along the east and west coasts of India. The vertical structure revealed the presence of strong, elevated aerosol layers in the altitude region of similar to 2-4 km, well above the atmospheric boundary layer (ABL). Horizontal gradients also showed a vertical structure, being sharp with the e(-1) scaling distance (D-0H) as small as similar to 150 km in the well-mixed regions mostly under the influence of local source effects. Above the ABL, where local effects are subdued, the gradients were much shallower (similar to 600-800 km); nevertheless, they were steep compared to the value of similar to 1500-2500 km reported for columnar AOD during winter. The gradients of these elevated layers were steeper over the east coast of India than over the west coast. Near-simultaneous radio sonde (Vaisala, Inc., Finland) ascents made over the northern Bay of Bengal showed the presence of convectively unstable regions, first from surface to similar to 750-1000 m and the other extending from 1750 to 3000 m separated by a stable region in between. These can act as a conduit for the advection of aerosols and favor the transport of continental aerosols in the higher levels (> 2 km) into the oceans without entering the marine boundary layer below. Large spatial gradient in aerosol optical and hence radiative impacts between the coastal landmass and the adjacent oceans within a short distance of < 300 km (even at an altitude of 3 km) during summer and the premonsoon is of significance to the regional climate.

Ocean atmosphere coupling over monsoon regions

In monsoon regions, the seasonal migration of the intertropical convergence zone (ITCZ) is manifested as a seasonal reversal of winds. Most of the summer monsoon rainfall over India occurs owing to synoptic and large-scale convection associated with the continental ITCZ (Fig. 1). We have investigated the interaction between these large-scale convective systems and the ocean over which they are generated1â3, concentrating on the relationship between organized convection over the Indian Ocean and sea surface temperature (SST). We report here that on a monthly basis the degree of cloudiness correlates well with SST for the relatively colder oceans, but when SST is maintained above 28 °C it ceases to be an important factor in determining the variability of cloudiness. Over the major regions of convection east of 70°E, which are warm year after year, the observed cloudiness cannot be correlated with variations in SST.

On the probability that the determinant of an nxn matrix over a finite field vanishe

An expression is derived for the probability that the determinant of an n x n matrix over a finite field vanishes; from this it is deduced that for a fixed field this probability tends to 1 as n tends to.

Time dependent rotational flow of a viscous fluid over an infinite porous disk with a magnetic field

Both the semi-similar and self-similar flows due to a viscous fluid rotating with time dependent angular velocity over a porous disk of large radius at rest with or without a magnetic field are investigated. For the self-similar case the resulting equations for the suction and no mass transfer cases are solved numerically by quasilinearization method whereas for the semi-similar case and injection in the self-similar case an implicit finite difference method with Newton's linearization is employed. For rapid deceleration of fluid and for moderate suction in the case of self-similar flow there exists a layer of fluid, close to the disk surface where the sense of rotation is opposite to that of the fluid rotating far away. The velocity profiles in the absence of magnetic field are found to be oscillatory except for suction. For the accelerating freestream, (semi-similar flow) the effect of time is to reduce the amplitude of the oscillations of the velocity components. On the other hand the effect of time for the oscillating case is just the opposite.

Incompressible micropolar fluid flow over a semi-infinite plate

Micropolar fluid flow over a semi-infinite flat plate has been described by using the parabolic co-ordinates and the method of series truncation in order to study the flow for low to large Reynolds numbers. These co-ordinates permit to study the flow regime at the leading edge. Numerical results have been presented for different Reynolds numbers. Results show a reduction in skin friction.

Sensible heat fluxes during the active and break phases of the southwest monsoon over the Indian region

Based on the theory given by Saltzman and Ashe (1976), sensible heat fluxes are calculated for the active and break phases of the southwest monsoon over the Indian region. The conclusion drawn is that the sensible heat flux is generally larger during the break monsoon situation when compared with that for the active monsoon situation. The synoptic heat flux is negligible when compared with mean and diurnal heat fluxes over the Indian region even during the monsoon season.