OpenRaiser/Intern-Atlas huggingface dataset:
Characterization of the errors of the FMM in particle simulations
Venue: arXiv cs.DS 2008
Year: 2008

The Fast Multipole Method (FMM) offers an acceleration for pairwise interaction calculation, known as $N$-body problems, from $\mathcal{O}(N^2)$ to $\mathcal{O}(N)$ with $N$ particles. This has brought dramatic increase in the capability of particle simulations in many application areas, such as electrostatics, particle formulations of fluid mechanics, and others. Although the literature on the subject provides theoretical error bounds for the FMM approximation, there are not many reports of the measured errors in a suite of computational experiments. We have performed such an experimental investigation, and summarized the results of about 1000 calculations using the FMM algorithm, to characterize the accuracy of the method in relation with the different parameters available to the user. In addition to the more standard diagnostic of the maximum error, we supply illustrations of the spatial distribution of the errors, which offers visual evidence of all the contributing factors to the overall approximation accuracy: multipole expansion, local expansion, hierarchical spatial decomposition (interaction lists, local domain, far domain). This presentation is a contribution to any researcher wishing to incorporate the FMM acceleration to their application code, as it aids in understanding where accuracy is gained or compromised.
Getting in the Zone for Successful Scalability
Venue: arXiv cs.PF 2008
Year: 2008

The universal scalability law (USL) is an analytic model used to quantify application scaling. It is universal because it subsumes Amdahl's law and Gustafson linearized scaling as special cases. Using simulation, we show: (i) that the USL is equivalent to synchronous queueing in a load-dependent machine repairman model and (ii) how USL, Amdahl's law, and Gustafson scaling can be regarded as boundaries defining three scalability zones. Typical throughput measurements lie across all three zones. Simulation scenarios provide deeper insight into queueing effects and thus provide a clearer indication of which application features should be tuned to get into the optimal performance zone.
Depth as Randomness Deficiency
Venue: arXiv cs.CC 2008
Year: 2008

Depth of an object concerns a tradeoff between computation time and excess of program length over the shortest program length required to obtain the object. It gives an unconditional lower bound on the computation time from a given program in absence of auxiliary information. Variants known as logical depth and computational depth are expressed in Kolmogorov complexity theory. We derive quantitative relation between logical depth and computational depth and unify the different depth notions by relating them to A. Kolmogorov and L. Levin's fruitful notion of randomness deficiency. Subsequently, we revisit the computational depth of infinite strings, introducing the notion of super deep sequences and relate it with other approaches.
An MAS-Based ETL Approach for Complex Data
Venue: arXiv cs.DB 2008
Year: 2008

In a data warehousing process, the phase of data integration is crucial. Many methods for data integration have been published in the literature. However, with the development of the Internet, the availability of various types of data (images, texts, sounds, videos, databases...) has increased, and structuring such data is a difficult task. We name these data, which may be structured or unstructured, "complex data". In this paper, we propose a new approach for complex data integration, based on a Multi-Agent System (MAS), in association to a data warehousing approach. Our objective is to take advantage of the MAS to perform the integration phase for complex data. We indeed consider the different tasks of the data integration process as services offered by agents. To validate this approach, we have actually developed an MAS for complex data integration.
A Complex Data Warehouse for Personalized, Anticipative Medicine
Venue: arXiv cs.DB 2008
Year: 2008

With the growing use of new technologies, healthcare is nowadays undergoing significant changes. Information-based medicine has to exploit medical decision-support systems and requires the analysis of various, heterogeneous data, such as patient records, medical images, biological analysis results, etc. In this paper, we present the design of the complex data warehouse relating to high-level athletes. It is original in two ways. First, it is aimed at storing complex medical data. Second, it is designed to allow innovative and quite different kinds of analyses to support: (1) personalized and anticipative medicine (in opposition to curative medicine) for well-identified patients; (2) broad-band statistical studies over a given population of patients. Furthermore, the system includes data relating to several medical fields. It is also designed to be evolutionary to take into account future advances in medical research.
Fundamental Constraints on Multicast Capacity Regions
Venue: arXiv cs.IT 2008
Year: 2008

Much of the existing work on the broadcast channel focuses only on the sending of private messages. In this work we examine the scenario where the sender also wishes to transmit common messages to subsets of receivers. For an L user broadcast channel there are 2L - 1 subsets of receivers and correspondingly 2L - 1 independent messages. The set of achievable rates for this channel is a 2L - 1 dimensional region. There are fundamental constraints on the geometry of this region. For example, observe that if the transmitter is able to simultaneously send L rate-one private messages, error-free to all receivers, then by sending the same information in each message, it must be able to send a single rate-one common message, error-free to all receivers. This swapping of private and common messages illustrates that for any broadcast channel, the inclusion of a point R* in the achievable rate region implies the achievability of a set of other points that are not merely component-wise less than R*. We formerly define this set and characterize it for L = 2 and L = 3. Whereas for L = 2 all the points in the set arise only from operations relating to swapping private and common messages, for L = 3 a form of network coding is required.
Metrics-Based Spreadsheet Visualization: Support for Focused Maintenance
Venue: arXiv cs.SE 2008
Year: 2008

Legacy spreadsheets are both, an asset, and an enduring problem concerning spreadsheets in business. To make spreadsheets stay alive and remain correct, comprehension of a given spreadsheet is highly important. Visualization techniques should ease the complex and mindblowing challenges of finding structures in a huge set of spreadsheet cells for building an adequate mental model of spreadsheet programs. Since spreadsheet programs are as diverse as the purpose they are serving and as inhomogeneous as their programmers, to find an appropriate representation or visualization technique for every spreadsheet program seems futile. We thus propose different visualization and representation methods that may ease spreadsheet comprehension but should not be applied with all kind of spreadsheet programs. Therefore, this paper proposes to use (complexity) measures as indicators for proper visualization.
Singularity Analysis of Limited-dof Parallel Manipulators using Grassmann-Cayley Algebra
Venue: arXiv cs.RO 2008
Year: 2008

This paper characterizes geometrically the singularities of limited DOF parallel manipulators. The geometric conditions associated with the dependency of six Plücker vector of lines (finite and infinite) constituting the rows of the inverse Jacobian matrix are formulated using Grassmann-Cayley algebra. Manipulators under consideration do not need to have a passive spherical joint somewhere in each leg. This study is illustrated with three example robots
A Statistical Approach to Modeling Indian Classical Music Performance
Venue: arXiv cs.SD 2008
Year: 2008

A raga is a melodic structure with fixed notes and a set of rules characterizing a certain mood endorsed through performance. By a vadi swar is meant that note which plays the most significant role in expressing the raga. A samvadi swar similarly is the second most significant note. However, the determination of their significance has an element of subjectivity and hence we are motivated to find some truths through an objective analysis. The paper proposes a probabilistic method of note detection and demonstrates how the relative frequency (relative number of occurrences of the pitch) of the more important notes stabilize far more quickly than that of others. In addition, a count for distinct transitory and similar looking non-transitory (fundamental) frequency movements (but possibly embedding distinct emotions!) between the notes is also taken depicting the varnalankars or musical ornaments decorating the notes and note sequences as rendered by the artist. They reflect certain structural properties of the ragas. Several case studies are presented.
On fractionality of the path packing problem
Venue: arXiv cs.DM 2008
Year: 2008

In this paper, we study fractional multiflows in undirected graphs. A fractional multiflow in a graph G with a node subset T, called terminals, is a collection of weighted paths with ends in T such that the total weights of paths traversing each edge does not exceed 1. Well-known fractional path packing problem consists of maximizing the total weight of paths with ends in a subset S of TxT over all fractional multiflows. Together, G,T and S form a network. A network is an Eulerian network if all nodes in N\T have even degrees. A term "fractionality" was defined for the fractional path packing problem by A. Karzanov as the smallest natural number D so that there exists a solution to the problem that becomes integer-valued when multiplied by D. A. Karzanov has defined the class of Eulerian networks in terms of T and S, outside which D is infinite and proved that whithin this class D can be 1,2 or 4. He conjectured that D should be 1 or 2 for this class of networks. In this paper we prove this conjecture.
Evaluation of an Intelligent Assistive Technology for Voice Navigation of Spreadsheets
Venue: arXiv cs.HC 2008
Year: 2008

An integral part of spreadsheet auditing is navigation. For sufferers of Repetitive Strain Injury who need to use voice recognition technology this navigation can be highly problematic. To counter this the authors have developed an intelligent voice navigation system, iVoice, which replicates common spreadsheet auditing behaviours through simple voice commands. This paper outlines the iVoice system and summarizes the results of a study to evaluate iVoice when compared to a leading voice recognition technology.
Spreadsheet modelling for solving combinatorial problems: The vendor selection problem
Venue: arXiv cs.SE 2008
Year: 2008

Spreadsheets have grown up and became very powerful and easy to use tools in applying analytical techniques for solving business problems. Operations managers, production managers, planners and schedulers can work with them in developing solid and practical Do-It-Yourself Decision Support Systems. Small and Medium size organizations, can apply OR methodologies without the presence of specialized software and trained personnel, which in many cases cannot afford anyway. This paper examines an efficient approach in solving combinatorial programming problems with the use of spreadsheets. A practical application, which demonstrates the approach, concerns the development of a spreadsheet-based DSS for the Multi Item Procurement Problem with Fixed Vendor Cost. The DSS has been build using exclusively standard spreadsheet feature and can solve real problems of substantial size. The benefits and limitations of the approach are also discussed.
A Primer on Spreadsheet Analytics
Venue: arXiv cs.SE 2008
Year: 2008

This paper provides guidance to an analyst who wants to extract insight from a spreadsheet model. It discusses the terminology of spreadsheet analytics, how to prepare a spreadsheet model for analysis, and a hierarchy of analytical techniques. These techniques include sensitivity analysis, tornado charts,and backsolving (or goal-seeking). This paper presents native-Excel approaches for automating these techniques, and discusses add-ins that are even more efficient. Spreadsheet optimization and spreadsheet Monte Carlo simulation are briefly discussed. The paper concludes by calling for empirical research, and describing desired features spreadsheet sensitivity analysis and spreadsheet optimization add-ins.
Spreadsheet End-User Behaviour Analysis
Venue: arXiv cs.SE 2008
Year: 2008

To aid the development of spreadsheet debugging tools, a knowledge of end-users natural behaviour within the Excel environment would be advantageous. This paper details the design and application of a novel data acquisition tool, which can be used for the unobtrusive recording of end-users mouse, keyboard and Excel specific actions during the debugging of Excel spreadsheets. A debugging experiment was conducted using this data acquisition tool, and based on analysis of end-users performance and behaviour data, the authors developed a "spreadsheet cell coverage feedback" debugging tool. Results from the debugging experiment are presented in terms of enduser debugging performance and behaviour, and the outcomes of an evaluation experiment with the debugging tool are detailed.
Spreadsheets: Aiming the Accountant's Hammer to Hit the Nail on the Head
Venue: arXiv cs.HC 2008
Year: 2008

Accounting and Finance (A&F) Professionals are arguably the most loyal and concentrated population of spreadsheet users. The work that they perform in spreadsheets has the most significant impact on financial data and business processes within global organizations today. Spreadsheets offer the flexibility and ease of use of a desktop application, combined with the power to perform complex data analysis. They are also the lowest cost business IT tool when stacked up against other functional tools. As a result, spreadsheets are used to support critical business processes in most organizations. In fact, research indicates that over half of financial management reporting is performed with spreadsheets by an accounting and finance professional. A disparity exists in the business world between the importance of spreadsheets on financial data (created by A&F Professionals) and the resources devoted to: The development and oversight of global spreadsheet standards; A recognized and accredited certification in spreadsheet proficiency; Corporate sponsored and required training; Awareness of emerging technologies as it relates to spreadsheet use. This management paper focuses on the current topics relevant to the largest user group (A&F Professionals) of the most widely used financial software application, spreadsheets, also known as the accountant's hammer.
Overview and main results of the DidaTab project
Venue: arXiv cs.HC 2008
Year: 2008

The DidaTab project (Didactics of Spreadsheet, teaching and learning spreadsheets) is a three year project (2005-2007) funded by the French Ministry of Research and dedicated to the study of personal and classroom uses of spreadsheets in the French context, focussing on the processes of appropriation and uses by secondary school students. In this paper, we present an overview of the project, briefly report the studies performed in the framework of the DidaTab project, and give the main results we obtained. We then explore the new research tracks we intend to develop, more in connection with EuSpRIG. Our main result is that the use of spreadsheet during secondary education (grade 6 to 12) is rather sparse for school work (and even more seldom at home) and that student competencies are weak. Curricula have to be reviewed to include more training of dynamics tabular tools (including databases queries) in order to ensure sufficient mastery of computer tools that have became necessary in many educational activities.
Modeling and Control with Local Linearizing Nadaraya Watson Regression
Venue: arXiv cs.CV 2008
Year: 2008

Black box models of technical systems are purely descriptive. They do not explain why a system works the way it does. Thus, black box models are insufficient for some problems. But there are numerous applications, for example, in control engineering, for which a black box model is absolutely sufficient. In this article, we describe a general stochastic framework with which such models can be built easily and fully automated by observation. Furthermore, we give a practical example and show how this framework can be used to model and control a motorcar powertrain.
Software dependability modeling using an industry-standard architecture description language
Venue: arXiv cs.SE 2008
Year: 2008

Performing dependability evaluation along with other analyses at architectural level allows both making architectural tradeoffs and predicting the effects of architectural decisions on the dependability of an application. This paper gives guidelines for building architectural dependability models for software systems using the AADL (Architecture Analysis and Design Language). It presents reusable modeling patterns for fault-tolerant applications and shows how the presented patterns can be used in the context of a subsystem of a real-life application.
Bisimilarity and Behaviour-Preserving Reconfigurations of Open Petri Nets
Venue: arXiv cs.LO 2008
Year: 2008

We propose a framework for the specification of behaviour-preserving reconfigurations of systems modelled as Petri nets. The framework is based on open nets, a mild generalisation of ordinary Place/Transition nets suited to model open systems which might interact with the surrounding environment and endowed with a colimit-based composition operation. We show that natural notions of bisimilarity over open nets are congruences with respect to the composition operation. The considered behavioural equivalences differ for the choice of the observations, which can be single firings or parallel steps. Additionally, we consider weak forms of such equivalences, arising in the presence of unobservable actions. We also provide an up-to technique for facilitating bisimilarity proofs. The theory is used to identify suitable classes of reconfiguration rules (in the double-pushout approach to rewriting) whose application preserves the observational semantics of the net.
On-the-Fly Coding to Enable Full Reliability Without Retransmission
Venue: arXiv cs.NI 2008
Year: 2008

This paper proposes a new reliability algorithm specifically useful when retransmission is either problematic or not possible. In case of multimedia or multicast communications and in the context of the Delay Tolerant Networking (DTN), the classical retransmission schemes can be counterproductive in terms of data transfer performance or not possible when the acknowledgment path is not always available. Indeed, over long delay links, packets retransmission has a meaning of cost and must be minimized.In this paper, we detail a novel reliability mechanism with an implicit acknowledgment strategy that could be used either within these new DTN proposals, for multimedia traffic or in the context of multicast transport protocols. This proposal is based on a new on-the-fly erasure coding concept specifically designed to operate efficient reliable transfer over bi-directional links. This proposal, named Tetrys, allows to unify a full reliability with an error correction scheme. In this paper, we model the performance of this proposal and demonstrate with a prototype, that we can achieve a full reliability without acknowledgment path confirmation. Indeed, the main findings are that Tetrys is not sensitive to the loss of acknowledgments while ensuring a faster data availability to the application compared to other traditional acknowledgment schemes. Finally, we pave the first step of the integration of such algorithm inside a congestion controlled protocol.
Enhanced Energy-Aware Feedback Scheduling of Embedded Control Systems
Venue: arXiv cs.OH 2008
Year: 2008

Dynamic voltage scaling (DVS) is one of the most effective techniques for reducing energy consumption in embedded and real-time systems. However, traditional DVS algorithms have inherent limitations on their capability in energy saving since they rarely take into account the actual application requirements and often exploit fixed timing constraints of real-time tasks. Taking advantage of application adaptation, an enhanced energy-aware feedback scheduling (EEAFS) scheme is proposed, which integrates feedback scheduling with DVS. To achieve further reduction in energy consumption over pure DVS while not jeopardizing the quality of control, the sampling period of each control loop is adapted to its actual control performance, thus exploring flexible timing constraints on control tasks. Extensive simulation results are given to demonstrate the effectiveness of EEAFS under different scenarios. Compared with the optimal pure DVS scheme, EEAFS saves much more energy while yielding comparable control performance.
Integrated Design and Implementation of Embedded Control Systems with Scilab
Venue: arXiv cs.OH 2008
Year: 2008

Embedded systems are playing an increasingly important role in control engineering. Despite their popularity, embedded systems are generally subject to resource constraints and it is therefore difficult to build complex control systems on embedded platforms. Traditionally, the design and implementation of control systems are often separated, which causes the development of embedded control systems to be highly time-consuming and costly. To address these problems, this paper presents a low-cost, reusable, reconfigurable platform that enables integrated design and implementation of embedded control systems. To minimize the cost, free and open source software packages such as Linux and Scilab are used. Scilab is ported to the embedded ARM-Linux system. The drivers for interfacing Scilab with several communication protocols including serial, Ethernet, and Modbus are developed. Experiments are conducted to test the developed embedded platform. The use of Scilab enables implementation of complex control algorithms on embedded platforms. With the developed platform, it is possible to perform all phases of the development cycle of embedded control systems in a unified environment, thus facilitating the reduction of development time and cost.
Simulated annealing for weighted polygon packing
Venue: arXiv cs.CG 2008
Year: 2008

In this paper we present a new algorithm for a layout optimization problem: this concerns the placement of weighted polygons inside a circular container, the two objectives being to minimize imbalance of mass and to minimize the radius of the container. This problem carries real practical significance in industrial applications (such as the design of satellites), as well as being of significant theoretical interest. Previous work has dealt with circular or rectangular objects, but here we deal with the more realistic case where objects may be represented as polygons and the polygons are allowed to rotate. We present a solution based on simulated annealing and first test it on instances with known optima. Our results show that the algorithm obtains container radii that are close to optimal. We also compare our method with existing algorithms for the (special) rectangular case. Experimental results show that our approach out-performs these methods in terms of solution quality.