Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2 D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Reduced Look Ahead Orthogonal Matching Pursuit

Compressed Sensing (CS) is an elegant technique to acquire signals and reconstruct them efficiently by solving a system of under-determined linear equations. The excitement in this field stems from the fact that we can sample at a rate way below the Nyquist rate and still reconstruct the signal provided some conditions are met. Some of the popular greedy reconstruction algorithms are the Orthogonal Matching Pursuit (OMP), the Subspace Pursuit (SP) and the Look Ahead Orthogonal Matching Pursuit (LAOMP). The LAOMP performs better than the OMP. However, when compared to the SP and the OMP, the computational complexity of LAOMP is higher. We introduce a modified version of the LAOMP termed as Reduced Look Ahead Orthogonal Matching Pursuit (Reduced LAOMP). Reduced LAOMP uses prior information from the results of the OMP and the SP in the quest to speedup the look ahead strategy in the LAOMP. Monte Carlo simulations of this algorithm deliver promising results.

Mass spectrometry based characterization of Hb Beckman variant in a falsely elevated HbA(1c) sample

Glycated hemoglobin (HbA(1c)) is a `gold standard' biomarker for assessing the glycemic index of an individual. HbA(1c) is formed due to nonenzymatic glycosylation at N-terminal valine residue of the P-globin chain. Cation exchange based high performance liquid chromatography (CE HPLC) is mostly used to quantify HbA(1c), in blood sample. A few genetic variants of hemoglobin and post-translationally modified variants of hemoglobin interfere with CE HPLC-based quantification,. resulting in its false positive estimation. Using mass spectrometry, we analyzed a blood sample with abnormally high HbA(1c) (52.1%) in the CE HPLC method. The observed HbA(1c) did not corroborate the blood glucose level of the patient. A mass spectrometry based bottom up proteomics approach, intact globin chain mass analysis, and chemical modification of the proteolytic peptides identified the presence of Hb Beckman, a genetic variant of hemoglobin, in the experimental sample. A similar surface area to charge ratio between HbA(1c) and Hb Beckman might have resulted in the coelution of the variant with HbA(1c) in CE HPLC. Therefore, in the screening of diabetes mellitus through the estimation of HbA(1c), it is important to look for genetic variants of hemoglobin in samples that show abnormally high glycemic index, and HbA(1c) must be estimated using an alternative method. (C) 2015 Elsevier Inc. All rights reserved.

Efficient Low Complexity Power Allocation Policies for Wireless Communication Systems Guaranteeing QoS

We consider near-optimal policies for a single user transmitting on a wireless channel which minimize average queue length under average power constraint. The power is consumed in transmission of data only. We consider the case when the power used in transmission is a linear function of the data transmitted. The transmission channel may experience multipath fading. Later, we also extend these results to the multiuser case. We show that our policies can be used in a system with energy harvesting sources at the transmitter. Next we consider data users which require minimum rate guarantees. Finally we consider the system which has both data and real time users. Our policies have low computational complexity, closed form expression for mean delays and require only the mean arrival rate with no queue length information.

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Raman and infra-red microspectroscopy: towards quantitative evaluation for clinical research by ratiometric analysis

Biomolecular structure elucidation is one of the major techniques for studying the basic processes of life. These processes get modulated, hindered or altered due to various causes like diseases, which is why biomolecular analysis and imaging play an important role in diagnosis, treatment prognosis and monitoring. Vibrational spectroscopy (IR and Raman), which is a molecular bond specific technique, can assist the researcher in chemical structure interpretation. Based on the combination with microscopy, vibrational microspectroscopy is currently emerging as an important tool for biomedical research, with a spatial resolution at the cellular and sub-cellular level. These techniques offer various advantages, enabling label-free, biomolecular fingerprinting in the native state. However, the complexity involved in deciphering the required information from a spectrum hampered their entry into the clinic. Today with the advent of automated algorithms, vibrational microspectroscopy excels in the field of spectropathology. However, researchers should be aware of how quantification based on absolute band intensities may be affected by instrumental parameters, sample thickness, water content, substrate backgrounds and other possible artefacts. In this review these practical issues and their effects on the quantification of biomolecules will be discussed in detail. In many cases ratiometric analysis can help to circumvent these problems and enable the quantitative study of biological samples, including ratiometric imaging in 1D, 2D and 3D. We provide an extensive overview from the recent scientific literature on IR and Raman band ratios used for studying biological systems and for disease diagnosis and treatment prognosis.

Metallographic Sample Prepared by Ion Beam Etching

Ion beam etching technique was used to reveal the metallograhpic microstructure and interface morphology of electroplating chromium coating, in particular, whose substrate surface layer was treated in advance by laser quenching. Chemical etchings were, also conducted for comparison. The reveal microstructures were observed and analyzed by scanning electron microscopy. The results show that ion beam etching can reveal well the whole microstructures of composite coating-substrate materials.

Weibull modulus for diverse strength due to sample-specificity

By sample specificity it is meant that specimens with the same nominal material parameters and tested under the same environmental conditions may exhibit different behavior with diversified strength. Such an effect has been widely observed in the testing of material failure and is usually attributed to the heterogeneity of material at the mesoscopic level. The degree with which mesoscopic heterogeneity affects macroscopic failure is still not clear. Recently, the problem has been examined by making use of statistical ensemble evolution of dynamical system and the mesoscopic stress re-distribution model (SRD). Sample specificity was observed for non-global mean stress field models, such as the duster mean field model, stress concentration at tip of microdamage, etc. Certain heterogeneity of microdamage could be sensitive to particular SRD leading to domino type of coalescence. Such an effect could start from the microdamage heterogeneity and then be magnified to other scale levels. This trans-scale sensitivity is the origin of sample specificity. The sample specificity leads to a failure probability Phi (N) with a transitional region 0 < (N) < 1, so that globally stable and catastrophic modes could co-exist. It is found that the scatter in strength can fit the Weibull distribution very well. Hence, the Weibull modulus is indicative of sample specificity. Numerical results obtained from the SRD for different non-global mean stress fields show that Weibull modulus increases with increasing sample span and influence region of microdamage.