Exploiting the Structure of the Constraint Graph for Efficient Points-to Analysis

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow-insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2x faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

Infinite push: a new support vector ranking algorithm that directly optimizes accuracy at the absolute top of the list

Ranking problems have become increasingly important in machine learning and data mining in recent years, with applications ranging from information retrieval and recommender systems to computational biology and drug discovery. In this paper, we describe a new ranking algorithm that directly maximizes the number of relevant objects retrieved at the absolute top of the list. The algorithm is a support vector style algorithm, but due to the different objective, it no longer leads to a quadratic programming problem. Instead, the dual optimization problem involves l1, ∞ constraints; we solve this dual problem using the recent l1, ∞ projection method of Quattoni et al (2009). Our algorithm can be viewed as an l∞-norm extreme of the lp-norm based algorithm of Rudin (2009) (albeit in a support vector setting rather than a boosting setting); thus we refer to the algorithm as the ‘Infinite Push’. Experiments on real-world data sets confirm the algorithm’s focus on accuracy at the absolute top of the list.

RNA-dependent RNA polymerase of Japanese encephalitis virus binds the initiator nucleotide GTP to form a mechanistically important pre-initiation state

Flaviviral RNA-dependent RNA polymerases (RdRps) initiate replication of the single-stranded RNA genome in the absence of a primer. The template sequence 5'-CU-3' at the 3'-end of the flaviviral genome is highly conserved. Surprisingly, flaviviral RdRps require high concentrations of the second incoming nucleotide GTP to catalyze de novo template-dependent RNA synthesis. We show that GTP stimulates de novo RNA synthesis by RdRp from Japanese encephalitis virus (jRdRp) also. Crystal structures of jRdRp complexed with GTP and ATP provide a basis for specific recognition of GTP. Comparison of the jRdRp(GTP) structure with other viral RdRp-GTP structures shows that GTP binds jRdRp in a novel conformation. Apo-jRdRp structure suggests that the conserved motif F of jRdRp occupies multiple conformations in absence of GTP. Motif F becomes ordered on GTP binding and occludes the nucleotide triphosphate entry tunnel. Mutational analysis of key residues that interact with GTP evinces that the jRdRp(GTP) structure represents a novel pre-initiation state. Also, binding studies show that GTP binding reduces affinity of RdRp for RNA, but the presence of the catalytic Mn2+ ion abolishes this inhibition. Collectively, these observations suggest that the observed pre-initiation state may serve as a check-point to prevent erroneous template-independent RNA synthesis by jRdRp during initiation.

Universal Conductance Fluctuations as a direct probe to valley coherence and universality class of disordered graphene

We demonstrate that the universal conductance fluctuations (UCF) can be used as a direct probe to study the valley quantum states in disordered graphene. The UCF magnitude in graphene is suppressed by a factor of four at high carrier densities where the short-range disorder essentially breaks the valley degeneracy of the K and K' valleys, leading to a density dependent crossover of symmetry class from symplectic near the Dirac point to orthogonal at high densities.

Growing Length Scales and Their Relation to Timescales in Glass-Forming Liquids

The question of whether the dramatic slowing down of the dynamics of glass-forming liquids near the structural glass transition is caused by the growth of one or more correlation lengths has received much attention in recent years. Several proposals have been made for both static and dynamic length scales that may be responsible for the growth of timescales as the glass transition is approached. These proposals are critically examined with emphasis on the dynamic length scale associated with spatial heterogeneity of local dynamics and the static point-to-set or mosaic length scale of the random first order transition theory of equilibrium glass transition. Available results for these length scales, obtained mostly from simulations, are summarized, and the relation of the growth of timescales near the glass transition with the growth of these length scales is examined. Some of the outstanding questions about length scales in glass-forming liquids are discussed, and studies in which these questions may be addressed are suggested.

Implication of a sigma-Methane Complex en Route to Elimination of Methane from a Ruthenium Complex: An Experimental and Theoretical Investigation

The five-coordinated 16-electron complex Ru(Me)(dppe)(2)]OTf] (3) undergoes methane elimination at room temperature to afford the ortho-metalated species (dppe){(C6H5)(C6H4)PCH2CH2P(C6H5)(2)}Ru]OTf] (7). Methane elimination, monitored using NMR spectroscopy, revealed no intermediate throughout the reaction. The NOE between Ru-Me protons and ortho phenyl protons and an agostic interaction trans to the methyl group were found in complex 3 by NMR spectroscopy, which form the basis for three plausible pathways for methane elimination and ortho metalation: pathway I (through spatial interaction), pathway II (through oxidative addition and reductive elimination), and pathway III (through agostic interaction). Methane elimination from complex 3 via pathway I was discounted, since it involves interactions through space and not through bonds. Moreover, the calculated energy barrier for the pathway I transition state was quite high (71.3 kcal/mol), which also indicates that this pathway is very unlikely. Furthermore, no spectroscopic evidence for oxidatively added seven-coordinated Ru(IV) species was found and the computed energy barrier of the transition state for pathway II was moderately high (41.1 kcal/mol), which suggests that this cannot be the right pathway for methane elimination and ortho-metalation of complex 3. On the other hand, indirect evidence in the form of chemical reactions point to the most plausible pathway for methane elimination, pathway III, via the intermediacy of a sigma-CH4 complex that could not be found spectroscopically. DFT calculations at several levels on this pathway showed an initial low-barrier rearrangement through TS1 to a square-pyramidal intermediate wherein methyl and agostic C-H are cis to each other. Migration of hydrogen from agostic C-H and elimination of methane proceed through the transition state TS2, which retains a weak metal-H bonding through most parts of the reaction coordinate. Upon comparison of all three pathways, pathway III was found to be the most likely for methane elimination and ortho-metalation of complex 3.

Novel Biobjective Clustering (BiGC) Based on Cooperative Game Theory

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

Improved recognition of aged Kannada documents by effective segmentation of merged characters

In optical character recognition of very old books, the recognition accuracy drops mainly due to the merging or breaking of characters. In this paper, we propose the first algorithm to segment merged Kannada characters by using a hypothesis to select the positions to be cut. This method searches for the best possible positions to segment, by taking into account the support vector machine classifier's recognition score and the validity of the aspect ratio (width to height ratio) of the segments between every pair of cut positions. The hypothesis to select the cut position is based on the fact that a concave surface exists above and below the touching portion. These concave surfaces are noted down by tracing the valleys in the top contour of the image and similarly doing it for the image rotated upside-down. The cut positions are then derived as closely matching valleys of the original and the rotated images. Our proposed segmentation algorithm works well for different font styles, shapes and sizes better than the existing vertical projection profile based segmentation. The proposed algorithm has been tested on 1125 different word images, each containing multiple merged characters, from an old Kannada book and 89.6% correct segmentation is achieved and the character recognition accuracy of merged words is 91.2%. A few points of merge are still missed due to the absence of a matched valley due to the specific shapes of the particular characters meeting at the merges.

Response Dynamics of Recirculation Structures in Coaxial Nonpremixed Swirl-Stabilized Flames Subjected to Acoustic Forcing

This paper reports the time-mean and phase-locked response of nonreacting as well as reacting flow field in a coaxial swirling jet/flame (nonpremixed). Two distinct swirl intensities plus two different central pipe flow rates at each swirl setting are investigated. The maximum response is observed at the 105 Hz mode in the range of excitation frequencies (0-315 Hz). The flow/flame exhibited minimal response beyond 300 Hz. It is seen that the aspect ratio change of inner recirculation zone (IRZ) under nonreacting conditions (at responsive modes) manifests as a corresponding increase in the time-mean flame aspect ratio. This is corroborated by similar to 25% decrease in the IRZ transverse width in both flame and cold flow states. In addition, 105 Hz excited states are found to shed high energy regions (eddies) asymmetrically when compared to dormant 315 Hz pulsing frequency. The kinetic energy (KE) of the flow field is subsequently reduced due to acoustic excitation and a corresponding increase (similar to O (1)) in fluctuation intensity is witnessed. The lower swirl intensity case is found to be more responsive than the high swirl case as in the former flow state the resistance offered by IRZ to incoming acoustic perturbations is lower due to inherently low inertia. Next, the phase-locked analysis of flow and flame structure is employed to further investigate the phase dependence of flow/flame response. It is found that the asymmetric shifting of IRZ mainly results at 270 deg acoustic forcing. The 90 deg phase angle forcing is observed to convect the IRZ farther downstream in both swirl cases as compared to other phase angles. The present work aims primarily at providing a fluid dynamic view point to the observed nonpremixed flame response without considering the confinement effects.

快速Delaunay逐点插入网格生成算法

对插入形心的Delaunay逐点插入算法,提出按单元可插度分组的双向链表组数据结构,避免了对最大可插度单元的搜索。采用了邻接单元搜索、双向链表存储、随机方向搜索、邻接旋转、几何量继承等技术,使算法的计算时间与生成单元数近似呈线性关系,时间复杂度达到O(N1.05),N为生成单元数。算例表明,在一台AMD Athlon3200+(主频2.0 GHz)PC上,该算法的四面体单元生成速度达50 000个/s以上。

On Best Proximity Point Theorems and Fixed Point Theorems for p-Cyclic Hybrid Self-Mappings in Banach Spaces

This paper relies on the study of fixed points and best proximity points of a class of so-called generalized point-dependent (K-Lambda)hybrid p-cyclic self-mappings relative to a Bregman distance Df, associated with a Gâteaux differentiable proper strictly convex function f in a smooth Banach space, where the real functions Lambda and K quantify the point-to-point hybrid and nonexpansive (or contractive) characteristics of the Bregman distance for points associated with the iterations through the cyclic self-mapping.Weak convergence results to weak cluster points are obtained for certain average sequences constructed with the iterates of the cyclic hybrid self-mappings.

Why are we fat? Discussions on the socioeconomic dimensions and responses to obesity

This paper draws together contributions to a scientific table discussion on obesity at the European Science Open Forum 2008 which took place in Barcelona, Spain. Socioeconomic dimensions of global obesity, including those factors promoting it, those surrounding the social perceptions of obesity and those related to integral public health solutions, are discussed. It argues that although scientific accounts of obesity point to large-scale changes in dietary and physical environments, media representations of obesity, which context public policy, pre-eminently follow individualistic models of explanation. While the debate at the forum brought together a diversity of views, all the contributors agreed that this was a global issue requiring an equally global response. Furthermore, an integrated ecological model of obesity proposes that to be effective, policy will need to address not only human health but also planetary health, and that therefore, public health and environmental policies coincide.

Transceiver designs and analysis for LTI, LTV and broadcast channels - new matrix decompositions and majorization theory

Signal processing techniques play important roles in the design of digital communication systems. These include information manipulation, transmitter signal processing, channel estimation, channel equalization and receiver signal processing. By interacting with communication theory and system implementing technologies, signal processing specialists develop efficient schemes for various communication problems by wisely exploiting various mathematical tools such as analysis, probability theory, matrix theory, optimization theory, and many others. In recent years, researchers realized that multiple-input multiple-output (MIMO) channel models are applicable to a wide range of different physical communications channels. Using the elegant matrix-vector notations, many MIMO transceiver (including the precoder and equalizer) design problems can be solved by matrix and optimization theory. Furthermore, the researchers showed that the majorization theory and matrix decompositions, such as singular value decomposition (SVD), geometric mean decomposition (GMD) and generalized triangular decomposition (GTD), provide unified frameworks for solving many of the point-to-point MIMO transceiver design problems.

In this thesis, we consider the transceiver design problems for linear time invariant (LTI) flat MIMO channels, linear time-varying narrowband MIMO channels, flat MIMO broadcast channels, and doubly selective scalar channels. Additionally, the channel estimation problem is also considered. The main contributions of this dissertation are the development of new matrix decompositions, and the uses of the matrix decompositions and majorization theory toward the practical transmit-receive scheme designs for transceiver optimization problems. Elegant solutions are obtained, novel transceiver structures are developed, ingenious algorithms are proposed, and performance analyses are derived.

The first part of the thesis focuses on transceiver design with LTI flat MIMO channels. We propose a novel matrix decomposition which decomposes a complex matrix as a product of several sets of semi-unitary matrices and upper triangular matrices in an iterative manner. The complexity of the new decomposition, generalized geometric mean decomposition (GGMD), is always less than or equal to that of geometric mean decomposition (GMD). The optimal GGMD parameters which yield the minimal complexity are derived. Based on the channel state information (CSI) at both the transmitter (CSIT) and receiver (CSIR), GGMD is used to design a butterfly structured decision feedback equalizer (DFE) MIMO transceiver which achieves the minimum average mean square error (MSE) under the total transmit power constraint. A novel iterative receiving detection algorithm for the specific receiver is also proposed. For the application to cyclic prefix (CP) systems in which the SVD of the equivalent channel matrix can be easily computed, the proposed GGMD transceiver has K/log_2(K) times complexity advantage over the GMD transceiver, where K is the number of data symbols per data block and is a power of 2. The performance analysis shows that the GGMD DFE transceiver can convert a MIMO channel into a set of parallel subchannels with the same bias and signal to interference plus noise ratios (SINRs). Hence, the average bit rate error (BER) is automatically minimized without the need for bit allocation. Moreover, the proposed transceiver can achieve the channel capacity simply by applying independent scalar Gaussian codes of the same rate at subchannels.

In the second part of the thesis, we focus on MIMO transceiver design for slowly time-varying MIMO channels with zero-forcing or MMSE criterion. Even though the GGMD/GMD DFE transceivers work for slowly time-varying MIMO channels by exploiting the instantaneous CSI at both ends, their performance is by no means optimal since the temporal diversity of the time-varying channels is not exploited. Based on the GTD, we develop space-time GTD (ST-GTD) for the decomposition of linear time-varying flat MIMO channels. Under the assumption that CSIT, CSIR and channel prediction are available, by using the proposed ST-GTD, we develop space-time geometric mean decomposition (ST-GMD) DFE transceivers under the zero-forcing or MMSE criterion. Under perfect channel prediction, the new system minimizes both the average MSE at the detector in each space-time (ST) block (which consists of several coherence blocks), and the average per ST-block BER in the moderate high SNR region. Moreover, the ST-GMD DFE transceiver designed under an MMSE criterion maximizes Gaussian mutual information over the equivalent channel seen by each ST-block. In general, the newly proposed transceivers perform better than the GGMD-based systems since the super-imposed temporal precoder is able to exploit the temporal diversity of time-varying channels. For practical applications, a novel ST-GTD based system which does not require channel prediction but shares the same asymptotic BER performance with the ST-GMD DFE transceiver is also proposed.

The third part of the thesis considers two quality of service (QoS) transceiver design problems for flat MIMO broadcast channels. The first one is the power minimization problem (min-power) with a total bitrate constraint and per-stream BER constraints. The second problem is the rate maximization problem (max-rate) with a total transmit power constraint and per-stream BER constraints. Exploiting a particular class of joint triangularization (JT), we are able to jointly optimize the bit allocation and the broadcast DFE transceiver for the min-power and max-rate problems. The resulting optimal designs are called the minimum power JT broadcast DFE transceiver (MPJT) and maximum rate JT broadcast DFE transceiver (MRJT), respectively. In addition to the optimal designs, two suboptimal designs based on QR decomposition are proposed. They are realizable for arbitrary number of users.

Finally, we investigate the design of a discrete Fourier transform (DFT) modulated filterbank transceiver (DFT-FBT) with LTV scalar channels. For both cases with known LTV channels and unknown wide sense stationary uncorrelated scattering (WSSUS) statistical channels, we show how to optimize the transmitting and receiving prototypes of a DFT-FBT such that the SINR at the receiver is maximized. Also, a novel pilot-aided subspace channel estimation algorithm is proposed for the orthogonal frequency division multiplexing (OFDM) systems with quasi-stationary multi-path Rayleigh fading channels. Using the concept of a difference co-array, the new technique can construct M^2 co-pilots from M physical pilot tones with alternating pilot placement. Subspace methods, such as MUSIC and ESPRIT, can be used to estimate the multipath delays and the number of identifiable paths is up to O(M^2), theoretically. With the delay information, a MMSE estimator for frequency response is derived. It is shown through simulations that the proposed method outperforms the conventional subspace channel estimator when the number of multipaths is greater than or equal to the number of physical pilots minus one.

The brine and gas content of sea ice with attention to low salinities and high temperatures

Based on the well known sea ice phase diagram, equations are derived for determining the brine and gas content of sea Ice for high temperatures (range 0 to -2 °C) and low salinities. The presently widely used equations of Cox and Weeks (1982) are valid only for temperatures below -2°C. Fresh-water ice is used as a boundary condition for the equations. The relative salt concentrations in brine are_assumed to be the same as in normal (or standard) seawater. Two sets of equations are presented: 1) accurate formulae based on UNESCO standard sea water equations, and 2) approximate formulae based on general properties of weak solutions. The approximate formulae are not essentially different from the classical system which basically assumes the freezing point to be a linear function of fractional salt content. The agreement between the two approaches is excellent and the approximate system is good enough for most applications.

Features of wave field, its effect to erosion - deposition processes in the Cua Dai (Hoi An), Cai river mouth (Nha Trang) and Phan Thiet Bay in typical local wind conditions

Based on the hydrodynamic model and Shore Protection Manual (CERC - USA) we have calculated wave field characteristics in the typical wind conditions (wind velocity equal to 13m/s in the high frequency direction of the wind regime). Comparison between measured and calculated wave parameters was presented and these results were corresponded to each other. The following main wave characteristics were calculated: -Pattern of the refraction wave field. -Average wave height field. -Longshore current velocity field in surf zone. From distribution features of wave field characteristics in research areas, it could be summarized as following: - The formation of wave fields in the research areas was unequal because of their local difference of hydrometeorological conditions, river discharge, bottom relief… - At Cuadai (Dai mouth, Hoian) area in the N direction of incident wave field, wave has caused serious variation of the coastline. The coastline in the whole region, especially, at the south of the mouth was eroded and the foreland in the north of the mouth was deposited. - At Cai river mouth (Nhatrang) area in the E direction of incident wave field, wave has effected strongly and directly to the inshore and channel structure. - At Phanthiet bay area in the SW direction of incident wave field, wave has effected strongly to the whole shoreline from Da point to Ne point and caused serious erosion.