Median computation in graphs using consensus strategies

Following the Majority Strategy in graphs, other consensus strategies, namely Plurality Strategy, Hill Climbing and Steepest Ascent Hill Climbing strategies on graphs are discussed as methods for the computation of median sets of pro¯les. A review of algorithms for median computation on median graphs is discussed and their time complexities are compared. Implementation of the consensus strategies on median computation in arbitrary graphs is discussed

Computation of locally free class groups

We show that the locally free class group of an order in a semisimple algebra over a number field is isomorphic to a certain ray class group. This description is then used to present an algorithm that computes the locally free class group. The algorithm is implemented in MAGMA for the case where the algebra is a group ring over the rational numbers.

On the Computation of Fourier Coefficients

In this paper we derive an identity for the Fourier coefficients of a differentiable function f(t) in terms of the Fourier coefficients of its derivative f'(t). This yields an algorithm to compute the Fourier coefficients of f(t) whenever the Fourier coefficients of f'(t) are known, and vice versa. Furthermore this generates an iterative scheme for N times differentiable functions complementing the direct computation of Fourier coefficients via the defining integrals which can be also treated automatically in certain cases.

Agricultural, architectural and archaeological evidence for the role and ecological adaptation of a scattered mountain oasis in Oman

The recent discovery of the monumental 5000 years old tower tombs on top of the up to 1850 m high Shir plateau has raised numerous questions about the economic and infrastructural basis of the agro-pastoral-piscicultural society which likely has constructed them. The scattered oasis settlement of Maqta, situated just below the towers in a rugged desert environment has therefore been studied from 2001 to 2003 to understand its prehistoric and present role along the ancient trade route which connected the inner-Omani Sharqiya across the southern Hajar mountains with the ocean port of Tiwi. Maqta consists of a central area with 59 buildings and 12 scattered temporary settlements comprising a total of about 200 semi-nomadic inhabitants and next to 900 sheep and goats. The 22 small springs with a flow rate between 5 and 1212-l h^-1 are watering 16 terrace systems totaling 4.5 ha of which 2.9 ha are planted to date palms (Phoenix dactylifera L.), 0.4 ha to wheat landraces (Triticum durum and Triticum aestivum) during the cooler winter months, 0.4 are left fallow and 0.8 h are abandoned. During a pronounced drought period from 2001 to 2003, the springs’ flow rate declined between 38% and 72%. Most of the recent buildings of the central housing area were found empty or used as temporary stores by the agro-pastoral population watching their flocks on the surrounding dry mountains. There is no indication that there ever was a settlement older than the present one. A number of Hafit (3100–2700 BC) and Umm an-Nar (2700–2000 BC) tombs just above the central housing area and further along one of the trade routes to the coast are the only indication of an old pastoral landuse in Maqta territory where oasis agriculture may have entered only well after 1000 AD. With this little evidence of existence during the 3rd millennium BC, Maqta is unlikely to have played any major role favouring the construction of the nearby monumental Shir tower tombs other than providing water for herders and their flocks, early migrant traders or tower tomb constructors.

Computation of relativistic symmetry orbitals for finite double point groups

A program is presented for the construction of relativistic symmetry-adapted molecular basis functions. It is applicable to 36 finite double point groups. The algorithm, based on the projection operator method, automatically generates linearly independent basis sets. Time reversal invariance is included in the program, leading to additional selection rules in the non-relativistic limit.

Fast computation of concept lattices using data mining techniques

We present a new algorithm called TITANIC for computing concept lattices. It is based on data mining techniques for computing frequent itemsets. The algorithm is experimentally evaluated and compared with B. Ganter's Next-Closure algorithm.

Algorithmic Computation of Formal Fourier Series

KAAD (Katholischer Akademischer Ausländer-Dienst)

ACTORS: A Model of Concurrent Computation in Distributed Systems

A foundational model of concurrency is developed in this thesis. We examine issues in the design of parallel systems and show why the actor model is suitable for exploiting large-scale parallelism. Concurrency in actors is constrained only by the availability of hardware resources and by the logical dependence inherent in the computation. Unlike dataflow and functional programming, however, actors are dynamically reconfigurable and can model shared resources with changing local state. Concurrency is spawned in actors using asynchronous message-passing, pipelining, and the dynamic creation of actors. This thesis deals with some central issues in distributed computing. Specifically, problems of divergence and deadlock are addressed. For example, actors permit dynamic deadlock detection and removal. The problem of divergence is contained because independent transactions can execute concurrently and potentially infinite processes are nevertheless available for interaction.

The Computation of Color

This thesis takes an interdisciplinary approach to the study of color vision, focussing on the phenomenon of color constancy formulated as a computational problem. The primary contributions of the thesis are (1) the demonstration of a formal framework for lightness algorithms; (2) the derivation of a new lightness algorithm based on regularization theory; (3) the synthesis of an adaptive lightness algorithm using "learning" techniques; (4) the development of an image segmentation algorithm that uses luminance and color information to mark material boundaries; and (5) an experimental investigation into the cues that human observers use to judge the color of the illuminant. Other computational approaches to color are reviewed and some of their links to psychophysics and physiology are explored.

Dataflow Computation for the J-Machine

The dataflow model of computation exposes and exploits parallelism in programs without requiring programmer annotation; however, instruction- level dataflow is too fine-grained to be efficient on general-purpose processors. A popular solution is to develop a "hybrid'' model of computation where regions of dataflow graphs are combined into sequential blocks of code. I have implemented such a system to allow the J-Machine to run Id programs, leaving exposed a high amount of parallelism --- such as among loop iterations. I describe this system and provide an analysis of its strengths and weaknesses and those of the J-Machine, along with ideas for improvement.

Reconfigurable Architectures for General-Purpose Computing

General-purpose computing devices allow us to (1) customize computation after fabrication and (2) conserve area by reusing expensive active circuitry for different functions in time. We define RP-space, a restricted domain of the general-purpose architectural space focussed on reconfigurable computing architectures. Two dominant features differentiate reconfigurable from special-purpose architectures and account for most of the area overhead associated with RP devices: (1) instructions which tell the device how to behave, and (2) flexible interconnect which supports task dependent dataflow between operations. We can characterize RP-space by the allocation and structure of these resources and compare the efficiencies of architectural points across broad application characteristics. Conventional FPGAs fall at one extreme end of this space and their efficiency ranges over two orders of magnitude across the space of application characteristics. Understanding RP-space and its consequences allows us to pick the best architecture for a task and to search for more robust design points in the space. Our DPGA, a fine- grained computing device which adds small, on-chip instruction memories to FPGAs is one such design point. For typical logic applications and finite- state machines, a DPGA can implement tasks in one-third the area of a traditional FPGA. TSFPGA, a variant of the DPGA which focuses on heavily time-switched interconnect, achieves circuit densities close to the DPGA, while reducing typical physical mapping times from hours to seconds. Rigid, fabrication-time organization of instruction resources significantly narrows the range of efficiency for conventional architectures. To avoid this performance brittleness, we developed MATRIX, the first architecture to defer the binding of instruction resources until run-time, allowing the application to organize resources according to its needs. Our focus MATRIX design point is based on an array of 8-bit ALU and register-file building blocks interconnected via a byte-wide network. With today's silicon, a single chip MATRIX array can deliver over 10 Gop/s (8-bit ops). On sample image processing tasks, we show that MATRIX yields 10-20x the computational density of conventional processors. Understanding the cost structure of RP-space helps us identify these intermediate architectural points and may provide useful insight more broadly in guiding our continual search for robust and efficient general-purpose computing structures.

New Architectural Models for Visibly Controllable Computing: The Relevance of Dynamic Object Oriented Architectures and Plan Based Computing Models

Traditionally, we've focussed on the question of how to make a system easy to code the first time, or perhaps on how to ease the system's continued evolution. But if we look at life cycle costs, then we must conclude that the important question is how to make a system easy to operate. To do this we need to make it easy for the operators to see what's going on and to then manipulate the system so that it does what it is supposed to. This is a radically different criterion for success. What makes a computer system visible and controllable? This is a difficult question, but it's clear that today's modern operating systems with nearly 50 million source lines of code are neither. Strikingly, the MIT Lisp Machine and its commercial successors provided almost the same functionality as today's mainstream sytsems, but with only 1 Million lines of code. This paper is a retrospective examination of the features of the Lisp Machine hardware and software system. Our key claim is that by building the Object Abstraction into the lowest tiers of the system, great synergy and clarity were obtained. It is our hope that this is a lesson that can impact tomorrow's designs. We also speculate on how the spirit of the Lisp Machine could be extended to include a comprehensive access control model and how new layers of abstraction could further enrich this model.

Omnidirectional Depth Computation from a Single Image

Omnidirectional cameras offer a much wider field of view than the perspective ones and alleviate the problems due to occlusions. However, both types of cameras suffer from the lack of depth perception. A practical method for obtaining depth in computer vision is to project a known structured light pattern on the scene avoiding the problems and costs involved by stereo vision. This paper is focused on the idea of combining omnidirectional vision and structured light with the aim to provide 3D information about the scene. The resulting sensor is formed by a single catadioptric camera and an omnidirectional light projector. It is also discussed how this sensor can be used in robot navigation applications

On optimal computation of MPLS label binding for multipoint-to-point connections

Most network operators have considered reducing Label Switched Routers (LSR) label spaces (i.e. the number of labels that can be used) as a means of simplifying management of underlaying Virtual Private Networks (VPNs) and, hence, reducing operational expenditure (OPEX). This letter discusses the problem of reducing the label spaces in Multiprotocol Label Switched (MPLS) networks using label merging - better known as MultiPoint-to-Point (MP2P) connections. Because of its origins in IP, MP2P connections have been considered to have tree- shapes with Label Switched Paths (LSP) as branches. Due to this fact, previous works by many authors affirm that the problem of minimizing the label space using MP2P in MPLS - the Merging Problem - cannot be solved optimally with a polynomial algorithm (NP-complete), since it involves a hard- decision problem. However, in this letter, the Merging Problem is analyzed, from the perspective of MPLS, and it is deduced that tree-shapes in MP2P connections are irrelevant. By overriding this tree-shape consideration, it is possible to perform label merging in polynomial time. Based on how MPLS signaling works, this letter proposes an algorithm to compute the minimum number of labels using label merging: the Full Label Merging algorithm. As conclusion, we reclassify the Merging Problem as Polynomial-solvable, instead of NP-complete. In addition, simulation experiments confirm that without the tree-branch selection problem, more labels can be reduced

Transmission delays in residual computation

The design of control, estimation or diagnosis algorithms most often assumes that all available process variables represent the system state at the same instant of time. However, this is never true in current network systems, because of the unknown deterministic or stochastic transmission delays introduced by the communication network. During the diagnosing stage, this will often generate false alarms. Under nominal operation, the different transmission delays associated with the variables that appear in the computation form produce discrepancies of the residuals from zero. A technique aiming at the minimisation of the resulting false alarms rate, that is based on the explicit modelling of communication delays and on their best-case estimation is proposed