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.

Compiler-assisted instruction decoder energy optimization for clustered VLIW architectures

Traditionally, an instruction decoder is designed as a monolithic structure that inhibit the leakage energy optimization. In this paper, we consider a split instruction decoder that enable the leakage energy optimization. We also propose a compiler scheduling algorithm that exploits instruction slack to increase the simultaneous active and idle duration in instruction decoder. The proposed compiler-assisted scheme obtains a further 14.5% reduction of energy consumption of instruction decoder over a hardware-only scheme for a VLIW architecture. The benefits are 17.3% and 18.7% in the context of a 2-clustered and a 4-clustered VLIW architecture respectively.

Cluster based training for scaling non-linear support vector machines

Support Vector Machines(SVMs) are hyperplane classifiers defined in a kernel induced feature space. The data size dependent training time complexity of SVMs usually prohibits its use in applications involving more than a few thousands of data points. In this paper we propose a novel kernel based incremental data clustering approach and its use for scaling Non-linear Support Vector Machines to handle large data sets. The clustering method introduced can find cluster abstractions of the training data in a kernel induced feature space. These cluster abstractions are then used for selective sampling based training of Support Vector Machines to reduce the training time without compromising the generalization performance. Experiments done with real world datasets show that this approach gives good generalization performance at reasonable computational expense.

Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.

Four group decodable differential scaled unitary linear space-time codes

Differential Unitary Space-Time Block codes (STBCs) offer a means to communicate on the Multiple Input Multiple Output (MIMO) channel without the need for channel knowledge at both the transmitter and the receiver. Recently Yuen-Guan-Tjhung have proposed Single-Symbol-Decodable Differential Space-Time Modulation based on Quasi-Orthogonal Designs (QODs) by replacing the original unitary criterion by a scaled unitary criterion. These codes were also shown to perform better than differential unitary STBCs from Orthogonal Designs (ODs). However the rate (as measured in complex symbols per channel use) of the codes of Yuen-Guan-Tjhung decay as the number of transmit antennas increase. In this paper, a new class of differential scaled unitary STBCs for all even number of transmit antennas is proposed. These codes have a rate of 1 complex symbols per channel use, achieve full diversity and moreover they are four-group decodable, i.e., the set of real symbols can be partitioned into four groups and decoding can be done for the symbols in each group separately. Explicit construction of multidimensional signal sets that yield full diversity for this new class of codes is also given.

Bond-order wave phase, spin solitons, and thermodynamics of a frustrated linear spin-1/2 Heisenberg antiferromagnet

The linear spin-1/2 Heisenberg antiferromagnet with exchanges J(1) and J(2) between first and second neighbors has a bond-order wave (BOW) phase that starts at the fluid-dimer transition at J(2)/J(1)=0.2411 and is particularly simple at J(2)/J(1)=1/2. The BOW phase has a doubly degenerate singlet ground state, broken inversion symmetry, and a finite-energy gap E-m to the lowest-triplet state. The interval 0.4 < J(2)/J(1) < 1.0 has large E-m and small finite-size corrections. Exact solutions are presented up to N = 28 spins with either periodic or open boundary conditions and for thermodynamics up to N = 18. The elementary excitations of the BOW phase with large E-m are topological spin-1/2 solitons that separate BOWs with opposite phase in a regular array of spins. The molar spin susceptibility chi(M)(T) is exponentially small for T << E-m and increases nearly linearly with T to a broad maximum. J(1) and J(2) spin chains approximate the magnetic properties of the BOW phase of Hubbard-type models and provide a starting point for modeling alkali-tetracyanoquinodimethane salts.

Reactive Pulsed Laser Deposition of titanium nitride thin film: Optimization of process parameters using Secondary Ion Mass Spectrometry

Reactive Pulsed Laser Deposition is a single step process wherein the ablated elemental metal reacts with a low pressure ambient gas to form a compound. We report here a Secondary Ion Mass Spectrometry based analytical methodology to conduct minimum number of experiments to arrive at optimal process parameters to obtain high quality TiN thin film. Quality of these films was confirmed by electron microscopic analysis. This methodology can be extended for optimization of other process parameters and materials. (C) 2009 Elsevier B.V. All rights reserved.

On the PAPR of cosets of linear codes

Employing an error control code is one of the techniques to reduce the Peak-to-Average Power Ratio (PAPR) in a Orthogonal Frequency Division Multiplexing system, a well known class of such codes being the cosets of Reed-Muller codes. In this paper, we consider the class of such coset-codes of arbitrary linear codes and present a method of doubling the size of such a code without increasing the PAPR, by combining two such binary coset-codes. We identify the conditions under which we can employ this doubling more than once with no marginal increase in the PAPR value. Given a PAPR and length, our method has enabled to get the best coset-code (in terms of the size). Also, we show that the PAPR information of the coset-codes of the extended codes is obtainable from the PAPR of the corresponding coset-codes of the parent code. We have also shown a special type of lengthening is useful in PAPR studies.

Optimal resource allocation in conflicts with the Lanchester linear law (2,1) model

This paper presents a detailed analysis of a model for military conflicts where the defending forces have to determine an optimal partitioning of available resources to counter attacks from an adversary in two different fronts in an area fire situation. Lanchester linear law attrition model is used to develop the dynamical equations governing the variation in force strength. Here we address a static resource allocation problem namely, Time-Zero-Allocation (TZA) where the resource allocation is done only at the initial time. Numerical examples are given to support the analytical results.

Multi-Tone Testing of Linear and Nonlinear Analog Circuits using Polynomial Coefficients

A method of testing for parametric faults of analog circuits based on a polynomial representation of fault-free function of the circuit is presented. The response of the circuit under test (CUT) is estimated as a polynomial in the applied input voltage at relevant frequencies in addition to DC. Classification or Cur is based on a comparison of the estimated polynomial coefficients with those of the fault free circuit. This testing method requires no design for test hardware as might be added to the circuit fly some other methods. The proposed method is illustrated for a benchmark elliptic filter. It is shown to uncover several parametric faults causing deviations as small as 5% from the nominal values.

Simultaneous material selection and geometry design of statically determinate trusses using continuous optimization

In this work, we explore simultaneous geometry design and material selection for statically determinate trusses by posing it as a continuous optimization problem. The underlying principles of our approach are structural optimization and Ashby’s procedure for material selection from a database. For simplicity and ease of initial implementation, only static loads are considered in this work with the intent of maximum stiffness, minimum weight/cost, and safety against failure. Safety of tensile and compression members in the truss is treated differently to prevent yield and buckling failures, respectively. Geometry variables such as lengths and orientations of members are taken to be the design variables in an assumed layout. Areas of cross-section of the members are determined to satisfy the failure constraints in each member. Along the lines of Ashby’s material indices, a new design index is derived for trusses. The design index helps in choosing the most suitable material for any geometry of the truss. Using the design index, both the design space and the material database are searched simultaneously using gradient-based optimization algorithms. The important feature of our approach is that the formulated optimization problem is continuous, although the material selection from a database is an inherently discrete problem. A few illustrative examples are included. It is observed that the method is capable of determining the optimal topology in addition to optimal geometry when the assumed layout contains more links than are necessary for optimality.

Target reliability based design optimization of anchored cantilever sheet pile walls

In this study, the stability of anchored cantilever sheet pile wall in sandy soils is investigated using reliability analysis. Targeted stability is formulated as an optimization problem in the framework of an inverse first order reliability method. A sensitivity analysis is conducted to investigate the effect of parameters influencing the stability of sheet pile wall. Backfill soil properties, soil - steel pile interface friction angle, depth of the water table from the top of the sheet pile wall, total depth of embedment below the dredge line, yield strength of steel, section modulus of steel sheet pile, and anchor pull are all treated as random variables. The sheet pile wall system is modeled as a series of failure mode combination. Penetration depth, anchor pull, and section modulus are calculated for various target component and system reliability indices based on three limit states. These are: rotational failure about the position of the anchor rod, expressed in terms of moment ratio; sliding failure mode, expressed in terms of force ratio; and flexural failure of the steel sheet pile wall, expressed in terms of the section modulus ratio. An attempt is made to propose reliability based design charts considering the failure criteria as well as the variability in the parameters. The results of the study are compared with studies in the literature.

Accuracy of absorbed dose in external photon beam radiotherapy : what level is sufficient and how to approach it?

Radiation therapy (RT) plays currently significant role in curative treatments of several cancers. External beam RT is carried out mostly by using megavoltage beams of linear accelerators. Tumor eradication and normal tissue complications correlate to dose absorbed in tissues. Normally this dependence is steep and it is crucial that actual dose within patient accurately correspond to the planned dose. All factors in a RT procedure contain uncertainties requiring strict quality assurance. From hospital physicist´s point of a view, technical quality control (QC), dose calculations and methods for verification of correct treatment location are the most important subjects. Most important factor in technical QC is the verification that radiation production of an accelerator, called output, is within narrow acceptable limits. The output measurements are carried out according to a locally chosen dosimetric QC program defining measurement time interval and action levels. Dose calculation algorithms need to be configured for the accelerators by using measured beam data. The uncertainty of such data sets limits for best achievable calculation accuracy. All these dosimetric measurements require good experience, are workful, take up resources needed for treatments and are prone to several random and systematic sources of errors. Appropriate verification of treatment location is more important in intensity modulated radiation therapy (IMRT) than in conventional RT. This is due to steep dose gradients produced within or close to healthy tissues locating only a few millimetres from the targeted volume. The thesis was concentrated in investigation of the quality of dosimetric measurements, the efficacy of dosimetric QC programs, the verification of measured beam data and the effect of positional errors on the dose received by the major salivary glands in head and neck IMRT. A method was developed for the estimation of the effect of the use of different dosimetric QC programs on the overall uncertainty of dose. Data were provided to facilitate the choice of a sufficient QC program. The method takes into account local output stability and reproducibility of the dosimetric QC measurements. A method based on the model fitting of the results of the QC measurements was proposed for the estimation of both of these factors. The reduction of random measurement errors and optimization of QC procedure were also investigated. A method and suggestions were presented for these purposes. The accuracy of beam data was evaluated in Finnish RT centres. Sufficient accuracy level was estimated for the beam data. A method based on the use of reference beam data was developed for the QC of beam data. Dosimetric and geometric accuracy requirements were evaluated for head and neck IMRT when function of the major salivary glands is intended to be spared. These criteria are based on the dose response obtained for the glands. Random measurement errors could be reduced enabling lowering of action levels and prolongation of measurement time interval from 1 month to even 6 months simultaneously maintaining dose accuracy. The combined effect of the proposed methods, suggestions and criteria was found to facilitate the avoidance of maximal dose errors of up to even about 8 %. In addition, their use may make the strictest recommended overall dose accuracy level of 3 % (1SD) achievable.