OpenRaiser/Intern-Atlas huggingface dataset:
Matrix-free GPU implementation of a preconditioned conjugate gradient solver for anisotropic elliptic PDEs
Venue: arXiv cs.NA 2013
Year: 2013

Many problems in geophysical and atmospheric modelling require the fast solution of elliptic partial differential equations (PDEs) in "flat" three dimensional geometries. In particular, an anisotropic elliptic PDE for the pressure correction has to be solved at every time step in the dynamical core of many numerical weather prediction models, and equations of a very similar structure arise in global ocean models, subsurface flow simulations and gas and oil reservoir modelling. The elliptic solve is often the bottleneck of the forecast, and an algorithmically optimal method has to be used and implemented efficiently. Graphics Processing Units have been shown to be highly efficient for a wide range of applications in scientific computing, and recently iterative solvers have been parallelised on these architectures. We describe the GPU implementation and optimisation of a Preconditioned Conjugate Gradient (PCG) algorithm for the solution of a three dimensional anisotropic elliptic PDE for the pressure correction in NWP. Our implementation exploits the strong vertical anisotropy of the elliptic operator in the construction of a suitable preconditioner. As the algorithm is memory bound, performance can be improved significantly by reducing the amount of global memory access. We achieve this by using a matrix-free implementation which does not require explicit storage of the matrix and instead recalculates the local stencil. Global memory access can also be reduced by rewriting the algorithm using loop fusion and we show that this further reduces the runtime on the GPU. We demonstrate the performance of our matrix-free GPU code by comparing it to a sequential CPU implementation and to a matrix-explicit GPU code which uses existing libraries. The absolute performance of the algorithm for different problem sizes is quantified in terms of floating point throughput and global memory bandwidth.
A Practical Cooperative Multicell MIMO-OFDMA Network Based on Rank Coordination
Venue: arXiv cs.IT 2013
Year: 2013

An important challenge of wireless networks is to boost the cell edge performance and enable multi-stream transmissions to cell edge users. Interference mitigation techniques relying on multiple antennas and coordination among cells are nowadays heavily studied in the literature. Typical strategies in OFDMA networks include coordinated scheduling, beamforming and power control. In this paper, we propose a novel and practical type of coordination for OFDMA downlink networks relying on multiple antennas at the transmitter and the receiver. The transmission ranks, i.e.\ the number of transmitted streams, and the user scheduling in all cells are jointly optimized in order to maximize a network utility function accounting for fairness among users. A distributed coordinated scheduler motivated by an interference pricing mechanism and relying on a master-slave architecture is introduced. The proposed scheme is operated based on the user report of a recommended rank for the interfering cells accounting for the receiver interference suppression capability. It incurs a very low feedback and backhaul overhead and enables efficient link adaptation. It is moreover robust to channel measurement errors and applicable to both open-loop and closed-loop MIMO operations. A 20% cell edge performance gain over uncoordinated LTE-A system is shown through system level simulations.
Enhancing Clustering Algorithm to Plan Efficient Mobile Network
Venue: arXiv cs.NI 2013
Year: 2013

With the rapid development in mobile network effective network planning tool is needed to satisfy the need of customers. However, deciding upon the optimum placement for the base stations (BS) to achieve best services while reducing the cost is a complex task requiring vast computational resource. This paper addresses antenna placement problem or the cell planning problem, involves locating and configuring infrastructure for mobile networks. The Cluster Partitioning Around Medoids (PAM) original algorithm has been modified and a new algorithm M-PAM (Modified-Partitioning Around Medoids) has been proposed by the authors in a recent work. In the present paper, the M-PAM algorithm is modified and a new algorithm CWN-PAM (Clustering with Weighted Node-Partitioning Around Medoids) has been proposed to satisfy the requirements and constraints. Implementation of this algorithm to a real case study is presented. Results demonstrate the effectiveness and flexibility of the modifying algorithm in tackling the important problem of mobile network planning.
Second-Order Non-Stationary Online Learning for Regression
Venue: arXiv cs.LG 2013
Year: 2013

The goal of a learner, in standard online learning, is to have the cumulative loss not much larger compared with the best-performing function from some fixed class. Numerous algorithms were shown to have this gap arbitrarily close to zero, compared with the best function that is chosen off-line. Nevertheless, many real-world applications, such as adaptive filtering, are non-stationary in nature, and the best prediction function may drift over time. We introduce two novel algorithms for online regression, designed to work well in non-stationary environment. Our first algorithm performs adaptive resets to forget the history, while the second is last-step min-max optimal in context of a drift. We analyze both algorithms in the worst-case regret framework and show that they maintain an average loss close to that of the best slowly changing sequence of linear functions, as long as the cumulative drift is sublinear. In addition, in the stationary case, when no drift occurs, our algorithms suffer logarithmic regret, as for previous algorithms. Our bounds improve over the existing ones, and simulations demonstrate the usefulness of these algorithms compared with other state-of-the-art approaches.
Inverse Signal Classification for Financial Instruments
Venue: arXiv cs.LG 2013
Year: 2013

The paper presents new machine learning methods: signal composition, which classifies time-series regardless of length, type, and quantity; and self-labeling, a supervised-learning enhancement. The paper describes further the implementation of the methods on a financial search engine system using a collection of 7,881 financial instruments traded during 2011 to identify inverse behavior among the time-series.
Clubs-based Particle Swarm Optimization
Venue: arXiv cs.NE 2013
Year: 2013

This paper introduces a new dynamic neighborhood network for particle swarm optimization. In the proposed Clubs-based Particle Swarm Optimization (C-PSO) algorithm, each particle initially joins a default number of what we call 'clubs'. Each particle is affected by its own experience and the experience of the best performing member of the clubs it is a member of. Clubs membership is dynamic, where the worst performing particles socialize more by joining more clubs to learn from other particles and the best performing particles are made to socialize less by leaving clubs to reduce their strong influence on other members. Particles return gradually to default membership level when they stop showing extreme performance. Inertia weights of swarm members are made random within a predefined range. This proposed dynamic neighborhood algorithm is compared with other two algorithms having static neighborhood topologies on a set of classic benchmark problems. The results showed superior performance for C-PSO regarding escaping local optima and convergence speed.
Secure Distance Bounding Verification using Physical-Channel Properties
Venue: arXiv cs.CR 2013
Year: 2013

We consider the problem of distance bounding verification (DBV), where a proving party claims a distance and a verifying party ensures that the prover is within the claimed distance. Current approaches to "secure" distance estimation use signal's time of flight, which requires the verifier to have an accurate clock. We study secure DBV using physical channel properties as an alternative to time measurement. We consider a signal propagation environment that attenuates signal as a function of distance, and then corrupts it by an additive noise. We consider three attacking scenarios against DBV, namely distance fraud (DFA), mafia fraud (MFA) and terrorist fraud (TFA) attacks. We show it is possible to construct efficient DBV protocols with DFA and MFA security, even against an unbounded adversary; on the other hand, it is impossible to design TFA-secure protocols without time measurement, even with a computationally-bounded adversary. We however provide a TFA-secure construction under the condition that the adversary's communication capability is limited to the bounded retrieval model (BRM). We use numerical analysis to examine the communication complexity of the introduced DBV protocols. We discuss our results and give directions for future research.
On computation of the total set of robust discrete-time PID controllers
Venue: arXiv cs.SY 2013
Year: 2013

The problem of finding the set of all multi-model robust PID and three-term stabilizers for discrete-time systems is solved in this paper. The method uses the fact that decoupling of parameter space at singular frequencies is invariant under a linear transformation. The resulting stable regions are composed by convex polygonal slices. The design problem includes the assertion of intervals with stable polygons and the detection of stable polygons. This paper completes the solutions to both problems.
IRS for Computer Character Sequences Filtration: a new software tool and algorithm to support the IRS at tokenization process
Venue: arXiv cs.IR 2013
Year: 2013

Tokenization is the task of chopping it up into pieces, called tokens, perhaps at the same time throwing away certain characters, such as punctuation. A token is an instance of token a sequence of characters in some particular document that are grouped together as a useful semantic unit for processing. New software tool and algorithm to support the IRS at tokenization process are presented. Our proposed tool will filter out the three computer character Sequences: IP-Addresses, Web URLs, Date, and Email Addresses. Our tool will use the pattern matching algorithms and filtration methods. After this process, the IRS can start a new tokenization process on the new retrieved text which will be free of these sequences.
Random Beamforming with Heterogeneous Users and Selective Feedback: Individual Sum Rate and Individual Scaling Laws
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates three open problems in random beamforming based communication systems: the scheduling policy with heterogeneous users, the closed form sum rate, and the randomness of multiuser diversity with selective feedback. By employing the cumulative distribution function based scheduling policy, we guarantee fairness among users as well as obtain multiuser diversity gain in the heterogeneous scenario. Under this scheduling framework, the individual sum rate, namely the average rate for a given user multiplied by the number of users, is of interest and analyzed under different feedback schemes. Firstly, under the full feedback scheme, we derive the closed form individual sum rate by employing a decomposition of the probability density function of the selected user's signal-to-interference-plus-noise ratio. This technique is employed to further obtain a closed form rate approximation with selective feedback in the spatial dimension. The analysis is also extended to random beamforming in a wideband OFDMA system with additional selective feedback in the spectral dimension wherein only the best beams for the best-L resource blocks are fed back. We utilize extreme value theory to examine the randomness of multiuser diversity incurred by selective feedback. Finally, by leveraging the tail equivalence method, the multiplicative effect of selective feedback and random observations is observed to establish the individual rate scaling.
On the Coherence Properties of Random Euclidean Distance Matrices
Venue: arXiv cs.IT 2013
Year: 2013

In the present paper we focus on the coherence properties of general random Euclidean distance matrices, which are very closely related to the respective matrix completion problem. This problem is of great interest in several applications such as node localization in sensor networks with limited connectivity. Our results can directly provide the sufficient conditions under which an EDM can be successfully recovered with high probability from a limited number of measurements.
Indian Sign Language Recognition Using Eigen Value Weighted Euclidean Distance Based Classification Technique
Venue: arXiv cs.CV 2013
Year: 2013

Sign Language Recognition is one of the most growing fields of research today. Many new techniques have been developed recently in these fields. Here in this paper, we have proposed a system using Eigen value weighted Euclidean distance as a classification technique for recognition of various Sign Languages of India. The system comprises of four parts: Skin Filtering, Hand Cropping, Feature Extraction and Classification. Twenty four signs were considered in this paper, each having ten samples, thus a total of two hundred forty images was considered for which recognition rate obtained was 97 percent.
Recognition of Facial Expression Using Eigenvector Based Distributed Features and Euclidean Distance Based Decision Making Technique
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, an Eigenvector based system has been presented to recognize facial expressions from digital facial images. In the approach, firstly the images were acquired and cropping of five significant portions from the image was performed to extract and store the Eigenvectors specific to the expressions. The Eigenvectors for the test images were also computed, and finally the input facial image was recognized when similarity was obtained by calculating the minimum Euclidean distance between the test image and the different expressions.
Energy Aware Task Scheduling for Soft Real Time Systems using an Analytical Approach for Energy Estimation
Venue: arXiv cs.OH 2013
Year: 2013

Embedded systems have pervaded all walks of our life. With the increasing importance of mobile embedded systems and flexible applications, considerable progress in research has been made for power management. Power constraints are increasingly becoming the critical component of the design specifications of these systems. It helps in pre-determining the suitable hardware architecture for the target application. The aim of this paper is to present a technique to estimate 'pre-run time' and 'power' of a software mapped onto a hardware system; guaranteeing the compliance of temporal constraints while generating a schedule of tasks of software. Real time systems must handle several independent macro-tasks, each represented by a task graph, which includes communications and precedence constraints. We propose a novel approach for power estimation of embedded software using the Control Data Flow Graph (CDFG) or task graph model. This methodology uses an existing Hierarchical Concurrent Flow Graph (HCFG) technique for the power analysis of the CDFGs. We have evaluated our technique for energy efficient scheduling over various task graph benchmarks. The results obtained prove the utility and efficacy of our proposed approach for power analysis of embedded software. We also present a methodology to obtain an energy optimal voltage assignment and perform scheduling by taking advantage of the relaxation in execution time of tasks.
Hybrid Maximum Likelihood Modulation Classification Using Multiple Radios
Venue: arXiv cs.IT 2013
Year: 2013

The performance of a modulation classifier is highly sensitive to channel signal-to-noise ratio (SNR). In this paper, we focus on amplitude-phase modulations and propose a modulation classification framework based on centralized data fusion using multiple radios and the hybrid maximum likelihood (ML) approach. In order to alleviate the computational complexity associated with ML estimation, we adopt the Expectation Maximization (EM) algorithm. Due to SNR diversity, the proposed multi-radio framework provides robustness to channel SNR. Numerical results show the superiority of the proposed approach with respect to single radio approaches as well as to modulation classifiers using moments based estimators.
Restricted Manipulation in Iterative Voting: Convergence and Condorcet Efficiency
Venue: arXiv cs.AI 2013
Year: 2013

In collective decision making, where a voting rule is used to take a collective decision among a group of agents, manipulation by one or more agents is usually considered negative behavior to be avoided, or at least to be made computationally difficult for the agents to perform. However, there are scenarios in which a restricted form of manipulation can instead be beneficial. In this paper we consider the iterative version of several voting rules, where at each step one agent is allowed to manipulate by modifying his ballot according to a set of restricted manipulation moves which are computationally easy and require little information to be performed. We prove convergence of iterative voting rules when restricted manipulation is allowed, and we present experiments showing that most iterative voting rules have a higher Condorcet efficiency than their non-iterative version.
Infinite games with uncertain moves
Venue: arXiv cs.GT 2013
Year: 2013

We study infinite two-player games where one of the players is unsure about the set of moves available to the other player. In particular, the set of moves of the other player is a strict superset of what she assumes it to be. We explore what happens to sets in various levels of the Borel hierarchy under such a situation. We show that the sets at every alternate level of the hierarchy jump to the next higher level.
How to Be Both Rich and Happy: Combining Quantitative and Qualitative Strategic Reasoning about Multi-Player Games (Extended Abstract)
Venue: arXiv cs.LO 2013
Year: 2013

We propose a logical framework combining a game-theoretic study of abilities of agents to achieve quantitative objectives in multi-player games by optimizing payoffs or preferences on outcomes with a logical analysis of the abilities of players for achieving qualitative objectives of players, i.e., reaching or maintaining game states with desired properties. We enrich concurrent game models with payoffs for the normal form games associated with the states of the model and propose a quantitative extension of the logic ATL* enabling the combination of quantitative and qualitative reasoning.
Lossy Channel Games under Incomplete Information
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we investigate lossy channel games under incomplete information, where two players operate on a finite set of unbounded FIFO channels and one player, representing a system component under consideration operates under incomplete information, while the other player, representing the component's environment is allowed to lose messages from the channels. We argue that these games are a suitable model for synthesis of communication protocols where processes communicate over unreliable channels. We show that in the case of finite message alphabets, games with safety and reachability winning conditions are decidable and finite-state observation-based strategies for the component can be effectively computed. Undecidability for (weak) parity objectives follows from the undecidability of (weak) parity perfect information games where only one player can lose messages.
Reducing Validity in Epistemic ATL to Validity in Epistemic CTL
Venue: arXiv cs.LO 2013
Year: 2013

We propose a validity preserving translation from a subset of epistemic Alternating-time Temporal Logic (ATL) to epistemic Computation Tree Logic (CTL). The considered subset of epistemic ATL is known to have the finite model property and decidable model-checking. This entails the decidability of validity but the implied algorithm is unfeasible. Reducing the validity problem to that in a corresponding system of CTL makes the techniques for automated deduction for that logic available for the handling of the apparently more complex system of ATL.
LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
Venue: arXiv cs.SI 2013
Year: 2013

An important challenge in big data analysis nowadays is detection of cohesive groups in large-scale networks, including social networks, genetic networks, communication networks and so. In this paper, we propose LabelRank, an efficient algorithm detecting communities through label propagation. A set of operators is introduced to control and stabilize the propagation dynamics. These operations resolve the randomness issue in traditional label propagation algorithms (LPA), stabilizing the discovered communities in all runs of the same network. Tests on real-world networks demonstrate that LabelRank significantly improves the quality of detected communities compared to LPA, as well as other popular algorithms.
Set-Membership Conjugate Gradient Constrained Adaptive Filtering Algorithm for Beamforming
Venue: arXiv cs.IT 2013
Year: 2013

We introduce a new linearly constrained minimum variance (LCMV) beamformer that combines the set-membership (SM) technique with the conjugate gradient (CG) method, and develop a low-complexity adaptive filtering algorithm for beamforming. The proposed algorithm utilizes a CG-based vector and a variable forgetting factor to perform the data-selective updates that are controlled by a time-varying bound related to the parameters. For the update, the CG-based vector is calculated iteratively (one iteration per update) to obtain the filter parameters and to avoid the matrix inversion. The resulting iterations construct a space of feasible solutions that satisfy the constraints of the LCMV optimization problem. The proposed algorithm reduces the computational complexity significantly and shows an enhanced convergence and tracking performance over existing algorithms.
A heuristic optimization method for mitigating the impact of a virus attack
Venue: arXiv cs.SI 2013
Year: 2013

Taking precautions before or during the start of a virus outbreak can heavily reduce the number of infected. The question which individuals should be immunized in order to mitigate the impact of the virus on the rest of population has received quite some attention in the literature. The dynamics of the of a virus spread through a population is often represented as information spread over a complex network. The strategies commonly proposed to determine which nodes are to be selected for immunization often involve only one centrality measure at a time, while often the topology of the network seems to suggest that a single metric is insufficient to capture the influence of a node entirely. In this work we present a generic method based on a genetic algorithm (GA) which does not rely explicitly on any centrality measures during its search but only exploits this type of information to narrow the search space. The fitness of an individual is defined as the estimated expected number of infections of a virus following SIR dynamics. The proposed method is evaluated on two contact networks: the Goodreau's Faux Mesa high school and the US air transportation network. The GA method manages to outperform the most common strategies based on a single metric for the air transportation network and its performance is comparable with the best performing strategy for the high school network.