Singularity structure of third-order dynamical systems .2

The singularity structure of the solutions of a general third-order system, with polynomial right-hand sides of degree less than or equal to two, is studied about a movable singular point, An algorithm for transforming the given third-order system to a third-order Briot-Bouquet system is presented, The dominant behavior of a solution of the given system near a movable singularity is used to construct a transformation that changes the given system directly to a third-order Briot-Bouquet system. The results of Horn for the third-order Briot-Bouquet system are exploited to give the complete form of the series solutions of the given third-order system; convergence of these series in a deleted neighborhood of the singularity is ensured, This algorithm is used to study the singularity structure of the solutions of the Lorenz system, the Rikitake system, the three-wave interaction problem, the Rabinovich system, the Lotka-Volterra system, and the May-Leonard system for different sets of parameter values. The proposed approach goes far beyond the ARS algorithm.

The existence of homeomorphic subgraphs in chordal graphs

We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to K-n (n greater than or equal to 3), K-m,K-n (m,n greater than or equal to 2), and wheels W-r (r greater than or equal to 3). Using these results, we develop a simple linear time algorithm for testing planarity of chordal graphs. We also show how these results lead to simple polynomial time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs for some special classes of pattern graphs.

Distributed intrusion detection in the presence of correlated sensor readings: Signal-space and communication-complexity view-point

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space view-point is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces f(s) and f(g) and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating f(s) and f(g) is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication-complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. Extensions to the multi-party case is straightforward and is briefly discussed. The average case CC of the relevant greaterthan (CT) function is characterized within two bits. Under the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm. 2010 Elsevier B.V. All rights reserved.

The Herzog-Vasconcelos conjecture for affine semigroup rings

Let S be a simplicial affine semigroup such that its semigroup ring A = k[S] is Buchsbaum. We prove for such A the Herzog-Vasconcelos conjecture: If the A-module Der(k)A of k-linear derivations of A has finite projective dimension then it is free and hence A is a polynomial ring by the well known graded case of the Zariski-Lipman conjecture.

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

Cyclic Prefix Based Cooperative Sequential Spectrum Sensing Algorithms for OFDM

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user is using Orthogonal Frequency Division Multiplexing (OFDM). For this we develop cooperative sequential detection algorithms that use the autocorrelation property of cyclic prefix (CP) used in OFDM systems. We study the effect of timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. We also modify the detector to mitigate the effects of these impairments. The performance of the proposed algorithms is studied via simulations. We show that sequential detection can significantly improve the performance over a fixed sample size detector.

Training-Embedded, Single-Symbol ML-Decodable, Distributed STBCs for Relay Networks

Recently, a special class of complex designs called Training-Embedded Complex Orthogonal Designs (TE-CODs) has been introduced to construct single-symbol Maximum Likelihood decodable (SSD) distributed space-time block codes (DSTBCs) for two-hop wireless relay networks using the amplify and forward protocol. However, to implement DSTBCs from square TE-CODs, the overhead due to the transmission of training symbols becomes prohibitively large as the number of relays increase. In this paper, we propose TE-Coordinate Interleaved Orthogonal Designs (TE-CIODs) to construct SSD DSTBCs. Exploiting the block diagonal structure of TE-CIODs, we show that the overhead due to the transmission of training symbols to implement DSTBCs from TE-CIODs is smaller than that for TE-CODs. We also show that DSTBCs from TE-CIODs offer higher rate than those from TE-CODs for identical number of relays while maintaining the SSD and full-diversity properties.

BER Analysis of Uplink OFDMA in the Presence of Carrier Frequency and Timing Offsets on Rician Fading Channels

In uplink orthogonal frequency division multiple access (OFDMA), carrier frequency offsets (CFO) and/or timing offsets (TO) of other users with respect to a desired user can cause significant multiuser interference (MUI). In this paper, we derive an analytical bit error rate (BER) expression that quantify the degradation in BER due to the combined effect of both CFOs and TOs in uplink OFDMA on Rician fading channels. Such an analytical BER derivation for uplink OFDMA with CFOs and TOs on Rician fading channels has not been reported so far. For the case of non-zero CFOs/TOs, we obtain an approximate BER expression involving a single integral. Analytical and simulation BER results are shown to match very well.

Single real-symbol decodable, high-rate, distributed space-time block codes

A scheme to apply the rate-1 real orthogonal designs (RODs) in relay networks with single real-symbol decodability of the symbols at the destination for any arbitrary number of relays is proposed. In the case where the relays do not have any information about the channel gains from the source to themselves, the best known distributed space time block codes (DSTBCs) for k relays with single real-symbol decodability offer an overall rate of complex symbols per channel use. The scheme proposed in this paper offers an overall rate of 2/2+k complex symbol per channel use, which is independent of the number of relays. Furthermore, in the scenario where the relays have partial channel information in the form of channel phase knowledge, the best known DSTBCs with single real-symbol decodability offer an overall rate of 1/3 complex symbols per channel use. In this paper, making use of RODs, a scheme which achieves the same overall rate of 1/3 complex symbols per channel use but with a decoding delay that is 50 percent of that of the best known DSTBCs, is presented. Simulation results of the symbol error rate performance for 10 relays, which show the superiority of the proposed scheme over the best known DSTBC for 10 relays with single real-symbol decodability, are provided.

Improved large-MIMO detection based on damped belief propagation

In this paper, we consider the application of belief propagation (BP) to achieve near-optimal signal detection in large multiple-input multiple-output (MIMO) systems at low complexities. Large-MIMO architectures based on spatial multiplexing (V-BLAST) as well as non-orthogonal space-time block codes(STBC) from cyclic division algebra (CDA) are considered. We adopt graphical models based on Markov random fields (MRF) and factor graphs (FG). In the MRF based approach, we use pairwise compatibility functions although the graphical models of MIMO systems are fully/densely connected. In the FG approach, we employ a Gaussian approximation (GA) of the multi-antenna interference, which significantly reduces the complexity while achieving very good performance for large dimensions. We show that i) both MRF and FG based BP approaches exhibit large-system behavior, where increasingly closer to optimal performance is achieved with increasing number of dimensions, and ii) damping of messages/beliefs significantly improves the bit error performance.

Improved preprocessing methods for modulo scheduling algorithms

Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakness with existing methods is that a distinct automaton must be constructed for each combination of a reservation table and initiation interval. In this work, we present a different approach to model conflicts. We construct one automaton for each reservation table which acts as a compact encoding of all the conflict automata for this table, which can be recovered for use in modulo-scheduling. The basic premise of the construction is to move away from the Proebsting-Fraser model of conflict automaton to the Muller model of automaton modelling issue sequences. The latter turns out to be useful and efficient in this situation. Having constructed this automaton, we show how to improve the estimate of resource constrained initiation interval. Such a bound is always better than the average-use estimate. We show that our bound is safe: it is always lower than the true initiation interval. This use of the automaton is orthogonal to its use in modulo-scheduling. Once we generate the required information during pre-processing, we can compute the lower bound for a program without any further reference to the automaton.

Optimum design of a helicopter rotor for low vibration using aeroelastic analysis and response surface methods

An aeroelastic analysis based on finite elements in space and time is used to model the helicopter rotor in forward flight. The rotor blade is represented as an elastic cantilever beam undergoing flap and lag bending, elastic torsion and axial deformations. The objective of the improved design is to reduce vibratory loads at the rotor hub that are the main source of helicopter vibration. Constraints are imposed on aeroelastic stability, and move limits are imposed on the blade elastic stiffness design variables. Using the aeroelastic analysis, response surface approximations are constructed for the objective function (vibratory hub loads). It is found that second order polynomial response surfaces constructed using the central composite design of the theory of design of experiments adequately represents the aeroelastic model in the vicinity of the baseline design. Optimization results show a reduction in the objective function of about 30 per cent. A key accomplishment of this paper is the decoupling of the analysis problem and the optimization problems using response surface methods, which should encourage the use of optimization methods by the helicopter industry. (C) 2002 Elsevier Science Ltd. All rights reserved.

System Dy-Fe-O: thermodynamic properties of ternary oxides using Calvet calorimetry and solid-state electrochemical cell

The enthalpy increments and the standard molar Gibbs energies of formation-of DyFeO3(s) and Dy3Fe5O12(s) have been measured using a Calvet micro-calorimeter and a solid oxide galvanic cell, respectively. A co-operative phase transition, related to anti-ferromagnetic to paramagnetic transformation, is apparent. from the heat capacity data for DyFeO3 at similar to 648 K. A similar type of phase transition has been observed for Dy3Fe5O12 at similar to 560 K which is related to ferrimagnetic to paramagnetic transformation. Enthalpy increment data for DyFeO3(s) and Dy3Fe5O12(s), except in the vicinity of the second-order transition, can be represented by the following polynomial expressions:{H(0)m(T) - H(0)m(298.15 K)) (Jmol(-1)) (+/-1.1%) = -52754 + 142.9 x (T (K)) + 2.48 x 10(-3) x (T (K))(2) + 2.951 x 10(6) x (T (K))(-1); (298.15 less than or equal to T (K) less than or equal to 1000) for DyFeO3(s), and {H(0)m(T) - H(0)m(298.15 K)} (Jmol(-1)) (+/-1.2%) = -191048 + 545.0 x (T - (K)) + 2.0 x 10(-5) x (T (K))(2) + 8.513 x 10(6) x (T (K))(-1); (208.15 less than or equal to T (K) less than or equal to 1000)for Dy3Fe5O12(s). The reversible emfs of the solid-state electrochemical cells: (-)Pt/{DyFeO3(s) + Dy2O3(s) + Fe(s)}/YDT/CSZ//{Fe(s) + Fe0.95O(s)}/Pt(+) and (-)Pt/{Fe(s) + Fe0.95O(s)}//CSZ//{DyFeO3(s) + Dy3Fe5O12(s) + Fe3O4(s)}/Pt(+), were measured in the temperature range from 1021 to 1250 K and 1035 to 1250 K, respectively. The standard Gibbs energies of formation of solid DyFeO3 and Dy3Fe5O12 calculated by the least squares regression analysis of the data obtained in the present study, and data for Fe0.95O and Dy2O3 from the literature, are given by Delta(f)G(0)m(DyFeO3,s)(kJmol(-1))(+/-3.2)= -1339.9 + 0.2473 x (T(K)); (1021 less than or equal to T (K) less than or equal to 1548)and D(f)G(0)m(Dy3Fe5O12,s) (kJmol(-1)) (+/-3.5) = -4850.4 + 0.9846 x (T (K)); (1035 less than or equal to T (K) less than or equal to 1250) The uncertainty estimates for Delta(f)G(0)m include the standard deviation in the emf and uncertainty in the data taken from the literature. Based on the thermodynamic information, oxygen potential diagram and chemical potential diagrams for the system Dy-Fe-O were developed at 1250 K. (C) 2002 Editions scientifiques et medicales Elsevier SAS. All rights reserved.

The restriction mapping problem revisited

In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied techniques for restriction mapping. While double digest is NP-complete, there is no known polynomial-time algorithm for partial digest. Another disadvantage of the above techniques is that there can be multiple solutions for reconstruction. In this paper, we study a simple technique called labeled partial digest for restriction mapping. We give a fast polynomial time (O(n(2) log n) worst-case) algorithm for finding all the n sites of a DNA molecule using this technique. An important advantage of the algorithm is the unique reconstruction of the DNA molecule from the digest. The technique is also robust in handling errors in fragment lengths which arises in the laboratory. We give a robust O(n(4)) worst-case algorithm that can provably tolerate an absolute error of O(Delta/n) (where Delta is the minimum inter-site distance), while giving a unique reconstruction. We test our theoretical results by simulating the performance of the algorithm on a real DNA molecule. Motivated by the similarity to the labeled partial digest problem, we address a related problem of interest-the de novo peptide sequencing problem (ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 389-398), which arises in the reconstruction of the peptide sequence of a protein molecule. We give a simple and efficient algorithm for the problem without using dynamic programming. The algorithm runs in time O(k log k), where k is the number of ions and is an improvement over the algorithm in Chen et al. (C) 2002 Elsevier Science (USA). All rights reserved.

Thermodynamic studies on NdFeO3(s)

The enthalpy increments and the standard molar Gibbs energy of formation of NdFeO3(s) have been measured using a hightemperature Calvet microcalorimeter and a solid oxide galvanic cell, respectively. A lambda-type transition, related to magnetic order-disorder transformation (antiferromagnetic to paramagnetic), is apparent from the heat capacity data at similar to 687 K. Enthalpy increments, except in the vicinity of transition, can be represented by a polynomial expression: {Hdegrees(m)(T)-Hdegrees(m) (298.15 K)} /J(.)mol(-1) (+/- 0.7%)=-53625.6+146.0(T/K) +1.150 X 10(-4)(T/K)(2) +3.007 x 10(6)(T/K)(-1); (298.15 less than or equal to T/K less than or equal to 1000). The heat capacity, the first differential of {Hdegrees(m)(T)-Hdegrees(m)(298.15 K)}with respect to temperature, is given by Cdegrees(pm)/J(.)K(-1.)mol(-1)=146.0+ 2.30x10(-4) (T/K) - 3.007 X 10(6)(T/K)(-2). The reversible emf's of the cell, (-) Pt/{NdFeO3(s) +Nd2O3(s)+Fe(s)}//YDT/CSZ// Fe(s)+'FeO'(s)}/Pt(+), were measured in the temperature range from 1004 to 1208 K. It can be represented within experimental error by a linear equation: E/V=(0.1418 +/- 0.0003)-(3.890 +/- 0.023) x 10(-5)(T/K). The Gibbs energy of formation of solid NdFeO, calculated by the least-squares regression analysis of the data obtained in the present study, and data for Fe0.95O and Nd2O3 from the literature, is given by Delta(f)Gdegrees(m)(NdFeO3 s)/kJ (.) mol(-1)( +/- 2.0)=1345.9+0.2542(T/K); (1000 less than or equal to T/K less than or equal to 1650). The error in Delta(f)Gdegrees(m)(NdFeO3, s, T) includes the standard deviation in emf and the uncertainty in the data taken from the literature. Values of Delta(f)Hdegrees(m)(NdFeO3, s, 298.15 K) and Sdegrees(m) (NdFeO3 s, 298.15 K) calculated by the second law method are - 1362.5 (+/-6) kJ (.) mol(-1) and 123.9 (+/-2.5) J (.) K-1 (.) mol(-1), respectively. Based on the thermodynamic information, an oxygen potential diagram for the system Nd-Fe-O was developed at 1350 K. (C) 2002 Elsevier Science (USA).