On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Performance of Quantized Equal Gain Transmission With Noisy Feedback Channels

In this paper, new results and insights are derived for the performance of multiple-input, single-output systems with beamforming at the transmitter, when the channel state information is quantized and sent to the transmitter over a noisy feedback channel. It is assumed that there exists a per-antenna power constraint at the transmitter, hence, the equal gain transmission (EGT) beamforming vector is quantized and sent from the receiver to the transmitter. The loss in received signal-to-noise ratio (SNR) relative to perfect beamforming is analytically characterized, and it is shown that at high rates, the overall distortion can be expressed as the sum of the quantization-induced distortion and the channel error-induced distortion, and that the asymptotic performance depends on the error-rate behavior of the noisy feedback channel as the number of codepoints gets large. The optimum density of codepoints (also known as the point density) that minimizes the overall distortion subject to a boundedness constraint is shown to be the same as the point density for a noiseless feedback channel, i.e., the uniform density. The binary symmetric channel with random index assignment is a special case of the analysis, and it is shown that as the number of quantized bits gets large the distortion approaches the same as that obtained with random beamforming. The accuracy of the theoretical expressions obtained are verified through Monte Carlo simulations.

Arithmetically Cohen-Macaulay bundles on complete intersection varieties of sufficiently high multidegree

Recently it has been proved that any arithmetically Cohen-Macaulay (ACM) bundle of rank two on a general, smooth hypersurface of degree at least three and dimension at least four is a sum of line bundles. When the dimension of the hypersurface is three, a similar result is true provided the degree of the hypersurface is at least six. We extend these results to complete intersection subvarieties by proving that any ACM bundle of rank two on a general, smooth complete intersection subvariety of sufficiently high multi-degree and dimension at least four splits. We also obtain partial results in the case of threefolds.

Commercialization of sustainable energy technologies

Commercialization efforts to diffuse sustainable energy technologies (SETs1) have so far remained as the biggest challenge in the field of renewable energy and energy efficiency. Limited success of diffusion through government driven pathways urges the need for market based approaches. This paper reviews the existing state of commercialization of SETs in the backdrop of the basic theory of technology diffusion. The different SETs in India are positioned in the technology diffusion map to reflect their slow state of commercialization. The dynamics of SET market is analysed to identify the issues, barriers and stakeholders in the process of SET commercialization. By upgrading the ‘potential adopters’ to ‘techno-entrepreneurs’, the study presents the mechanisms for adopting a private sector driven ‘business model’ approach for successful diffusion of SETs. This is expected to integrate the processes of market transformation and entrepreneurship development with innovative regulatory, marketing, financing, incentive and delivery mechanisms leading to SET commercialization.

Asymptotic behaviour and boundedness of linear systems with time varying coefficients

Motivated by developments in spacecraft dynamics, the asymptotic behaviour and boundedness of solution of a special class of time varying systems in which each term appears as the sum of a constant and a time varying part, are analysed in this paper. It is not possible to apply standard textbook results to such systems, which are originally in second order. Some of the existing results are reformulated. Four theorems which explore the relations between the asymptotic behaviour/boundedness of the constant coefficient system, obtained by equating the time varying terms to zero, to the corresponding behaviour of the time varying system, are developed. The results show the behaviour of the two systems to be intimately related, provided the solutions of the constant coefficient system approach zero are bounded for large values of time, and the time varying terms are suitably restrained. Two problems are tackled using these theorems.

A molecular theory of collective orientational relaxation in pure and binary dipolar liquids

A molecular theory of collective orientational relaxation of dipolar molecules in a dense liquid is presented. Our work is based on a generalized, nonlinear, Smoluchowski equation (GSE) that includes the effects of intermolecular interactions through a mean‐field force term. The effects of translational motion of the liquid molecules on the orientational relaxation is also included self‐consistently in the GSE. Analytic expressions for the wave‐vector‐dependent orientational correlation functions are obtained for one component, pure liquid and also for binary mixtures. We find that for a dipolar liquid of spherical molecules, the correlation function ϕ(k,t) for l=1, where l is the rank of the spherical harmonics, is biexponential. At zero wave‐vector, one time constant becomes identical with the dielectric relaxation time of the polar liquid. The second time constant is the longitudinal relaxation time, but the contribution of this second component is small. We find that polar forces do not affect the higher order correlation functions (l>1) of spherical dipolar molecules in a linearized theory. The expression of ϕ(k,t) for a binary liquid is a sum of four exponential terms. We also find that the wave‐vector‐dependent relaxation times depend strongly on the microscopic structure of the dense liquid. At intermediate wave vectors, the translational diffusion greatly accelerates the rate of orientational relaxation. The present study indicates that one must pay proper attention to the microscopic structure of the liquid while treating the translational effects. An analysis of the nonlinear terms of the GSE is also presented. An interesting coupling between the number density fluctuation and the orientational fluctuation is uncovered.

Studies on nonisothermal solid state galvanic cells — effect of gradients on EMF

An expression for the EMF of a nonisothermal galvanic cell, with gradients in both temperature and chemical potential across a solid electrolyte, is derived based on the phenomenological equations of irreversible thermodynamics. The EMF of the nonisothermal cell can be written as a sum of the contributions from the chemical potential gradient and the EMF of a thermocell operating in the same temperature gradient but at unit activity of the neutral form of the migrating species. The validity of the derived equation is confirmed experimentally by imposing nonlinear gradients of temperature and chemical potential across galvanic cells constructed using fully stabilized zirconia as the electrolyte. The nature of the gradient has no effect on the EMF.

Design of crosspoint-irredundant PLAs using minimal number of control inputs

The problem of determining a minimal number of control inputs for converting a programmable logic array (PLA) with undetectable faults to crosspoint-irredundant PLA for testing has been formulated as a nonstandard set covering problem. By representing subsets of sets as cubes, this problem has been reformulated as familiar problems. It is noted that this result has significance because a crosspoint-irredundant PLA can be converted to a completely testable PLA in a straightforward fashion, thus achieving very good fault coverage and easy testability.

Optimal reservoir operation for irrigation of multiple crops using genetic algorithms

This paper presents a genetic algorithm (GA) model for obtaining an optimal operating policy and optimal crop water allocations from an irrigation reservoir. The objective is to maximize the sum of the relative yields from all crops in the irrigated area. The model takes into account reservoir inflow, rainfall on the irrigated area, intraseasonal competition for water among multiple crops, the soil moisture dynamics in each cropped area, the heterogeneous nature of soils. and crop response to the level of irrigation applied. The model is applied to the Malaprabha single-purpose irrigation reservoir in Karnataka State, India. The optimal operating policy obtained using the GA is similar to that obtained by linear programming. This model can be used for optimal utilization of the available water resources of any reservoir system to obtain maximum benefits.

Approximate multipole coefficients of RF ion traps as functions of aperture size

In this study we present approximate analytical expressions for estimating the variation in multipole expansion coefficients as a function of the size of the apertures in the electrodes in axially symmetric (3D) and two-dimensional (2D) ion trap ion traps. Following the approach adopted in our earlier studies which focused on the role of apertures to fields within the traps, here too, the analytical expression we develop is a sum of two terms, A(n,noAperiure), the multipole expansion coefficient for a trap with no apertures and A(n,dueToAperture), the multipole expansion coefficient contributed by the aperture. A(n,noAperture) has been obtained numerically and A(n,dueToAperture) is obtained from the n th derivative of the potential within the trap. The expressions derived have been tested on two 3D geometries and two 2D geometries. These include the quadrupole ion trap (QIT) and the cylindrical ion trap (CIT) for 3D geometries and the linear ion trap (LIT) and the rectilinear ion trap (RIT) for the 2D geometries. Multipole expansion coefficients A(2) to A(12), estimated by our analytical expressions, were compared with the values obtained numerically (using the boundary element method) for aperture sizes varying up to 50% of the trap dimension. In all the plots presented, it is observed that our analytical expression for the variation of multipole expansion coefficients versus aperture size closely follows the trend of the numerical evaluations for the range of aperture sizes considered. The maximum relative percentage errors, which provide an estimate of the deviation of our values from those obtained numerically for each multipole expansion coefficient, are seen to be largely in the range of 10-15%. The leading multipole expansion coefficient, A(2), however, is seen to be estimated very well by our expressions, with most values being within 1% of the numerically determined values, with larger deviations seen for the QIT and the LIT for large aperture sizes. (C) 2010 Elsevier B.V. All rights reserved.

Direct current electrical resistivity of zinc borate glasses containing transition metal oxides

The resistivities of zinc borate glasses containing Fe2O3, V2O5, and Fe2O3 + V2O5 have been measured as a function of composition and temperature. The values of resistivity and activation energy decrease as the transition metal oxide content is increased. The conductivities of the glasses containing Fe2O3 + V2O5 are more than the sum of those of the glasses containing only Fe2O3 or V2O5 (i.e. the activation energies are less than the sum of those in the glasses containing only Fe2O3 or V2O5). The results are discussed in terms of existing theories.

A New Approach to the Problem of Scattering of Water Waves by Vertical Barriers

Using a modified Green's function technique the two well-known basic problems of scattering of surface water waves by vertical barriers are reduced to the problem of solving a pair of uncoupled integral equations involving the “jump” and “sum” of the limiting values of the velocity potential on the two sides of the barriers in each case. These integral equations are then solved, in closed form, by the aid of an integral transform technique involving a general trigonometric kernel as applicable to the problems associated with a radiation condition.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

A classification of homogeneous operators in the Cowen-Douglas class

An explicit construction of all the homogeneous holomorphic Hermitian vector bundles over the unit disc D is given. It is shown that every such vector bundle is a direct sum of irreducible ones. Among these irreducible homogeneous holomorphic Hermitian vector bundles over D, the ones corresponding to operators in the Cowen-Douglas class B-n(D) are identified. The classification of homogeneous operators in B-n(D) is completed using an explicit realization of these operators. We also show how the homogeneous operators in B-n(D) split into similarity classes. (C) 2011 Elsevier Inc. All rights reserved.