Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

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.

On the duality between rate and power optimizations

Sequence design problems are considered in this paper. The problem of sum power minimization in a spread spectrum system can be reduced to the problem of sum capacity maximization, and vice versa. A solution to one of the problems yields a solution to the other. Subsequently, conceptually simple sequence design algorithms known to hold for the white-noise case are extended to the colored noise case. The algorithms yield an upper bound of 2N - L on the number of sequences where N is the processing gain and L the number of non-interfering subsets of users. If some users (at most N - 1) are allowed to signal along a limited number of multiple dimensions, then N orthogonal sequences suffice.

Boundary value problems for third-order nonlinear ordinary differential equations

In this paper, we describe how to analyze boundary value problems for third-order nonlinear ordinary differential equations over an infinite interval. Several physical problems of interest are governed by such systems. The seminumerical schemes described here offer some advantages over solutions obtained by using traditional methods such as finite differences, shooting method, etc. These techniques also reveal the analytic structure of the solution function. For illustrative purposes, several physical problems, mainly drawn from fluid mechanics, are considered; they clearly demonstrate the efficiency of the techniques presented here.

On Guo and Nixon's Criterion for Feature Subset Selection: Assumptions, Implications,and Alternative Options

Guo and Nixon proposed a feature selection method based on maximizing I(x; Y),the multidimensional mutual information between feature vector x and class variable Y. Because computing I(x; Y) can be difficult in practice, Guo and Nixon proposed an approximation of I(x; Y) as the criterion for feature selection. We show that Guo and Nixon's criterion originates from approximating the joint probability distributions in I(x; Y) by second-order product distributions. We remark on the limitations of the approximation and discuss computationally attractive alternatives to compute I(x; Y).

Boundary value problems for third-order nonlinear ordinary differential equations

In this paper, we describe how to analyze boundary value problems for third-order nonlinear ordinary differential equations over an infinite interval. Several physical problems of interest are governed by such systems. The seminumerical schemes described here offer some advantages over solutions obtained by using traditional methods such as finite differences, shooting method, etc. These techniques also reveal the analytic structure of the solution function. For illustrative purposes, several physical problems, mainly drawn from fluid mechanics, are considered; they clearly demonstrate the efficiency of the techniques presented here.

On the ignition and extinction problems in forced convection systems

In this paper the problem of ignition and extinction has been formulated for the flow of a compressible fluid with Prandtl and Schmidt numbers taken as unity. In particular, the problems of (i) a jet impinging on a wall of combustible material and (ii) the opposed jet diffusion flame have been studied. In the wall jet case, three approximations in the momentum equation namely, (i) potential flow, (ii) viscous flow, (ii) viscous incompressible with k = 1 and (iii) Lees' approximation (taking pressure gradient terms zero) are studied. It is shown that the predictions of the mass flow rates at extinction are not very sensitive to the approximations made in the momentum equation. The effects of varying the wall temperature in the case (i) and the jet temperature in the case (ii) on the extinction speeds have been studied. The effects of varying the activation energy and the free stream oxidant concentration in case (ii), have also been investigated.

A semi-experimental approach to plane problems in elasticity

A semi-experimental approach to solve two-dimensional problems in elasticity is given. The method has been applied to two problems, (i) a square deep beam, and (ii) a bridge pier with a sloping boundary. For the first problem sufficient analytical results are available and hence the accuracy of the method can be verified. Then the method has been extended to the second problem for which sufficient results are not available.

Estimation of the critical viscous sublayer in heat transfer problems

Imagining a disturbance made on a compressible boundary layer with the help of a heat source, the critical viscous sublayer, through which the skin friction at any point on a surface is connected with the heat transferred from a heated element embedded in it, has been estimated. Under similar conditions of external flow (Ray1)) the ratio of the critical viscous sublayer to the undisturbed boundary layer thickness is about one-tenth in the laminar case and one hundredth in the turbulent case. These results are similar to those (cf.1)) found in shock wave boundary layer interaction problems.

A particle filtering approach for structural system identification in vehicle–structure interaction problems

The problem of identification of parameters of a beam-moving oscillator system based on measurement of time histories of beam strains and displacements is considered. The governing equations of motion here have time varying coefficients. The parameters to be identified are however time invariant and consist of mass, stiffness and damping characteristics of the beam and oscillator subsystems. A strategy based on dynamic state estimation method, that employs particle filtering algorithms, is proposed to tackle the identification problem. The method can take into account measurement noise, guideway unevenness, spatially incomplete measurements, finite element models for supporting structure and moving vehicle, and imperfections in the formulation of the mathematical models. Numerical illustrations based on synthetic data on beam-oscillator system are presented to demonstrate the satisfactory performance of the proposed procedure.

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.

High-Rate,2-Group ML-Decodable STBCs for 2(m) Transmit Antennas

A Space-Time Block Code (STBC) in K-variables is said to be g-Group ML-Decodable (GMLD) if its Maximum-Likelihood (ML) decoding metric can be written as a sum of g independent terms, with each term being a function of a subset of the K variables. In this paper, a construction method to obtain high-rate, 2-GMLD STBCs for 2(m) transmit antennas, m > 1, is presented. The rate of the STBC obtained for 2(m) transmit antennas is 2(m-2) + 1/2(m), complex symbols per channel use. The design method is illustrated for the case of 4 and 8 transmit antennas. The code obtained for 4 transmit antennas is equivalent to the rate-5/4 Quasi-Orthogonal design (QOD) proposed by Yuen, Guan and Tjung.