Szöllösi, Tomáš
2012-01-01
The first part of this work deals with the optimization and evolutionary algorithms which are used as a tool to solve complex optimization problems. The discussed algorithms are Differential Evolution, Genetic Algorithm, Simulated Annealing and deterministic non-evolutionary algorithm Taboo Search.. Consequently the discussion is held on the issue of testing the optimization algorithms through the use of the test function gallery and comparison solution all algorithms on Travelling salesman p...
Eremeev, Anton V.
2015-01-01
This manuscript contains an outline of lectures course "Evolutionary Algorithms" read by the author in Omsk State University n.a. F.M.Dostoevsky. The course covers Canonic Genetic Algorithm and various other genetic algorithms as well as evolutioanry algorithms in general. Some facts, such as the Rotation Property of crossover, the Schemata Theorem, GA performance as a local search and "almost surely" convergence of evolutionary algorithms are given with complete proofs. The text is in Russian.
Joux, Antoine
2009-01-01
Illustrating the power of algorithms, Algorithmic Cryptanalysis describes algorithmic methods with cryptographically relevant examples. Focusing on both private- and public-key cryptographic algorithms, it presents each algorithm either as a textual description, in pseudo-code, or in a C code program.Divided into three parts, the book begins with a short introduction to cryptography and a background chapter on elementary number theory and algebra. It then moves on to algorithms, with each chapter in this section dedicated to a single topic and often illustrated with simple cryptographic applic
Tel, G.
1993-01-01
We define the notion of total algorithms for networks of processes. A total algorithm enforces that a "decision" is taken by a subset of the processes, and that participation of all processes is required to reach this decision. Total algorithms are an important building block in the design of distri
Abrams, Daniel S.
This thesis describes several new quantum algorithms. These include a polynomial time algorithm that uses a quantum fast Fourier transform to find eigenvalues and eigenvectors of a Hamiltonian operator, and that can be applied in cases (commonly found in ab initio physics and chemistry problems) for which all known classical algorithms require exponential time. Fast algorithms for simulating many body Fermi systems are also provided in both first and second quantized descriptions. An efficient quantum algorithm for anti-symmetrization is given as well as a detailed discussion of a simulation of the Hubbard model. In addition, quantum algorithms that calculate numerical integrals and various characteristics of stochastic processes are described. Two techniques are given, both of which obtain an exponential speed increase in comparison to the fastest known classical deterministic algorithms and a quadratic speed increase in comparison to classical Monte Carlo (probabilistic) methods. I derive a simpler and slightly faster version of Grover's mean algorithm, show how to apply quantum counting to the problem, develop some variations of these algorithms, and show how both (apparently distinct) approaches can be understood from the same unified framework. Finally, the relationship between physics and computation is explored in some more depth, and it is shown that computational complexity theory depends very sensitively on physical laws. In particular, it is shown that nonlinear quantum mechanics allows for the polynomial time solution of NP-complete and #P oracle problems. Using the Weinberg model as a simple example, the explicit construction of the necessary gates is derived from the underlying physics. Nonlinear quantum algorithms are also presented using Polchinski type nonlinearities which do not allow for superluminal communication. (Copies available exclusively from MIT Libraries, Rm. 14- 0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
Hromkovic, Juraj
2009-01-01
Explores the science of computing. This book starts with the development of computer science, algorithms and programming, and then explains and shows how to exploit the concepts of infinity, computability, computational complexity, nondeterminism and randomness.
Hu, T C
2002-01-01
Newly enlarged, updated second edition of a valuable text presents algorithms for shortest paths, maximum flows, dynamic programming and backtracking. Also discusses binary trees, heuristic and near optimums, matrix multiplication, and NP-complete problems. 153 black-and-white illus. 23 tables.Newly enlarged, updated second edition of a valuable, widely used text presents algorithms for shortest paths, maximum flows, dynamic programming and backtracking. Also discussed are binary trees, heuristic and near optimums, matrix multiplication, and NP-complete problems. New to this edition: Chapter 9
Anna Bourmistrova; Milan Simic; Reza Hoseinnezhad; Jazar, Reza N.
2011-01-01
The autodriver algorithm is an intelligent method to eliminate the need of steering by a driver on a well-defined road. The proposed method performs best on a four-wheel steering (4WS) vehicle, though it is also applicable to two-wheel-steering (TWS) vehicles. The algorithm is based on coinciding the actual vehicle center of rotation and road center of curvature, by adjusting the kinematic center of rotation. The road center of curvature is assumed prior information for a given road, while th...
Directory of Open Access Journals (Sweden)
Anna Bourmistrova
2011-02-01
Full Text Available The autodriver algorithm is an intelligent method to eliminate the need of steering by a driver on a well-defined road. The proposed method performs best on a four-wheel steering (4WS vehicle, though it is also applicable to two-wheel-steering (TWS vehicles. The algorithm is based on coinciding the actual vehicle center of rotation and road center of curvature, by adjusting the kinematic center of rotation. The road center of curvature is assumed prior information for a given road, while the dynamic center of rotation is the output of dynamic equations of motion of the vehicle using steering angle and velocity measurements as inputs. We use kinematic condition of steering to set the steering angles in such a way that the kinematic center of rotation of the vehicle sits at a desired point. At low speeds the ideal and actual paths of the vehicle are very close. With increase of forward speed the road and tire characteristics, along with the motion dynamics of the vehicle cause the vehicle to turn about time-varying points. By adjusting the steering angles, our algorithm controls the dynamic turning center of the vehicle so that it coincides with the road curvature center, hence keeping the vehicle on a given road autonomously. The position and orientation errors are used as feedback signals in a closed loop control to adjust the steering angles. The application of the presented autodriver algorithm demonstrates reliable performance under different driving conditions.
DEFF Research Database (Denmark)
Markham, Annette
This paper takes an actor network theory approach to explore some of the ways that algorithms co-construct identity and relational meaning in contemporary use of social media. Based on intensive interviews with participants as well as activity logging and data tracking, the author presents a richly...... layered set of accounts to help build our understanding of how individuals relate to their devices, search systems, and social network sites. This work extends critical analyses of the power of algorithms in implicating the social self by offering narrative accounts from multiple perspectives. It also...... contributes an innovative method for blending actor network theory with symbolic interaction to grapple with the complexity of everyday sensemaking practices within networked global information flows....
Energy Technology Data Exchange (ETDEWEB)
Fontana, W.
1990-12-13
In this paper complex adaptive systems are defined by a self- referential loop in which objects encode functions that act back on these objects. A model for this loop is presented. It uses a simple recursive formal language, derived from the lambda-calculus, to provide a semantics that maps character strings into functions that manipulate symbols on strings. The interaction between two functions, or algorithms, is defined naturally within the language through function composition, and results in the production of a new function. An iterated map acting on sets of functions and a corresponding graph representation are defined. Their properties are useful to discuss the behavior of a fixed size ensemble of randomly interacting functions. This function gas'', or Turning gas'', is studied under various conditions, and evolves cooperative interaction patterns of considerable intricacy. These patterns adapt under the influence of perturbations consisting in the addition of new random functions to the system. Different organizations emerge depending on the availability of self-replicators.
Evolutionary Graph Drawing Algorithms
Institute of Scientific and Technical Information of China (English)
Huang Jing-wei; Wei Wen-fang
2003-01-01
In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.
Liu, Entao; Temlyakov, Vladimir N.
2010-01-01
We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy-type algorithms. We call such greedy algorithms {\\it super greedy algorithms}. The idea of picking several elements at a greedy step of the algorithm is not new. Recently, we observed the following new phenomenon. For incoherent dictionaries these new type of algorithms (super greedy algorithms) provide the same (in the sense of order) upper...
DEFF Research Database (Denmark)
This book constitutes the refereed proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, held in Riga, Latvia, in July 2006. The 36 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 154 submissions. The papers address all...... issues of theoretical algorithmics and applications in various fields including graph algorithms, computational geometry, scheduling, approximation algorithms, network algorithms, data storage and manipulation, combinatorics, sorting, searching, online algorithms, optimization, etc....
Converting online algorithms to local computation algorithms
Mansour, Yishay; Vardi, Shai; Xie, Ning
2012-01-01
We propose a general method for converting online algorithms to local computation algorithms by selecting a random permutation of the input, and simulating running the online algorithm. We bound the number of steps of the algorithm using a query tree, which models the dependencies between queries. We improve previous analyses of query trees on graphs of bounded degree, and extend the analysis to the cases where the degrees are distributed binomially, and to a special case of bipartite graphs. Using this method, we give a local computation algorithm for maximal matching in graphs of bounded degree, which runs in time and space O(log^3 n). We also show how to convert a large family of load balancing algorithms (related to balls and bins problems) to local computation algorithms. This gives several local load balancing algorithms which achieve the same approximation ratios as the online algorithms, but run in O(log n) time and space. Finally, we modify existing local computation algorithms for hypergraph 2-color...
Fister, Iztok; Yang, Xin-She; Fister, Dušan
2013-01-01
Swarm intelligence is a very powerful technique to be used for optimization purposes. In this paper we present a new swarm intelligence algorithm, based on the bat algorithm. The Bat algorithm is hybridized with differential evolution strategies. Besides showing very promising results of the standard benchmark functions, this hybridization also significantly improves the original bat algorithm.
Energy Technology Data Exchange (ETDEWEB)
Geist, G.A. [Oak Ridge National Lab., TN (United States). Computer Science and Mathematics Div.; Howell, G.W. [Florida Inst. of Tech., Melbourne, FL (United States). Dept. of Applied Mathematics; Watkins, D.S. [Washington State Univ., Pullman, WA (United States). Dept. of Pure and Applied Mathematics
1997-11-01
The BR algorithm, a new method for calculating the eigenvalues of an upper Hessenberg matrix, is introduced. It is a bulge-chasing algorithm like the QR algorithm, but, unlike the QR algorithm, it is well adapted to computing the eigenvalues of the narrowband, nearly tridiagonal matrices generated by the look-ahead Lanczos process. This paper describes the BR algorithm and gives numerical evidence that it works well in conjunction with the Lanczos process. On the biggest problems run so far, the BR algorithm beats the QR algorithm by a factor of 30--60 in computing time and a factor of over 100 in matrix storage space.
Priyamvada Paliwal#1, Meghna Sharma
2013-01-01
The DBSCAN algorithm can identify clusters in large spatial data sets by looking at the local density of database elements, using only one input parameter. This paper presents a comprehensive study of DBSCAN algorithm and the enhanced version of DBSCAN algorithm The salient of this paper to present enhanced DBSCAN algorithm with its implementation with the complexity and the difference between the older version of DBSCAN algorithm. And there are also additional features described with this al...
Algorithmically specialized parallel computers
Snyder, Lawrence; Gannon, Dennis B
1985-01-01
Algorithmically Specialized Parallel Computers focuses on the concept and characteristics of an algorithmically specialized computer.This book discusses the algorithmically specialized computers, algorithmic specialization using VLSI, and innovative architectures. The architectures and algorithms for digital signal, speech, and image processing and specialized architectures for numerical computations are also elaborated. Other topics include the model for analyzing generalized inter-processor, pipelined architecture for search tree maintenance, and specialized computer organization for raster
Overview: Evolutionary Algorithms
Bartz-Beielstein, Thomas (Dr.); Mersmann, Olaf
2014-01-01
Evolutionary algorithm (EA) is an umbrella term used to describe population-based stochastic direct search algorithms that in some sense mimic natural evolution. Prominent representatives of such algorithms are genetic algorithms, evolution strategies, evolutionary programming, and genetic programming. On the basis of the evolutionary cycle, similarities and differences between these algorithms are described. We briefly discuss how EAs can be adapted to work well in case of multiple objective...
Overview: Evolutionary Algorithms
Bartz-Beielstein, Thomas (Dr.); Branke, Jürgen; Mehnen, Jörn; Mersmann, Olaf
2015-01-01
Evolutionary algorithm (EA) is an umbrella term used to describe population-based stochastic direct search algorithms that in some sense mimic natural evolution. Prominent representatives of such algorithms are genetic algorithms, evolution strategies, evolutionary programming, and genetic programming. On the basis of the evolutionary cycle, similarities and differences between these algorithms are described. We briefly discuss how EAs can be adapted to work well in case of multiple objective...
Quantum Computation and Algorithms
International Nuclear Information System (INIS)
It is now firmly established that quantum algorithms provide a substantial speedup over classical algorithms for a variety of problems, including the factorization of large numbers and the search for a marked element in an unsorted database. In this talk I will review the principles of quantum algorithms, the basic quantum gates and their operation. The combination of superposition and interference, that makes these algorithms efficient, will be discussed. In particular, Grover's search algorithm will be presented as an example. I will show that the time evolution of the amplitudes in Grover's algorithm can be found exactly using recursion equations, for any initial amplitude distribution
New focused crawling algorithm
Institute of Scientific and Technical Information of China (English)
Su Guiyang; Li Jianhua; Ma Yinghua; Li Shenghong; Song Juping
2005-01-01
Focused carawling is a new research approach of search engine. It restricts information retrieval and provides search service in specific topic area. Focused crawling search algorithm is a key technique of focused crawler which directly affects the search quality. This paper first introduces several traditional topic-specific crawling algorithms, then an inverse link based topic-specific crawling algorithm is put forward. Comparison experiment proves that this algorithm has a good performance in recall, obviously better than traditional Breadth-First and Shark-Search algorithms. The experiment also proves that this algorithm has a good precision.
Symplectic algebraic dynamics algorithm
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the algebraic dynamics solution of ordinary differential equations andintegration of ,the symplectic algebraic dynamics algorithm sn is designed,which preserves the local symplectic geometric structure of a Hamiltonian systemand possesses the same precision of the na ve algebraic dynamics algorithm n.Computer experiments for the 4th order algorithms are made for five test modelsand the numerical results are compared with the conventional symplectic geometric algorithm,indicating that sn has higher precision,the algorithm-inducedphase shift of the conventional symplectic geometric algorithm can be reduced,and the dynamical fidelity can be improved by one order of magnitude.
Competing Sudakov Veto Algorithms
Kleiss, Ronald
2016-01-01
We present a way to analyze the distribution produced by a Monte Carlo algorithm. We perform these analyses on several versions of the Sudakov veto algorithm, adding a cutoff, a second variable and competition between emission channels. The analysis allows us to prove that multiple, seemingly different competition algorithms, including those that are currently implemented in most parton showers, lead to the same result. Finally, we test their performance and show that there are significantly faster alternatives to the commonly used algorithms.
Borbely, Eva
2007-01-01
A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. A quantum system can undergo two types of operation, measurement and quantum state transformation, operations themselves must be unitary (reversible). Most quantum algorithms involve a series of quantum state transformations followed by a measurement. Currently very few quantum algorithms are known and no general design methodology e...
Accurate Finite Difference Algorithms
Goodrich, John W.
1996-01-01
Two families of finite difference algorithms for computational aeroacoustics are presented and compared. All of the algorithms are single step explicit methods, they have the same order of accuracy in both space and time, with examples up to eleventh order, and they have multidimensional extensions. One of the algorithm families has spectral like high resolution. Propagation with high order and high resolution algorithms can produce accurate results after O(10(exp 6)) periods of propagation with eight grid points per wavelength.
Approximate iterative algorithms
Almudevar, Anthony Louis
2014-01-01
Iterative algorithms often rely on approximate evaluation techniques, which may include statistical estimation, computer simulation or functional approximation. This volume presents methods for the study of approximate iterative algorithms, providing tools for the derivation of error bounds and convergence rates, and for the optimal design of such algorithms. Techniques of functional analysis are used to derive analytical relationships between approximation methods and convergence properties for general classes of algorithms. This work provides the necessary background in functional analysis a
Autonomous Star Tracker Algorithms
DEFF Research Database (Denmark)
Betto, Maurizio; Jørgensen, John Leif; Kilsgaard, Søren;
1998-01-01
Proposal, in response to an ESA R.f.P., to design algorithms for autonomous star tracker operations.The proposal also included the development of a star tracker breadboard to test the algorithms performances.......Proposal, in response to an ESA R.f.P., to design algorithms for autonomous star tracker operations.The proposal also included the development of a star tracker breadboard to test the algorithms performances....
Hybridization of evolutionary algorithms
Fister, Iztok; Mernik, Marjan; Brest, Janez
2012-01-01
Evolutionary algorithms are good general problem solver but suffer from a lack of domain specific knowledge. However, the problem specific knowledge can be added to evolutionary algorithms by hybridizing. Interestingly, all the elements of the evolutionary algorithms can be hybridized. In this chapter, the hybridization of the three elements of the evolutionary algorithms is discussed: the objective function, the survivor selection operator and the parameter settings. As an objective function...
DEFF Research Database (Denmark)
Husfeldt, Thore
2015-01-01
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...... techniques and is organized by algorithmic paradigm....
Nature-inspired optimization algorithms
Yang, Xin-She
2014-01-01
Nature-Inspired Optimization Algorithms provides a systematic introduction to all major nature-inspired algorithms for optimization. The book's unified approach, balancing algorithm introduction, theoretical background and practical implementation, complements extensive literature with well-chosen case studies to illustrate how these algorithms work. Topics include particle swarm optimization, ant and bee algorithms, simulated annealing, cuckoo search, firefly algorithm, bat algorithm, flower algorithm, harmony search, algorithm analysis, constraint handling, hybrid methods, parameter tuning
Zhou, Xiaojun; Gui, Weihua
2012-01-01
In terms of the concepts of state and state transition, a new heuristic random search algorithm named state transition algorithm is proposed. For continuous function optimization problems, four special transformation operators called rotation, translation, expansion and axesion are designed. Adjusting measures of the transformations are mainly studied to keep the balance of exploration and exploitation. Convergence analysis is also discussed about the algorithm based on random search method. In the meanwhile, to strengthen the search ability in high dimensional space, communication strategy is introduced into the basic algorithm and intermittent exchange is presented to prevent premature convergence. Finally, experiments are carried out for the algorithms. With 10 common benchmark unconstrained continuous functions used to test the performance, the results show that state transition algorithms are promising algorithms due to their good global search capability and convergence property when compared with some ...
Deductive Algorithmic Knowledge
Pucella, Riccardo
2004-01-01
The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge with the latter defined with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of ...
Fingerprint Feature Extraction Algorithm
Directory of Open Access Journals (Sweden)
Mehala. G
2014-03-01
Full Text Available The goal of this paper is to design an efficient Fingerprint Feature Extraction (FFE algorithm to extract the fingerprint features for Automatic Fingerprint Identification Systems (AFIS. FFE algorithm, consists of two major subdivisions, Fingerprint image preprocessing, Fingerprint image postprocessing. A few of the challenges presented in an earlier are, consequently addressed, in this paper. The proposed algorithm is able to enhance the fingerprint image and also extracting true minutiae.
Recursive forgetting algorithms
DEFF Research Database (Denmark)
Parkum, Jens; Poulsen, Niels Kjølstad; Holst, Jan
1992-01-01
In the first part of the paper, a general forgetting algorithm is formulated and analysed. It contains most existing forgetting schemes as special cases. Conditions are given ensuring that the basic convergence properties will hold. In the second part of the paper, the results are applied to a...... specific algorithm with selective forgetting. Here, the forgetting is non-uniform in time and space. The theoretical analysis is supported by a simulation example demonstrating the practical performance of this algorithm...
Fingerprint Feature Extraction Algorithm
Mehala. G
2014-01-01
The goal of this paper is to design an efficient Fingerprint Feature Extraction (FFE) algorithm to extract the fingerprint features for Automatic Fingerprint Identification Systems (AFIS). FFE algorithm, consists of two major subdivisions, Fingerprint image preprocessing, Fingerprint image postprocessing. A few of the challenges presented in an earlier are, consequently addressed, in this paper. The proposed algorithm is able to enhance the fingerprint image and also extractin...
Integer factorization algorithms
Bogataj, Polona
2011-01-01
The decomposition of a natural number into a product of prime numbers is called factorization. The main problem with factorization is the fact that there is no known efficient algorithm which would factor a given natural number n in polynomial time. The closest equivalent to such an algorithm is Shor's algorithm for quantum computers, which is still not practically applicable. The difficulties with factorization form the basis for modern cryptosystems—the most renowned among them is the RSA a...
Introduction to Evolutionary Algorithms
Yu, Xinjie
2010-01-01
Evolutionary algorithms (EAs) are becoming increasingly attractive for researchers from various disciplines, such as operations research, computer science, industrial engineering, electrical engineering, social science, economics, etc. This book presents an insightful, comprehensive, and up-to-date treatment of EAs, such as genetic algorithms, differential evolution, evolution strategy, constraint optimization, multimodal optimization, multiobjective optimization, combinatorial optimization, evolvable hardware, estimation of distribution algorithms, ant colony optimization, particle swarm opti
Recursive forgetting algorithms
DEFF Research Database (Denmark)
Parkum, Jens; Poulsen, Niels Kjølstad; Holst, Jan
1992-01-01
In the first part of the paper, a general forgetting algorithm is formulated and analysed. It contains most existing forgetting schemes as special cases. Conditions are given ensuring that the basic convergence properties will hold. In the second part of the paper, the results are applied...... to a specific algorithm with selective forgetting. Here, the forgetting is non-uniform in time and space. The theoretical analysis is supported by a simulation example demonstrating the practical performance of this algorithm...
Spectral Decomposition Algorithm (SDA)
National Aeronautics and Space Administration — Spectral Decomposition Algorithm (SDA) is an unsupervised feature extraction technique similar to PCA that was developed to better distinguish spectral features in...
Explaining algorithms using metaphors
Forišek, Michal
2013-01-01
There is a significant difference between designing a new algorithm, proving its correctness, and teaching it to an audience. When teaching algorithms, the teacher's main goal should be to convey the underlying ideas and to help the students form correct mental models related to the algorithm. This process can often be facilitated by using suitable metaphors. This work provides a set of novel metaphors identified and developed as suitable tools for teaching many of the 'classic textbook' algorithms taught in undergraduate courses worldwide. Each chapter provides exercises and didactic notes fo
Evolutionary Algorithm Definition
Directory of Open Access Journals (Sweden)
Nada M.A. AL-Salami
2009-01-01
Full Text Available Problem statement: Most resent evolutionary algorithms work under weak theoretical basis and thus, they are computationally expensive. Approach: This study discussed the use of new evolutionary algorithm for automatic programming, based on theoretical definitions of program behaviors. Evolutionary process adapted fixed and self-organized input-output specification of the problem, to evolve good finite state machine that efficiently satisfies these specifications. Results: The proposed algorithm enhanced evolutionary process by simultaneously solving multi-parts from the same problem. Conclusion: The probability that the algorithm will converge to the optimal solution was highly enhanced when decomposing the main problem into multi-part.
Parallel Algorithms for Normalization
Boehm, Janko; Laplagne, Santiago; Pfister, Gerhard; Steenpass, Andreas; Steidel, Stefan
2011-01-01
Given a reduced affine algebra A over a perfect field K, we present parallel algorithms to compute the normalization \\bar{A} of A. Our starting point is the algorithm of Greuel, Laplagne, and Seelisch, which is an improvement of de Jong's algorithm. First, we propose to stratify the singular locus Sing(A) in a way which is compatible with normalization, apply a local version of the normalization algorithm at each stratum, and find \\bar{A} by putting the local results together. Second, in the case where K = Q is the field of rationals, we propose modular versions of the global and local algorithms. We have implemented our algorithms in the computer algebra system SINGULAR and compare their performance with that of other algorithms. In the case where K = Q, we also discuss the use of modular computations of Groebner bases, radicals and primary decompositions. We point out that in most examples, the new algorithms outperform the algorithm of Greuel, Laplagne, and Seelisch by far, even if we do not run them in pa...
Fatigue Evaluation Algorithms: Review
DEFF Research Database (Denmark)
Passipoularidis, Vaggelis; Brøndsted, Povl
rotor blade construction. Two versions of the algorithm, the one using single-step and the other using incremental application of each load cycle (in case of ply failure) are implemented and compared. Simulation results confirm the ability of the algorithm to take into account load sequence effects. In...
Kreutzer, Stephan
2009-01-01
Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a "logical" and a "structural" component, that is they are results of the form: every computational problem that can be formalised in a given logic L can be solved efficiently on every class C of structures satisfying certain conditions. This paper gives a survey of algorithmic meta-theorems obtained in recent years and the methods used to prove them. As many meta-theorems use results from graph minor theory, we give a brief introduction to the theory developed by Robertson and Seymour for their proof of the graph minor theorem and state the main algorithmic consequences of this theory as far as they are needed in the theory of algorithmic meta-theorems.
A New Modified Firefly Algorithm
Directory of Open Access Journals (Sweden)
Medha Gupta
2016-07-01
Full Text Available Nature inspired meta-heuristic algorithms studies the emergent collective intelligence of groups of simple agents. Firefly Algorithm is one of the new such swarm-based metaheuristic algorithm inspired by the flashing behavior of fireflies. The algorithm was first proposed in 2008 and since then has been successfully used for solving various optimization problems. In this work, we intend to propose a new modified version of Firefly algorithm (MoFA and later its performance is compared with the standard firefly algorithm along with various other meta-heuristic algorithms. Numerical studies and results demonstrate that the proposed algorithm is superior to existing algorithms.
Directory of Open Access Journals (Sweden)
Hans Schonemann
1996-12-01
Full Text Available Some algorithms for singularity theory and algebraic geometry The use of Grobner basis computations for treating systems of polynomial equations has become an important tool in many areas. This paper introduces of the concept of standard bases (a generalization of Grobner bases and the application to some problems from algebraic geometry. The examples are presented as SINGULAR commands. A general introduction to Grobner bases can be found in the textbook [CLO], an introduction to syzygies in [E] and [St1]. SINGULAR is a computer algebra system for computing information about singularities, for use in algebraic geometry. The basic algorithms in SINGULAR are several variants of a general standard basis algorithm for general monomial orderings (see [GG]. This includes wellorderings (Buchberger algorithm ([B1], [B2] and tangent cone orderings (Mora algorithm ([M1], [MPT] as special cases: It is able to work with non-homogeneous and homogeneous input and also to compute in the localization of the polynomial ring in 0. Recent versions include algorithms to factorize polynomials and a factorizing Grobner basis algorithm. For a complete description of SINGULAR see [Si].
Comparison Study for Clonal Selection Algorithm and Genetic Algorithm
Ezgi Deniz Ulker; Sadık Ulker
2012-01-01
Two metaheuristic algorithms namely Artificial Immune Systems (AIS) and Genetic Algorithms are classified as computational systems inspired by theoretical immunology and genetics mechanisms. In this work we examine the comparative performances of two algorithms. A special selection algorithm, Clonal Selection Algorithm (CLONALG), which is a subset of Artificial Immune Systems, and Genetic Algorithms are tested with certain benchmark functions. It is shown that depending on type of a function ...
Diagnostic Algorithm Benchmarking
Poll, Scott
2011-01-01
A poster for the NASA Aviation Safety Program Annual Technical Meeting. It describes empirical benchmarking on diagnostic algorithms using data from the ADAPT Electrical Power System testbed and a diagnostic software framework.
Unsupervised learning algorithms
Aydin, Kemal
2016-01-01
This book summarizes the state-of-the-art in unsupervised learning. The contributors discuss how with the proliferation of massive amounts of unlabeled data, unsupervised learning algorithms, which can automatically discover interesting and useful patterns in such data, have gained popularity among researchers and practitioners. The authors outline how these algorithms have found numerous applications including pattern recognition, market basket analysis, web mining, social network analysis, information retrieval, recommender systems, market research, intrusion detection, and fraud detection. They present how the difficulty of developing theoretically sound approaches that are amenable to objective evaluation have resulted in the proposal of numerous unsupervised learning algorithms over the past half-century. The intended audience includes researchers and practitioners who are increasingly using unsupervised learning algorithms to analyze their data. Topics of interest include anomaly detection, clustering,...
A Simple Calculator Algorithm.
Cook, Lyle; McWilliam, James
1983-01-01
The problem of finding cube roots when limited to a calculator with only square root capability is discussed. An algorithm is demonstrated and explained which should always produce a good approximation within a few iterations. (MP)
International Nuclear Information System (INIS)
The δf Algorithm is a low noise particle code algorithm. The perturbation of the distribution function (δf) away from a large equilibrium is evolved rather than the total distribution function. ''Particles'' in the code are actually Lagrangian markers at which the value of the distribution functalon is known. The magnitude of the numerical noise is characteristic of the size of the perturbation rather than the equilibrium, and scales roughly as the inverse of the number of particles. In this paper. the algorithm is described. and conserved energies are derived for linear and nonlinear sets of equations. Two different forms of the energy principle test separately adequate resolution in time and space and adequacy of the number of simulation particles. A semi-implicit time step method is described which allows violation of the Courant condition. Low noise capabilities of a linear code using the algorithm are demonstrated
A more robust boosting algorithm
Freund, Yoav
2009-01-01
We present a new boosting algorithm, motivated by the large margins theory for boosting. We give experimental evidence that the new algorithm is significantly more robust against label noise than existing boosting algorithm.
Quantum algorithmic information theory
Svozil, Karl
1995-01-01
The agenda of quantum algorithmic information theory, ordered `top-down,' is the quantum halting amplitude, followed by the quantum algorithmic information content, which in turn requires the theory of quantum computation. The fundamental atoms processed by quantum computation are the quantum bits which are dealt with in quantum information theory. The theory of quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capa...
Algorithmic Problem Complexity
Burgin, Mark
2008-01-01
People solve different problems and know that some of them are simple, some are complex and some insoluble. The main goal of this work is to develop a mathematical theory of algorithmic complexity for problems. This theory is aimed at determination of computer abilities in solving different problems and estimation of resources that computers need to do this. Here we build the part of this theory related to static measures of algorithms. At first, we consider problems for finite words and stud...
The proximal distance algorithm
Lange, Kenneth; Keys, Kevin L.
2015-01-01
The MM principle is a device for creating optimization algorithms satisfying the ascent or descent property. The current survey emphasizes the role of the MM principle in nonlinear programming. For smooth functions, one can construct an adaptive interior point method based on scaled Bregmann barriers. This algorithm does not follow the central path. For convex programming subject to nonsmooth constraints, one can combine an exact penalty method with distance majorization to create versatile a...
Incremental algorithms on lists
Jeuring, J.T.
2007-01-01
Incremental computations can improve the performance of interactive programs such as spreadsheet programs, program development environments, text editors, etc. Incremental algorithms describe how to compute a required value depending on the input, after the input has been edited. By considering the possible different edit actions on the data type lists, the basic data type used in spreadsheet programs and text editors, we define incremental algorithms on lists. Some theory for the constructio...
Multicanonical Cluster Algorithm
Rummukainen, K.
1992-01-01
In this talk I present a multicanonical hybrid-like two-step algorithm, which consists of a microcanonical spin system update with demons, and a multicanonical demon refresh. The demons act as a buffer between the multicanonical heat bath and the spin system, allowing for a large variety of update schemes. In this work the cluster algorithm is demonstrated with the 2-dimensional 7-state Potts model, using volumes up to $128^2$.
Institute of Scientific and Technical Information of China (English)
WANG Ji-Ke; MAO Ze-Pu; BIAN Jian-Ming; CAO Guo-Fu; CAO Xue-Xiang; CHEN Shen-Jian; DENG Zi-Yan; FU Cheng-Dong; GAO Yuan-Ning; HE Kang-Lin; HE Miao; HUA Chun-Fei; HUANG Bin; HUANG Xing-Tao; JI Xiao-Sin; LI Fei; LI Hai-Bo; LI Wei-Dong; LIANG Yu-Tie; LIU Chun-Xiu; LIU Huai-Min; LIU Suo; LIU Ying-Jie; MA Qiu-Mei; MA Xiang; MAO Ya-Jun; MO Xiao-Hu; PAN Ming-Hua; PANG Cai-Ying; PING Rong-Gang; QIN Ya-Hong; QIU Jin-Fa; SUN Sheng-Sen; SUN Yong-Zhao; WANG Liang-Liang; WEN Shuo-Pin; WU Ling-Hui; XIE Yu-Guang; XU Min; YAN Liang; YOU Zheng-Yun; YUAN Chang-Zheng; YUAN Ye; ZHANG Bing-Yun; ZHANG Chang-Chun; ZHANG Jian-Yong; ZHANG Xue-Yao; ZHANG Yao; ZHENG Yang-Heng; ZHU Ke-Jun; ZHU Yong-Sheng; ZHU Zhi-Li; ZOU Jia-Heng
2009-01-01
A track fitting algorithm based on the Kalman filter method has been developed for BESⅢ of BEPCⅡ.The effects of multiple scattering and energy loss when the charged particles go through the detector,non-uniformity of magnetic field (NUMF) and wire sag, etc., have been carefully handled.This algorithm works well and the performance satisfies the physical requirements tested by the simulation data.
Local approximate inference algorithms
Jung, Kyomin; Shah, Devavrat
2006-01-01
We present a new local approximation algorithm for computing Maximum a Posteriori (MAP) and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\\em appropriately} chosen small components; then computing estimates locally in each of these components and then producing a {\\em good} global solution. We show that if the underlying graph $G$ either excl...
Milani, Alfredo
2004-01-01
This paper present a technique based on genetic algorithms for generating online adaptive services. Online adaptive systems provide flexible services to a mass of clients/users for maximising some system goals, they dynamically adapt the form and the content of the issued services while the population of clients evolve over time. The idea of online genetic algorithms (online GAs) is to use the online clients response behaviour as a fitness function in order to produce the next ...
Institute of Scientific and Technical Information of China (English)
无
2008-01-01
The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper, we introduce the motif tracking algorithm (MTA), a novel immune inspired (IS) pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases, the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilization of an intuitive symbolic representation.The resulting population of motifs is shown to have considerable potential value for other applications such as forecasting and algorithm seeding.
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the exact analytical solution of ordinary differential equations, a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm. A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models. The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision, and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Institute of Scientific and Technical Information of China (English)
WANG ShunJin; ZHANG Hua
2007-01-01
Based on the exact analytical solution of ordinary differential equations,a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm.A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models.The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision,and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
A Parallel Butterfly Algorithm
Poulson, Jack
2014-02-04
The butterfly algorithm is a fast algorithm which approximately evaluates a discrete analogue of the integral transform (Equation Presented.) at large numbers of target points when the kernel, K(x, y), is approximately low-rank when restricted to subdomains satisfying a certain simple geometric condition. In d dimensions with O(Nd) quasi-uniformly distributed source and target points, when each appropriate submatrix of K is approximately rank-r, the running time of the algorithm is at most O(r2Nd logN). A parallelization of the butterfly algorithm is introduced which, assuming a message latency of α and per-process inverse bandwidth of β, executes in at most (Equation Presented.) time using p processes. This parallel algorithm was then instantiated in the form of the open-source DistButterfly library for the special case where K(x, y) = exp(iΦ(x, y)), where Φ(x, y) is a black-box, sufficiently smooth, real-valued phase function. Experiments on Blue Gene/Q demonstrate impressive strong-scaling results for important classes of phase functions. Using quasi-uniform sources, hyperbolic Radon transforms, and an analogue of a three-dimensional generalized Radon transform were, respectively, observed to strong-scale from 1-node/16-cores up to 1024-nodes/16,384-cores with greater than 90% and 82% efficiency, respectively. © 2014 Society for Industrial and Applied Mathematics.
Wilson, William; Aickelin, Uwe; 10.1007/s11633.008.0032.0
2010-01-01
The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper we introduce the Motif Tracking Algorithm, a novel immune inspired pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilisation of an intuitive symbolic representation. The resulting population of motifs is shown to have considerable potential value for other ap...
DEFF Research Database (Denmark)
Vissing, S.; Hededal, O.
An algorithm is presented for computing the m smallest eigenvalues and corresponding eigenvectors of the generalized eigenvalue problem (A - λB)Φ = 0 where A and B are real n x n symmetric matrices. In an iteration scheme the matrices A and B are projected simultaneously onto an m-dimensional sub......An algorithm is presented for computing the m smallest eigenvalues and corresponding eigenvectors of the generalized eigenvalue problem (A - λB)Φ = 0 where A and B are real n x n symmetric matrices. In an iteration scheme the matrices A and B are projected simultaneously onto an m......-dimensional subspace in order to establish and solve a symmetric generalized eigenvalue problem in the subspace. The algorithm is described in pseudo code and implemented in the C programming language for lower triangular matrices A and B. The implementation includes procedures for selecting initial iteration vectors...
Handbook of Memetic Algorithms
Cotta, Carlos; Moscato, Pablo
2012-01-01
Memetic Algorithms (MAs) are computational intelligence structures combining multiple and various operators in order to address optimization problems. The combination and interaction amongst operators evolves and promotes the diffusion of the most successful units and generates an algorithmic behavior which can handle complex objective functions and hard fitness landscapes. “Handbook of Memetic Algorithms” organizes, in a structured way, all the the most important results in the field of MAs since their earliest definition until now. A broad review including various algorithmic solutions as well as successful applications is included in this book. Each class of optimization problems, such as constrained optimization, multi-objective optimization, continuous vs combinatorial problems, uncertainties, are analysed separately and, for each problem, memetic recipes for tackling the difficulties are given with some successful examples. Although this book contains chapters written by multiple authors, ...
CERN. Geneva; PUNZI, Giovanni
2015-01-01
Charge particle reconstruction is one of the most demanding computational tasks found in HEP, and it becomes increasingly important to perform it in real time. We envision that HEP would greatly benefit from achieving a long-term goal of making track reconstruction happen transparently as part of the detector readout ("detector-embedded tracking"). We describe here a track-reconstruction approach based on a massively parallel pattern-recognition algorithm, inspired by studies of the processing of visual images by the brain as it happens in nature ('RETINA algorithm'). It turns out that high-quality tracking in large HEP detectors is possible with very small latencies, when this algorithm is implemented in specialized processors, based on current state-of-the-art, high-speed/high-bandwidth digital devices.
Temperature Corrected Bootstrap Algorithm
Comiso, Joey C.; Zwally, H. Jay
1997-01-01
A temperature corrected Bootstrap Algorithm has been developed using Nimbus-7 Scanning Multichannel Microwave Radiometer data in preparation to the upcoming AMSR instrument aboard ADEOS and EOS-PM. The procedure first calculates the effective surface emissivity using emissivities of ice and water at 6 GHz and a mixing formulation that utilizes ice concentrations derived using the current Bootstrap algorithm but using brightness temperatures from 6 GHz and 37 GHz channels. These effective emissivities are then used to calculate surface ice which in turn are used to convert the 18 GHz and 37 GHz brightness temperatures to emissivities. Ice concentrations are then derived using the same technique as with the Bootstrap algorithm but using emissivities instead of brightness temperatures. The results show significant improvement in the area where ice temperature is expected to vary considerably such as near the continental areas in the Antarctic, where the ice temperature is colder than average, and in marginal ice zones.
Tiled QR factorization algorithms
Bouwmeester, Henricus; Langou, Julien; Robert, Yves
2011-01-01
This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, Greedy, and those found within PLASMA. Although neither Modi and Clarke nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q^2 f(q), where f is any function such that \\lim_{+\\infty} f= 0. This novel and important complexity result applies to all matrices where p and q are proportional, p = \\lambda q, with \\lambda >= 1, thereby encompassing many important situations in practice (least squares). We provide an extensive set of experiments that show the superiority of the new algorithms for tall matrices.
Algorithms for Global Positioning
DEFF Research Database (Denmark)
Borre, Kai; Strang, Gilbert
The emergence of satellite technology has changed the lives of millions of people. In particular, GPS has brought an unprecedented level of accuracy to the field of geodesy. This text is a guide to the algorithms and mathematical principles that account for the success of GPS technology and repla......The emergence of satellite technology has changed the lives of millions of people. In particular, GPS has brought an unprecedented level of accuracy to the field of geodesy. This text is a guide to the algorithms and mathematical principles that account for the success of GPS technology....... At the heart of the matter are the positioning algorithms on which GPS technology relies, the discussion of which will affirm the mathematical contents of the previous chapters. Numerous ready-to-use MATLAB codes are included for the reader. This comprehensive guide will be invaluable for engineers...
Fusion of motion segmentation algorithms
Ellis, Anna-Louise
2008-01-01
Many algorithms have been developed to achieve motion segmentation for video surveillance. The algorithms produce varying performances under the infinite amount of changing conditions. It has been recognised that individually these algorithms have useful properties. Fusing the statistical result of these algorithms is investigated, with robust motion segmentation in mind.
Quantum CPU and Quantum Algorithm
Wang, An Min
1999-01-01
Making use of an universal quantum network -- QCPU proposed by me\\upcite{My1}, it is obtained that the whole quantum network which can implement some the known quantum algorithms including Deutsch algorithm, quantum Fourier transformation, Shor's algorithm and Grover's algorithm.
An Improved Algorithm of Apriori
Liao, Binhua
This paper puts forward a kind of improved algorithm after analyzing the classical Apriori algorithm. Through scanning database only once, all transactions are transformed into components of a two-dimensional array. The algorithm becomes more practical by introducing weight. Moreover, the unnecessary data are deleted in time, and the joining and pruning steps become simple. This, therefore, improves the efficiency of Apriori algorithm.
Yet Another Efficient Unification Algorithm
Suciu, Alin
2006-01-01
The unification algorithm is at the core of the logic programming paradigm, the first unification algorithm being developed by Robinson [5]. More efficient algorithms were developed later [3] and I introduce here yet another efficient unification algorithm centered on a specific data structure, called the Unification Table.
A Generalized Jacobi Algorithm
DEFF Research Database (Denmark)
Vissing, S.; Krenk, S.
An algorithm is developed for the generalized eigenvalue problem (A - λB)φ = O where A and B are real symmetric matrices. The matrices A and B are diagonalized simultaneously by a series of generalized Jacobi transformations and all eigenvalues and eigenvectors are obtained. A criterion expressed...... in terms of the transformation parameters is used to omit transformations leading to very small changes. The algorithm is described in pseudo code for lower triangular matrices A and B and implemented in the programming Language C....
Fast Local Computation Algorithms
Rubinfeld, Ronitt; Tamir, Gil; Vardi, Shai; Xie, Ning
2011-01-01
For input $x$, let $F(x)$ denote the set of outputs that are the "legal" answers for a computational problem $F$. Suppose $x$ and members of $F(x)$ are so large that there is not time to read them in their entirety. We propose a model of {\\em local computation algorithms} which for a given input $x$, support queries by a user to values of specified locations $y_i$ in a legal output $y \\in F(x)$. When more than one legal output $y$ exists for a given $x$, the local computation algorithm should...
Algorithms for Reinforcement Learning
Szepesvari, Csaba
2010-01-01
Reinforcement learning is a learning paradigm concerned with learning to control a system so as to maximize a numerical performance measure that expresses a long-term objective. What distinguishes reinforcement learning from supervised learning is that only partial feedback is given to the learner about the learner's predictions. Further, the predictions may have long term effects through influencing the future state of the controlled system. Thus, time plays a special role. The goal in reinforcement learning is to develop efficient learning algorithms, as well as to understand the algorithms'
Wireless communications algorithmic techniques
Vitetta, Giorgio; Colavolpe, Giulio; Pancaldi, Fabrizio; Martin, Philippa A
2013-01-01
This book introduces the theoretical elements at the basis of various classes of algorithms commonly employed in the physical layer (and, in part, in MAC layer) of wireless communications systems. It focuses on single user systems, so ignoring multiple access techniques. Moreover, emphasis is put on single-input single-output (SISO) systems, although some relevant topics about multiple-input multiple-output (MIMO) systems are also illustrated.Comprehensive wireless specific guide to algorithmic techniquesProvides a detailed analysis of channel equalization and channel coding for wi
Tiled QR factorization algorithms
Bouwmeester, Henricus; Jacquelin, Mathias; Langou, Julien; Robert, Yves
2011-01-01
This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, Greedy, and those found within PLASMA. Although neither Modi and Clarke nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q^2 f(q), where f is any function such that \\lim_{+\\infty} f= 0. This novel and...
Algorithm for structure constants
Paiva, F M
2011-01-01
In a $n$-dimensional Lie algebra, random numerical values are assigned by computer to $n(n-1)$ especially selected structure constants. An algorithm is then created, which calculates without ambiguity the remaining constants, obeying the Jacobi conditions. Differently from others, this algorithm is suitable even for poor personal computer. ------------- En $n$-dimensia algebro de Lie, hazardaj numeraj valoroj estas asignitaj per komputilo al $n(n-1)$ speciale elektitaj konstantoj de strukturo. Tiam algoritmo estas kreita, kalkulante senambigue la ceterajn konstantojn, obeante kondicxojn de Jacobi. Malsimile al aliaj algoritmoj, tiu cxi tauxgas ecx por malpotenca komputilo.
Parallel Algorithms and Patterns
Energy Technology Data Exchange (ETDEWEB)
Robey, Robert W. [Los Alamos National Lab. (LANL), Los Alamos, NM (United States)
2016-06-16
This is a powerpoint presentation on parallel algorithms and patterns. A parallel algorithm is a well-defined, step-by-step computational procedure that emphasizes concurrency to solve a problem. Examples of problems include: Sorting, searching, optimization, matrix operations. A parallel pattern is a computational step in a sequence of independent, potentially concurrent operations that occurs in diverse scenarios with some frequency. Examples are: Reductions, prefix scans, ghost cell updates. We only touch on parallel patterns in this presentation. It really deserves its own detailed discussion which Gabe Rockefeller would like to develop.
New Effective Multithreaded Matching Algorithms
Energy Technology Data Exchange (ETDEWEB)
Manne, Fredrik; Halappanavar, Mahantesh
2014-05-19
Matching is an important combinatorial problem with a number of applications in areas such as community detection, sparse linear algebra, and network alignment. Since computing optimal matchings can be very time consuming, several fast approximation algorithms, both sequential and parallel, have been suggested. Common to the algorithms giving the best solutions is that they tend to be sequential by nature, while algorithms more suitable for parallel computation give solutions of less quality. We present a new simple 1 2 -approximation algorithm for the weighted matching problem. This algorithm is both faster than any other suggested sequential 1 2 -approximation algorithm on almost all inputs and also scales better than previous multithreaded algorithms. We further extend this to a general scalable multithreaded algorithm that computes matchings of weight comparable with the best sequential algorithms. The performance of the suggested algorithms is documented through extensive experiments on different multithreaded architectures.
An Ordering Linear Unification Algorithm
Institute of Scientific and Technical Information of China (English)
胡运发
1989-01-01
In this paper,we present an ordering linear unification algorithm(OLU).A new idea on substituteion of the binding terms is introduced to the algorithm,which is able to overcome some drawbacks of other algorithms,e.g.,MM algorithm[1],RG1 and RG2 algorithms[2],Particularly,if we use the directed eyclie graphs,the algoritm needs not check the binding order,then the OLU algorithm can also be aplied to the infinite tree data struceture,and a higher efficiency can be expected.The paper focuses upon the discussion of OLU algorithm and a partial order structure with respect to the unification algorithm.This algorithm has been implemented in the GKD-PROLOG/VAX 780 interpreting system.Experimental results have shown that the algorithm is very simple and efficient.
A Panoply of Quantum Algorithms
Furrow, Bartholomew
2006-01-01
We create a variety of new quantum algorithms that use Grover's algorithm and similar techniques to give polynomial speedups over their classical counterparts. We begin by introducing a set of tools that carefully minimize the impact of errors on running time; those tools provide us with speedups to already-published quantum algorithms, such as improving Durr, Heiligman, Hoyer and Mhalla's algorithm for single-source shortest paths [quant-ph/0401091] by a factor of lg N. The algorithms we con...
Fuzzy Priority CPU Scheduling Algorithm
Bashir Alam; M.N. Doja; R. Biswas; Mansaf Alam
2011-01-01
There are several CPU scheduling algorithms like FCFS, SRTN,RR , priority etc. Scheduling decision of these algorithms are based on parameters which are assumed to be crisp. However, in many circumstances these parameters are vague. The vagueness of these parameters suggests that scheduler should use fuzzy logic in scheduling the jobs. A fuzzy priority CPU scheduling algorithm has been proposed. This proposed algorithm improves the priority based CPU scheduling algorithm as obvious from simul...
The Middle Pivot Element Algorithm
Anchala Kumari; Soubhik Chakraborty
2012-01-01
This paper is an improvement over the previous work on New Sorting Algorithm first proposed by Sundararajan and Chakraborty (2007). Here we have taken the pivot element as the middle element of the array. We call this improved version Middle Pivot Element Algorithm (MPA) and it is found that MPA is much faster than the two algorithms RPA (Random Pivot element Algorithm) and FPA (First Pivot element Algorithm) in which the pivot element was selected either randomly or as the first element, res...
Thulasiraman, K
2011-01-01
This adaptation of an earlier work by the authors is a graduate text and professional reference on the fundamentals of graph theory. It covers the theory of graphs, its applications to computer networks and the theory of graph algorithms. Also includes exercises and an updated bibliography.
de Casteljau's Algorithm Revisited
DEFF Research Database (Denmark)
Gravesen, Jens
1998-01-01
It is demonstrated how all the basic properties of Bezier curves can be derived swiftly and efficiently without any reference to the Bernstein polynomials and essentially with only geometric arguments. This is achieved by viewing one step in de Casteljau's algorithm as an operator (the de Casteljau...
Multisource Algorithmic Information Theory
Shen, Alexander
2006-01-01
Multisource information theory is well known in Shannon setting. It studies the possibilities of information transfer through a network with limited capacities. Similar questions could be studied for algorithmic information theory and provide a framework for several known results and interesting questions.
Sorting Algorithms with Restrictions
Aslanyan, Hakob
2011-01-01
Sorting is one of the most used and well investigated algorithmic problem [1]. Traditional postulation supposes the sorting data archived, and the elementary operation as comparisons of two numbers. In a view of appearance of new processors and applied problems with data streams, sorting changed its face. This changes and generalizations are the subject of investigation in the research below.
de Casteljau's Algorithm Revisited
DEFF Research Database (Denmark)
Gravesen, Jens
It is demonstrated how all the basic properties of Bezier curves can be derived swiftly and efficiently without any reference to the Bernstein polynomials and essentially with only geometric arguments. This is achieved by viewing one step in de Casteljau's algorithm as an operator (the de Casteljau...
Drake, Michael
2011-01-01
One debate that periodically arises in mathematics education is the issue of how to teach calculation more effectively. "Modern" approaches seem to initially favour mental calculation, informal methods, and the development of understanding before introducing written forms, while traditionalists tend to champion particular algorithms. The debate is…
The Xmath Integration Algorithm
Bringslid, Odd
2009-01-01
The projects Xmath (Bringslid and Canessa, 2002) and dMath (Bringslid, de la Villa and Rodriguez, 2007) were supported by the European Commission in the so called Minerva Action (Xmath) and The Leonardo da Vinci programme (dMath). The Xmath eBook (Bringslid, 2006) includes algorithms into a wide range of undergraduate mathematical issues embedded…
General cardinality genetic algorithms
Koehler; Bhattacharyya; Vose
1997-01-01
A complete generalization of the Vose genetic algorithm model from the binary to higher cardinality case is provided. Boolean AND and EXCLUSIVE-OR operators are replaced by multiplication and addition over rings of integers. Walsh matrices are generalized with finite Fourier transforms for higher cardinality usage. Comparison of results to the binary case are provided. PMID:10021767
Modular Regularization Algorithms
DEFF Research Database (Denmark)
Jacobsen, Michael
2004-01-01
The class of linear ill-posed problems is introduced along with a range of standard numerical tools and basic concepts from linear algebra, statistics and optimization. Known algorithms for solving linear inverse ill-posed problems are analyzed to determine how they can be decomposed into indepen......The class of linear ill-posed problems is introduced along with a range of standard numerical tools and basic concepts from linear algebra, statistics and optimization. Known algorithms for solving linear inverse ill-posed problems are analyzed to determine how they can be decomposed...... into independent modules. These modules are then combined to form new regularization algorithms with other properties than those we started out with. Several variations are tested using the Matlab toolbox MOORe Tools created in connection with this thesis. Object oriented programming techniques are explained...... and used to set up the illposed problems in the toolbox. Hereby, we are able to write regularization algorithms that automatically exploit structure in the ill-posed problem without being rewritten explicitly. We explain how to implement a stopping criteria for a parameter choice method based upon...
Python algorithms mastering basic algorithms in the Python language
Hetland, Magnus Lie
2014-01-01
Python Algorithms, Second Edition explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques. The book deals with some of the most important and challenging areas of programming and computer science in a highly readable manner. It covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs. Well-known algorithms and data struc
Benchmarking monthly homogenization algorithms
Directory of Open Access Journals (Sweden)
V. K. C. Venema
2011-08-01
Full Text Available The COST (European Cooperation in Science and Technology Action ES0601: Advances in homogenization methods of climate series: an integrated approach (HOME has executed a blind intercomparison and validation study for monthly homogenization algorithms. Time series of monthly temperature and precipitation were evaluated because of their importance for climate studies and because they represent two important types of statistics (additive and multiplicative. The algorithms were validated against a realistic benchmark dataset. The benchmark contains real inhomogeneous data as well as simulated data with inserted inhomogeneities. Random break-type inhomogeneities were added to the simulated datasets modeled as a Poisson process with normally distributed breakpoint sizes. To approximate real world conditions, breaks were introduced that occur simultaneously in multiple station series within a simulated network of station data. The simulated time series also contained outliers, missing data periods and local station trends. Further, a stochastic nonlinear global (network-wide trend was added.
Participants provided 25 separate homogenized contributions as part of the blind study as well as 22 additional solutions submitted after the details of the imposed inhomogeneities were revealed. These homogenized datasets were assessed by a number of performance metrics including (i the centered root mean square error relative to the true homogeneous value at various averaging scales, (ii the error in linear trend estimates and (iii traditional contingency skill scores. The metrics were computed both using the individual station series as well as the network average regional series. The performance of the contributions depends significantly on the error metric considered. Contingency scores by themselves are not very informative. Although relative homogenization algorithms typically improve the homogeneity of temperature data, only the best ones improve
The Deterministic Dendritic Cell Algorithm
Greensmith, Julie
2010-01-01
The Dendritic Cell Algorithm is an immune-inspired algorithm orig- inally based on the function of natural dendritic cells. The original instantiation of the algorithm is a highly stochastic algorithm. While the performance of the algorithm is good when applied to large real-time datasets, it is difficult to anal- yse due to the number of random-based elements. In this paper a deterministic version of the algorithm is proposed, implemented and tested using a port scan dataset to provide a controllable system. This version consists of a controllable amount of parameters, which are experimented with in this paper. In addition the effects are examined of the use of time windows and variation on the number of cells, both which are shown to influence the algorithm. Finally a novel metric for the assessment of the algorithms output is introduced and proves to be a more sensitive metric than the metric used with the original Dendritic Cell Algorithm.
An Adaptive Memory Evolution Algorithm
Directory of Open Access Journals (Sweden)
Caihong Wu
2013-01-01
Full Text Available Memory mechanism is applied to the optimization algorithm by more study. In order to improve the algorithm of adaptive ability, introducing memory ability in evolutionary algorithm framework, an Adaptive Memory Evolution Algorithm (AMEA is proposed. The algorithm set matrix to record the exploring experiences and exploring results of the individual parent. The algorithm uses these records to guide the generation of offspring. And thus AMEA can adaptively select the dimension to mutate and exploring radius. In addition, to improve the algorithm accuracy, the algorithm raises the best opportunities by using super-variation operator. In the simulation test, compared with similar algorithms, the results show that AMEA has fast convergence speed and optimum performance of global convergence.
Skeletonization Algorithm for Numeral Patterns
Directory of Open Access Journals (Sweden)
Gupta Rakesh
2008-12-01
Full Text Available Skeletonization has been a part of morphological image processing for a wide variety of applications. Skeletonization algorithms have played an important role in the preprocessing phase of OCR systems. Many algorithms for vectorization by skeletonization have been devised and applied to a great variety of pictures and drawings for data compression, pattern recognition and raster-to-vector conversion. The vectorization algorithms often used in pattern recognition tasks also require one-pixel-wide lines as input. But parallel skeletonization algorithms which generate one-pixel-wide skeletons can have difficulty in preserving the connectivity of an image or generate spurious branches. In this paper an alternative parallel skeletonization algorithm has been developed and implemented. This algorithm is better than already existing algorithms in terms of connectivity and spurious branches. A few most common skeletonization algorithms have been implemented and evaluated on the basis of performance parameters and compared with newly developed algorithm.
Genetic Algorithms and Local Search
Whitley, Darrell
1996-01-01
The first part of this presentation is a tutorial level introduction to the principles of genetic search and models of simple genetic algorithms. The second half covers the combination of genetic algorithms with local search methods to produce hybrid genetic algorithms. Hybrid algorithms can be modeled within the existing theoretical framework developed for simple genetic algorithms. An application of a hybrid to geometric model matching is given. The hybrid algorithm yields results that improve on the current state-of-the-art for this problem.
Robust seed selection algorithm for k-means type algorithms
Pavan, K. Karteeka; Rao, Allam Appa; Rao, A. V. Dattatreya; Sridhar, G. R.
2012-01-01
Selection of initial seeds greatly affects the quality of the clusters and in k-means type algorithms. Most of the seed selection methods result different results in different independent runs. We propose a single, optimal, outlier insensitive seed selection algorithm for k-means type algorithms as extension to k-means++. The experimental results on synthetic, real and on microarray data sets demonstrated that effectiveness of the new algorithm in producing the clustering results
Institute of Scientific and Technical Information of China (English)
LIU Shan; LIAO Yongyi
2007-01-01
In this paper,We study the Apriori and FP-growth algorithm in mining association rules and give a method for computing all the frequent item-sets in a database.Its basic idea is giving a concept based on the boolean vector business product,which be computed between all the businesses,then we can get all the two frequent item-sets (min_sup=2).We basis their inclusive relation to construct a set-tree of item-sets in database transaction,and then traverse path in it and get all the frequent item-sets.Therefore,we can get minimal frequent item sets between transactions and items in the database without scanning the database and iteratively computing in Apriori algorithm.
Partitional clustering algorithms
2015-01-01
This book summarizes the state-of-the-art in partitional clustering. Clustering, the unsupervised classification of patterns into groups, is one of the most important tasks in exploratory data analysis. Primary goals of clustering include gaining insight into, classifying, and compressing data. Clustering has a long and rich history that spans a variety of scientific disciplines including anthropology, biology, medicine, psychology, statistics, mathematics, engineering, and computer science. As a result, numerous clustering algorithms have been proposed since the early 1950s. Among these algorithms, partitional (nonhierarchical) ones have found many applications, especially in engineering and computer science. This book provides coverage of consensus clustering, constrained clustering, large scale and/or high dimensional clustering, cluster validity, cluster visualization, and applications of clustering. Examines clustering as it applies to large and/or high-dimensional data sets commonly encountered in reali...
Deprit, André; Palacián, Jesúus; Deprit, Etienne
2001-03-01
The relegation algorithm extends the method of normalization by Lie transformations. Given a Hamiltonian that is a power series ℋ = ℋ0+ ɛℋ1+ ... of a small parameter ɛ, normalization constructs a map which converts the principal part ℋ0into an integral of the transformed system — relegation does the same for an arbitrary function ℋ[G]. If the Lie derivative induced by ℋ[G] is semi-simple, a double recursion produces the generator of the relegating transformation. The relegation algorithm is illustrated with an elementary example borrowed from galactic dynamics; the exercise serves as a standard against which to test software implementations. Relegation is also applied to the more substantial example of a Keplerian system perturbed by radiation pressure emanating from a rotating source.
Genetic Algorithm for Optimization: Preprocessor and Algorithm
Sen, S. K.; Shaykhian, Gholam A.
2006-01-01
Genetic algorithm (GA) inspired by Darwin's theory of evolution and employed to solve optimization problems - unconstrained or constrained - uses an evolutionary process. A GA has several parameters such the population size, search space, crossover and mutation probabilities, and fitness criterion. These parameters are not universally known/determined a priori for all problems. Depending on the problem at hand, these parameters need to be decided such that the resulting GA performs the best. We present here a preprocessor that achieves just that, i.e., it determines, for a specified problem, the foregoing parameters so that the consequent GA is a best for the problem. We stress also the need for such a preprocessor both for quality (error) and for cost (complexity) to produce the solution. The preprocessor includes, as its first step, making use of all the information such as that of nature/character of the function/system, search space, physical/laboratory experimentation (if already done/available), and the physical environment. It also includes the information that can be generated through any means - deterministic/nondeterministic/graphics. Instead of attempting a solution of the problem straightway through a GA without having/using the information/knowledge of the character of the system, we would do consciously a much better job of producing a solution by using the information generated/created in the very first step of the preprocessor. We, therefore, unstintingly advocate the use of a preprocessor to solve a real-world optimization problem including NP-complete ones before using the statistically most appropriate GA. We also include such a GA for unconstrained function optimization problems.
Convex hull ranking algorithm for multi-objective evolutionary algorithms
Davoodi Monfrared, M.; Mohades, A.; Rezaei, J.
2012-01-01
Due to many applications of multi-objective evolutionary algorithms in real world optimization problems, several studies have been done to improve these algorithms in recent years. Since most multi-objective evolutionary algorithms are based on the non-dominated principle, and their complexity depen
An efficient algorithm for function optimization: modified stem cells algorithm
Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad
2013-03-01
In this paper, we propose an optimization algorithm based on the intelligent behavior of stem cell swarms in reproduction and self-organization. Optimization algorithms, such as the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) algorithm, Ant Colony Optimization (ACO) algorithm and Artificial Bee Colony (ABC) algorithm, can give solutions to linear and non-linear problems near to the optimum for many applications; however, in some case, they can suffer from becoming trapped in local optima. The Stem Cells Algorithm (SCA) is an optimization algorithm inspired by the natural behavior of stem cells in evolving themselves into new and improved cells. The SCA avoids the local optima problem successfully. In this paper, we have made small changes in the implementation of this algorithm to obtain improved performance over previous versions. Using a series of benchmark functions, we assess the performance of the proposed algorithm and compare it with that of the other aforementioned optimization algorithms. The obtained results prove the superiority of the Modified Stem Cells Algorithm (MSCA).
Quantum gate decomposition algorithms.
Energy Technology Data Exchange (ETDEWEB)
Slepoy, Alexander
2006-07-01
Quantum computing algorithms can be conveniently expressed in a format of a quantum logical circuits. Such circuits consist of sequential coupled operations, termed ''quantum gates'', or quantum analogs of bits called qubits. We review a recently proposed method [1] for constructing general ''quantum gates'' operating on an qubits, as composed of a sequence of generic elementary ''gates''.
Combinatory CPU Scheduling Algorithm
Saeeda Bibi; Farooque Azam*; Yasir Chaudhry
2010-01-01
Central Processing Unit (CPU) plays a significant role in computer system by transferring its control among different processes. As CPU is a central component, hence it must be used efficiently. Operating system performs an essential task that is known as CPU scheduling for efficient utilization of CPU. CPU scheduling has strong effect on resource utilization as well as overall performance of the system. In this paper, a new CPU scheduling algorithm called Combinatory is proposed that combine...
Graph algorithms for bioinformatics
Profiti, Giuseppe
2015-01-01
Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, than...
Benchmarking conflict resolution algorithms
Vanaret, Charlie; Gianazza, David; Durand, Nicolas; Gotteland, Jean-Baptiste
2012-01-01
Applying a benchmarking approach to conflict resolution problems is a hard task, as the analytical form of the constraints is not simple. This is especially the case when using realistic dynamics and models, considering accelerating aircraft that may follow flight paths that are not direct. Currently, there is a lack of common problems and data that would allow researchers to compare the performances of several conflict resolution algorithms. The present paper introduces a benchmarking approa...
Jochemczyk, Wanda; Olędzka, Katarzyna; Samulska, Agnieszka
2010-01-01
We teach algorithmics at early stages of children development by means of various programming languages and ICT tools in order to develop their cognitive and mathematical skills. Computational thinking is not only a useful for computer scientists, but also a fundamental skill for other people. We should teach children computational skills along with reading, writing, and arithmetic. In this article we present our three-year experience of teaching courses, during which we combine face-to-fa...
Leuenberger, Gabriel
2014-01-01
This paper proposes a novel research direction for algorithmic probability theory, which now allows to formalize philosophical questions about concepts such as the simulation argument, personal identity, and the rationality of utilitarianism. Pushing progress in these directions might be of high relevance for future society and artificial general intelligence. We start to build up a set of formulae while relating them to the real world. We then use our gained understanding to outline in a few...
Demaine, Erik D.; Lynch, Jayson; Mirano, Geronimo J.; Tyagi, Nirvan
2016-01-01
We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bound on the amount of energy a system must dissipate if it destroys information. We propose energy-aware variations of three standard models of computation: circuit RAM, word RAM, and transdichotomous RAM. On top of these models, we build familiar high-level primitives such as control logic, memory allocation, and gar...
Boosting foundations and algorithms
Schapire, Robert E
2012-01-01
Boosting is an approach to machine learning based on the idea of creating a highly accurate predictor by combining many weak and inaccurate "rules of thumb." A remarkably rich theory has evolved around boosting, with connections to a range of topics, including statistics, game theory, convex optimization, and information geometry. Boosting algorithms have also enjoyed practical success in such fields as biology, vision, and speech processing. At various times in its history, boosting has been perceived as mysterious, controversial, even paradoxical.
Reda, Ibrahim; Andreas, Afshin
2015-04-01
The Solar Position Algorithm (SPA) calculates the solar zenith and azimuth angles in the period from the year -2000 to 6000, with uncertainties of +/- 0.0003 degrees based on the date, time, and location on Earth. SPA is implemented in C; in addition to being available for download, an online calculator using this code is available at http://www.nrel.gov/midc/solpos/spa.html.
Clustering using Genetic Algorithms
Czech Academy of Sciences Publication Activity Database
Kudová, Petra
Ostrava : VŠB Technická univerzita, 2007 - (Snášel, V.; Platoš, J.), s. 1-11 ISBN 978-80-248-1332-5. [WETDAP 2007. Workshop in Conjunction with Znalosti 2007 /1./. Ostrava (CZ), 22.02.2007-22.02.2007] R&D Projects: GA AV ČR 1ET100300414 Institutional research plan: CEZ:AV0Z10300504 Keywords : evolutionary techniques * genetic algorithms * unsupervised learning * clustering Subject RIV: IN - Informatics, Computer Science
Czech Academy of Sciences Publication Activity Database
Kudová, Petra
Los Alamitos : IEEE, 2007 - (Tjoa, A.; Wagner, R.), s. 138-142 ISBN 978-0-7695-2932-5. [ETID '07. International Workshop on Evolutionary Techniques /1./, DEXA 2007 International Conference /18./. Regensburg (DE), 03.09.2007-07.09.2007] R&D Projects: GA AV ČR 1ET100300414 Institutional research plan: CEZ:AV0Z10300504 Keywords : clustering * genetic algorithms * k-means Subject RIV: IN - Informatics, Computer Science
Energy Technology Data Exchange (ETDEWEB)
Symbalisty, E.M.D.; Zinn, J.; Whitaker, R.W.
1995-09-01
This paper describes the history, physics, and algorithms of the computer code RADFLO and its extension HYCHEM. RADFLO is a one-dimensional, radiation-transport hydrodynamics code that is used to compute early-time fireball behavior for low-altitude nuclear bursts. The primary use of the code is the prediction of optical signals produced by nuclear explosions. It has also been used to predict thermal and hydrodynamic effects that are used for vulnerability and lethality applications. Another closely related code, HYCHEM, is an extension of RADFLO which includes the effects of nonequilibrium chemistry. Some examples of numerical results will be shown, along with scaling expressions derived from those results. We describe new computations of the structures and luminosities of steady-state shock waves and radiative thermal waves, which have been extended to cover a range of ambient air densities for high-altitude applications. We also describe recent modifications of the codes to use a one-dimensional analog of the CAVEAT fluid-dynamics algorithm in place of the former standard Richtmyer-von Neumann algorithm.
Large scale tracking algorithms.
Energy Technology Data Exchange (ETDEWEB)
Hansen, Ross L.; Love, Joshua Alan; Melgaard, David Kennett; Karelitz, David B.; Pitts, Todd Alan; Zollweg, Joshua David; Anderson, Dylan Z.; Nandy, Prabal; Whitlow, Gary L.; Bender, Daniel A.; Byrne, Raymond Harry
2015-01-01
Low signal-to-noise data processing algorithms for improved detection, tracking, discrimination and situational threat assessment are a key research challenge. As sensor technologies progress, the number of pixels will increase signi cantly. This will result in increased resolution, which could improve object discrimination, but unfortunately, will also result in a significant increase in the number of potential targets to track. Many tracking techniques, like multi-hypothesis trackers, suffer from a combinatorial explosion as the number of potential targets increase. As the resolution increases, the phenomenology applied towards detection algorithms also changes. For low resolution sensors, "blob" tracking is the norm. For higher resolution data, additional information may be employed in the detection and classfication steps. The most challenging scenarios are those where the targets cannot be fully resolved, yet must be tracked and distinguished for neighboring closely spaced objects. Tracking vehicles in an urban environment is an example of such a challenging scenario. This report evaluates several potential tracking algorithms for large-scale tracking in an urban environment.
Iterative Algorithms for Nonexpansive Mappings
Directory of Open Access Journals (Sweden)
Yao Yonghong
2008-01-01
Full Text Available Abstract We suggest and analyze two new iterative algorithms for a nonexpansive mapping in Banach spaces. We prove that the proposed iterative algorithms converge strongly to some fixed point of .
Building Better Nurse Scheduling Algorithms
Aickelin, Uwe
2008-01-01
The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.
Disk Scheduling: Selection of Algorithm
Yashvir, S.; Prakash, Om
2012-01-01
The objective of this paper is to take some aspects of disk scheduling and scheduling algorithms. The disk scheduling is discussed with a sneak peak in general and selection of algorithm in particular.
Fast Density Based Clustering Algorithm
Priyanka Trikha; Singh Vijendra
2013-01-01
Clustering problem is an unsupervised learning problem. It is a procedure that partition data objects into matching clusters. The data objects in the same cluster are quite similar to each other and dissimilar in the other clusters. The traditional algorithms do not meet the latest multiple requirements simultaneously for objects. Density-based clustering algorithms find clusters based on density of data points in a region. DBSCAN algorithm is one of the density-based clustering algorithms. I...
Join-Graph Propagation Algorithms
Mateescu, Robert; Kask, Kalev; Gogate, Vibhav; Dechter, Rina
2014-01-01
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with a...
Open Mass Spectrometry Search Algorithm
Geer, L Y; Kowalak, J A; Wagner, L; Xu, M; Maynard, D M; Yang, X; Shi, W; Bryant, S H; Geer, Lewis Y.; Markey, Sanford P.; Kowalak, Jeffrey A.; Wagner, Lukas; Xu, Ming; Maynard, Dawn M.; Yang, Xiaoyu; Shi, Wenyao; Bryant, Stephen H.
2004-01-01
Large numbers of MS/MS peptide spectra generated in proteomics experiments require efficient, sensitive and specific algorithms for peptide identification. In the Open Mass Spectrometry Search Algorithm [OMSSA], specificity is calculated by a classic probability score using an explicit model for matching experimental spectra to sequences. At default thresholds, OMSSA matches more spectra from a standard protein cocktail than a comparable algorithm. OMSSA is designed to be faster than published algorithms in searching large MS/MS datasets.
Genetic Algorithms and Quantum Computation
Giraldi, Gilson A.; Portugal, Renato; Thess, Ricardo N.
2004-01-01
Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best ...
Foundations of genetic algorithms 1991
FOGA
1991-01-01
Foundations of Genetic Algorithms 1991 (FOGA 1) discusses the theoretical foundations of genetic algorithms (GA) and classifier systems.This book compiles research papers on selection and convergence, coding and representation, problem hardness, deception, classifier system design, variation and recombination, parallelization, and population divergence. Other topics include the non-uniform Walsh-schema transform; spurious correlations and premature convergence in genetic algorithms; and variable default hierarchy separation in a classifier system. The grammar-based genetic algorithm; condition
Combinatorial optimization algorithms and complexity
Papadimitriou, Christos H
1998-01-01
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering.
Evolutionary Algorithms and Dynamic Programming
Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian
2013-01-01
Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how ...
Essential algorithms a practical approach to computer algorithms
Stephens, Rod
2013-01-01
A friendly and accessible introduction to the most useful algorithms Computer algorithms are the basic recipes for programming. Professional programmers need to know how to use algorithms to solve difficult programming problems. Written in simple, intuitive English, this book describes how and when to use the most practical classic algorithms, and even how to create new algorithms to meet future needs. The book also includes a collection of questions that can help readers prepare for a programming job interview. Reveals methods for manipulating common data structures s
Comparison of Text Categorization Algorithms
Institute of Scientific and Technical Information of China (English)
SHI Yong-feng; ZHAO Yan-ping
2004-01-01
This paper summarizes several automatic text categorization algorithms in common use recently, analyzes and compares their advantages and disadvantages.It provides clues for making use of appropriate automatic classifying algorithms in different fields.Finally some evaluations and summaries of these algorithms are discussed, and directions to further research have been pointed out.
Continuous Media Tasks Scheduling Algorithm
Directory of Open Access Journals (Sweden)
Myungryun Yoo
2016-03-01
Full Text Available In this paper the authors propose modified proportional share scheduling algorithm considering the characteristics of continuous media such as its continuity and time dependency. Proposed scheduling algorithm shows graceful degradation of performance in overloaded situation and decreases the number of context switching. Proposed scheduling algorithm is evaluated using several numerical tests under various conditions, especially overloaded situation.
Multipartite entanglement in quantum algorithms
Bruss D.; MacChiavello C.
2011-01-01
We investigate the entanglement features of the quantum states employed in quantum algorithms. In particular, we analyse the multipartite entanglement properties in the Deutsch-Jozsa, Grover and Simon algorithms. Our results show that for these algorithms most instances involve multipartite entanglement.
Algorithmic approach to diagram techniques
International Nuclear Information System (INIS)
An algorithmic approach to diagram techniques of elementary particles is proposed. The definition and axiomatics of the theory of algorithms are presented, followed by the list of instructions of an algorithm formalizing the construction of graphs and the assignment of mathematical objects to them. (T.A.)
Opposite Degree Algorithm and Its Applications
Directory of Open Access Journals (Sweden)
Xiao-Guang Yue
2015-12-01
Full Text Available The opposite (Opposite Degree, referred to as OD algorithm is an intelligent algorithm proposed by Yue Xiaoguang et al. Opposite degree algorithm is mainly based on the concept of opposite degree, combined with the idea of design of neural network and genetic algorithm and clustering analysis algorithm. The OD algorithm is divided into two sub algorithms, namely: opposite degree - numerical computation (OD-NC algorithm and opposite degree - Classification computation (OD-CC algorithm.
Opposite Degree Algorithm and Its Applications
Xiao-Guang Yue
2015-01-01
The opposite (Opposite Degree, referred to as OD) algorithm is an intelligent algorithm proposed by Yue Xiaoguang et al. Opposite degree algorithm is mainly based on the concept of opposite degree, combined with the idea of design of neural network and genetic algorithm and clustering analysis algorithm. The OD algorithm is divided into two sub algorithms, namely: opposite degree - numerical computation (OD-NC) algorithm and opposite degree - Classification computation (OD-CC) algorithm.
HISTORY BASED PROBABILISTIC BACKOFF ALGORITHM
Directory of Open Access Journals (Sweden)
Narendran Rajagopalan
2012-01-01
Full Text Available Performance of Wireless LAN can be improved at each layer of the protocol stack with respect to energy efficiency. The Media Access Control layer is responsible for the key functions like access control and flow control. During contention, Backoff algorithm is used to gain access to the medium with minimum probability of collision. After studying different variations of back off algorithms that have been proposed, a new variant called History based Probabilistic Backoff Algorithm is proposed. Through mathematical analysis and simulation results using NS-2, it is seen that proposed History based Probabilistic Backoff algorithm performs better than Binary Exponential Backoff algorithm.
Parallelization of the PC Algorithm
DEFF Research Database (Denmark)
Madsen, Anders Læsø; Jensen, Frank; Salmerón, Antonio; Langseth, Helge; Nielsen, Thomas Dyhre
2015-01-01
This paper describes a parallel version of the PC algorithm for learning the structure of a Bayesian network from data. The PC algorithm is a constraint-based algorithm consisting of five steps where the first step is to perform a set of (conditional) independence tests while the remaining four....... The proposed parallel PC algorithm is evaluated on data sets generated at random from five different real- world Bayesian networks. The results demonstrate that significant time performance improvements are possible using the proposed algorithm....
Directory of Open Access Journals (Sweden)
Jyoti Kalyani
2006-01-01
Full Text Available Security of wired and wireless networks is the most challengeable in today's computer world. The aim of this study was to give brief introduction about viruses and worms, their creators and characteristics of algorithms used by viruses. Here wired and wireless network viruses are elaborated. Also viruses are compared with human immune system. On the basis of this comparison four guidelines are given to detect viruses so that more secure systems are made. While concluding this study it is found that the security is most challengeable, thus it is required to make more secure models which automatically detect viruses and prevent the system from its affect.
Algorithmic States of Exception
McQuillan, Daniel
2015-01-01
In this paper I argue that pervasive tracking and data-mining are leading to shifts in governmentality that can be characterised as algorithmic states of exception. I also argue that the apparatus that performs this change owes as much to everyday business models as it does to mass surveillance. I look at technical changes at the level of data structures, such as the move to NoSQL databases, and how this combines with data-mining and machine learning to accelerate the use of prediction as a ...
Chazelle, Bernard
2015-01-01
The following anecdote, perhaps apocryphal, is told about the great Danish physicist Niels Bohr:– Professor Bohr, I see you have a horseshoe hanging on the wall. Don’t tell me you believe in this kind of thing!– Don’t worry, I don’t believe in it at all, but I was told that it works even if you don’t believe in it. So it goes for the algorithmic revolution. Beyond the scepticism or infatuation of the day regarding the latest IT novelty hides one of those paradigm shifts dear to Thomas Kuh...
Rabideau, Gregg R.; Chien, Steve A.
2010-01-01
AVA v2 software selects goals for execution from a set of goals that oversubscribe shared resources. The term goal refers to a science or engineering request to execute a possibly complex command sequence, such as image targets or ground-station downlinks. Developed as an extension to the Virtual Machine Language (VML) execution system, the software enables onboard and remote goal triggering through the use of an embedded, dynamic goal set that can oversubscribe resources. From the set of conflicting goals, a subset must be chosen that maximizes a given quality metric, which in this case is strict priority selection. A goal can never be pre-empted by a lower priority goal, and high-level goals can be added, removed, or updated at any time, and the "best" goals will be selected for execution. The software addresses the issue of re-planning that must be performed in a short time frame by the embedded system where computational resources are constrained. In particular, the algorithm addresses problems with well-defined goal requests without temporal flexibility that oversubscribes available resources. By using a fast, incremental algorithm, goal selection can be postponed in a "just-in-time" fashion allowing requests to be changed or added at the last minute. Thereby enabling shorter response times and greater autonomy for the system under control.
Algorithmic Relative Complexity
Directory of Open Access Journals (Sweden)
Daniele Cerra
2011-04-01
Full Text Available Information content and compression are tightly related concepts that can be addressed through both classical and algorithmic information theories, on the basis of Shannon entropy and Kolmogorov complexity, respectively. The definition of several entities in Kolmogorov’s framework relies upon ideas from classical information theory, and these two approaches share many common traits. In this work, we expand the relations between these two frameworks by introducing algorithmic cross-complexity and relative complexity, counterparts of the cross-entropy and relative entropy (or Kullback-Leibler divergence found in Shannon’s framework. We define the cross-complexity of an object x with respect to another object y as the amount of computational resources needed to specify x in terms of y, and the complexity of x related to y as the compression power which is lost when adopting such a description for x, compared to the shortest representation of x. Properties of analogous quantities in classical information theory hold for these new concepts. As these notions are incomputable, a suitable approximation based upon data compression is derived to enable the application to real data, yielding a divergence measure applicable to any pair of strings. Example applications are outlined, involving authorship attribution and satellite image classification, as well as a comparison to similar established techniques.
Fatigue evaluation algorithms: Review
Energy Technology Data Exchange (ETDEWEB)
Passipoularidis, V.A.; Broendsted, P.
2009-11-15
A progressive damage fatigue simulator for variable amplitude loads named FADAS is discussed in this work. FADAS (Fatigue Damage Simulator) performs ply by ply stress analysis using classical lamination theory and implements adequate stiffness discount tactics based on the failure criterion of Puck, to model the degradation caused by failure events in ply level. Residual strength is incorporated as fatigue damage accumulation metric. Once the typical fatigue and static properties of the constitutive ply are determined,the performance of an arbitrary lay-up under uniaxial and/or multiaxial load time series can be simulated. The predictions are validated against fatigue life data both from repeated block tests at a single stress ratio as well as against spectral fatigue using the WISPER, WISPERX and NEW WISPER load sequences on a Glass/Epoxy multidirectional laminate typical of a wind turbine rotor blade construction. Two versions of the algorithm, the one using single-step and the other using incremental application of each load cycle (in case of ply failure) are implemented and compared. Simulation results confirm the ability of the algorithm to take into account load sequence effects. In general, FADAS performs well in predicting life under both spectral and block loading fatigue. (author)
Online Pairwise Learning Algorithms.
Ying, Yiming; Zhou, Ding-Xuan
2016-04-01
Pairwise learning usually refers to a learning task that involves a loss function depending on pairs of examples, among which the most notable ones are bipartite ranking, metric learning, and AUC maximization. In this letter we study an online algorithm for pairwise learning with a least-square loss function in an unconstrained setting of a reproducing kernel Hilbert space (RKHS) that we refer to as the Online Pairwise lEaRning Algorithm (OPERA). In contrast to existing works (Kar, Sriperumbudur, Jain, & Karnick, 2013 ; Wang, Khardon, Pechyony, & Jones, 2012 ), which require that the iterates are restricted to a bounded domain or the loss function is strongly convex, OPERA is associated with a non-strongly convex objective function and learns the target function in an unconstrained RKHS. Specifically, we establish a general theorem that guarantees the almost sure convergence for the last iterate of OPERA without any assumptions on the underlying distribution. Explicit convergence rates are derived under the condition of polynomially decaying step sizes. We also establish an interesting property for a family of widely used kernels in the setting of pairwise learning and illustrate the convergence results using such kernels. Our methodology mainly depends on the characterization of RKHSs using its associated integral operators and probability inequalities for random variables with values in a Hilbert space. PMID:26890352
An Improved Robot Path Planning Algorithm Based on Genetic Algorithm
Directory of Open Access Journals (Sweden)
Hammin Liu
2012-12-01
Full Text Available Robot path planning is a NP problem; traditional optimization methods are not very effective to solve it. Traditional genetic algorithm trapped into the local minimum easily. Therefore, based on a simple genetic algorithm and combine the base ideology of orthogonal design method then applied it to the population initialization, using the intergenerational elite mechanism, as well as the introduction of adaptive local search operator to prevent trapped into the local minimum and improve the convergence speed to form a new genetic algorithm. Through the series of numerical experiments, the new algorithm has been proved to be efficiency. We also use the proposed algorithm to solve the robot path planning problem and the experiment results indicated that the new algorithm is efficiency for solving the robot path planning problems and the best path usually can be found.
The Watershed Algorithm for Image Segmentation
Institute of Scientific and Technical Information of China (English)
OU Yan; LIN Nan
2007-01-01
This article introduced the watershed algorithm for the segmentation, illustrated the segmation process by implementing this algorithm. By comparing with another three related algorithm, this article revealed both the advantages and drawbacks of the watershed algorithm.
Probabilistic analysis of geometric algorithms
Energy Technology Data Exchange (ETDEWEB)
Golin, M.J.
1990-01-01
In the paper, the authors describe the subtleties involved in probabilistically analyzing simple algorithms in computational geometry. The authors also work through a few easy examples of such analyses. The first example analyzes Quicksort, the second analyzes Quickhull, and the third analyzes interpoint distances between uniformly distributed points in hypercubes or hypertori. The authors present a simple but effective preprocessing algorithm for calculating convex hulls. The algorithm is short and intuitive. It does a fast linear scan through the points, identifying many which are not on the convex hull and can therefore be eliminated. The authors perform an exact analysis of this algorithm showing that, given n points distributed uniformly in the unit square, only about 8 sq. root (n) of them remain after the preprocessing step: in higher dimensions only d{sub d}n{sup 1 {minus}1/d} will remain. The authors present the results of simulations comparing our mathematical analysis to reality. Finally, the authors end with a discussion of what distinguishes this algorithm from certain obvious variants. The authors analyze closet pair algorithms. First, the authors analyze a sweep-line closest-pair algorithm, one similar in spirit to Hoey and Shamos' divide and conquer algorithm for solving the same problem. The result is that, given n points uniformly distributed in the unit square and then sorted, there is a six line algorithm that finds the closest pair in O(n) expected time. Moreover, this algorithm uses no complicated data structures. The authors then analyze a second algorithm, one that finds the closest pair using a modified version of Bentley and Papadimitriou's nearest neighbor projection algorithm. The result, again, is that after the sorting stage, the linear scan stage of this new algorithm also finds the closest pair in O(n) expected time.
STAR Algorithm Integration Team - Facilitating operational algorithm development
Mikles, V. J.
2015-12-01
The NOAA/NESDIS Center for Satellite Research and Applications (STAR) provides technical support of the Joint Polar Satellite System (JPSS) algorithm development and integration tasks. Utilizing data from the S-NPP satellite, JPSS generates over thirty Environmental Data Records (EDRs) and Intermediate Products (IPs) spanning atmospheric, ocean, cryosphere, and land weather disciplines. The Algorithm Integration Team (AIT) brings technical expertise and support to product algorithms, specifically in testing and validating science algorithms in a pre-operational environment. The AIT verifies that new and updated algorithms function in the development environment, enforces established software development standards, and ensures that delivered packages are functional and complete. AIT facilitates the development of new JPSS-1 algorithms by implementing a review approach based on the Enterprise Product Lifecycle (EPL) process. Building on relationships established during the S-NPP algorithm development process and coordinating directly with science algorithm developers, the AIT has implemented structured reviews with self-contained document suites. The process has supported algorithm improvements for products such as ozone, active fire, vegetation index, and temperature and moisture profiles.
Memarsadeghi, Nargess
2011-01-01
More efficient versions of an interpolation method, called kriging, have been introduced in order to reduce its traditionally high computational cost. Written in C++, these approaches were tested on both synthetic and real data. Kriging is a best unbiased linear estimator and suitable for interpolation of scattered data points. Kriging has long been used in the geostatistic and mining communities, but is now being researched for use in the image fusion of remotely sensed data. This allows a combination of data from various locations to be used to fill in any missing data from any single location. To arrive at the faster algorithms, sparse SYMMLQ iterative solver, covariance tapering, Fast Multipole Methods (FMM), and nearest neighbor searching techniques were used. These implementations were used when the coefficient matrix in the linear system is symmetric, but not necessarily positive-definite.
Quicksort algorithm again revisited
Directory of Open Access Journals (Sweden)
Charles Knessl
1999-12-01
Full Text Available We consider the standard Quicksort algorithm that sorts n distinct keys with all possible n! orderings of keys being equally likely. Equivalently, we analyze the total path length L(n in a randomly built binary search tree. Obtaining the limiting distribution of L(n is still an outstanding open problem. In this paper, we establish an integral equation for the probability density of the number of comparisons L(n. Then, we investigate the large deviations of L(n. We shall show that the left tail of the limiting distribution is much ``thinner'' (i.e., double exponential than the right tail (which is only exponential. Our results contain some constants that must be determined numerically. We use formal asymptotic methods of applied mathematics such as the WKB method and matched asymptotics.
Algorithmes, machines et langages
Berry, Gérard
2014-01-01
Enseignement : Le temps et les événements en informatique J’ai donné le cours « Le temps et les événements en informatique » dans le cadre de la chaire Algorithmes, machines et langages, créée le 4 juillet 2013 comme première chaire de plein exercice en informatique. J’avais introduit l’informatique au Collège de France en 2007-2008 par le cours « Pourquoi et comment le monde devient numérique », au sein de la chaire annuelle d’Innovation technologique Liliane Bettencourt, puis, en 2009-2010,...
Fighting Censorship with Algorithms
Mahdian, Mohammad
In countries such as China or Iran where Internet censorship is prevalent, users usually rely on proxies or anonymizers to freely access the web. The obvious difficulty with this approach is that once the address of a proxy or an anonymizer is announced for use to the public, the authorities can easily filter all traffic to that address. This poses a challenge as to how proxy addresses can be announced to users without leaking too much information to the censorship authorities. In this paper, we formulate this question as an interesting algorithmic problem. We study this problem in a static and a dynamic model, and give almost tight bounds on the number of proxy servers required to give access to n people k of whom are adversaries. We will also discuss how trust networks can be used in this context.
Multisensor data fusion algorithm development
Energy Technology Data Exchange (ETDEWEB)
Yocky, D.A.; Chadwick, M.D.; Goudy, S.P.; Johnson, D.K.
1995-12-01
This report presents a two-year LDRD research effort into multisensor data fusion. We approached the problem by addressing the available types of data, preprocessing that data, and developing fusion algorithms using that data. The report reflects these three distinct areas. First, the possible data sets for fusion are identified. Second, automated registration techniques for imagery data are analyzed. Third, two fusion techniques are presented. The first fusion algorithm is based on the two-dimensional discrete wavelet transform. Using test images, the wavelet algorithm is compared against intensity modulation and intensity-hue-saturation image fusion algorithms that are available in commercial software. The wavelet approach outperforms the other two fusion techniques by preserving spectral/spatial information more precisely. The wavelet fusion algorithm was also applied to Landsat Thematic Mapper and SPOT panchromatic imagery data. The second algorithm is based on a linear-regression technique. We analyzed the technique using the same Landsat and SPOT data.
Fractal simplex algorithm in VBA
Ouzký, Karel
2009-01-01
Basic idea of fractal simplex algorithm is based in the theory of matrix counting and knowledge of matrix representation of simplex tabuleao from revised simplex method. My desire is to explain theoretical basics on which this algorithm works and provide solution in language Visual Basic for Applications in application MS Excel 2007. Main benefit I see in the fact, that algorithm can solved specific class of mathematical problems in a way of exactness counting whithout necessity of using deci...
Algorithms over partially ordered sets
DEFF Research Database (Denmark)
Baer, Robert M.; Østerby, Ole
1969-01-01
partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi......-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms....
GPU accelerated Rna folding algorithm
Rizk, Guillaume; Lavenier, Dominique
2009-01-01
Many bioinformatics studies require the analysis of RNA or DNA structures. More specifically, extensive work is done to elaborate efficient algorithms able to predict the 2-D folding structures of RNA or DNA sequences. However, the high computational complexity of the algorithms, combined with the rapid increase of genomic data, triggers the need of faster methods. Current approaches focus on parallelizing these algorithms on multiprocessor systems or on clusters, yielding to good performance...
Tau reconstruction and identification algorithm
Indian Academy of Sciences (India)
Raman Khurana
2012-11-01
CMS has developed sophisticated tau identification algorithms for tau hadronic decay modes. Production of tau lepton decaying to hadrons are studied at 7 TeV centre-of-mass energy with 2011 collision data collected by CMS detector and has been used to measure the performance of tau identification algorithms by measuring identification efficiency and misidentification rates from electrons, muons and hadronic jets. These algorithms enable extended reach for the searches for MSSM Higgs, and other exotic particles.
HISTORY BASED PROBABILISTIC BACKOFF ALGORITHM
Narendran Rajagopalan; C.Mala
2012-01-01
Performance of Wireless LAN can be improved at each layer of the protocol stack with respect to energy efficiency. The Media Access Control layer is responsible for the key functions like access control and flow control. During contention, Backoff algorithm is used to gain access to the medium with minimum probability of collision. After studying different variations of back off algorithms that have been proposed, a new variant called History based Probabilistic Backoff Algorithm is proposed....
Generating Specials: The Zorro Algorithm
Thamsborg, Jacob
2006-01-01
The concept of a configuration graph associated to a primitive, aperiodic substitution is introduced in [1] as a convenient graphical representation of the infinite indeterminism of the shift space of the substitution. The main result of [1] is an algorithm to calculate this graph from the substitution, in this paper we turn the tables and produce substitutions from graphs. We do this using the Zorro algorithm, an entirely constructive and easily applicable algorithm. In the process we show t...
Theoretical Aspects of Evolutionary Algorithms
Wegener, Ingo
2001-01-01
Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many different situations. However, the theory on these algorithms is still in its infancy. Here it is discussed how and why such a theory should be developed. Afterwards, some fundamental results on evolutionary algorithms are presented in order to show how theoretical results on randomized search heuristics can be proved and how they contribute to the understanding of evolutionary a...
Machine Learning an algorithmic perspective
Marsland, Stephen
2009-01-01
Traditional books on machine learning can be divided into two groups - those aimed at advanced undergraduates or early postgraduates with reasonable mathematical knowledge and those that are primers on how to code algorithms. The field is ready for a text that not only demonstrates how to use the algorithms that make up machine learning methods, but also provides the background needed to understand how and why these algorithms work. Machine Learning: An Algorithmic Perspective is that text.Theory Backed up by Practical ExamplesThe book covers neural networks, graphical models, reinforcement le
Recent results on howard's algorithm
DEFF Research Database (Denmark)
Miltersen, P.B.
2013-01-01
Howard’s algorithm is a fifty-year old generally applicable algorithm for sequential decision making in face of uncertainty. It is routinely used in practice in numerous application areas that are so important that they usually go by their acronyms, e.g., OR, AI, and CAV. While Howard’s algorithm...... is generally recognized as fast in practice, until recently, its worst case time complexity was poorly understood. However, a surge of results since 2009 has led us to a much more satisfactory understanding of the worst case time complexity of the algorithm in the various settings in which it applies...
Preconditioned quantum linear system algorithm.
Clader, B D; Jacobs, B C; Sprouse, C R
2013-06-21
We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers. To demonstrate the algorithm's applicability, we show how it can be used to compute the electromagnetic scattering cross section of an arbitrary target exponentially faster than the best classical algorithm. PMID:23829722
Diversity-Guided Evolutionary Algorithms
DEFF Research Database (Denmark)
Ursem, Rasmus Kjær
2002-01-01
Population diversity is undoubtably a key issue in the performance of evolutionary algorithms. A common hypothesis is that high diversity is important to avoid premature convergence and to escape local optima. Various diversity measures have been used to analyze algorithms, but so far few...... algorithms have used a measure to guide the search. The diversity-guided evolutionary algorithm (DGEA) uses the wellknown distance-to-average-point measure to alternate between phases of exploration (mutation) and phases of exploitation (recombination and selection). The DGEA showed remarkable results...
Practical Parallel External Memory Algorithms via Simulation of Parallel Algorithms
Robillard, David E
2010-01-01
This thesis introduces PEMS2, an improvement to PEMS (Parallel External Memory System). PEMS executes Bulk-Synchronous Parallel (BSP) algorithms in an External Memory (EM) context, enabling computation with very large data sets which exceed the size of main memory. Many parallel algorithms have been designed and implemented for Bulk-Synchronous Parallel models of computation. Such algorithms generally assume that the entire data set is stored in main memory at once. PEMS overcomes this limitation without requiring any modification to the algorithm by using disk space as memory for additional "virtual processors". Previous work has shown this to be a promising approach which scales well as computational resources (i.e. processors and disks) are added. However, the technique incurs significant overhead when compared with purpose-built EM algorithms. PEMS2 introduces refinements to the simulation process intended to reduce this overhead as well as the amount of disk space required to run the simulation. New func...
A New Metaheuristic Bat-Inspired Algorithm
Yang, Xin-She
2010-01-01
Metaheuristic algorithms such as particle swarm optimization, firefly algorithm and harmony search are now becoming powerful methods for solving many tough optimization problems. In this paper, we propose a new metaheuristic method, the Bat Algorithm, based on the echolocation behaviour of bats. We also intend to combine the advantages of existing algorithms into the new bat algorithm. After a detailed formulation and explanation of its implementation, we will then compare the proposed algorithm with other existing algorithms, including genetic algorithms and particle swarm optimization. Simulations show that the proposed algorithm seems much superior to other algorithms, and further studies are also discussed.
Toward an Algorithmic Pedagogy
Directory of Open Access Journals (Sweden)
Holly Willis
2007-01-01
Full Text Available The demand for an expanded definition of literacy to accommodate visual and aural media is not particularly new, but it gains urgency as college students transform, becoming producers of media in many of their everyday social activities. The response among those who grapple with these issues as instructors has been to advocate for new definitions of literacy and particularly, an understanding of visual literacy. These efforts are exemplary, and promote a much needed rethinking of literacy and models of pedagogy. However, in what is more akin to a manifesto than a polished argument, this essay argues that we need to push farther: What if we moved beyond visual rhetoric, as well as a game-based pedagogy and the adoption of a broad range of media tools on campus, toward a pedagogy grounded fundamentally in a media ecology? Framing this investigation in terms of a media ecology allows us to take account of the multiply determining relationships wrought not just by individual media, but by the interrelationships, dependencies and symbioses that take place within the dynamic system that is today’s high-tech university. An ecological approach allows us to examine what happens when new media practices collide with computational models, providing a glimpse of possible transformations not only ways of being but ways of teaching and learning. How, then, may pedagogical practices be transformed computationally or algorithmically and to what ends?
Pulmonary thromboembolism diagnosis algorithms
Energy Technology Data Exchange (ETDEWEB)
Kasai, Takeshi; Eto, Jun; Hayano, Daisuke; Ohashi, Masaki; Yoneda, Takahiro; Oyama, Hisaya; Inaba, Akira [Kameda General Hospital, Kamogawa, Chiba (Japan). Trauma and Emergency Care Center
2002-01-01
Our algorithm for diagnosing pulmonary thromboembolism combines ventilation/perfusion scanning with clinical criteria. Our perfusion scanning criterion states that high probability defines 2 segmental perfusion defects without corresponding radiographic abnormality and indeterminate probability defines less than 2 segmental perfusion defects (low probability: less than one segmental perfusion defect; intermediate: perfusion defects between high and low probability). The clinical criterion is divided into 7 items related to symptoms and signs suggestive of pulmonary thromboembolism. More than 4 items are defined as a highly suspicious clinical manifestation (HSCM), and less than 4 are considered a low suspicious clinical manifestation (LSCM). In 31 cases of high probability, 18 of HSCM did not include pulmonary angiograhy (PAG), and 13 of LSCM included PAG (positive: 11; negative: 2). In 12 cases of indeterminate probability, 7 of LSCM were observed without PAG and 5 of HSCM with PAG (positive: 4; negative: 1). PAG performance thus decreased to 41.9%. The positive prediction of high probability is 93.5%, which is very high, compared to indeterminate probability at 33.3%. (author)
Two Aspects of Evolutionary Algorithms
Institute of Scientific and Technical Information of China (English)
无
2000-01-01
In this paper we discuss the paradigm of evolutionary algorithms (Eas). We argue about the need for new heuristics in real-world problem solving, discussing reasons why some problems are difficult tosolve. After introducing the main concepts of evolutionary algorithms, we concentrate on two issues:(1)self-adaptation of the parameters of EA, and (2) handling constraints.
A distributed spanning tree algorithm
DEFF Research Database (Denmark)
Johansen, Karl Erik; Jørgensen, Ulla Lundin; Nielsen, Svend Hauge;
1988-01-01
We present a distributed algorithm for constructing a spanning tree for connected undirected graphs. Nodes correspond to processors and edges correspond to two way channels. Each processor has initially a distinct identity and all processors perform the same algorithm. Computation as well as...
Ensemble algorithms in reinforcement learning
Wiering, Marco A; van Hasselt, Hado
2008-01-01
This paper describes several ensemble methods that combine multiple different reinforcement learning (RL) algorithms in a single agent. The aim is to enhance learning speed and final performance by combining the chosen actions or action probabilities of different RL algorithms. We designed and imple
Cascade Error Projection Learning Algorithm
Duong, T. A.; Stubberud, A. R.; Daud, T.
1995-01-01
A detailed mathematical analysis is presented for a new learning algorithm termed cascade error projection (CEP) and a general learning frame work. This frame work can be used to obtain the cascade correlation learning algorithm by choosing a particular set of parameters.
Algorithms in combinatorial design theory
Colbourn, CJ
1985-01-01
The scope of the volume includes all algorithmic and computational aspects of research on combinatorial designs. Algorithmic aspects include generation, isomorphism and analysis techniques - both heuristic methods used in practice, and the computational complexity of these operations. The scope within design theory includes all aspects of block designs, Latin squares and their variants, pairwise balanced designs and projective planes and related geometries.
Hirschberg's Algorithm for Approximate Matching
Directory of Open Access Journals (Sweden)
Adam Drozdek
2002-01-01
Full Text Available The Hirschberg algorithm was devised to solve the longest common subsequence problem. The paper discusses the way of adopting the algorithm to solve the string matching problem in linear space to determine edit distance for two strings and their alignment.
Penalty Algorithms in Hilbert Spaces
Institute of Scientific and Technical Information of China (English)
Jean Pierre DUSSAULT; Hai SHEN; André BANDRAUK
2007-01-01
We analyze the classical penalty algorithm for nonlinear programming in HUbert spaces and obtain global convergence results, as well as asymptotic superlinear convergence order. These convergence results generalize similar results obtained for finite-dimensional problems. Moreover, the nature of the algorithms allows us to solve the unconstrained subproblems in finite-dimensional spaces.
A Fast Fractional Difference Algorithm
DEFF Research Database (Denmark)
Jensen, Andreas Noack; Nielsen, Morten Ørregaard
We provide a fast algorithm for calculating the fractional difference of a time series. In standard implementations, the calculation speed (number of arithmetic operations) is of order T 2, where T is the length of the time series. Our algorithm allows calculation speed of order T logT . For...
A fast fractional difference algorithm
DEFF Research Database (Denmark)
Jensen, Andreas Noack; Nielsen, Morten Ørregaard
2014-01-01
We provide a fast algorithm for calculating the fractional difference of a time series. In standard implementations, the calculation speed (number of arithmetic operations) is of order T 2, where T is the length of the time series. Our algorithm allows calculation speed of order T logT . For...
Sliding Window Orthonormal PAST Algorithm
Badeau, Roland; Abed-Meraim, Karim; Richard, Gaël; David, Bertrand
2003-01-01
This paper introduces an orthonormal version of the sliding-window Projection Approximation Subspace Tracker (PAST). The new algorithm guarantees the orthonormality of the signal subspace basis at each iteration. Moreover, it has the same complexity as the original PAST algorithm, and like the more computationally demanding natural power (NP) method, it satisfies a global convergence property, and reaches an excellent tracking performance.
A Distributed Spanning Tree Algorithm
DEFF Research Database (Denmark)
Johansen, Karl Erik; Jørgensen, Ulla Lundin; Nielsen, Sven Hauge; Nielsen, Søren Erik; Skyum, Sven
We present a distributed algorithm for constructing a spanning tree for connected undirected graphs. Nodes correspond to processors and edges correspond to two-way channels. Each processor has initially a distinct identity and all processors perform the same algorithm. Computation as well as...
Echo Cancellation I: Algorithms Simulation
Directory of Open Access Journals (Sweden)
P. Sovka
2000-04-01
Full Text Available Echo cancellation system used in mobile communications is analyzed.Convergence behavior and misadjustment of several LMS algorithms arecompared. The misadjustment means errors in filter weight estimation.The resulting echo suppression for discussed algorithms with simulatedas well as rela speech signals is evaluated. The optional echocancellation configuration is suggested.
Streaming Algorithms for Line Simplification
DEFF Research Database (Denmark)
Abam, Mohammad; de Berg, Mark; Hachenberger, Peter;
2010-01-01
problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our...... simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance...... (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k 2) additional storage....
Directory of Open Access Journals (Sweden)
Issam Dagher
2010-06-01
Full Text Available In this paper a recursive algorithm of calculating the discriminant features of thePCA-LDA procedure is introduced. This algorithm computes the principalcomponents of a sequence of vectors incrementally without estimating thecovariance matrix (so covariance-free and at the same time computing the lineardiscriminant directions along which the classes are well separated. Two majortechniques are used sequentially in a real time fashion in order to obtain the mostefficient and linearly discriminative components. This procedure is done bymerging the runs of two algorithms based on principal component analysis (PCAand linear discriminant analysis (LDA running sequentially. This algorithm isapplied to face recognition problem. Simulation results on different databasesshowed high average success rate of this algorithm compared to PCA and LDAalgorithms. The advantage of the incremental property of this algorithmcompared to the batch PCA-LDA is also shown.
The Chopthin Algorithm for Resampling
Gandy, Axel; Lau, F. Din-Houn
2016-08-01
Resampling is a standard step in particle filters and more generally sequential Monte Carlo methods. We present an algorithm, called chopthin, for resampling weighted particles. In contrast to standard resampling methods the algorithm does not produce a set of equally weighted particles; instead it merely enforces an upper bound on the ratio between the weights. Simulation studies show that the chopthin algorithm consistently outperforms standard resampling methods. The algorithms chops up particles with large weight and thins out particles with low weight, hence its name. It implicitly guarantees a lower bound on the effective sample size. The algorithm can be implemented efficiently, making it practically useful. We show that the expected computational effort is linear in the number of particles. Implementations for C++, R (on CRAN), Python and Matlab are available.
A secured Cryptographic Hashing Algorithm
Mohanty, Rakesh; Bishi, Sukant kumar
2010-01-01
Cryptographic hash functions for calculating the message digest of a message has been in practical use as an effective measure to maintain message integrity since a few decades. This message digest is unique, irreversible and avoids all types of collisions for any given input string. The message digest calculated from this algorithm is propagated in the communication medium along with the original message from the sender side and on the receiver side integrity of the message can be verified by recalculating the message digest of the received message and comparing the two digest values. In this paper we have designed and developed a new algorithm for calculating the message digest of any message and implemented t using a high level programming language. An experimental analysis and comparison with the existing MD5 hashing algorithm, which is predominantly being used as a cryptographic hashing tool, shows this algorithm to provide more randomness and greater strength from intrusion attacks. In this algorithm th...
A Review on Quantum Search Algorithms
Giri, Pulak Ranjan; Korepin, Vladimir E.
2016-01-01
The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It can be understood from the early invented quantum algorithms such as Deutsch's algorithm, Deutsch-Jozsa algorithm and its variation as Bernstein-Vazirani algorithm, Simon algorithm, Shor's algorithms etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science becau...
An Improved K-means Clustering Algorithm
Xiuchang Huang; Wei Su
2014-01-01
An improved k-means clustering algorithm based on K-MEANS algorithm is proposed. This paper gives an improved traditional algorithm by analyzing the statistical data. After a comparison between the actual data and the simulation data, this paper safely shows that the improved algorithm significantly reduce classification error on the simulation data set and the quality of the improved algorithm is much better than K-MEANS algorithm. Such comparative results confirm that the improved algorithm...
A New Page Ranking Algorithm Based On WPRVOL Algorithm
Directory of Open Access Journals (Sweden)
Roja Javadian Kootenae
2013-03-01
Full Text Available The amount of information on the web is always growing, thus powerful search tools are needed to search for such a large collection. Search engines in this direction help users so they can find their desirable information among the massive volume of information in an easier way. But what is important in the search engines and causes a distinction between them is page ranking algorithm used in them. In this paper a new page ranking algorithm based on "Weighted Page Ranking based on Visits of Links (WPRVOL Algorithm" for search engines is being proposed which is called WPR'VOL for short. The proposed algorithm considers the number of visits of first and second level in-links. The original WPRVOL algorithm takes into account the number of visits of first level in-links of the pages and distributes rank scores based on the popularity of the pages whereas the proposed algorithm considers both in-links of that page (first level in-links and in-links of the pages that point to it (second level in-links in order to calculation of rank of the page, hence more related pages are displayed at the top of search result list. In the summary it is said that the proposed algorithm assigns higher rank to pages that both themselves and pages that point to them be important.
Algorithmic advances in stochastic programming
Energy Technology Data Exchange (ETDEWEB)
Morton, D.P.
1993-07-01
Practical planning problems with deterministic forecasts of inherently uncertain parameters often yield unsatisfactory solutions. Stochastic programming formulations allow uncertain parameters to be modeled as random variables with known distributions, but the size of the resulting mathematical programs can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We consider two classes of decomposition-based stochastic programming algorithms. The first type of algorithm addresses problems with a ``manageable`` number of scenarios. The second class incorporates Monte Carlo sampling within a decomposition algorithm. We develop and empirically study an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs within a prespecified tolerance. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of ``real-world`` multistage stochastic hydroelectric scheduling problems. Recently, there has been an increased focus on decomposition-based algorithms that use sampling within the optimization framework. These approaches hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. With this as motivation, we develop a stopping rule theory for algorithms in which bounds on the optimal objective function value are estimated by sampling. Rules are provided for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence interval statements for the quality of the proposed solution can be verified. Issues associated with the application of this theory to two sampling-based algorithms are considered, and preliminary empirical coverage results are presented.
Cloud-based Evolutionary Algorithms: An algorithmic study
Merelo, Juan-J; Mora, Antonio M; Castillo, Pedro; Romero, Gustavo; Laredo, JLJ
2011-01-01
After a proof of concept using Dropbox(tm), a free storage and synchronization service, showed that an evolutionary algorithm using several dissimilar computers connected via WiFi or Ethernet had a good scaling behavior in terms of evaluations per second, it remains to be proved whether that effect also translates to the algorithmic performance of the algorithm. In this paper we will check several different, and difficult, problems, and see what effects the automatic load-balancing and asynchrony have on the speed of resolution of problems.
Scheduling with genetic algorithms
Fennel, Theron R.; Underbrink, A. J., Jr.; Williams, George P. W., Jr.
1994-01-01
In many domains, scheduling a sequence of jobs is an important function contributing to the overall efficiency of the operation. At Boeing, we develop schedules for many different domains, including assembly of military and commercial aircraft, weapons systems, and space vehicles. Boeing is under contract to develop scheduling systems for the Space Station Payload Planning System (PPS) and Payload Operations and Integration Center (POIC). These applications require that we respect certain sequencing restrictions among the jobs to be scheduled while at the same time assigning resources to the jobs. We call this general problem scheduling and resource allocation. Genetic algorithms (GA's) offer a search method that uses a population of solutions and benefits from intrinsic parallelism to search the problem space rapidly, producing near-optimal solutions. Good intermediate solutions are probabalistically recombined to produce better offspring (based upon some application specific measure of solution fitness, e.g., minimum flowtime, or schedule completeness). Also, at any point in the search, any intermediate solution can be accepted as a final solution; allowing the search to proceed longer usually produces a better solution while terminating the search at virtually any time may yield an acceptable solution. Many processes are constrained by restrictions of sequence among the individual jobs. For a specific job, other jobs must be completed beforehand. While there are obviously many other constraints on processes, it is these on which we focussed for this research: how to allocate crews to jobs while satisfying job precedence requirements and personnel, and tooling and fixture (or, more generally, resource) requirements.
Neighborhood-following algorithms for linear programming
Institute of Scientific and Technical Information of China (English)
AI Wenbao
2004-01-01
In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(√nL)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.
An improved form of the ELMS algorithm
Institute of Scientific and Technical Information of China (English)
Gao Ying; Xie Shengli
2005-01-01
ELMS algorithm is the first two-channel adaptive filtering algorithm that takes into account the cross-correlation between the two input signals. The algorithm does not preprocess input signals, so it does not degrade the quality of the speech. However, a lot of computer simulation results show that ELMS algorithm has a bad performance. The ELMS algorithm is analyzed firstly, then a new algorithm is presented by modifying the block matrix used in ELMS algorithm to approximate input signals self-correlation matrix. The computer simulation results indicate that the improved algorithm has a better behavior than the ELMS algorithm.
Directory of Open Access Journals (Sweden)
Ahmed Majid Taha
2015-08-01
Full Text Available In this study a new Bat Algorithm (BA based on multi-swarm technique called the Multi-Swarm Bat Algorithm (MSBA is proposed to address the problem of premature convergence phenomenon. The problem happens when search process converges to non-optimal solution due to the loss of diversity during the evolution process. MSBA was designed with improved ability in exploring new solutions, which was essential in reducing premature convergence. The exploration ability was improved by having a number of sub-swarms watching over the best local optima. In MSBA, when the quality of best local optima does not improve after a pre-defined number of iterations, the population is split equally into several smaller sub-swarms, with one of them remains close to the current best local optima for further exploitation while the other sub-swarms continue to explore for new local optima. The proposed algorithm has been applied in feature selection problem and the results were compared against eight algorithms, which are Ant Colony Optimization (ACO, Genetic Algorithm (GA, Tabu Search (TS, Scatter Search (SS, Great Deluge Algorithm (GDA and stander BA. The results showed that the MSBA is much more effective that it is able to find new best solutions at times when the rest of other algorithms are not able to.
Application of detecting algorithm based on network
Institute of Scientific and Technical Information of China (English)
张凤斌; 杨永田; 江子扬; 孙冰心
2004-01-01
Because currently intrusion detection systems cannot detect undefined intrusion behavior effectively,according to the robustness and adaptability of the genetic algorithms, this paper integrates the genetic algorithms into an intrusion detection system, and a detection algorithm based on network traffic is proposed. This algorithm is a real-time and self-study algorithm and can detect undefined intrusion behaviors effectively.
An efficient algorithm for linear programming
Venkaiah, CH V
1990-01-01
A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.
A general framework for shortest path algorithms
W.H.L.M. Pijls (Wim); A.W.J. Kolen
1992-01-01
textabstractIn this paper we present a general framework for shortest path algorithms, including amongst others Dijkstra's algorithm and the A* algorithm. By showing that all algorithms are special cases of one algorithm in which some of the nondeterministic choices are made deterministic, terminati
Solving Scheduling problems using Selective Breeding Algorithm and Hybrid Algorithm
P.Sriramya; B. Parvathavarthini; M. Chandrasekaran
2013-01-01
The n-job, m-machine scheduling problem is one of the general scheduling problems in a system. Scheduling problems vary widely according to specific production tasks but most are NP-hard problems.Scheduling problems are usually solved using heuristics to get optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using reasonable resources in many cases. In this paper, Selective Breeding Algorithm (SBA) and Hybrid Algorithm (HA) are us...
Instance-specific algorithm configuration
Malitsky, Yuri
2014-01-01
This book presents a modular and expandable technique in the rapidly emerging research area of automatic configuration and selection of the best algorithm for the instance at hand. The author presents the basic model behind ISAC and then details a number of modifications and practical applications. In particular, he addresses automated feature generation, offline algorithm configuration for portfolio generation, algorithm selection, adaptive solvers, online tuning, and parallelization. The author's related thesis was honorably mentioned (runner-up) for the ACP Dissertation Award in 2014,
Complex networks an algorithmic perspective
Erciyes, Kayhan
2014-01-01
Network science is a rapidly emerging field of study that encompasses mathematics, computer science, physics, and engineering. A key issue in the study of complex networks is to understand the collective behavior of the various elements of these networks.Although the results from graph theory have proven to be powerful in investigating the structures of complex networks, few books focus on the algorithmic aspects of complex network analysis. Filling this need, Complex Networks: An Algorithmic Perspective supplies the basic theoretical algorithmic and graph theoretic knowledge needed by every r
PRACTICAL ALGORITHMS FOR TORNADO CODES
Institute of Scientific and Technical Information of China (English)
无
2006-01-01
Tornado codes have been used in the error control of data transmission in IP network. The efficiency of this erasure codes is critically affected by the short cycles in its bipartite graph. To remove this effect,two algorithms are introduced: (1) while generating the graph, the cycle eliminating algorithm is used to reduce the number of the short cycles in it; (2) in the decoding algorithm, cycles that are inevitably in the graph are used to remove decoding efficiency degradation. The simulation results show that they have a better performance than that of general tornado codes.
EXACT ALGORITHM FOR BIN COVERING
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
This paper presents a new arc flow model for the one-dimensional bin covering problem and an algorithm to solve the problem exactly through a branch-and-bound procedure and the technique of column generation. The subproblems occuring in the procedure of branch-and-bound have the same structure and therefore can be solved by the same algorithm. In order to solve effectively the subproblems which are generally large scale, a column generation algorithm is employed. Many rules found in this paper can improve the performance of the methods.
Cluster algorithms and computational complexity
Li, Xuenan
Cluster algorithms for the 2D Ising model with a staggered field have been studied and a new cluster algorithm for path sampling has been worked out. The complexity properties of Bak-Seppen model and the Growing network model have been studied by using the Computational Complexity Theory. The dynamic critical behavior of the two-replica cluster algorithm is studied. Several versions of the algorithm are applied to the two-dimensional, square lattice Ising model with a staggered field. The dynamic exponent for the full algorithm is found to be less than 0.5. It is found that odd translations of one replica with respect to the other together with global flips are essential for obtaining a small value of the dynamic exponent. The path sampling problem for the 1D Ising model is studied using both a local algorithm and a novel cluster algorithm. The local algorithm is extremely inefficient at low temperature, where the integrated autocorrelation time is found to be proportional to the fourth power of correlation length. The dynamic exponent of the cluster algorithm is found to be zero and therefore proved to be much more efficient than the local algorithm. The parallel computational complexity of the Bak-Sneppen evolution model is studied. It is shown that Bak-Sneppen histories can be generated by a massively parallel computer in a time that is polylog in the length of the history, which means that the logical depth of producing a Bak-Sneppen history is exponentially less than the length of the history. The parallel dynamics for generating Bak-Sneppen histories is contrasted to standard Bak-Sneppen dynamics. The parallel computational complexity of the Growing Network model is studied. The growth of the network with linear kernels is shown to be not complex and an algorithm with polylog parallel running time is found. The growth of the network with gamma ≥ 2 super-linear kernels can be realized by a randomized parallel algorithm with polylog expected running time.
An investigation of genetic algorithms
International Nuclear Information System (INIS)
Genetic algorithms mimic biological evolution by natural selection in their search for better individuals within a changing population. they can be used as efficient optimizers. This report discusses the developing field of genetic algorithms. It gives a simple example of the search process and introduces the concept of schema. It also discusses modifications to the basic genetic algorithm that result in species and niche formation, in machine learning and artificial evolution of computer programs, and in the streamlining of human-computer interaction. (author). 3 refs., 1 tab., 2 figs
Subcubic Control Flow Analysis Algorithms
DEFF Research Database (Denmark)
Midtgaard, Jan; Van Horn, David
We give the first direct subcubic algorithm for performing control flow analysis of higher-order functional programs. Despite the long held belief that inclusion-based flow analysis could not surpass the ``cubic bottleneck, '' we apply known set compression techniques to obtain an algorithm...... that runs in time O(n^3/log n) on a unit cost random-access memory model machine. Moreover, we refine the initial flow analysis into two more precise analyses incorporating notions of reachability. We give subcubic algorithms for these more precise analyses and relate them to an existing analysis from...
A filtered backprojection algorithm with characteristics of the iterative landweber algorithm
L. Zeng, Gengsheng
2012-01-01
Purpose: In order to eventually develop an analytical algorithm with noise characteristics of an iterative algorithm, this technical note develops a window function for the filtered backprojection (FBP) algorithm in tomography that behaves as an iterative Landweber algorithm.
Enhanced Segment Compression Steganographic Algorithm
Directory of Open Access Journals (Sweden)
STRATULAT, M.
2013-08-01
Full Text Available Steganography is the science and art of concealing messages using techniques that allow only the sender and receiver to know of the message?s existence and be able to decipher it. In this article, we would like to present a new steganographic technique for concealing digital images: the Enhanced Segment Compression Steganographic Algorithm (ESCSA. We start by mentioning several desired properties that we have taken into consideration for our algorithm. Next, we define some quality metrics with which we can measure how well / to what extent those properties are achieved. A detailed presentation of the component parts of the algorithm follows, accompanied by quantitative analyses of parameters of interest. Finally, we discuss the strengths and weaknesses of our algorithm. In addition, we make a few suggestions regarding possible further refinements of the ESCSA.
Algorithmic Cheminformatics (Dagstuhl Seminar 14452)
DEFF Research Database (Denmark)
Banzhaf, Wolfgang; Flamm, Christoph; Merkle, Daniel;
2015-01-01
Dagstuhl Seminar 14452 “Algorithmic Cheminformatics” brought together leading researchers from both chemistry and computer science. The meeting successfully aimed at bridging in the apparent gap between the two disciplines. The participants surveyed areas of overlapping interests and identified...
Fluid-structure-coupling algorithm
International Nuclear Information System (INIS)
A fluid-structure-interaction algorithm has been developed and incorporated into the two dimensional code PELE-IC. This code combines an Eulerian incompressible fluid algorithm with a Lagrangian finite element shell algorithm and incorporates the treatment of complex free surfaces. The fluid structure, and coupling algorithms have been verified by the calculation of solved problems from the literature and from air and steam blowdown experiments. The code has been used to calculate loads and structural response from air blowdown and the oscillatory condensation of steam bubbles in water suppression pools typical of boiling water reactors. The techniques developed here have been extended to three dimensions and implemented in the computer code PELE-3D
Planar graphs theory and algorithms
Nishizeki, T
1988-01-01
Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.
Fibonacci Numbers and Computer Algorithms.
Atkins, John; Geist, Robert
1987-01-01
The Fibonacci Sequence describes a vast array of phenomena from nature. Computer scientists have discovered and used many algorithms which can be classified as applications of Fibonacci's sequence. In this article, several of these applications are considered. (PK)
Aggregation Algorithms in Heterogeneous Tables
Titus Felix FURTUNA; Ivan, Ion; Marian DARDALA
2006-01-01
The heterogeneous tables are most used in the problem of aggregation. A solution for this problem is to standardize these tables of figures. In this paper, we proposed some methods of aggregation based on the hierarchical algorithms.
Efficient Algorithms for Subgraph Listing
Directory of Open Access Journals (Sweden)
Niklas Zechner
2014-05-01
Full Text Available Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Ga̧sieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.
Quasigroup based crypto-algorithms
Shcherbacov, Victor
2012-01-01
Modifications of Markovski quasigroup based crypto-algorithm have been proposed. Some of these modifications are based on the systems of orthogonal n-ary groupoids. T-quasigroups based stream ciphers have been constructed.
Designing algorithms using CAD technologies
Directory of Open Access Journals (Sweden)
Alin IORDACHE
2008-01-01
Full Text Available A representative example of eLearning-platform modular application, Ã¢Â€Â˜Logical diagramsÃ¢Â€Â™, is intended to be a useful learning and testing tool for the beginner programmer, but also for the more experienced one. The problem this application is trying to solve concerns young programmers who forget about the fundamentals of this domain, algorithmic. Logical diagrams are a graphic representation of an algorithm, which uses different geometrical figures (parallelograms, rectangles, rhombuses, circles with particular meaning that are called blocks and connected between them to reveal the flow of the algorithm. The role of this application is to help the user build the diagram for the algorithm and then automatically generate the C code and test it.
Kernel Generalized Noise Clustering Algorithm
Institute of Scientific and Technical Information of China (English)
WU Xiao-hong; ZHOU Jian-jiang
2007-01-01
To deal with the nonlinear separable problem, the generalized noise clustering (GNC) algorithm is extended to a kernel generalized noise clustering (KGNC) model. Different from the fuzzy c-means (FCM) model and the GNC model which are based on Euclidean distance, the presented model is based on kernel-induced distance by using kernel method. By kernel method the input data are nonlinearly and implicitly mapped into a high-dimensional feature space, where the nonlinear pattern appears linear and the GNC algorithm is performed. It is unnecessary to calculate in high-dimensional feature space because the kernel function can do itjust in input space. The effectiveness of the proposed algorithm is verified by experiments on three data sets. It is concluded that the KGNC algorithm has better clustering accuracy than FCM and GNC in clustering data sets containing noisy data.
Cascade Error Projection: A New Learning Algorithm
Duong, T. A.; Stubberud, A. R.; Daud, T.; Thakoor, A. P.
1995-01-01
A new neural network architecture and a hardware implementable learning algorithm is proposed. The algorithm, called cascade error projection (CEP), handles lack of precision and circuit noise better than existing algorithms.
Multicore Processing for Clustering Algorithms
Directory of Open Access Journals (Sweden)
RekhanshRao
2012-03-01
Full Text Available Data Mining algorithms such as classification and clustering are the future of computation, though multidimensional data-processing is required. People are using multicore processors with GPU’s. Most of the programming languages doesn’t provide multiprocessing facilities and hence wastage of processing resources. Clustering and classification algorithms are more resource consuming. In this paper we have shown strategies to overcome such deficiencies using multicore processing platform OpelCL.
Subsampling algorithms for semidefinite programming
Directory of Open Access Journals (Sweden)
Alexandre W. d'Aspremont
2011-01-01
Full Text Available We derive a stochastic gradient algorithm for semidefinite optimization using randomization techniques. The algorithm uses subsampling to reduce the computational cost of each iteration and the subsampling ratio explicitly controls granularity, i.e. the tradeoff between cost per iteration and total number of iterations. Furthermore, the total computational cost is directly proportional to the complexity (i.e. rank of the solution. We study numerical performance on some large-scale problems arising in statistical learning.
Patel Nimisha; Prof. Sheetal Mehta
2013-01-01
Data mining is a process that discover the knowledge or hidden pattern from large databases. In the large database using association rules throughfind meaningful relationship between large amount of itemsets and this itemset through create frequent itemset. Association rule mining is the most paramount application in the large database. Most of the Association rule mining algorithm are improved and derivative. The traditional algorithms scan databases many times so, time complexity and space ...
Neutronic rebalance algorithms for SIMMER
International Nuclear Information System (INIS)
Four algorithms to solve the two-dimensional neutronic rebalance equations in SIMMER are investigated. Results of the study are presented and indicate that a matrix decomposition technique with a variable convergence criterion is the best solution algorithm in terms of accuracy and calculational speed. Rebalance numerical stability problems are examined. The results of the study can be applied to other neutron transport codes which use discrete ordinates techniques
Algorithms to identify failure pattern
Poudel, Bhuwan Krishna Som
2013-01-01
This project report was written for ?Algorithms to Identify Failure Pattern? at NTNU (Norwegian University of Science and Technology), IME (Faculty of Information Technology, Mathematics and Electrical Engineering) and IDI (Department of Computer Science).In software application, there are three types of failure pattern: point pattern, block pattern and stripe pattern. The purpose of the report is to prepare an algorithm that identifies the pattern in a software application. Only theoretical ...
Behavior Classification Algorithms at Intersections
Aoude, Georges; Desaraju, Vishnu Rajeswar; Stephens, Lauren H.; How, Jonathan P.
2011-01-01
The ability to classify driver behavior lays the foundation for more advanced driver assistance systems. Improving safety at intersections has also been identified as high priority due to the large number of intersection related fatalities. This paper focuses on developing algorithms for estimating driver behavior at road intersections. It introduces two classes of algorithms that can classify drivers as compliant or violating. They are based on 1) Support Vector Machines (SVM) and 2) Hidden ...
Stochastic approximation algorithms and applications
Kushner, Harold J
1997-01-01
In recent years algorithms of the stochastic approximation type have found applications in new and diverse areas, and new techniques have been developed for proofs of convergence and rate of convergence. The actual and potential applications in signal processing have exploded. New challenges have arisen in applications to adaptive control. This book presents a thorough coverage of the ODE method used to analyze these algorithms.
A memetic fingerprint matching algorithm
Sheng, Weiguo; Howells, Gareth; Fairhurst, Michael; Deravi, Farzin
2007-01-01
Minutiae point pattern matching is the most common approach for fingerprint verification. Although many minutiae point pattern matching algorithms have been proposed, reliable automatic fingerprint verification remains as a challenging problem, both with respect to recovering the optimal alignment and the construction of an adequate matching function. In this paper, we develop a memetic fingerprint matching algorithm (MFMA) which aims to identify the optimal or near optimal global matching, b...
Multicore Processing for Clustering Algorithms
RekhanshRao; Kapil Kumar Nagwanshi; SipiDubey
2012-01-01
Data Mining algorithms such as classification and clustering are the future of computation, though multidimensional data-processing is required. People are using multicore processors with GPU’s. Most of the programming languages doesn’t provide multiprocessing facilities and hence wastage of processing resources. Clustering and classification algorithms are more resource consuming. In this paper we have shown strategies to overcome such deficiencies using multicore processing platform OpelCL....
CPU Scheduling Algorithms: A Survey
Imran Qureshi
2014-01-01
Scheduling is the fundamental function of operating system. For scheduling, resources of system shared among processes which are going to be executed. CPU scheduling is a technique by which processes are allocating to the CPU for a specific time quantum. In this paper the review of different scheduling algorithms are perform with different parameters, such as running time, burst time and waiting times etc. The reviews algorithms are first come first serve, Shortest Job First, Round Robin, ...
Communication Complexity (for Algorithm Designers)
Roughgarden, Tim
2015-01-01
This document collects the lecture notes from my course "Communication Complexity (for Algorithm Designers),'' taught at Stanford in the winter quarter of 2015. The two primary goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds. Along the way, we'll also: 3. Get exposure t...
Simple Algorithm Portfolio for SAT
Nikolic, Mladen; Maric, Filip; Janicic, Predrag
2011-01-01
The importance of algorithm portfolio techniques for SAT has long been noted, and a number of very successful systems have been devised, including the most successful one --- SATzilla. However, all these systems are quite complex (to understand, reimplement, or modify). In this paper we propose a new algorithm portfolio for SAT that is extremely simple, but in the same time so efficient that it outperforms SATzilla. For a new SAT instance to be solved, our portfolio finds its k-nearest neighb...
Distributed systems an algorithmic approach
Ghosh, Sukumar
2006-01-01
Most applications in distributed computing center around a set of common subproblems. Distributed Systems: An Algorithmic Approach presents the algorithmic issues and necessary background theory that are needed to properly understand these challenges. Achieving a balance between theory and practice, this book bridges the gap between theoreticians and practitioners. With a set of exercises featured in each chapter, the book begins with background information that contains various interprocess communication techniques and middleware services, followed by foundational topics that cover system
Atrial Fibrillation and Pacing Algorithms
Terranova, Paolo; Severgnini, Barbara; Valli, Paolo; Dell'Orto, Simonetta; Greco, Enrico Maria
2006-01-01
Pacing prevention algorithms have been introduced in order to maximize the benefits of atrial pacing in atrial fibrillation prevention. It has been demonstrated that algorithms actually keep overdrive atrial pacing, reduce atrial premature contractions, and prevent short-long atrial cycle phenomenon, with good patient tolerance. However, clinical studies showed inconsistent benefits on clinical endpoints such as atrial fibrillation burden. Factors which may be responsible for neutral results ...
Evolutionary Algorithms in Astronautic Applications
Maiwald, Volker
2010-01-01
Evolutionary algorithms (EA) are a computation tool that utilizes biological principles found in the evolution theory. One major difference to other optimization methods is the fact that a large group of solutions is evaluated, not a single one. Combination of various solutions from such a group, called population, allows improvement of the solutions. Overall several terms in usage in the field of evolutionary algorithms have their origin in genetics or biology, especially the ...
Evolutionary Algorithms for Reinforcement Learning
Grefenstette, J. J.; Moriarty, D. E.; Schultz, A.C.
2011-01-01
There are two distinct approaches to solving reinforcement learning problems, namely, searching in value function space and searching in policy space. Temporal difference methods and evolutionary algorithms are well-known examples of these approaches. Kaelbling, Littman and Moore recently provided an informative survey of temporal difference methods. This article focuses on the application of evolutionary algorithms to the reinforcement learning problem, emphasizing alternative policy represe...
Evolutionary algorithms in multiobjective problems
Syomkin, A. M.; Zmitrovich, A. I.
2003-01-01
Many real-world problems involve two types of difficulties: 1) multiple, conflicting objectives and 2) a highly complex search space. Efficient evolutionary strategies have been developed to deal with both types of difficulties. Evolutionary algorithms possess several characteristics such as parallelism and robustness that make them preferable to classical optimization methods. In this work 1 conducted comparative studies among the well-known evolutionary algorithms based on NP-hard 0-1 multi...
Larson, Harold J.; Jayachandran, Toke.
1983-01-01
The Comprehensive Engine Management System (CEMS) Phase IV, will provide real time data analysis capability for all Air Force oil analysis laboratories. This paper describes the statistical algorithm used by this system to aid the oil analysis technician in making his recommendations. The algorithm incorporates usage and oil consumption variables, and employs least squares to minimize the effects of the random errors in the spectrometer readings. Prepared for: Directorate of M...
Clustering algorithm incorporating density and direction
Song, Yu-Chen; O'Grady, Michael J; O'Hare, G. M. P.; Wang, Wei
2008-01-01
This paper analyses the advantages and disadvantages of the K-means algorithm and the DENCLUE algorithm. In order to realise the automation of clustering analysis and eliminate human factors, both partitioning and density-based methods were adopted, resulting in a new algorithm – Clustering Algorithm based on object Density and Direction (CADD). This paper discusses the theory and algorithm design of the CADD algorithm. As an illustration of its applicability, CADD was used to cluster r...
United assembly algorithm for optical burst switching
Institute of Scientific and Technical Information of China (English)
Jinhui Yu(于金辉); Yijun Yang(杨教军); Yuehua Chen(陈月华); Ge Fan(范戈)
2003-01-01
Optical burst switching (OBS) is a promising optical switching technology. The burst assembly algorithm controls burst assembly, which significantly impacts performance of OBS network. This paper provides a new assembly algorithm, united assembly algorithm, which has more practicability than conventional algorithms. In addition, some factors impacting selections of parameters of this algorithm are discussed and the performance of this algorithm is studied by computer simulation.
Constructing a Scheduling Algorithm For Multidirectional Elevators
Edlund, Joakim; Berntsson, Fredrik
2015-01-01
With this thesis we aim to create an efficient scheduling algorithm for elevators that can move in multiple directions and establish if and when the algorithm is efficient in comparison to algorithms constructed for traditional elevator algorithms. To measure efficiency, a simulator is constructed to simulate an elevator system implementing different algorithms. Because of the challenge of constructing a simulator and since we did not find either a simulator nor any algorithms for use in mult...
Improved Apriori Algorithm for Mining Association Rules
Darshan M. Tank
2014-01-01
Association rules are the main technique for data mining. Apriori algorithm is a classical algorithm of association rule mining. Lots of algorithms for mining association rules and their mutations are proposed on basis of Apriori algorithm, but traditional algorithms are not efficient. For the two bottlenecks of frequent itemsets mining: the large multitude of candidate 2- itemsets, the poor efficiency of counting their support. Proposed algorithm reduces one redundant pruning operations of C...
Some tactical algorithms for spherical geometry
Shudde, Rex H.
1986-01-01
This report presents two great circle navigation algorithms, a closest point of approach algorithm and intercept algorithm. It also presents an implementation program for the algorithms that is written in the BASIC language for an IBM PC. Instead of using classical spherical geometry or the general spherical triangle, these algorithms incorporate rectangular coordinates and vectors on the surface of the spherical. The intent of the report is to provide algorithms for spherical earth models th...
Efficient iterative adaptive pole placement algorithm
Institute of Scientific and Technical Information of China (English)
李俊民; 李靖; 杨磊
2004-01-01
An iterative adaptive pole placement algorithm is presented. The stability and the convergence of the algorithm are respectively established. Since one-step iterative formulation in computing controller's parameters is used, the on-line computation cost is greatly reduced with respected to the traditional algorithm. The algorithm with the feed-forward can follow arbitrarily bounded output. The algorithm is also extended to multivariate case. Simulation examples show the efficiency and robustness of the algorithm.
Swarm Intelligence Based Algorithms: A Critical Analysis
Yang, Xin-She
2014-01-01
Many optimization algorithms have been developed by drawing inspiration from swarm intelligence (SI). These SI-based algorithms can have some advantages over traditional algorithms. In this paper, we carry out a critical analysis of these SI-based algorithms by analyzing their ways to mimic evolutionary operators. We also analyze the ways of achieving exploration and exploitation in algorithms by using mutation, crossover and selection. In addition, we also look at algorithms using dynamic sy...
Multithreaded Algorithms for Graph Coloring
Energy Technology Data Exchange (ETDEWEB)
Catalyurek, Umit V.; Feo, John T.; Gebremedhin, Assefaw H.; Halappanavar, Mahantesh; Pothen, Alex
2012-10-21
Graph algorithms are challenging to parallelize when high performance and scalability are primary goals. Low concurrency, poor data locality, irregular access pattern, and high data access to computation ratio are among the chief reasons for the challenge. The performance implication of these features is exasperated on distributed memory machines. More success is being achieved on shared-memory, multi-core architectures supporting multithreading. We consider a prototypical graph problem, coloring, and show how a greedy algorithm for solving it can be e*ectively parallelized on multithreaded architectures. We present in particular two di*erent parallel algorithms. The first relies on speculation and iteration, and is suitable for any shared-memory, multithreaded system. The second uses data ow principles and is targeted at the massively multithreaded Cray XMT system. We benchmark the algorithms on three di*erent platforms and demonstrate scalable runtime performance. In terms of quality of solution, both algorithms use nearly the same number of colors as the serial algorithm.
TRAVERSAL ALGORITHM FOR COMPLETE COVERAGE
Directory of Open Access Journals (Sweden)
Coimbatore Ganeshsankar Balaji
2012-01-01
Full Text Available There are many applications which require complete coverage and obstacle avoidance. The classical A* algorithm provides the user a shortest path by avoiding the obstacle. As well, the Dijkstraâs algorithm finds the shortest path between the source and destination. But in many applications we require complete coverage of the proposed area with obstacle avoidance. There are LSP, LSSP, BSA, spiral-STC and Complete Coverage D* algorithms which do not realize complete (100% coverage. The complete coverage using a critical point algorithm assures complete coverage, but it is not well suited for applications like mine detection. Also for covering the missed region it keeps the obstacle as a critical point which is not advisable in critical applications where obstacle may be a dangerous one. To overcome this and to achieve the complete coverage we propose a novel graph traversal algorithm Traversal Algorithm for Complete Coverage (TRACC. Here the area to be scanned is decomposed into a finite number of cells. The traversal is done through all the cells after making sure the next cell has no obstacle. TRACC assures thorough coverage of the proposed area and ensuring that all the obstacles are avoided. Hence the TRACC always have the safer path while covering the entire area. It also reports the obstacle placed or blocked cell.
Recursive Branching Simulated Annealing Algorithm
Bolcar, Matthew; Smith, J. Scott; Aronstein, David
2012-01-01
This innovation is a variation of a simulated-annealing optimization algorithm that uses a recursive-branching structure to parallelize the search of a parameter space for the globally optimal solution to an objective. The algorithm has been demonstrated to be more effective at searching a parameter space than traditional simulated-annealing methods for a particular problem of interest, and it can readily be applied to a wide variety of optimization problems, including those with a parameter space having both discrete-value parameters (combinatorial) and continuous-variable parameters. It can take the place of a conventional simulated- annealing, Monte-Carlo, or random- walk algorithm. In a conventional simulated-annealing (SA) algorithm, a starting configuration is randomly selected within the parameter space. The algorithm randomly selects another configuration from the parameter space and evaluates the objective function for that configuration. If the objective function value is better than the previous value, the new configuration is adopted as the new point of interest in the parameter space. If the objective function value is worse than the previous value, the new configuration may be adopted, with a probability determined by a temperature parameter, used in analogy to annealing in metals. As the optimization continues, the region of the parameter space from which new configurations can be selected shrinks, and in conjunction with lowering the annealing temperature (and thus lowering the probability for adopting configurations in parameter space with worse objective functions), the algorithm can converge on the globally optimal configuration. The Recursive Branching Simulated Annealing (RBSA) algorithm shares some features with the SA algorithm, notably including the basic principles that a starting configuration is randomly selected from within the parameter space, the algorithm tests other configurations with the goal of finding the globally optimal
BACKPROPAGATION LEARNING ALGORITHM BASED ON LEVENBERG MARQUARDT ALGORITHM
Directory of Open Access Journals (Sweden)
S.Sapna
2012-10-01
Full Text Available Data Mining aims at discovering knowledge out of data and presenting it in a form that is easily compressible to humans. Data Mining represents a process developed to examine large amounts of data routinely collected. The term also refers to a collection of tools used to perform the process. One of the useful applications in the field of medicine is the incurable chronic disease diabetes. Data Mining algorithm is used for testing the accuracy in predicting diabetic status. Fuzzy Systems are been used for solving a wide range of problems in different application domain and Genetic Algorithm for designing. Fuzzy systems allows in introducing the learning and adaptation capabilities. Neural Networks are efficiently used for learning membership functions. Diabetes occurs throughout the world, but Type 2 is more common in the most developed countries. The greater increase in prevalence is however expected in Asia and Africa where most patients will likely be found by 2030. This paper is proposed on the Levenberg – Marquardt algorithm which is specifically designed to minimize sum-of-square error functions. Levernberg-Marquardt algorithm gives the best performance in the prediction of diabetes compared to any other backpropogation algorithm.
Improved autonomous star identification algorithm
Luo, Li-Yan; Xu, Lu-Ping; Zhang, Hua; Sun, Jing-Rong
2015-06-01
The log-polar transform (LPT) is introduced into the star identification because of its rotation invariance. An improved autonomous star identification algorithm is proposed in this paper to avoid the circular shift of the feature vector and to reduce the time consumed in the star identification algorithm using LPT. In the proposed algorithm, the star pattern of the same navigation star remains unchanged when the stellar image is rotated, which makes it able to reduce the star identification time. The logarithmic values of the plane distances between the navigation and its neighbor stars are adopted to structure the feature vector of the navigation star, which enhances the robustness of star identification. In addition, some efforts are made to make it able to find the identification result with fewer comparisons, instead of searching the whole feature database. The simulation results demonstrate that the proposed algorithm can effectively accelerate the star identification. Moreover, the recognition rate and robustness by the proposed algorithm are better than those by the LPT algorithm and the modified grid algorithm. Project supported by the National Natural Science Foundation of China (Grant Nos. 61172138 and 61401340), the Open Research Fund of the Academy of Satellite Application, China (Grant No. 2014_CXJJ-DH_12), the Fundamental Research Funds for the Central Universities, China (Grant Nos. JB141303 and 201413B), the Natural Science Basic Research Plan in Shaanxi Province, China (Grant No. 2013JQ8040), the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20130203120004), and the Xi’an Science and Technology Plan, China (Grant. No CXY1350(4)).
Convergent message passing algorithms - a unifying view
Meltzer, Talya; Weiss, Yair
2012-01-01
Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right...
Contact-impact algorithms on parallel computers
International Nuclear Information System (INIS)
Contact-impact algorithms on parallel computers are discussed within the context of explicit finite element analysis. The algorithms concerned include a contact searching algorithm and an algorithm for contact force calculations. The contact searching algorithm is based on the territory concept of the general HITA algorithm. However, no distinction is made between different contact bodies, or between different contact surfaces. All contact segments from contact boundaries are taken as a single set. Hierarchy territories and contact territories are expanded. A three-dimensional bucket sort algorithm is used to sort contact nodes. The defence node algorithm is used in the calculation of contact forces. Both the contact searching algorithm and the defence node algorithm are implemented on the connection machine CM-200. The performance of the algorithms is examined under different circumstances, and numerical results are presented. ((orig.))
A Review on Quantum Search Algorithms
Giri, Pulak Ranjan
2016-01-01
The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It can be understood from the early invented quantum algorithms such as Deutsch's algorithm, Deutsch-Jozsa algorithm and its variation as Bernstein-Vazirani algorithm, Simon algorithm, Shor's algorithms etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science because it comes as a subroutine in many important algorithms. Quantum database search of Grover achieves the task of finding the target element in an unsorted database in a time quadratically faster than the classical computer. We review the Grover quantum search algorithms for a singe and multiple target elements in a database. The partial search algorithm of Grover and Radhakrishnan and its optimization by Korepin, called GRK algorithm are also discussed.
Ensemble algorithms in reinforcement learning.
Wiering, Marco A; van Hasselt, Hado
2008-08-01
This paper describes several ensemble methods that combine multiple different reinforcement learning (RL) algorithms in a single agent. The aim is to enhance learning speed and final performance by combining the chosen actions or action probabilities of different RL algorithms. We designed and implemented four different ensemble methods combining the following five different RL algorithms: Q-learning, Sarsa, actor-critic (AC), QV-learning, and AC learning automaton. The intuitively designed ensemble methods, namely, majority voting (MV), rank voting, Boltzmann multiplication (BM), and Boltzmann addition, combine the policies derived from the value functions of the different RL algorithms, in contrast to previous work where ensemble methods have been used in RL for representing and learning a single value function. We show experiments on five maze problems of varying complexity; the first problem is simple, but the other four maze tasks are of a dynamic or partially observable nature. The results indicate that the BM and MV ensembles significantly outperform the single RL algorithms. PMID:18632380
SDR Input Power Estimation Algorithms
Nappier, Jennifer M.; Briones, Janette C.
2013-01-01
The General Dynamics (GD) S-Band software defined radio (SDR) in the Space Communications and Navigation (SCAN) Testbed on the International Space Station (ISS) provides experimenters an opportunity to develop and demonstrate experimental waveforms in space. The SDR has an analog and a digital automatic gain control (AGC) and the response of the AGCs to changes in SDR input power and temperature was characterized prior to the launch and installation of the SCAN Testbed on the ISS. The AGCs were used to estimate the SDR input power and SNR of the received signal and the characterization results showed a nonlinear response to SDR input power and temperature. In order to estimate the SDR input from the AGCs, three algorithms were developed and implemented on the ground software of the SCAN Testbed. The algorithms include a linear straight line estimator, which used the digital AGC and the temperature to estimate the SDR input power over a narrower section of the SDR input power range. There is a linear adaptive filter algorithm that uses both AGCs and the temperature to estimate the SDR input power over a wide input power range. Finally, an algorithm that uses neural networks was designed to estimate the input power over a wide range. This paper describes the algorithms in detail and their associated performance in estimating the SDR input power.
FEATURE SELECTION METHODS AND ALGORITHMS
Directory of Open Access Journals (Sweden)
L.Ladha,
2011-05-01
Full Text Available Feature selection is an important topic in data mining, especially for high dimensional datasets. Feature selection (also known as subset selection is a process commonly used in machine learning, wherein subsets of the features available from the data are selected for application of a learning algorithm. The best subset contains the least number of dimensions that most contribute to accuracy; wediscard the remaining, unimportant dimensions. This is an important stage of preprocessing and is one of two ways of avoiding the curse of dimensionality (the other is feature extraction. There are twoapproaches in Feature selection known as Forward selection and backward selection. Feature selection has been an active research area in pattern recognition, statistics, and data mining communities.The main idea of feature selection is to choose a subset of input variables by eliminating features with little or no predictive information. Feature selection methods can be decomposed into three broad classes. One is Filter methods and another one is Wrapper method and the third one is Embedded method. This paper presents an empirical comparison of feature selection methods and its algorithms. In view of the substantial number of existing feature selection algorithms, the need arises to count on criteria that enable to adequately decide which algorithm to use in certain situations. This work reviews several fundamental algorithms found in the literature and assesses their performance in a controlled scenario.
Algorithms, complexity, and the sciences.
Papadimitriou, Christos
2014-11-11
Algorithms, perhaps together with Moore's law, compose the engine of the information technology revolution, whereas complexity--the antithesis of algorithms--is one of the deepest realms of mathematical investigation. After introducing the basic concepts of algorithms and complexity, and the fundamental complexity classes P (polynomial time) and NP (nondeterministic polynomial time, or search problems), we discuss briefly the P vs. NP problem. We then focus on certain classes between P and NP which capture important phenomena in the social and life sciences, namely the Nash equlibrium and other equilibria in economics and game theory, and certain processes in population genetics and evolution. Finally, an algorithm known as multiplicative weights update (MWU) provides an algorithmic interpretation of the evolution of allele frequencies in a population under sex and weak selection. All three of these equivalences are rife with domain-specific implications: The concept of Nash equilibrium may be less universal--and therefore less compelling--than has been presumed; selection on gene interactions may entail the maintenance of genetic variation for longer periods than selection on single alleles predicts; whereas MWU can be shown to maximize, for each gene, a convex combination of the gene's cumulative fitness in the population and the entropy of the allele distribution, an insight that may be pertinent to the maintenance of variation in evolution. PMID:25349382
Energy Technology Data Exchange (ETDEWEB)
Hindmarsh, A.C.
2000-12-01
In October-November 2000, I gave a series of talks, describing in some detail the algorithms in two general-purpose solvers: (1) the PVODE solver for systems of ordinary differential equations (ODEs), and (2) the IDA solver for systems of differential-algebraic equations (DAEs). The material was organized into three parts: (1) Part A: Overview; (2) Part B: The PVODE Algorithm; and (3) Part C: The IDA Algorithm. This document consists of the viewgraphs for the corresponding three talks. Except for the correction of some minor errors, the talk viewgraphs are given here exactly as presented. Each of the three sets of pages is numbered independently, with page numbers starting at 1. A brief outline of each of the talks, and a list of references, is also included in the report, some of which are cited in the viewgraphs.
Some nonlinear space decomposition algorithms
Energy Technology Data Exchange (ETDEWEB)
Tai, Xue-Cheng; Espedal, M. [Univ. of Bergen (Norway)
1996-12-31
Convergence of a space decomposition method is proved for a general convex programming problem. The space decomposition refers to methods that decompose a space into sums of subspaces, which could be a domain decomposition or a multigrid method for partial differential equations. Two algorithms are proposed. Both can be used for linear as well as nonlinear elliptic problems and they reduce to the standard additive and multiplicative Schwarz methods for linear elliptic problems. Two {open_quotes}hybrid{close_quotes} algorithms are also presented. They converge faster than the additive one and have better parallelism than the multiplicative method. Numerical tests with a two level domain decomposition for linear, nonlinear and interface elliptic problems are presented for the proposed algorithms.
Simple Algorithm Portfolio for SAT
Nikolic, Mladen; Janicic, Predrag
2011-01-01
The importance of algorithm portfolio techniques for SAT has long been noted, and a number of very successful systems have been devised, including the most successful one --- SATzilla. However, all these systems are quite complex (to understand, reimplement, or modify). In this paper we propose a new algorithm portfolio for SAT that is extremely simple, but in the same time so efficient that it outperforms SATzilla. For a new SAT instance to be solved, our portfolio finds its k-nearest neighbors from the training set and invokes a solver that performs the best at those instances. The main distinguishing feature of our algorithm portfolio is the locality of the selection procedure --- the selection of a SAT solver is based only on few instances similar to the input one.
Evaluation of Rule Extraction Algorithms
Directory of Open Access Journals (Sweden)
Tiruveedula GopiKrishna
2014-05-01
Full Text Available For the data mining domain, the lack of explanation facilities seems to be a serious drawback for techniques based on Artificial Neural Networks, or, for that matter, any technique producing opaque models In particular, the ability to generate even limited explanations is absolutely crucial for user acceptance of such systems. Since the purpose of most data mining systems is to support decision making,the need for explanation facilities in these systems is apparent. The task for the data miner is thus to identify the complex but general relationships that are likely to carry over to production data and the explanation facility makes this easier. Also focused the quality of the extracted rules; i.e. how well the required explanation is performed. In this research some important rule extraction algorithms are discussed and identified the algorithmic complexity; i.e. how efficient the underlying rule extraction algorithm is
DSTATCOM Control Algorithms: A Review
Directory of Open Access Journals (Sweden)
Ambarnath Banerji
2012-06-01
Full Text Available The concept that an inverter can be used as a generalized impedance converter to realize either inductive or capacitive reactance has been widely used to mitigate power quality issues of distribution networks. One such device is the DSTATCOM which is connected in shunt at the load end. The heart of the DSTATCOM is a converter. The control algorithm of the converter is very important. It causes the converter to address the power quality problems in efficient manner. This paper discusses the various control algorithms of the converter. The manners in which the power quality issues are mitigated by the converter are also explored. Simulations of the control algorithms are made on MATLAB platform to ascertain the effectiveness of each control method for power quality mitigation.
Throughput Analysis of Symmetric Algorithms
Directory of Open Access Journals (Sweden)
S. Pavithra
2012-09-01
Full Text Available Today’s world, for secure data transmission via Internet or any public network, there is no alternative to cryptography. The role of cryptography is most important in the field of network security. In this paper, we compare the various cryptographic algorithms. On the basis of parameter taken as time various cryptographic algorithms are evaluated on different audio and video files. Different audio and video files are having different processing speed on which various size of file are processed. Calculation of time for encryption and decryption in different audio and video file format such as .vob, .mp3 and .DAT, having file size for audio 1 MB to 10MB and for video 1MB to 1100MB respectively. Encryption processing time and decryption processing time are compared between various cryptographic algorithms which come out to be not too much. Overall time depend on the corresponding file size. Throughput analysis also done.
Quantum walks and search algorithms
Portugal, Renato
2013-01-01
This book addresses an interesting area of quantum computation called quantum walks, which play an important role in building quantum algorithms, in particular search algorithms. Quantum walks are the quantum analogue of classical random walks. It is known that quantum computers have great power for searching unsorted databases. This power extends to many kinds of searches, particularly to the problem of finding a specific location in a spatial layout, which can be modeled by a graph. The goal is to find a specific node knowing that the particle uses the edges to jump from one node to the next. This book is self-contained with main topics that include: Grover's algorithm, describing its geometrical interpretation and evolution by means of the spectral decomposition of the evolution operater Analytical solutions of quantum walks on important graphs like line, cycles, two-dimensional lattices, and hypercubes using Fourier transforms Quantum walks on generic graphs, describing methods to calculate the limiting d...
Fisher Algorithm: Variations And Applications
Directory of Open Access Journals (Sweden)
Adegoke
2013-12-01
Full Text Available This paper examines Fisherface (Linear Discriminant Analysis methods, its different modifications as applied to feature extraction in face recognition. Researchers showed that Fisher algorithm, though it performs better than PCA, Eigenface and some other fundamental methods, computational complexity, enormous hardware resources usage are inhibitors to its implementation. Different versions or adaptations of Fisher algorithm had been developed, and applied to face recognition and validated using some of the available public face databases. If fisher algorithm and its various variations had so marvelously helped in face recognition, application of this effective dimensionality reduction method can be applied to research area of iris recognition system. This will in return enhance performance of biometric systems in its application to computer security and surveillance.
A Spectral Canonical Electrostatic Algorithm
Webb, Stephen D
2015-01-01
Studying single-particle dynamics over many periods of oscillations is a well-understood problem solved using symplectic integration. Such integration schemes derive their update sequence from an approximate Hamiltonian, guaranteeing that the geometric structure of the underlying problem is preserved. Simulating a self-consistent system over many oscillations can introduce numerical artifacts such as grid heating. This unphysical heating stems from using non-symplectic methods on Hamiltonian systems. With this guidance, we derive an electrostatic algorithm using a discrete form of Hamilton's Principle. The resulting algorithm, a gridless spectral electrostatic macroparticle model, does not exhibit the unphysical heating typical of most particle-in-cell methods. We present results of this using a two-body problem as an example of the algorithm's energy- and momentum-conserving properties.
The Fast Fibonacci Decompression Algorithm
Baca, R; Platos, J; Kratky, M; El-Qawasmeh, E
2007-01-01
Data compression has been widely applied in many data processing areas. Compression methods use variable-size codes with the shorter codes assigned to symbols or groups of symbols that appear in the data frequently. Fibonacci coding, as a representative of these codes, is used for compressing small numbers. Time consumption of a decompression algorithm is not usually as important as the time of a compression algorithm. However, efficiency of the decompression may be a critical issue in some cases. For example, a real-time compression of tree data structures follows this issue. Tree's pages are decompressed during every reading from a secondary storage into the main memory. In this case, the efficiency of a decompression algorithm is extremely important. We have developed a Fast Fibonacci decompression for this purpose. Our approach is up to $3.5\\times$ faster than the original implementation.
Firefly Algorithm for Structural Search.
Avendaño-Franco, Guillermo; Romero, Aldo H
2016-07-12
The problem of computational structure prediction of materials is approached using the firefly (FF) algorithm. Starting from the chemical composition and optionally using prior knowledge of similar structures, the FF method is able to predict not only known stable structures but also a variety of novel competitive metastable structures. This article focuses on the strengths and limitations of the algorithm as a multimodal global searcher. The algorithm has been implemented in software package PyChemia ( https://github.com/MaterialsDiscovery/PyChemia ), an open source python library for materials analysis. We present applications of the method to van der Waals clusters and crystal structures. The FF method is shown to be competitive when compared to other population-based global searchers. PMID:27232694
Projection Classification Based Iterative Algorithm
Zhang, Ruiqiu; Li, Chen; Gao, Wenhua
2015-05-01
Iterative algorithm has good performance as it does not need complete projection data in 3D image reconstruction area. It is possible to be applied in BGA based solder joints inspection but with low convergence speed which usually acts with x-ray Laminography that has a worse reconstruction image compared to the former one. This paper explores to apply one projection classification based method which tries to separate the object to three parts, i.e. solute, solution and air, and suppose that the reconstruction speed decrease from solution to two other parts on both side lineally. And then SART and CAV algorithms are improved under the proposed idea. Simulation experiment result with incomplete projection images indicates the fast convergence speed of the improved iterative algorithms and the effectiveness of the proposed method. Less the projection images, more the superiority is also founded.
Fault Tolerant External Memory Algorithms
DEFF Research Database (Denmark)
Jørgensen, Allan Grønlund; Brodal, Gerth Stølting; Mølhave, Thomas
2009-01-01
Algorithms dealing with massive data sets are usually designed for I/O-efficiency, often captured by the I/O model by Aggarwal and Vitter. Another aspect of dealing with massive data is how to deal with memory faults, e.g. captured by the adversary based faulty memory RAM by Finocchi and Italiano....... However, current fault tolerant algorithms do not scale beyond the internal memory. In this paper we investigate for the first time the connection between I/O-efficiency in the I/O model and fault tolerance in the faulty memory RAM, and we assume that both memory and disk are unreliable. We show a lower...... bound on the number of I/Os required for any deterministic dictionary that is resilient to memory faults. We design a static and a dynamic deterministic dictionary with optimal query performance as well as an optimal sorting algorithm and an optimal priority queue. Finally, we consider scenarios where...
Algorithms for Decision Tree Construction
Chikalov, Igor
2011-01-01
The study of algorithms for decision tree construction was initiated in 1960s. The first algorithms are based on the separation heuristic [13, 31] that at each step tries dividing the set of objects as evenly as possible. Later Garey and Graham [28] showed that such algorithm may construct decision trees whose average depth is arbitrarily far from the minimum. Hyafil and Rivest in [35] proved NP-hardness of DT problem that is constructing a tree with the minimum average depth for a diagnostic problem over 2-valued information system and uniform probability distribution. Cox et al. in [22] showed that for a two-class problem over information system, even finding the root node attribute for an optimal tree is an NP-hard problem. © Springer-Verlag Berlin Heidelberg 2011.
Algorithms for Protein Structure Prediction
DEFF Research Database (Denmark)
Paluszewski, Martin
-trace. Here we present three different approaches for reconstruction of C-traces from predictable measures. In our first approach [63, 62], the C-trace is positioned on a lattice and a tabu-search algorithm is applied to find minimum energy structures. The energy function is based on half-sphere-exposure (HSE......) is more robust than standard Monte Carlo search. In the second approach for reconstruction of C-traces, an exact branch and bound algorithm has been developed [67, 65]. The model is discrete and makes use of secondary structure predictions, HSE, CN and radius of gyration. We show how to compute good lower...... bounds for partial structures very fast. Using these lower bounds, we are able to find global minimum structures in a huge conformational space in reasonable time. We show that many of these global minimum structures are of good quality compared to the native structure. Our branch and bound algorithm...
An inversion algorithm for general tridiagonal matrix
Institute of Scientific and Technical Information of China (English)
Rui-sheng RAN; Ting-zhu HUANG; Xing-ping LIU; Tong-xiang GU
2009-01-01
An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established.The algorithm is then generalized to deal with a general tridiagonal matrix without any restriction. Comparison with other methods is provided, indicating low computational complexity of the proposed algorithm, and its applicability to general tridiagonal matrices.
A Modified Algorithm for Feedforward Neural Networks
Institute of Scientific and Technical Information of China (English)
夏战国; 管红杰; 李政伟; 孟斌
2002-01-01
As a most popular learning algorithm for the feedforward neural networks, the classic BP algorithm has its many shortages. To overcome some of the shortages, a modified learning algorithm is proposed in the article. And the simulation result illustrate the modified algorithm is more effective and practicable.
Seamless Merging of Hypertext and Algorithm Animation
Karavirta, Ville
2009-01-01
Online learning material that students use by themselves is one of the typical usages of algorithm animation (AA). Thus, the integration of algorithm animations into hypertext is seen as an important topic today to promote the usage of algorithm animation in teaching. This article presents an algorithm animation viewer implemented purely using…
Scalable and Efficient Improved Apriori Algorithm
NUTAN DHANGE; PROF. SHEETAL DHANDE
2013-01-01
Apriori algorithm is a classical algorithm of association rule mining and widely used for mining association rule which uses frequent item. Based on the Apriori algorithm analysis and research, this paper points out the main problems on the application, and puts forward the improved This paper presents an improved Apriori algorithm to increase the efficiency of generating association rules.
Generalized Evolutionary Algorithm based on Tsallis Statistics
Dukkipati, Ambedkar; Murty, M. Narasimha; Bhatnagar, Shalabh
2004-01-01
Generalized evolutionary algorithm based on Tsallis canonical distribution is proposed. The algorithm uses Tsallis generalized canonical distribution to weigh the configurations for `selection' instead of Gibbs-Boltzmann distribution. Our simulation results show that for an appropriate choice of non-extensive index that is offered by Tsallis statistics, evolutionary algorithms based on this generalization outperform algorithms based on Gibbs-Boltzmann distribution.
HEATR project: ATR algorithm parallelization
Deardorf, Catherine E.
1998-09-01
High Performance Computing (HPC) Embedded Application for Target Recognition (HEATR) is a project funded by the High Performance Computing Modernization Office through the Common HPC Software Support Initiative (CHSSI). The goal of CHSSI is to produce portable, parallel, multi-purpose, freely distributable, support software to exploit emerging parallel computing technologies and enable application of scalable HPC's for various critical DoD applications. Specifically, the CHSSI goal for HEATR is to provide portable, parallel versions of several existing ATR detection and classification algorithms to the ATR-user community to achieve near real-time capability. The HEATR project will create parallel versions of existing automatic target recognition (ATR) detection and classification algorithms and generate reusable code that will support porting and software development process for ATR HPC software. The HEATR Team has selected detection/classification algorithms from both the model- based and training-based (template-based) arena in order to consider the parallelization requirements for detection/classification algorithms across ATR technology. This would allow the Team to assess the impact that parallelization would have on detection/classification performance across ATR technology. A field demo is included in this project. Finally, any parallel tools produced to support the project will be refined and returned to the ATR user community along with the parallel ATR algorithms. This paper will review: (1) HPCMP structure as it relates to HEATR, (2) Overall structure of the HEATR project, (3) Preliminary results for the first algorithm Alpha Test, (4) CHSSI requirements for HEATR, and (5) Project management issues and lessons learned.
Decryption of pure-position permutation algorithms
Institute of Scientific and Technical Information of China (English)
赵晓宇; 陈刚; 张亶; 王肖虹; 董光昌
2004-01-01
Pure position permutation image encryption algorithms, commonly used as image encryption investigated in this work are unfortunately frail under known-text attack. In view of the weakness of pure position permutation algorithm,we put forward an effective decryption algorithm for all pure-position permutation algorithms. First, a summary of the pure position permutation image encryption algorithms is given by introducing the concept of ergodic matrices. Then, by using probability theory and algebraic principles, the decryption probability of pure-position permutation algorithms is verified theoretically; and then, by defining the operation system of fuzzy ergodic matrices, we improve a specific decryption al-gorithm. Finally, some simulation results are shown.
Old And New Algorithms For Toeplitz Systems
Brent, Richard P.
1988-02-01
Toeplitz linear systems and Toeplitz least squares problems commonly arise in digital signal processing. In this paper we survey some old, "well known" algorithms and some recent algorithms for solving these problems. We concentrate our attention on algorithms which can be implemented efficiently on a variety of parallel machines (including pipelined vector processors and systolic arrays). We distinguish between algorithms which require inner products, and algorithms which avoid inner products, and thus are better suited to parallel implementation on some parallel architectures. Finally, we mention some "asymptotically fast" 0(n(log n)2) algorithms and compare them with 0(n2) algorithms.
An Improved Cognitive Radio Spectrum Sensing Algorithm
Li Xiao; Kuankuan Li; Dengyin Zhang
2013-01-01
To improve the cognitive radio user’s detection performance and reduce the complexity, this paper composites the Fractal box dimension algorithm and the 3th-order cyclic-cumulate (TCC) algorithm and improves the TCC algorithm, so a novel detection algorithm is proposed that the Fractal box dimension is used when the signal to noise (SNR) is high, while the improved TCC algorithm is used when the SNR is low. This new algorithm not only avoids using TCC algorithm with high complexity when the c...
NEW HMM ALGORITHM FOR TOPOLOGY OPTIMIZATION
Institute of Scientific and Technical Information of China (English)
Zuo Kongtian; Zhao Yudong; Chen Liping; Zhong Yifang; Huang Yuying
2005-01-01
A new hybrid MMA-MGCMMA (HMM) algorithm for solving topology optimization problems is presented. This algorithm combines the method of moving asymptotes (MMA) algorithm and the modified globally convergent version of the method of moving asymptotes (MGCMMA) algorithm in the optimization process. This algorithm preserves the advantages of both MMA and MGCMMA. The optimizer is switched from MMA to MGCMMA automatically, depending on the numerical oscillation value existing in the calculation. This algorithm can improve calculation efficiency and accelerate convergence compared with simplex MMA or MGCMMA algorithms, which is proven with an example.
A Note on Shor's Quantum Algorithm
Institute of Scientific and Technical Information of China (English)
CAO Zheng-jun; LIU Li-hua
2006-01-01
Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller's randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus,an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor's algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.
New recursive algorithm for matrix inversion
Institute of Scientific and Technical Information of China (English)
Cao Jianshu; Wang Xuegang
2008-01-01
To reduce the computational complexity of matrix inversion, which is the majority of processing in many practical applications, two numerically efficient recursive algorithms (called algorithms Ⅰ and Ⅱ, respectively)are presented. Algorithm Ⅰ is used to calculate the inverse of such a matrix, whose leading principal minors are all nonzero. Algorithm Ⅱ, whereby, the inverse of an arbitrary nonsingular matrix can be evaluated is derived via improving the algorithm Ⅰ. The implementation, for algorithm Ⅱ or Ⅰ, involves matrix-vector multiplications and vector outer products. These operations are computationally fast and highly parallelizable. MATLAB simulations show that both recursive algorithms are valid.
An Algorithm for Streaming Clustering
Tang, Jiaowei
2011-01-01
A simple existing data stream clustering algorithm DenStream based on DBScan is studied. Based on DenStream a modified algorithm called DenStream2 is proposed. It follows most of the framework and theory of DenStream. Denstream2 is implemented as a foreign function in an extensible data stream management system (DSMS), where queries over streams are allowed. The generated clusters inferred from each window of an input a data stream are emitted as new stream clusters. The output stream can be ...
Hill climbing algorithms and trivium
DEFF Research Database (Denmark)
Borghoff, Julia; Knudsen, Lars Ramkilde; Matusiewicz, Krystian
2011-01-01
This paper proposes a new method to solve certain classes of systems of multivariate equations over the binary field and its cryptanalytical applications. We show how heuristic optimization methods such as hill climbing algorithms can be relevant to solving systems of multivariate equations. A...... characteristic of equation systems that may be efficiently solvable by the means of such algorithms is provided. As an example, we investigate equation systems induced by the problem of recovering the internal state of the stream cipher Trivium. We propose an improved variant of the simulated annealing method...
New algorithm for OHSS prevention
DEFF Research Database (Denmark)
Papanikolaou, Evangelos G; Humaidan, Peter; Polyzos, Nikos;
2011-01-01
four new modalities: the GnRH antagonist protocol, GnRH agonist (GnRHa) triggering of ovulation, blastocyst transfer and embryo/oocyte vitrification, renders feasible the elimination of OHSS in connection with ovarian hyperstimulation for IVF treatment. The proposed current algorithm is based on the...... number of follicles developed after ovarian stimulation, setting a cut-off level at the development of 18 or more follicles. Further, fulfilling this criterion, the algorithm is based on four decision-making points: the final day of patient work-up, the day of triggering final oocyte maturation, day-1...
Industrial Applications of Evolutionary Algorithms
Sanchez, Ernesto; Tonda, Alberto
2012-01-01
This book is intended as a reference both for experienced users of evolutionary algorithms and for researchers that are beginning to approach these fascinating optimization techniques. Experienced users will find interesting details of real-world problems, and advice on solving issues related to fitness computation, modeling and setting appropriate parameters to reach optimal solutions. Beginners will find a thorough introduction to evolutionary computation, and a complete presentation of all evolutionary algorithms exploited to solve different problems. The book could fill the gap between the
Wavelets theory, algorithms, and applications
Montefusco, Laura
2014-01-01
Wavelets: Theory, Algorithms, and Applications is the fifth volume in the highly respected series, WAVELET ANALYSIS AND ITS APPLICATIONS. This volume shows why wavelet analysis has become a tool of choice infields ranging from image compression, to signal detection and analysis in electrical engineering and geophysics, to analysis of turbulent or intermittent processes. The 28 papers comprising this volume are organized into seven subject areas: multiresolution analysis, wavelet transforms, tools for time-frequency analysis, wavelets and fractals, numerical methods and algorithms, and applicat
Combinatorial optimization theory and algorithms
Korte, Bernhard
2002-01-01
Combinatorial optimization is one of the youngest and most active areas of discrete mathematics, and is probably its driving force today. This book describes the most important ideas, theoretical results, and algorithms of this field. It is conceived as an advanced graduate text, and it can also be used as an up-to-date reference work for current research. The book includes the essential fundamentals of graph theory, linear and integer programming, and complexity theory. It covers classical topics in combinatorial optimization as well as very recent ones. The emphasis is on theoretical results and algorithms with provably good performance. Some applications and heuristics are mentioned, too.
Ensemble Methods Foundations and Algorithms
Zhou, Zhi-Hua
2012-01-01
An up-to-date, self-contained introduction to a state-of-the-art machine learning approach, Ensemble Methods: Foundations and Algorithms shows how these accurate methods are used in real-world tasks. It gives you the necessary groundwork to carry out further research in this evolving field. After presenting background and terminology, the book covers the main algorithms and theories, including Boosting, Bagging, Random Forest, averaging and voting schemes, the Stacking method, mixture of experts, and diversity measures. It also discusses multiclass extension, noise tolerance, error-ambiguity a
THE FEATURE SUBSET SELECTION ALGORITHM
Institute of Scientific and Technical Information of China (English)
Liu Yongguo; Li Xueming; Wu Zhongfu
2003-01-01
The motivation of data mining is how to extract effective information from huge data in very large database. However, some redundant and irrelevant attributes, which result in low performance and high computing complexity, are included in the very large database in general.So, Feature Subset Selection (FSS) becomes one important issue in the field of data mining. In this letter, an FSS model based on the filter approach is built, which uses the simulated annealing genetic algorithm. Experimental results show that convergence and stability of this algorithm are adequately achieved.
THE FEATURE SUBSET SELECTION ALGORITHM
Institute of Scientific and Technical Information of China (English)
LiuYongguo; LiXueming; 等
2003-01-01
The motivation of data mining is how to extract effective information from huge data in very large database.However,some redundant irrelevant attributes,which result in low performance and high computing complexity,are included in the very large database in general.So,Feature Selection(FSS)becomes one important issue in the field of data mining.In this letter,an Fss model based on the filter approach is built,which uses the simulated annealing gentic algorithm.Experimental results show that convergence and stability of this algorithm are adequately achieved.
Big Data Mining: Tools & Algorithms
Directory of Open Access Journals (Sweden)
Adeel Shiraz Hashmi
2016-03-01
Full Text Available We are now in Big Data era, and there is a growing demand for tools which can process and analyze it. Big data analytics deals with extracting valuable information from that complex data which can’t be handled by traditional data mining tools. This paper surveys the available tools which can handle large volumes of data as well as evolving data streams. The data mining tools and algorithms which can handle big data have also been summarized, and one of the tools has been used for mining of large datasets using distributed algorithms.
Algorithmics of matching under preferences
Manlove, David
2013-01-01
Matching problems with preferences are all around us - they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists.In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. This book describes the most important results in this area, providing a timely upda
Parallel algorithms and cluster computing
Hoffmann, Karl Heinz
2007-01-01
This book presents major advances in high performance computing as well as major advances due to high performance computing. It contains a collection of papers in which results achieved in the collaboration of scientists from computer science, mathematics, physics, and mechanical engineering are presented. From the science problems to the mathematical algorithms and on to the effective implementation of these algorithms on massively parallel and cluster computers we present state-of-the-art methods and technology as well as exemplary results in these fields. This book shows that problems which seem superficially distinct become intimately connected on a computational level.
Evaluation of flux synthesis algorithms
International Nuclear Information System (INIS)
The flux synthesis algorithm which is the best fit to the numerical solution of the multigroup diffusion equations, was determined. Three different types of synthesis were studied: 1) discontinuous synthesis 2) continuous synthesis 3) pseudo-continuous synthesis. A matrix and a differential formulation were developed for the first two types of synthesis. For pseudo-continuous synthesis only the matrix formulation was used. Some tests were performed and the results allowed us to establish the following order of efficiency for the algorithms: 1) continuous synthesis (matrix formulation) 2) continuous synthesis (differential formulation) 3) pseudo-continuous synthesis 4) discontinuous synthesis (matrix formulation) 5) discontinuous synthesis (differential formulation). (Author)
A Robust Parsing Algorithm For Link Grammars
Grinberg, Dennis; Lafferty, John; Sleator, Daniel
1995-01-01
In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by mak...
MICROSTRIP COUPLER DESIGN USING BAT ALGORITHM
Directory of Open Access Journals (Sweden)
EzgiDeniz Ulker
2014-01-01
Full Text Available Evolutionary and swarm algorithms have found many applications in design problems since todays computing power enables these algorithms to find solutions to complicated design problems very fast. Newly proposed hybridalgorithm, bat algorithm, has been applied for the design of microwave microstrip couplers for the first time. Simulation results indicate that the bat algorithm is a very fast algorithm and it produces very reliable results.
Fast Efficient Clustering Algorithm for Balanced Data
Adel A. Sewisy; Marghny, M. H.; Rasha M. Abd ElAziz; Taloba, Ahmed I.
2014-01-01
The Cluster analysis is a major technique for statistical analysis, machine learning, pattern recognition, data mining, image analysis and bioinformatics. K-means algorithm is one of the most important clustering algorithms. However, the k-means algorithm needs a large amount of computational time for handling large data sets. In this paper, we developed more efficient clustering algorithm to overcome this deficiency named Fast Balanced k-means (FBK-means). This algorithm is not only yields t...
Parallel algorithms for unconstrained optimizations by multisplitting
Energy Technology Data Exchange (ETDEWEB)
He, Qing [Arizona State Univ., Tempe, AZ (United States)
1994-12-31
In this paper a new parallel iterative algorithm for unconstrained optimization using the idea of multisplitting is proposed. This algorithm uses the existing sequential algorithms without any parallelization. Some convergence and numerical results for this algorithm are presented. The experiments are performed on an Intel iPSC/860 Hyper Cube with 64 nodes. It is interesting that the sequential implementation on one node shows that if the problem is split properly, the algorithm converges much faster than one without splitting.
AN SVAD ALGORITHM BASED ON FNNKD METHOD
Institute of Scientific and Technical Information of China (English)
Chen Dong; Zhang Yan; Kuang Jingming
2002-01-01
The capacity of mobile communication system is improved by using Voice Activity Detection (VAD) technology. In this letter, a novel VAD algorithm, SVAD algorithm based on Fuzzy Neural Network Knowledge Discovery (FNNKD) method is proposed. The performance of SVAD algorithm is discussed and compared with traditional algorithm recommended by ITU G.729B in different situations. The simulation results show that the SVAD algorithm performs better.
A NEW ALGORITHM FOR SCANSAR PROCESSING
Institute of Scientific and Technical Information of China (English)
Qiao Rongrong; Wang Zhensong; Ian Cumming
2001-01-01
In this paper, a new phase preserving algorithm-the short IFFT algorithm for the burst-mode ScanSAR processing is presented. Analysis and simulation are done to verify the phase accuracy of this algorithm. Finally, the phase accuracy of this algorithm by making interferogram with simulated burst-mode INSAR data is illustrated. The results show that this new algorithm works well for interferometric application of ScanSAR data.
Blind Alley Aware ACO Routing Algorithm
Yoshikawa, Masaya; Otani, Kazuo
2010-10-01
The routing problem is applied to various engineering fields. Many researchers study this problem. In this paper, we propose a new routing algorithm which is based on Ant Colony Optimization. The proposed algorithm introduces the tabu search mechanism to escape the blind alley. Thus, the proposed algorithm enables to find the shortest route, even if the map data contains the blind alley. Experiments using map data prove the effectiveness in comparison with Dijkstra algorithm which is the most popular conventional routing algorithm.
FACE RECOGNITION BASED ON CUCKOO SEARCH ALGORITHM
VIPINKUMAR TIWARI
2012-01-01
Feature Selection is a optimization technique used in face recognition technology. Feature selection removes the irrelevant, noisy and redundant data thus leading to the more accurate recognition of face from the database.Cuckko Algorithm is one of the recent optimization algorithm in the league of nature based algorithm. Its optimization results are better than the PSO and ACO optimization algorithms. The proposal of applying the Cuckoo algorithm for feature selection in the process of face ...
Two Algorithms for Processing Electronic Nose Data
Young, Rebecca; Linnell, Bruce
2007-01-01
Two algorithms for processing the digitized readings of electronic noses, and computer programs to implement the algorithms, have been devised in a continuing effort to increase the utility of electronic noses as means of identifying airborne compounds and measuring their concentrations. One algorithm identifies the two vapors in a two-vapor mixture and estimates the concentration of each vapor (in principle, this algorithm could be extended to more than two vapors). The other algorithm identifies a single vapor and estimates its concentration.
Multithreaded Implementation of Hybrid String Matching Algorithm
Directory of Open Access Journals (Sweden)
Akhtar Rasool
2012-03-01
Full Text Available Reading and taking reference from many books and articles, and then analyzing the Navies algorithm, Boyer Moore algorithm and Knuth Morris Pratt (KMP algorithm and a variety of improved algorithms, summarizes various advantages and disadvantages of the pattern matching algorithms. And on this basis, a new algorithm – Multithreaded Hybrid algorithm is introduced. The algorithm refers to Boyer Moore algorithm, KMP algorithm and the thinking of improved algorithms. Utilize the last character of the string, the next character and the method to compare from side to side, and then advance a new hybrid pattern matching algorithm. And it adjusted the comparison direction and the order of the comparison to make the maximum moving distance of each time to reduce the pattern matching time. The algorithm reduces the comparison number and greatlyreduces the moving number of the pattern and improves the matching efficiency. Multithreaded implementation of hybrid, pattern matching algorithm performs the parallel string searching on different text data by executing a number of threads simultaneously. This approach is advantageous from all other string-pattern matching algorithm in terms of time complexity. This again improves the overall string matching efficiency.
Edge Crossing Minimization Algorithm for Hierarchical Graphs Based on Genetic Algorithms
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
We present an edge crossing minimization algorithm forhierarchical gr aphs based on genetic algorithms, and comparing it with some heuristic algorithm s. The proposed algorithm is more efficient and has the following advantages: th e frame of the algorithms is unified, the method is simple, and its implementati on and revision are easy.
Algorithm Visualization in Teaching Practice
Törley, Gábor
2014-01-01
This paper presents the history of algorithm visualization (AV), highlighting teaching-methodology aspects. A combined, two-group pedagogical experiment will be presented as well, which measured the efficiency and the impact on the abstract thinking of AV. According to the results, students, who learned with AV, performed better in the experiment.
Littlewood's algorithm and quaternion matrices
Merino, Dennis I.; Sergeichuk, Vladimir V.
2007-01-01
A strengthened form of Schur's triangularization theorem is given for quaternion matrices with real spectrum (for complex matrices it was given by Littlewood). Littlewood's algorithm for reducing a complex matrix to a canonical form under unitary similarity is extended to quaternion matrices whose eigenvalues have geometric multiplicity 1.
Variance Adjusted Actor Critic Algorithms
Tamar, Aviv; Mannor, Shie
2013-01-01
We present an actor-critic framework for MDPs where the objective is the variance-adjusted expected return. Our critic uses linear function approximation, and we extend the concept of compatible features to the variance-adjusted setting. We present an episodic actor-critic algorithm and show that it converges almost surely to a locally optimal point of the objective function.
Detection Algorithms: FFT vs. KLT
Maccone, Claudio
Given the vast distances between the stars, we can anticipate that any received SETI signal will be exceedingly weak. How can we hope to extract (or even recognize) such signals buried well beneath the natural background noise with which they must compete? This chapter analyzes, compares, and contrasts the two dominant signal detection algorithms used by SETI scientists to recognize extremely weak candidate signals.
Diverse Consequences of Algorithmic Probability
Özkural, Eray
2011-01-01
We reminisce and discuss applications of algorithmic probability to a wide range of problems in artificial intelligence, philosophy and technological society. We propose that Solomonoff has effectively axiomatized the field of artificial intelligence, therefore establishing it as a rigorous scientific discipline. We also relate to our own work in incremental machine learning and philosophy of complexity.
Algorithmic Issues in Modeling Motion
DEFF Research Database (Denmark)
Agarwal, P. K; Guibas, L. J; Edelsbrunner, H.;
2003-01-01
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory...
Adaptive protection algorithm and system
Hedrick, Paul [Pittsburgh, PA; Toms, Helen L [Irwin, PA; Miller, Roger M [Mars, PA
2009-04-28
An adaptive protection algorithm and system for protecting electrical distribution systems traces the flow of power through a distribution system, assigns a value (or rank) to each circuit breaker in the system and then determines the appropriate trip set points based on the assigned rank.
Key Concepts in Informatics: Algorithm
Szlávi, Péter; Zsakó, László
2014-01-01
"The system of key concepts contains the most important key concepts related to the development tasks of knowledge areas and their vertical hierarchy as well as the links of basic key concepts of different knowledge areas." (Vass 2011) One of the most important of these concepts is the algorithm. In everyday life, when learning or…
Coagulation algorithms with size binning
Statton, David M.; Gans, Jason; Williams, Eric
1994-01-01
The Smoluchowski equation describes the time evolution of an aerosol particle size distribution due to aggregation or coagulation. Any algorithm for computerized solution of this equation requires a scheme for describing the continuum of aerosol particle sizes as a discrete set. One standard form of the Smoluchowski equation accomplishes this by restricting the particle sizes to integer multiples of a basic unit particle size (the monomer size). This can be inefficient when particle concentrations over a large range of particle sizes must be calculated. Two algorithms employing a geometric size binning convention are examined: the first assumes that the aerosol particle concentration as a function of size can be considered constant within each size bin; the second approximates the concentration as a linear function of particle size within each size bin. The output of each algorithm is compared to an analytical solution in a special case of the Smoluchowski equation for which an exact solution is known . The range of parameters more appropriate for each algorithm is examined.
Classification algorithms using adaptive partitioning
Binev, Peter
2014-12-01
© 2014 Institute of Mathematical Statistics. Algorithms for binary classification based on adaptive tree partitioning are formulated and analyzed for both their risk performance and their friendliness to numerical implementation. The algorithms can be viewed as generating a set approximation to the Bayes set and thus fall into the general category of set estimators. In contrast with the most studied tree-based algorithms, which utilize piecewise constant approximation on the generated partition [IEEE Trans. Inform. Theory 52 (2006) 1335.1353; Mach. Learn. 66 (2007) 209.242], we consider decorated trees, which allow us to derive higher order methods. Convergence rates for these methods are derived in terms the parameter - of margin conditions and a rate s of best approximation of the Bayes set by decorated adaptive partitions. They can also be expressed in terms of the Besov smoothness β of the regression function that governs its approximability by piecewise polynomials on adaptive partition. The execution of the algorithms does not require knowledge of the smoothness or margin conditions. Besov smoothness conditions are weaker than the commonly used Holder conditions, which govern approximation by nonadaptive partitions, and therefore for a given regression function can result in a higher rate of convergence. This in turn mitigates the compatibility conflict between smoothness and margin parameters.
Understanding Algorithms in Different Presentations
Csernoch, Mária; Biró, Piroska; Abari, Kálmán; Máth, János
2015-01-01
Within the framework of the Testing Algorithmic and Application Skills project we tested first year students of Informatics at the beginning of their tertiary education. We were focusing on the students' level of understanding in different programming environments. In the present paper we provide the results from the University of Debrecen, the…
Chaos Synthesis by Evolutionary Algorithms
Czech Academy of Sciences Publication Activity Database
Zelinka, I.; Chen, G.; Čelikovský, Sergej
Berlin : Springer-Verlag, 2010 - (Zelinka, I.; Čelikovský, S.; Richter, H.; Chen, G.), s. 345-382 ISBN 978-3-642-10706-1. - (Studies in Computational Intelligence. 267) Institutional research plan: CEZ:AV0Z10750506 Keywords : chaos synthesis * evolutionary algorithms * self organizingmigrating * evolutionary computing Subject RIV: BC - Control Systems Theory
ALGORITHM OF OUTSOURCING RELATIONS MANAGEMENT
Directory of Open Access Journals (Sweden)
Arthur Kurbanov
2012-01-01
Full Text Available In recent years, domestic and foreign outsourcing practice was widespread. In the transition to outsourcing there are difficulties associated with the practical organization of the interaction between the customer and the performer. An algorithm of management of the relationship with the performer (outsourcer. Particular attention is given to the criteria for evaluation of potential contractors.
Knowledge-based tracking algorithm
Corbeil, Allan F.; Hawkins, Linda J.; Gilgallon, Paul F.
1990-10-01
This paper describes the Knowledge-Based Tracking (KBT) algorithm for which a real-time flight test demonstration was recently conducted at Rome Air Development Center (RADC). In KBT processing, the radar signal in each resolution cell is thresholded at a lower than normal setting to detect low RCS targets. This lower threshold produces a larger than normal false alarm rate. Therefore, additional signal processing including spectral filtering, CFAR and knowledge-based acceptance testing are performed to eliminate some of the false alarms. TSC's knowledge-based Track-Before-Detect (TBD) algorithm is then applied to the data from each azimuth sector to detect target tracks. In this algorithm, tentative track templates are formed for each threshold crossing and knowledge-based association rules are applied to the range, Doppler, and azimuth measurements from successive scans. Lastly, an M-association out of N-scan rule is used to declare a detection. This scan-to-scan integration enhances the probability of target detection while maintaining an acceptably low output false alarm rate. For a real-time demonstration of the KBT algorithm, the L-band radar in the Surveillance Laboratory (SL) at RADC was used to illuminate a small Cessna 310 test aircraft. The received radar signal wa digitized and processed by a ST-100 Array Processor and VAX computer network in the lab. The ST-100 performed all of the radar signal processing functions, including Moving Target Indicator (MTI) pulse cancelling, FFT Doppler filtering, and CFAR detection. The VAX computers performed the remaining range-Doppler clustering, beamsplitting and TBD processing functions. The KBT algorithm provided a 9.5 dB improvement relative to single scan performance with a nominal real time delay of less than one second between illumination and display.
A Cavity QED Implementation of Deutsch-Jozsa Algorithm
Guerra, E. S.
2004-01-01
The Deutsch-Jozsa algorithm is a generalization of the Deutsch algorithm which was the first algorithm written. We present schemes to implement the Deutsch algorithm and the Deutsch-Jozsa algorithm via cavity QED.
Improvement and Validation of the BOAT Algorithm
Directory of Open Access Journals (Sweden)
Yingchun Liu
2014-04-01
Full Text Available The main objective of this paper is improving the BOAT classification algorithm and applying it in credit card big data analysis. Decision tree algorithm is a data analysis method for the classification which can be used to describe the extract important data class models or predict future data trends. The BOAT algorithm can reduce the data during reading and writing the operations, the improved algorithms in large data sets under the operating efficiency, and in line with the popular big data analysis. Through this paper, BOAT algorithm can further improve the performance of the algorithm and the distributed data sources under the performance. In this paper, large banking sectors of credit card data as the being tested data sets. The improved algorithm, the original BOAT algorithms, and the performance of other classical classification algorithms will be compared and analyzed.
FICA:fuzzy imperialist competitive algorithm
Institute of Scientific and Technical Information of China (English)
Saeid ARISH; Ali AMIRI; Khadije NOORI
2014-01-01
Despite the success of the imperialist competitive algorithm (ICA) in solving optimization problems, it still suffers from frequently falling into local minima and low convergence speed. In this paper, a fuzzy version of this algorithm is proposed to address these issues. In contrast to the standard version of ICA, in the proposed algorithm, powerful countries are chosen as imperialists in each step;according to a fuzzy membership function, other countries become colonies of all the empires. In ab-sorption policy, based on the fuzzy membership function, colonies move toward the resulting vector of all imperialists. In this algorithm, no empire will be eliminated;instead, during the execution of the algorithm, empires move toward one point. Other steps of the algorithm are similar to the standard ICA. In experiments, the proposed algorithm has been used to solve the real world optimization problems presented for IEEE-CEC 2011 evolutionary algorithm competition. Results of experiments confirm the performance of the algorithm.
Opposition-Based Adaptive Fireworks Algorithm
Directory of Open Access Journals (Sweden)
Chibing Gong
2016-07-01
Full Text Available A fireworks algorithm (FWA is a recent swarm intelligence algorithm that is inspired by observing fireworks explosions. An adaptive fireworks algorithm (AFWA proposes additional adaptive amplitudes to improve the performance of the enhanced fireworks algorithm (EFWA. The purpose of this paper is to add opposition-based learning (OBL to AFWA with the goal of further boosting performance and achieving global optimization. Twelve benchmark functions are tested in use of an opposition-based adaptive fireworks algorithm (OAFWA. The final results conclude that OAFWA significantly outperformed EFWA and AFWA in terms of solution accuracy. Additionally, OAFWA was compared with a bat algorithm (BA, differential evolution (DE, self-adapting control parameters in differential evolution (jDE, a firefly algorithm (FA, and a standard particle swarm optimization 2011 (SPSO2011 algorithm. The research results indicate that OAFWA ranks the highest of the six algorithms for both solution accuracy and runtime cost.
Semi-optimal Practicable Algorithmic Cooling
Elias, Yuval; Weinstein, Yossi; 10.1103/PhysRevA.83.042340
2011-01-01
Algorithmic Cooling (AC) of spins applies entropy manipulation algorithms in open spin-systems in order to cool spins far beyond Shannon's entropy bound. AC of nuclear spins was demonstrated experimentally, and may contribute to nuclear magnetic resonance (NMR) spectroscopy. Several cooling algorithms were suggested in recent years, including practicable algorithmic cooling (PAC) and exhaustive AC. Practicable algorithms have simple implementations, yet their level of cooling is far from optimal; Exhaustive algorithms, on the other hand, cool much better, and some even reach (asymptotically) an optimal level of cooling, but they are not practicable. We introduce here semi-optimal practicable AC (SOPAC), wherein few cycles (typically 2-6) are performed at each recursive level. Two classes of SOPAC algorithms are proposed and analyzed. Both attain cooling levels significantly better than PAC, and are much more efficient than the exhaustive algorithms. The new algorithms are shown to bridge the gap between PAC a...
Birkhoffian symplectic algorithms derived from Hamiltonian symplectic algorithms
Xin-Lei, Kong; Hui-Bin, Wu; Feng-Xiang, Mei
2016-01-01
In this paper, we focus on the construction of structure preserving algorithms for Birkhoffian systems, based on existing symplectic schemes for the Hamiltonian equations. The key of the method is to seek an invertible transformation which drives the Birkhoffian equations reduce to the Hamiltonian equations. When there exists such a transformation, applying the corresponding inverse map to symplectic discretization of the Hamiltonian equations, then resulting difference schemes are verified to be Birkhoffian symplectic for the original Birkhoffian equations. To illustrate the operation process of the method, we construct several desirable algorithms for the linear damped oscillator and the single pendulum with linear dissipation respectively. All of them exhibit excellent numerical behavior, especially in preserving conserved quantities. Project supported by the National Natural Science Foundation of China (Grant No. 11272050), the Excellent Young Teachers Program of North China University of Technology (Grant No. XN132), and the Construction Plan for Innovative Research Team of North China University of Technology (Grant No. XN129).
Comparing Online Algorithms for Bin Packing Problems
DEFF Research Database (Denmark)
Epstein, Leah; Favrholdt, Lene Monrad; Kohrt, Jens Svalgaard
2012-01-01
The relative worst-order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm. In this paper, we apply the relative worst......-order ratio to online algorithms for several common variants of the bin packing problem. We mainly consider pairs of algorithms that are not distinguished by the competitive ratio and show that the relative worst-order ratio prefers the intuitively better algorithm of each pair....
Affine Projection Algorithm Using Regressive Estimated Error
Zhang, Shu; Zhi, Yongfeng
2011-01-01
An affine projection algorithm using regressive estimated error (APA-REE) is presented in this paper. By redefining the iterated error of the affine projection algorithm (APA), a new algorithm is obtained, and it improves the adaptive filtering convergence rate. We analyze the iterated error signal and the stability for the APA-REE algorithm. The steady-state weights of the APA-REE algorithm are proved to be unbiased and consist. The simulation results show that the proposed algorithm has a f...
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A; Smith, S T; Edelman, Alan; Smith, Steven T.
1998-01-01
In this paper we develop new Newton and conjugate gradient algorithms on the Grassmann and Stiefel manifolds. These manifolds represent the constraints that arise in such areas as the symmetric eigenvalue problem, nonlinear eigenvalue problems, electronic structures computations, and signal processing. In addition to the new algorithms, we show how the geometrical framework gives penetrating new insights allowing us to create, understand, and compare algorithms. The theory proposed here provides a taxonomy for numerical linear algebra algorithms that provide a top level mathematical view of previously unrelated algorithms. It is our hope that developers of new algorithms and perturbation theories will benefit from the theory, methods, and examples in this paper.
Mining Frequent Itemsets Using Genetic Algorithm
Ghosh, Soumadip; Sarkar, Debasree; Sarkar, Partha Pratim; 10.5121/ijaia.2010.1411
2010-01-01
In general frequent itemsets are generated from large data sets by applying association rule mining algorithms like Apriori, Partition, Pincer-Search, Incremental, Border algorithm etc., which take too much computer time to compute all the frequent itemsets. By using Genetic Algorithm (GA) we can improve the scenario. The major advantage of using GA in the discovery of frequent itemsets is that they perform global search and its time complexity is less compared to other algorithms as the genetic algorithm is based on the greedy approach. The main aim of this paper is to find all the frequent itemsets from given data sets using genetic algorithm.
Generalized fairing algorithm of parametric cubic splines
Institute of Scientific and Technical Information of China (English)
WANG Yuan-jun; CAO Yuan
2006-01-01
Kjellander has reported an algorithm for fairing uniform parametric cubic splines. Poliakoff extended Kjellander's algorithm to non-uniform case. However, they merely changed the bad point's position, and neglected the smoothing of tangent at bad point. In this paper, we present a fairing algorithm that both changed point's position and its corresponding tangent vector. The new algorithm possesses the minimum property of energy. We also proved Poliakoff's fairing algorithm is a deduction of our fairing algorithm. Several fairing examples are given in this paper.
A hybrid clustering algorithm for data mining
Jain, Ravindra
2012-01-01
Data clustering is a process of arranging similar data into groups. A clustering algorithm partitions a data set into several groups such that the similarity within a group is better than among groups. In this paper a hybrid clustering algorithm based on K-mean and K-harmonic mean (KHM) is described. The proposed algorithm is tested on five different datasets. The research is focused on fast and accurate clustering. Its performance is compared with the traditional K-means & KHM algorithm. The result obtained from proposed hybrid algorithm is much better than the traditional K-mean & KHM algorithm.
Algorithms for Boolean Function Query Properties
Aaronson, Scott
2001-01-01
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of...
A quantum algorithm for examining oracles
Azuma, Hiroo
2004-01-01
In this paper, we consider a quantum algorithm for solving the following problem: ``Suppose $f$ is a function given as a black box (that is also called an oracle) and $f$ is invariant under some AND-mask. Examine a property of $f$ by querying the oracle.'' We compare the efficiency of our quantum algorithm with that of classical algorithms by evaluating the expected number of queries for each algorithm. We show that our quantum algorithm is more efficient than any classical algorithm in some ...
Linear Time Algorithms for Parallel Machine Scheduling
Institute of Scientific and Technical Information of China (English)
Zhi Yi TAN; Yong HE
2007-01-01
This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems.The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio.Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.
A Survey on Star Identification Algorithms
Directory of Open Access Journals (Sweden)
Daniele Mortari
2009-01-01
Full Text Available The author surveys algorithms used in star identification, commonly used in star trackers to determine the attitude of a spacecraft. Star trackers are a staple of attitude determination systems for most types of satellites. The paper covers: (a lost-in-space algorithms (when no a priori attitude information is available, (b recursive algorithms (when some a priori attitude information is available, and (c non-dimensional algorithms (when the star tracker calibration is not well-known. The performance of selected algorithms and supporting algorithms are compared.
Why is Boris algorithm so good?
International Nuclear Information System (INIS)
Due to its excellent long term accuracy, the Boris algorithm is the de facto standard for advancing a charged particle. Despite its popularity, up to now there has been no convincing explanation why the Boris algorithm has this advantageous feature. In this paper, we provide an answer to this question. We show that the Boris algorithm conserves phase space volume, even though it is not symplectic. The global bound on energy error typically associated with symplectic algorithms still holds for the Boris algorithm, making it an effective algorithm for the multi-scale dynamics of plasmas
Dr. R.Manicka chezian; Nishad Pm
2012-01-01
There are several algorithms like binary search, linear search, Interpolation search, Ternary search and, etc used for search. Search algorithms locate the position of an item in a sorted. But the time taken for the search is huge. The search algorithm initially set the first and last index for the search; this directly leads to thetime complexity. This paper proposes a new prefix search indexing algorithm is called Subset Count Index Based Search Algorithm (SCIBS). This algorithm achieved th...
Genetic Algorithm for Graph Colouring: Exploration of Galinier and Hao's algorithm
Celia A. Glass; Prügel-Bennett, Adam
2003-01-01
This paper examines the best current algorithm for solving the Chromatic Number Problem, due to Galinier and Hao (Journal of Combinatorial Optimization,1999, 3(4), pp 379-397). The algorithm combines a Genetic Algorithm with Tabu Search. We show that the algorithm remains powerful even if the Tabu Search component is eliminated, and explore the reasons for its success where other Genetic Algorithms have failed. In addition we propose a generalized algorithm for the Frequency Assignment Problem.
The Berlekamp-Massey Algorithm and the Euclidean Algorithm: a Closer Link
Bras-Amorós, Maria; O'Sullivan, Michael E.
2009-01-01
The two primary decoding algorithms for Reed-Solomon codes are the Berlekamp-Massey algorithm and the Sugiyama et al. adaptation of the Euclidean algorithm, both designed to solve a key equation. In this article an alternative version of the key equation and a new way to use the Euclidean algorithm to solve it are presented, which yield the Berlekamp-Massey algorithm. This results in a new, simpler, and compacter presentation of the Berlekamp-Massey algorithm.
Garg, Poonam
2010-01-01
Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many optimization problems. However, premature convergence is an inherent characteristic of such classical genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the premature convergence. The cryptanalysis of simplified data encryption standard can be formulated as NP-Hard combinatorial problem. In this paper, a comparison between memetic algorithm and genetic algorithm were made in order to investigate the performance for the cryptanalysis on simplified data encryption standard problems(SDES). The methods were tested and various experimental results show that memetic algorithm performs better than the genetic algorithms for such type of NP-Hard combinatorial problem. This paper represents our first effort toward efficient memetic algo...
Poonam Garg
2010-01-01
Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many optimization problems. However, premature convergence is an inherent characteristic of such classical genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the premature convergence. The cryptanalysis of simplifie...
An Improved Multicast Routing Algorithm
Institute of Scientific and Technical Information of China (English)
蒋廷耀; 李庆华
2004-01-01
Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper,we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks.
Constrained Multiobjective Biogeography Optimization Algorithm
Directory of Open Access Journals (Sweden)
Hongwei Mo
2014-01-01
Full Text Available Multiobjective optimization involves minimizing or maximizing multiple objective functions subject to a set of constraints. In this study, a novel constrained multiobjective biogeography optimization algorithm (CMBOA is proposed. It is the first biogeography optimization algorithm for constrained multiobjective optimization. In CMBOA, a disturbance migration operator is designed to generate diverse feasible individuals in order to promote the diversity of individuals on Pareto front. Infeasible individuals nearby feasible region are evolved to feasibility by recombining with their nearest nondominated feasible individuals. The convergence of CMBOA is proved by using probability theory. The performance of CMBOA is evaluated on a set of 6 benchmark problems and experimental results show that the CMBOA performs better than or similar to the classical NSGA-II and IS-MOEA.
Diversity-Based Boosting Algorithm
Directory of Open Access Journals (Sweden)
Jafar A. Alzubi
2016-05-01
Full Text Available Boosting is a well known and efficient technique for constructing a classifier ensemble. An ensemble is built incrementally by altering the distribution of training data set and forcing learners to focus on misclassification errors. In this paper, an improvement to Boosting algorithm called DivBoosting algorithm is proposed and studied. Experiments on several data sets are conducted on both Boosting and DivBoosting. The experimental results show that DivBoosting is a promising method for ensemble pruning. We believe that it has many advantages over traditional boosting method because its mechanism is not solely based on selecting the most accurate base classifiers but also based on selecting the most diverse set of classifiers.
Optimisation algorithms for microarray biclustering.
Perrin, Dimitri; Duhamel, Christophe
2013-01-01
In providing simultaneous information on expression profiles for thousands of genes, microarray technologies have, in recent years, been largely used to investigate mechanisms of gene expression. Clustering and classification of such data can, indeed, highlight patterns and provide insight on biological processes. A common approach is to consider genes and samples of microarray datasets as nodes in a bipartite graphs, where edges are weighted e.g. based on the expression levels. In this paper, using a previously-evaluated weighting scheme, we focus on search algorithms and evaluate, in the context of biclustering, several variations of Genetic Algorithms. We also introduce a new heuristic "Propagate", which consists in recursively evaluating neighbour solutions with one more or one less active conditions. The results obtained on three well-known datasets show that, for a given weighting scheme, optimal or near-optimal solutions can be identified. PMID:24109756
Innovations in lattice QCD algorithms
International Nuclear Information System (INIS)
Lattice QCD calculations demand a substantial amount of computing power in order to achieve the high precision results needed to better understand the nature of strong interactions, assist experiment to discover new physics, and predict the behavior of a diverse set of physical systems ranging from the proton itself to astrophysical objects such as neutron stars. However, computer power alone is clearly not enough to tackle the calculations we need to be doing today. A steady stream of recent algorithmic developments has made an important impact on the kinds of calculations we can currently perform. In this talk I am reviewing these algorithms and their impact on the nature of lattice QCD calculations performed today
Innovations in Lattice QCD Algorithms
International Nuclear Information System (INIS)
Lattice QCD calculations demand a substantial amount of computing power in order to achieve the high precision results needed to better understand the nature of strong interactions, assist experiment to discover new physics, and predict the behavior of a diverse set of physical systems ranging from the proton itself to astrophysical objects such as neutron stars. However, computer power alone is clearly not enough to tackle the calculations we need to be doing today. A steady stream of recent algorithmic developments has made an important impact on the kinds of calculations we can currently perform. In this talk I am reviewing these algorithms and their impact on the nature of lattice QCD calculations performed today
MUSIC algorithms for rebar detection
International Nuclear Information System (INIS)
The MUSIC (MUltiple SIgnal Classification) algorithm is employed to detect and localize an unknown number of scattering objects which are small in size as compared to the wavelength. The ensemble of objects to be detected consists of both strong and weak scatterers. This represents a scattering environment challenging for detection purposes as strong scatterers tend to mask the weak ones. Consequently, the detection of more weakly scattering objects is not always guaranteed and can be completely impaired when the noise corrupting data is of a relatively high level. To overcome this drawback, here a new technique is proposed, starting from the idea of applying a two-stage MUSIC algorithm. In the first stage strong scatterers are detected. Then, information concerning their number and location is employed in the second stage focusing only on the weak scatterers. The role of an adequate scattering model is emphasized to improve drastically detection performance in realistic scenarios. (paper)
Genetic Algorithms for Case Adaptation
International Nuclear Information System (INIS)
Case based reasoning (CBR) paradigm has been widely used to provide computer support for recalling and adapting known cases to novel situations. Case adaptation algorithms generally rely on knowledge based and heuristics in order to change the past solutions to solve new problems. However, case adaptation has always been a difficult process to engineers within (CBR) cycle. Its difficulties can be referred to its domain dependency; and computational cost. In an effort to solve this problem, this research explores a general-purpose method that applying a genetic algorithm (GA) to CBR adaptation. Therefore, it can decrease the computational complexity of the search space in the problems having a great dependency on their domain knowledge. The proposed model can be used to perform a variety of design tasks on a broad set of application domains. However, it has been implemented for the tablet formulation as a domain of application. The proposed system has improved the performance of the CBR design systems
Image reconstruction algorithms from projections
International Nuclear Information System (INIS)
Many physical or bio-physical phenomena can be analysed as 'images' that is to say a bi-dimensionnal representation of a characteristic parameter of the material (density, concentration of a given element, resistivity, etc...). The various algorithms reviewed in the paper lead to a numerical reconstitution of such an image from a finite set of measurements considered as 'projections' of the initial object. We first give a physical insight then the mathematical formulation of the various concepts necessary for the presentation of the problem; after that we show why and how many reconstruction algorithms are possible. These different strategies are quickly compared chiefly according to realization facilities, structure, volume and performances (speed, accuracy) of the processing system required
MUSIC algorithms for rebar detection
Solimene, Raffaele; Leone, Giovanni; Dell'Aversano, Angela
2013-12-01
The MUSIC (MUltiple SIgnal Classification) algorithm is employed to detect and localize an unknown number of scattering objects which are small in size as compared to the wavelength. The ensemble of objects to be detected consists of both strong and weak scatterers. This represents a scattering environment challenging for detection purposes as strong scatterers tend to mask the weak ones. Consequently, the detection of more weakly scattering objects is not always guaranteed and can be completely impaired when the noise corrupting data is of a relatively high level. To overcome this drawback, here a new technique is proposed, starting from the idea of applying a two-stage MUSIC algorithm. In the first stage strong scatterers are detected. Then, information concerning their number and location is employed in the second stage focusing only on the weak scatterers. The role of an adequate scattering model is emphasized to improve drastically detection performance in realistic scenarios.
A possible hypercomputational quantum algorithm
Sicard, Andres; Velez, Mario; Ospina, Juan
2005-05-01
The term 'hypermachine' denotes any data processing device (theoretical or that can be implemented) capable of carrying out tasks that cannot be performed by a Turing machine. We present a possible quantum algorithm for a classically non-computable decision problem, Hilbert's tenth problem; more specifically, we present a possible hypercomputation model based on quantum computation. Our algorithm is inspired by the one proposed by Tien D. Kieu, but we have selected the infinite square well instead of the (one-dimensional) simple harmonic oscillator as the underlying physical system. Our model exploits the quantum adiabatic process and the characteristics of the representation of the dynamical Lie algebra su(1,1) associated to the infinite square well.
Innovations in Lattice QCD Algorithms
Energy Technology Data Exchange (ETDEWEB)
Konstantinos Orginos
2006-06-25
Lattice QCD calculations demand a substantial amount of computing power in order to achieve the high precision results needed to better understand the nature of strong interactions, assist experiment to discover new physics, and predict the behavior of a diverse set of physical systems ranging from the proton itself to astrophysical objects such as neutron stars. However, computer power alone is clearly not enough to tackle the calculations we need to be doing today. A steady stream of recent algorithmic developments has made an important impact on the kinds of calculations we can currently perform. In this talk I am reviewing these algorithms and their impact on the nature of lattice QCD calculations performed today.
Coevolution Evolutionary Algorithm: A Survey
Jeniefer Kavetha. M
2013-01-01
Evolutionary Computing techniques have become one of the most powerful tools for solving optimization problems and isbased on the mechanisms of natural selection and genetics. In Evolutionary Algorithm, Co-evolution is a natural choice for learning in problem domains where one agent’s behaviour is directly related to the behaviour of other agents. Co-evolution provides a framework to implement search heuristics that are more elaborate than those driving the exploration of the state space in c...
Experiments on Graph Clustering Algorithms
Brandes, Ulrik; Gaertler, Marco; Wagner, Dorothea
2003-01-01
A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on particular aspects of this rather vague concept have been proposed no conclusive argument on their appropriateness has been given. As a first step towards understanding the consequences of particular conceptions, we conducted an experimental evaluation of graph clustering approaches. By combining proven techniques f...
Computed laminography and reconstruction algorithm
Que, Jie-Min; Cao, Da-Quan; Zhao, Wei; Tang, Xiao; Sun, Cui-Li; Wang, Yan-Fang; Wei, Cun-Feng; Shi, Rong-Jian; Wei, Long; Yu, Zhong-Qiang; Yan, Yong-Lian
2012-08-01
Computed laminography (CL) is an alternative to computed tomography if large objects are to be inspected with high resolution. This is especially true for planar objects. In this paper, we set up a new scanning geometry for CL, and study the algebraic reconstruction technique (ART) for CL imaging. We compare the results of ART with variant weighted functions by computer simulation with a digital phantom. It proves that ART algorithm is a good choice for the CL system.
Computed laminography and reconstruction algorithm
International Nuclear Information System (INIS)
Computed laminography (CL) is an alternative to computed tomography if large objects are to be inspected with high resolution. This is especially true for planar objects. In this paper, we set up a new scanning geometry for CL, and study the algebraic reconstruction technique (ART) for CL imaging. We compare the results of ART with variant weighted functions by computer simulation with a digital phantom. It proves that ART algorithm is a good choice for the CL system. (authors)
A Fast Manifold Learning Algorithm
Lukui Shi; Junhua Gu
2012-01-01
A fast manifold learning algorithm was proposed which only preserved the similarities or dissimilarities between each point and some objects. The embedded coordinates were obtained through optimizing the part stress function with the deepest gradient descent method. Experiments showed that the method could find the true structure of the manifold and had lower complexity. At the same time, we discussed the effectiveness of the number of far points and the initial value to the embedded results.
The CMS Particle Flow Algorithm
Beaudette, Florian
2014-01-01
A particle flow event-reconstruction algorithm has been successfully deployed in the CMS experiment and is nowadays used by most of the analyses. It aims at identifying and reconstructing individually each particle arising from the LHC proton-proton collision, by combining the information from all the subdetectors. The resulting particle-flow event reconstruction leads to an improved performance for the reconstruction of jets and MET, and for the identification of electrons, muons, and taus. ...
Implementing Strassen's Algorithm with BLIS
Huang, Jianyu; Smith, Tyler M.; Henry, Greg M.; Van de Geijn, Robert A.
2016-01-01
We dispel with "street wisdom" regarding the practical implementation of Strassen's algorithm for matrix-matrix multiplication (DGEMM). Conventional wisdom: it is only practical for very large matrices. Our implementation is practical for small matrices. Conventional wisdom: the matrices being multiplied should be relatively square. Our implementation is practical for rank-k updates, where k is relatively small (a shape of importance for libraries like LAPACK). Conventional wisdom: it inheren...
Analysis of Various Clustering Algorithms
Asst Prof. Sunila Godara,; Ms. Amita Verma,
2013-01-01
Data clustering is a process of putting similar data into groups. A clustering algorithm partitions a data set into several groups such that the similarity within a group is larger than among groups. This paper reviews four types of clustering techniques- k-Means Clustering, Farther first clustering, Density Based Clustering, Filtered clusterer. These clustering techniques are implemented and analyzed using a clustering tool WEKA. Performance of the 4 techniques are presented and compared.
Marginalization algorithm for compositional models
Czech Academy of Sciences Publication Activity Database
Jiroušek, Radim; Kratochvíl, Václav
Paris: Editions EDK, 2006 - (Bouchon-Meunier, B.; Yager, R.), s. 2300-2307 ISBN 2-84254-112-X. [IPMU 2006 /11./. Paris (FR), 02.07.2006-07.07.2006] R&D Projects: GA MŠk 1M0572; GA AV ČR IAA2075302 Institutional research plan: CEZ:AV0Z10750506 Keywords : compositional model * multidimensional distribution * Bayesian network * marginalization * algorithm Subject RIV: BA - General Mathematics
A secured Cryptographic Hashing Algorithm
Mohanty, Rakesh; Sarangi, Niharjyoti; Bishi, Sukant kumar
2010-01-01
Cryptographic hash functions for calculating the message digest of a message has been in practical use as an effective measure to maintain message integrity since a few decades. This message digest is unique, irreversible and avoids all types of collisions for any given input string. The message digest calculated from this algorithm is propagated in the communication medium along with the original message from the sender side and on the receiver side integrity of the message can be verified b...
An Accelerated Incremental Radiosity Algorithm
Institute of Scientific and Technical Information of China (English)
XING Changyu; SUN Jizhou; R. L. Grimsdale
2000-01-01
The incremental radiosity method has been shown to be an efficient technique for providing global illumination in dynamic environments as it exploits temporal coherence in object space. This paper presents an accelerated incremental radiosity algorithm, which is based on a dynamically followed partial matrix.This not only reduces the computation cost in determining incremental form-factors when the geometrical relationships between objects are constantly changing, but also simplifies the management of user interaction with comparatively little storage cost.
Weighted graph algorithms with Python
Kapanowski, A.; Gałuszka, Ł.
2015-01-01
Python implementation of selected weighted graph algorithms is presented. The minimal graph interface is defined together with several classes implementing this interface. Graph nodes can be any hashable Python objects. Directed edges are instances of the Edge class. Graphs are instances of the Graph class. It is based on the adjacency-list representation, but with fast lookup of nodes and neighbors (dict-of-dict structure). Other implementations of this class are also possible. In this work,...
Algorithms for regional source localization
Dandach, S. H.; Bullo, F.
2009-01-01
In this paper we use the MAP criterion to locate a region containing a source. Sensors placed in a field of interest divide the latter into smaller regions and take measurements that are transmitted over noisy wireless channels. We propose implementations of our algorithm that consider complete and limited communication among sensors and seek to choose the most likely hypothesis. Each hypothesis corresponds to the event that a given region contains the source. Corrupted measurements are used ...
Quantum Computations: Fundamentals And Algorithms
Duplij, Steven; Shapoval, Illia
2007-01-01
Basic concepts of quantum theory of information, principles of quantum calculations and the possibility of creation on this basis unique on calculation power and functioning principle device, named quantum computer, are briefly reviewed. The main blocks of quantum logic, schemes of implementation of quantum calculations, as well as some known today effective quantum algorithms, called to realize advantages of quantum calculations upon classical, are concerned. Among them special place is take...
Algorithms for Weighted Boolean Optimization
Manquinho, Vasco; Marques-Silva, Joao; Planes Cid, Jordi
2009-01-01
The Pseudo-Boolean Optimization (PBO) and Maximum Satisfiability (MaxSAT) problems are natural optimization extensions of Boolean Satisfiability (SAT). In the recent past, different algorithms have been proposed for PBO and for MaxSAT, despite the existence of straightforward mappings from PBO to MaxSAT and viceversa. This papers proposes Weighted Boolean Optimization (WBO), a new uni- fied framework that aggregates and extends PBO and MaxSAT. In addition, the paper proposes...
Nurse Rostering with Genetic Algorithms
Aickelin, Uwe
2010-01-01
In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses' wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in tha...
Teaching Multiplication Algorithms from Other Cultures
Lin, Cheng-Yao
2007-01-01
This article describes a number of multiplication algorithms from different cultures around the world: Hindu, Egyptian, Russian, Japanese, and Chinese. Students can learn these algorithms and better understand the operation and properties of multiplication.
Chinese handwriting recognition an algorithmic perspective
Su, Tonghua
2013-01-01
This book provides an algorithmic perspective on the recent development of Chinese handwriting recognition. Two technically sound strategies, the segmentation-free and integrated segmentation-recognition strategy, are investigated and algorithms that have worked well in practice are primarily focused on. Baseline systems are initially presented for these strategies and are subsequently expanded on and incrementally improved. The sophisticated algorithms covered include: 1) string sample expansion algorithms which synthesize string samples from isolated characters or distort realistic string samples; 2) enhanced feature representation algorithms, e.g. enhanced four-plane features and Delta features; 3) novel learning algorithms, such as Perceptron learning with dynamic margin, MPE training and distributed training; and lastly 4) ensemble algorithms, that is, combining the two strategies using both parallel structure and serial structure. All the while, the book moves from basic to advanced algorithms, helping ...
ITERATIVE ALGORITHMS FOR DATA ASSIMILATION PROBLEMS
Institute of Scientific and Technical Information of China (English)
无
2002-01-01
Iterative algorithms for solving the data assimilation problems are considered, based on the main and adjoint equations. Spectral properties of the control operators of the problem are studied, the iterative algorithms are justified.
DNA Coding Based Knowledge Discovery Algorithm
Institute of Scientific and Technical Information of China (English)
LI Ji-yun; GENG Zhao-feng; SHAO Shi-huang
2002-01-01
A novel DNA coding based knowledge discovery algorithm was proposed, an example which verified its validity was given. It is proved that this algorithm can discover new simplified rules from the original rule set efficiently.
A Hybrid Architecture Approach for Quantum Algorithms
Directory of Open Access Journals (Sweden)
Mohammad R.S. Aghaei
2009-01-01
Full Text Available Problem statement: In this study, a general plan of hybrid architecture for quantum algorithms is proposed. Approach: Analysis of the quantum algorithms shows that these algorithms were hybrid with two parts. First, the relationship of classical and quantum parts of the hybrid algorithms was extracted. Then a general plan of hybrid structure was designed. Results: This plan was illustrated the hybrid architecture and the relationship of classical and quantum parts of the algorithms. This general plan was used to increase implementation performance of quantum algorithms. Conclusion/Recommendations: Moreover, simulation results of quantum algorithms on the hybrid architecture proved that quantum algorithms can be implemented on the general plan as well.
Spaceborne SAR Imaging Algorithm for Coherence Optimized.
Directory of Open Access Journals (Sweden)
Zhiwei Qiu
Full Text Available This paper proposes SAR imaging algorithm with largest coherence based on the existing SAR imaging algorithm. The basic idea of SAR imaging algorithm in imaging processing is that output signal can have maximum signal-to-noise ratio (SNR by using the optimal imaging parameters. Traditional imaging algorithm can acquire the best focusing effect, but would bring the decoherence phenomenon in subsequent interference process. Algorithm proposed in this paper is that SAR echo adopts consistent imaging parameters in focusing processing. Although the SNR of the output signal is reduced slightly, their coherence is ensured greatly, and finally the interferogram with high quality is obtained. In this paper, two scenes of Envisat ASAR data in Zhangbei are employed to conduct experiment for this algorithm. Compared with the interferogram from the traditional algorithm, the results show that this algorithm is more suitable for SAR interferometry (InSAR research and application.
Performance Analysis of Cone Detection Algorithms
Mariotti, Letizia
2015-01-01
Many algorithms have been proposed to help clinicians evaluate cone density and spacing, as these may be related to the onset of retinal diseases. However, there has been no rigorous comparison of the performance of these algorithms. In addition, the performance of such algorithms is typically determined by comparison with human observers. Here we propose a technique to simulate realistic images of the cone mosaic. We use the simulated images to test the performance of two popular cone detection algorithms and we introduce an algorithm which is used by astronomers to detect stars in astronomical images. We use Free Response Operating Characteristic (FROC) curves to evaluate and compare the performance of the three algorithms. This allows us to optimize the performance of each algorithm. We observe that performance is significantly enhanced by up-sampling the images. We investigate the effect of noise and image quality on cone mosaic parameters estimated using the different algorithms, finding that the estimat...
Results of Evolution Supervised by Genetic Algorithms
Jäntschi, Lorentz; Bălan, Mugur C; Sestraş, Radu E
2010-01-01
A series of results of evolution supervised by genetic algorithms with interest to agricultural and horticultural fields are reviewed. New obtained original results from the use of genetic algorithms on structure-activity relationships are reported.
Cache-Oblivious Algorithms and Data Structures
DEFF Research Database (Denmark)
Brodal, Gerth Stølting
2004-01-01
Frigo, Leiserson, Prokop and Ramachandran in 1999 introduced the ideal-cache model as a formal model of computation for developing algorithms in environments with multiple levels of caching, and coined the terminology of cache-oblivious algorithms. Cache-oblivious algorithms are described as stan...... apply to multi-level memory hierarchies. This paper gives an overview of the results achieved on cache-oblivious algorithms and data structures since the seminal paper by Frigo et al....
Automatic Algorithm Selection for Complex Simulation Problems
Ewald, Roland
2012-01-01
To select the most suitable simulation algorithm for a given task is often difficult. This is due to intricate interactions between model features, implementation details, and runtime environment, which may strongly affect the overall performance. An automated selection of simulation algorithms supports users in setting up simulation experiments without demanding expert knowledge on simulation. Roland Ewald analyzes and discusses existing approaches to solve the algorithm selection problem in the context of simulation. He introduces a framework for automatic simulation algorithm selection and
Fast identification algorithms for forensic applications
Beekhof, Fokko Pieter; Voloshynovskyy, Svyatoslav; Koval, Oleksiy; Holotyak, Taras
2009-01-01
In this work a novel fast search algorithm is proposed that is designed to offer improved performance in terms of identification accuracy whilst maintaining acceptable speed for forensic applications involving biometrics and Physically Unclonable Functions. A framework for forensic applications is presented, followed by a review of optimal and existing fast algorithms. We show why the new algorithm has the power to outperform the other algorithms with a theoretic analysis and confirm this usi...
A comprehensive review of firefly algorithms
Fister, Iztok; Fister Jr, Iztok; Yang, Xin-She; Brest, Janez
2013-01-01
The firefly algorithm has become an increasingly important tool of Swarm Intelligence that has been applied in almost all areas of optimization, as well as engineering practice. Many problems from various areas have been successfully solved using the firefly algorithm and its variants. In order to use the algorithm to solve diverse problems, the original firefly algorithm needs to be modified or hybridized. This paper carries out a comprehensive review of this living and evolving discipline o...
A Euclidean algorithm for integer matrices
DEFF Research Database (Denmark)
Lauritzen, Niels; Thomsen, Jesper Funch
2015-01-01
We present a Euclidean algorithm for computing a greatest common right divisor of two integer matrices. The algorithm is derived from elementary properties of finitely generated modules over the ring of integers.......We present a Euclidean algorithm for computing a greatest common right divisor of two integer matrices. The algorithm is derived from elementary properties of finitely generated modules over the ring of integers....
A Comprehensive Review of Swarm Optimization Algorithms
Ab Wahab, Mohd Nadhir; Nefti-Meziani, Samia; Atyabi, Adham
2015-01-01
Many swarm optimization algorithms have been introduced since the early 60’s, Evolutionary Programming to the most recent, Grey Wolf Optimization. All of these algorithms have demonstrated their potential to solve many optimization problems. This paper provides an in-depth survey of well-known optimization algorithms. Selected algorithms are briefly explained and compared with each other comprehensively through experiments conducted using thirty well-known benchmark functions. Their advantage...
Cultural Algorithm for Engineering Design Problems
Xuesong Yan
2012-01-01
Many engineering optimization problems can be state as function optimization with constrained, intelligence optimization algorithm can solve these problems well. Cultural Algorithms are a class of computational models derived from observing the cultural evolution process in nature, cultural algorithms in the optimization of the complex constrained functions of its superior performance. Experiment results reveal that the proposed algorithm can find better solutions when compared to other heuri...
An Algorithm for Successive Identification of Reflections
DEFF Research Database (Denmark)
Hansen, Kim Vejlby; Larsen, Jan
1994-01-01
A new algorithm for successive identification of seismic reflections is proposed. Generally, the algorithm can be viewed as a curve matching method for images with specific structure. However, in the paper, the algorithm works on seismic signals assembled to constitute an image in which the...... synthetic CMP gather, whereas the other is based on a real recorded CMP gather. Initially, the algorithm requires an estimate of the wavelet that can be performed by any wavelet estimation method.>...
A REVIEW ON ASSOCIATION RULE MINING ALGORITHMS
JYOTI ARORA, NIDHI BHALLA, SANJEEV RAO
2013-01-01
In this paper, a review of four different association rule mining algorithmsApriori, AprioriTid,Apriori hybrid and tertius algorithms and their drawbacks which would be helpful to find new solution for the Problems found in these algorithms and also presents a comparison between different association mining algorithms. Association rule mining is the one of the most important technique of the data mining. Its aim is to extract interesting correlations, frequent patterns and association among s...
Application of Apriori Algorithm to Customer Analysis
Mu jiankang
2013-01-01
How to maximize the information is a very important problem for the decision-makers. Apriori algorithm based on association rules of data mining technology has been employed as the research instrument. This study analyzes the definition of association rules and apriori algorithm, studies the process of apriori algorithm, make an empirical analysis on the consumer's purchase behavior. The experimental results show that apriori algorithm is an important techn...
An algorithm for segmenting range imagery
Energy Technology Data Exchange (ETDEWEB)
Roberts, R.S.
1997-03-01
This report describes the technical accomplishments of the FY96 Cross Cutting and Advanced Technology (CC&AT) project at Los Alamos National Laboratory. The project focused on developing algorithms for segmenting range images. The image segmentation algorithm developed during the project is described here. In addition to segmenting range images, the algorithm can fuse multiple range images thereby providing true 3D scene models. The algorithm has been incorporated into the Rapid World Modelling System at Sandia National Laboratory.
Implementation of Cryptographic Algorithm on FPGA
Prof. S. Venkateswarlu; Deepa G.M; G. Sriteja
2013-01-01
Advanced Encryption Standard (AES), a Federal Information Processing Standard (FIPS), is anapproved cryptographic algorithm that is used to protect electronic data. The AES can be programmed insoftware or built with hardware. The paper presents a hardware implementation of the AES algorithm onFPGA. The algorithm was implemented in FPGA using Spartan 3E starter kit and Xilinx ISE developmentsuite. The purpose of this attempt was to test the correctness of the implemented algorithm and to gaine...
Integer algorithms in cryptology and information assurance
Verkhovsky, Boris S
2014-01-01
Integer Algorithms in Cryptology and Information Assurance is a collection of the author's own innovative approaches in algorithms and protocols for secret and reliable communication. It concentrates on the "what" and "how" behind implementing the proposed cryptographic algorithms rather than on formal proofs of "why" these algorithms work. The book consists of five parts (in 28 chapters) and describes the author's research results in: -->Innovative methods in cryptography (secret communication between initiated parties);Cryptanalysis (how to break the e
Algorithms and Requirements for Measuring Network Bandwidth
Energy Technology Data Exchange (ETDEWEB)
Jin, Guojun
2002-12-08
This report unveils new algorithms for actively measuring (not estimating) available bandwidths with very low intrusion, computing cross traffic, thus estimating the physical bandwidth, provides mathematical proof that the algorithms are accurate, and addresses conditions, requirements, and limitations for new and existing algorithms for measuring network bandwidths. The paper also discusses a number of important terminologies and issues for network bandwidth measurement, and introduces a fundamental parameter -Maximum Burst Size that is critical for implementing algorithms based on multiple packets.
An algorithm for multiplication of Dirac numbers
Aleksandr Cariow; Galina Cariowa
2013-01-01
In this work a rationalized algorithm for Dirac numbers multiplication is presented. This algorithm has a low computational complexity feature and is well suited to parallelization of computations. The computation of two Dirac numbers product using the naïve method takes 256 real multiplications and 240 real additions, while the proposed algorithm can compute the same result in only 128 real multiplications and 160 real additions. During synthesis of the discussed algorithm we use the fact th...
Distance Concentration-Based Artificial Immune Algorithm
Institute of Scientific and Technical Information of China (English)
LIU Tao; WANG Yao-cai; WANG Zhi-jie; MENG Jiang
2005-01-01
The diversity, adaptation and memory of biological immune system attract much attention of researchers. Several optimal algorithms based on immune system have also been proposed up to now. The distance concentration-based artificial immune algorithm (DCAIA) is proposed to overcome defects of the classical artificial immune algorithm (CAIA) in this paper. Compared with genetic algorithm (GA) and CAIA, DCAIA is good for solving the problem of precocity,holding the diversity of antibody, and enhancing convergence rate.
A Direct Manipulation Language for Explaining Algorithms
Scott, Jeremy; Guo, Philip J.; Davis, Randall
2014-01-01
Instructors typically explain algorithms in computer science by tracing their behavior, often on blackboards, sometimes with algorithm visualizations. Using blackboards can be tedious because they do not facilitate manipulation of the drawing, while visualizations often operate at the wrong level of abstraction or must be laboriously hand-coded for each algorithm. In response, we present a direct manipulation (DM) language for explaining algorithms by manipulating visualized data structures. ...
Chess Player by Co-Evolutionary Algorithm
Ramos, Nuno; Salgado, Sergio; Rosa, Agostinho C
2016-01-01
A co-evolutionary algorithm (CA) based chess player is presented. Implementation details of the algorithms, namely coding, population, variation operators are described. The alpha-beta or mini-max like behaviour of the player is achieved through two competitive or cooperative populations. Special attention is given to the fitness function evaluation (the heart of the solution). Test results on algorithms vs. algorithms or human player is provided.
Application of Chaos in Genetic Algorithms
Institute of Scientific and Technical Information of China (English)
YANG Li-Jiang; CHEN Tian-Lun
2002-01-01
Through replacing Gaussian mutation operator in real-coded genetic algorithm with a chaotic mapping, wepresent a genetic algorithm with chaotic mutation. To examine this new algorithm, we applied our algorithm to functionoptimization problems and obtained good results. Furthermore the orbital points' distribution of chaotic mapping andthe effects of chaotic mutation with different parameters were studied in order to make the chaotic mutation mechanismbe utilized efficiently.
Research of Embedded Hardware Optimization Design Algorithm
Xuesong Yan
2012-01-01
Embedded hardware design is important in real world applications, but with the increase of the hardware scale the traditional methods can not design them well. Cultural Algorithms are a class of computational models derived from observing the cultural evolution process in nature. Aiming at the disadvantages of basic Cultural Algorithms like being trapped easily into a local optimum, this paper improves the basic Cultural Algorithms and proposes a new algorithm to solve the overcomes of the ba...
Active noise cancellation algorithms for impulsive noise
Li, Peng; Yu, Xun
2012-01-01
Impulsive noise is an important challenge for the practical implementation of active noise control (ANC) systems. The advantages and disadvantages of popular filtered-X least mean square (FXLMS) ANC algorithm and nonlinear filtered-X least mean M-estimate (FXLMM) algorithm are discussed in this paper. A new modified FXLMM algorithm is also proposed to achieve better performance in controlling impulsive noise. Computer simulations and experiments are carried out for all three algorithms and th...
A Deterministic and Polynomial Modified Perceptron Algorithm
Directory of Open Access Journals (Sweden)
Olof Barr
2006-01-01
Full Text Available We construct a modified perceptron algorithm that is deterministic, polynomial and also as fast as previous known algorithms. The algorithm runs in time O(mn3lognlog(1/ρ, where m is the number of examples, n the number of dimensions and ρ is approximately the size of the margin. We also construct a non-deterministic modified perceptron algorithm running in timeO(mn2lognlog(1/ρ.
A Survey on Star Identification Algorithms
Daniele Mortari; Benjamin B. Spratling
2009-01-01
The author surveys algorithms used in star identification, commonly used in star trackers to determine the attitude of a spacecraft. Star trackers are a staple of attitude determination systems for most types of satellites. The paper covers: (a) lost-in-space algorithms (when no a priori attitude information is available), (b) recursive algorithms (when some a priori attitude information is available), and (c) non-dimensional algorithms (when the star tracker calibration is not well-known). T...
OPTIMISED RANDOM MUTATIONS FOR EVOLUTIONARY ALGORITHMS
Sean McGerty; Frank Moisiadis
2014-01-01
To demonstrate our approaches we will use Sudoku puzzles, which are an excellent test bed for evolutionary algorithms. The puzzles are accessible enough for people to enjoy. However the more complex puzzles require thousands of iterations before an evolutionary algorithm finds a solution. If we were attempting to compare evolutionary algorithms we could count their iterations to solution as an indicator of relative efficiency. Evolutionary algorithms however include a process of r...
Trilateral market coupling. Algorithm appendix
International Nuclear Information System (INIS)
Market Coupling is both a mechanism for matching orders on the exchange and an implicit cross-border capacity allocation mechanism. Market Coupling improves the economic surplus of the coupled markets: the highest purchase orders and the lowest sale orders of the coupled power exchanges are matched, regardless of the area where they have been submitted; matching results depend however on the Available Transfer Capacity (ATC) between the coupled hubs. Market prices and schedules of the day-ahead power exchanges of the several connected markets are simultaneously determined with the use of the Available Transfer Capacity defined by the relevant Transmission System Operators. The transmission capacity is thereby implicitly auctioned and the implicit cost of the transmission capacity from one market to the other is the price difference between the two markets. In particular, if the transmission capacity between two markets is not fully used, there is no price difference between the markets and the implicit cost of the transmission capacity is null. Market coupling relies on the principle that the market with the lowest price exports electricity to the market with the highest price. Two situations may appear: either the Available Transfer Capacity (ATC) is large enough and the prices of both markets are equalized (price convergence), or the ATC is too small and the prices cannot be equalized. The Market Coupling algorithm takes as an input: 1 - The Available Transfer Capacity (ATC) between each area for each flow direction and each Settlement Period of the following day (i.e. for each hour of following day); 2 - The (Block Free) Net Export Curves (NEC) of each market for each hour of the following day, i.e., the difference between the total quantity of Divisible Hourly Bids and the total quantity of Divisible Hourly Offers for each price level. The NEC reflects a market's import or export volume sensitivity to price. 3 - The Block Orders submitted by the participants in
Optimisation of nonlinear motion cueing algorithm based on genetic algorithm
Asadi, Houshyar; Mohamed, Shady; Rahim Zadeh, Delpak; Nahavandi, Saeid
2015-04-01
Motion cueing algorithms (MCAs) are playing a significant role in driving simulators, aiming to deliver the most accurate human sensation to the simulator drivers compared with a real vehicle driver, without exceeding the physical limitations of the simulator. This paper provides the optimisation design of an MCA for a vehicle simulator, in order to find the most suitable washout algorithm parameters, while respecting all motion platform physical limitations, and minimising human perception error between real and simulator driver. One of the main limitations of the classical washout filters is that it is attuned by the worst-case scenario tuning method. This is based on trial and error, and is effected by driving and programmers experience, making this the most significant obstacle to full motion platform utilisation. This leads to inflexibility of the structure, production of false cues and makes the resulting simulator fail to suit all circumstances. In addition, the classical method does not take minimisation of human perception error and physical constraints into account. Production of motion cues and the impact of different parameters of classical washout filters on motion cues remain inaccessible for designers for this reason. The aim of this paper is to provide an optimisation method for tuning the MCA parameters, based on nonlinear filtering and genetic algorithms. This is done by taking vestibular sensation error into account between real and simulated cases, as well as main dynamic limitations, tilt coordination and correlation coefficient. Three additional compensatory linear blocks are integrated into the MCA, to be tuned in order to modify the performance of the filters successfully. The proposed optimised MCA is implemented in MATLAB/Simulink software packages. The results generated using the proposed method show increased performance in terms of human sensation, reference shape tracking and exploiting the platform more efficiently without reaching
Algorithm 896: LSA: Algorithms for Large-Scale Optimization
Czech Academy of Sciences Publication Activity Database
Lukšan, Ladislav; Matonoha, Ctirad; Vlček, Jan
2009-01-01
Roč. 36, č. 3 (2009), 16-1-16-29. ISSN 0098-3500 R&D Projects: GA AV ČR IAA1030405; GA ČR GP201/06/P397 Institutional research plan: CEZ:AV0Z10300504 Keywords : algorithms * design * large-scale optimization * large-scale nonsmooth optimization * large-scale nonlinear least squares * large-scale nonlinear minimax * large-scale systems of nonlinear equations * sparse problems * partially separable problems * limited-memory methods * discrete Newton methods * quasi-Newton methods * primal interior-point methods Subject RIV: BB - Applied Statistics, Operational Research Impact factor: 1.904, year: 2009
Engineering a Cache-Oblivious Sorting Algorithm
DEFF Research Database (Denmark)
Brodal, Gerth Stølting; Fagerberg, Rolf; Vinther, Kristoffer
2007-01-01
This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort, and compare the final algorithm with Quicksort, the established standard...
Storage Capacity of the Tilinglike Learning Algorithm
Buhot, Arnaud; Gordon, Mirta B.
2000-01-01
The storage capacity of an incremental learning algorithm for the parity machine, the Tilinglike Learning Algorithm, is analytically determined in the limit of a large number of hidden perceptrons. Different learning rules for the simple perceptron are investigated. The usual Gardner-Derrida one leads to a storage capacity close to the upper bound, which is independent of the learning algorithm considered.
In-Trail Procedure (ITP) Algorithm Design
Munoz, Cesar A.; Siminiceanu, Radu I.
2007-01-01
The primary objective of this document is to provide a detailed description of the In-Trail Procedure (ITP) algorithm, which is part of the Airborne Traffic Situational Awareness In-Trail Procedure (ATSA-ITP) application. To this end, the document presents a high level description of the ITP Algorithm and a prototype implementation of this algorithm in the programming language C.
CSP description of some parallel sorting algorithms
Energy Technology Data Exchange (ETDEWEB)
Linck, M.H.
1982-11-01
Hoare's CSP notation is used to describe 3 parallel sorting algorithms. The first algorithm uses n/2 processes working in parallel, the second uses an array of n parallel processes and the third algorithm is a parallel version of quicksort. 12 references.
Successive combination jet algorithm for hadron collisions
Ellis, S D; Ellis, Stephen D.; Soper, Davision E.
1993-01-01
Jet finding algorithms, as they are used in $e^+ e^-$ and hadron collisions, are reviewed and compared. It is suggested that a successive combination style algorithm, similar to that used in $e^+ e^-$ physics, might be useful also in hadron collisions, where cone style algorithms have been used previously.
Particle Swarm Optimization and Genetic Algorithms
Elisa Valentina Oneţ
2009-01-01
This paper presents two evolutionary computation techniques: particle swarm optimization – part of swarm intelligence and genetic algorithms – part of the evolutionary algorithms. The basic algorithm for each is reviewed, in case of optimization problems in asearch space. It is presented how each evolutionary computation technique works, and the way in which features from one can be included into the other.
Quantum Central Processing Unit and Quantum Algorithm
Institute of Scientific and Technical Information of China (English)
王安民
2002-01-01
Based on a scalable and universal quantum network, quantum central processing unit, proposed in our previous paper [Chin. Phys. Left. 18 (2001)166], the whole quantum network for the known quantum algorithms,including quantum Fourier transformation, Shor's algorithm and Grover's algorithm, is obtained in a unitied way.
Cross layer scheduling algorithm for LTE Downlink
DEFF Research Database (Denmark)
Popovska Avramova, Andrijana; Yan, Ying; Dittmann, Lars
2012-01-01
. This paper evaluates a cross layer scheduling algorithm that aims at minimizing the resource utilization. The algorithm makes decisions regarding the channel conditions and the size of transmission buffers and different QoS demands. The simulation results show that the new algorithm improves the...
A Hybrid Task Scheduling Algorithm in Grid
Institute of Scientific and Technical Information of China (English)
ZHANG Yan-mei; CAO Huai-hu; YU Zhen-wei
2006-01-01
Task scheduling in Grid has been proved to be NP- complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony and Genetic Algorithm.Compared with the related work, the result shows that the HTS algorithm significantly surpasses the previous approaches in schedule length ratio and speedup.
Parallel Genetic Algorithm for Channel Routing
Rao, Prahlada BB; Patnaik, LM; Hansdah, RC
1993-01-01
In this paper, we propose a new channel routing algorithm based on genetic approach. This involves designing a new encoding scheme and an evaluation function used by the genetic algorithm (GA) for channel routing problem. The algorithm has been implemented as both sequential and distributed CA. The speedup achieved is positive and encouraging.
Floating Entanglement Witness Measure and Genetic Algorithm
Baghbanpourasl, A.; Najarbashi, G.; Seyedkazemi, M.
2007-01-01
In this paper based on the notion of entanglement witness, a new measure of entanglement called floating entanglement witness measure is introduced which satisfies some of the usual properties of a good entanglement measure. By exploiting genetic algorithm, we introduce a classical algorithm that computes floating entanglement witness measure. This algorithm also provides a method for finding entanglement witness for a given entangled state.
Voronoi Particle Merging Algorithm for PIC Codes
Luu, Phuc T
2016-01-01
We present a new particle-merging algorithm for the particle-in-cell method. Based on the concept of the Voronoi diagram, the algorithm partitions the phase space into smaller subsets, which consist of only particles that are in close proximity in the phase space to each other. We show the performance of our algorithm in the case of magnetic shower.
Parameter incremental learning algorithm for neural networks.
Wan, Sheng; Banta, Larry E
2006-11-01
In this paper, a novel stochastic (or online) training algorithm for neural networks, named parameter incremental learning (PIL) algorithm, is proposed and developed. The main idea of the PIL strategy is that the learning algorithm should not only adapt to the newly presented input-output training pattern by adjusting parameters, but also preserve the prior results. A general PIL algorithm for feedforward neural networks is accordingly presented as the first-order approximate solution to an optimization problem, where the performance index is the combination of proper measures of preservation and adaptation. The PIL algorithms for the multilayer perceptron (MLP) are subsequently derived. Numerical studies show that for all the three benchmark problems used in this paper the PIL algorithm for MLP is measurably superior to the standard online backpropagation (BP) algorithm and the stochastic diagonal Levenberg-Marquardt (SDLM) algorithm in terms of the convergence speed and accuracy. Other appealing features of the PIL algorithm are that it is computationally as simple as the BP algorithm, and as easy to use as the BP algorithm. It, therefore, can be applied, with better performance, to any situations where the standard online BP algorithm is applicable. PMID:17131658
Learning Intelligent Genetic Algorithms Using Japanese Nonograms
Tsai, Jinn-Tsong; Chou, Ping-Yi; Fang, Jia-Cen
2012-01-01
An intelligent genetic algorithm (IGA) is proposed to solve Japanese nonograms and is used as a method in a university course to learn evolutionary algorithms. The IGA combines the global exploration capabilities of a canonical genetic algorithm (CGA) with effective condensed encoding, improved fitness function, and modified crossover and…
Another Disjoint Compression Algorithm for OCT
Krithika, R.; Narayanaswamy, N. S.
2013-01-01
We describe an elegant O*(2^k) algorithm for the disjoint compression problem for Odd Cycle Transversal based on a reduction to Above Guarantee Vertex Cover. We believe that this algorithm refines the understanding of the Odd Cycle Transversal algorithm by Reed, Smith and Vetta.
F4 Algorithm For Euclidean Rings
Sadiq, Afshan
2010-01-01
This short note is the generalization of Faugere F4-algorithm for polynomial rings with coefficients in Euclidean rings. This algorithm computes successively a Groebner basis replacing the reduction of one single s-polynomial in Buchberger's algorithm by the simultaneous reduction of several polynomials.
Stabilizing the Richardson Algorithm by Controlling Chaos
He, Song
1996-01-01
By viewing the operations of the Richardson purification algorithm as a discrete time dynamical process, we propose a method to overcome the instability of the algorithm by controlling chaos. We present theoretical analysis and numerical results on the behavior and performance of the stabilized algorithm.
An algorithm for reduct cardinality minimization
AbouEisha, Hassan M.
2013-12-01
This is devoted to the consideration of a new algorithm for reduct cardinality minimization. This algorithm transforms the initial table to a decision table of a special kind, simplify this table, and use a dynamic programming algorithm to finish the construction of an optimal reduct. Results of computer experiments with decision tables from UCI ML Repository are discussed. © 2013 IEEE.
Progress in lattice field theory algorithms
International Nuclear Information System (INIS)
I present a summary of recent algorithmic developments for lattice field theories. In particular I give a pedagogical introduction to the new Multicanonical algorithm, and discuss the relation between the Hybrid Overrelaxation and Hybrid Monte Carlo algorithms. I also attempt to clarify the role of the dynamical critical exponent z and its connection with 'computational cost'. (orig.)
Inverse Computation and the Universal Resolving Algorithm
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
We survey fundamental concepts for inverse programming and thenpresent the Uni v ersal Resolving Algorithm, an algorithm for inverse computation in a first-orde r , functional programming language. We discuss the key concepts of the algorithm, including a three-step approach based on the notion of a perfect process tree, and demonstrate our implementation with several examples of inverse computation.
On the Analysis of Evolutionary Algorithms
Jansen, Thomas; Wegener, Ingo
2001-01-01
There is a lot of experimental evidence that crossover is, for some functions, an essential operator of evolutionary algorithms. Nevertheless, it was an open problem to prove for some function that an evolutionary algorithm using crossover is essentially more efficient than evolutionary algorithms without crossover. In this paper, such an example is presented and its properties are proved.
Occurrences Algorithm for String Searching Based on Brute-force Algorithm
Ababneh Mohammad; Oqeili Saleh; Rawan A. Abdeen
2006-01-01
This study proposes a string searching algorithm as an improvement of the brute-force searching algorithm. The algorithm is named as, Occurrences algorithm. It is based on performing preprocessing for the pattern and for the text before beginning to search for the pattern in the text.
Knowledge Recognition Algorithm enables P = NP
Wen, Han Xiao
2010-01-01
This paper introduces a knowledge recognition algorithm (KRA) that is both a Turing machine algorithm and an Oracle Turing machine algorithm. By definition KRA is a non-deterministic language recognition algorithm. Simultaneously it can be implemented as a deterministic Turing machine algorithm. KRA applies mirrored perceptual-conceptual languages to learn member-class relations between the two languages iteratively and retrieve information through deductive and reductive recognition from one language to another. The novelty of KRA is that the conventional concept of relation is adjusted. The computation therefore becomes efficient bidirectional string mapping.
Bat Algorithm for Multi-objective Optimisation
Yang, Xin-She
2012-01-01
Engineering optimization is typically multiobjective and multidisciplinary with complex constraints, and the solution of such complex problems requires efficient optimization algorithms. Recently, Xin-She Yang proposed a bat-inspired algorithm for solving nonlinear, global optimisation problems. In this paper, we extend this algorithm to solve multiobjective optimisation problems. The proposed multiobjective bat algorithm (MOBA) is first validated against a subset of test functions, and then applied to solve multiobjective design problems such as welded beam design. Simulation results suggest that the proposed algorithm works efficiently.
External-Memory Algorithms and Data Structures
DEFF Research Database (Denmark)
Arge, Lars; Zeh, Norbert
2010-01-01
. This is due to the huge difference in access time of fast internal memory and slower external memory such as disks. The goal of theoretical work in the area of external memory algorithms (also called I/O algorithms or out-of-core algorithms) has been to develop algorithms that minimize the Input/Output...... to specify the functional details of computation taking place within the supported paradigms. This will allow a wide variety of algorithms to be implemented within the system.Be portable across a variety hardware platforms.Be extensible, so that new features can be easily added later.TPIE is implemented...
Analysis of a multiple dispatch algorithm
Holmberg, Johannes
2004-01-01
The development of the new programming language Scream, within the project Software Renaissance, led to the need of a good multiple dispatch algorithm. A multiple dispatch algorithm, called Compressed n-dimensional table with row sharing; CNT-RS, was developed from the algorithm Compressed n-dimensional table, CNT. The purpose of CNT-RS was to create a more efficient algorithm. This report is the result of the work to analyse the CNT-RS algorithm. In this report the domain of multiple dispat...
FACE RECOGNITION BASED ON CUCKOO SEARCH ALGORITHM
Directory of Open Access Journals (Sweden)
VIPINKUMAR TIWARI
2012-07-01
Full Text Available Feature Selection is a optimization technique used in face recognition technology. Feature selection removes the irrelevant, noisy and redundant data thus leading to the more accurate recognition of face from the database.Cuckko Algorithm is one of the recent optimization algorithm in the league of nature based algorithm. Its optimization results are better than the PSO and ACO optimization algorithms. The proposal of applying the Cuckoo algorithm for feature selection in the process of face recognition is presented in this paper.
Statistical Mechanics Algorithms and Computations
Krauth, Werner
2006-01-01
This book discusses the computational approach in modern statistical physics, adopting simple language and an attractive format of many illustrations, tables and printed algorithms. The discussion of key subjects in classical and quantum statistical physics will appeal to students, teachers and researchers in physics and related sciences. The focus is on orientation with implementation details kept to a minimum. - ;This book discusses the computational approach in modern statistical physics in a clear and accessible way and demonstrates its close relation to other approaches in theoretical phy
Prosthaphaeresis – a Forgotten Algorithm
Czech Academy of Sciences Publication Activity Database
Porubský, Štefan
Praha : Národní technické muzeum v Praze, 2010 - (Hadravová, A.; Mahoney, T.; Hadrava, P.), s. 63-77 ISBN 978-80-7037-193-0. - (Acta historiae rerum naturalium necnon technicarum. 10) R&D Projects: GA AV ČR 1ET200300529 Institutional research plan: CEZ:AV0Z10300504 Keywords : prostaphaeresis * multiplication algorithm * arithmetics of 16. century * trigonometry * Tycho Brahe * Paul Wittich * Johann Werner * Jost Buergi * Georg Joachim von Lauchen Rheticus * Nicolaus Copernicus Subject RIV: BA - General Mathematics
Algorithms for optimizing drug therapy
Directory of Open Access Journals (Sweden)
Martin Lene
2004-07-01
Full Text Available Abstract Background Drug therapy has become increasingly efficient, with more drugs available for treatment of an ever-growing number of conditions. Yet, drug use is reported to be sub optimal in several aspects, such as dosage, patient's adherence and outcome of therapy. The aim of the current study was to investigate the possibility to optimize drug therapy using computer programs, available on the Internet. Methods One hundred and ten officially endorsed text documents, published between 1996 and 2004, containing guidelines for drug therapy in 246 disorders, were analyzed with regard to information about patient-, disease- and drug-related factors and relationships between these factors. This information was used to construct algorithms for identifying optimum treatment in each of the studied disorders. These algorithms were categorized in order to define as few models as possible that still could accommodate the identified factors and the relationships between them. The resulting program prototypes were implemented in HTML (user interface and JavaScript (program logic. Results Three types of algorithms were sufficient for the intended purpose. The simplest type is a list of factors, each of which implies that the particular patient should or should not receive treatment. This is adequate in situations where only one treatment exists. The second type, a more elaborate model, is required when treatment can by provided using drugs from different pharmacological classes and the selection of drug class is dependent on patient characteristics. An easily implemented set of if-then statements was able to manage the identified information in such instances. The third type was needed in the few situations where the selection and dosage of drugs were depending on the degree to which one or more patient-specific factors were present. In these cases the implementation of an established decision model based on fuzzy sets was required. Computer programs
Algorithms for Next Generation Networks
Cormode, Graham
2010-01-01
Data networking now plays a major role in everyday life and new applications continue to appear at a blinding pace. Yet we still do not have a sound foundation for designing, evaluating and managing these networks. This book covers topics at the intersection of algorithms and networking. It builds a complete picture of the current state of research on Next Generation Networks and the challenges for the years ahead. Particular focus is given to evolving research initiatives and the architecture they propose and implications for networking. Topics: Network design and provisioning, hardware issue
Algorithms for Protein Structure Prediction
Paluszewski, Martin
2008-01-01
The problem of predicting the three-dimensional structure of a protein given itsamino acid sequence is one of the most important open problems in bioinformatics.One of the carbon atoms in amino acids is the C-atom and the overallstructure of a protein is often represented by a so-called C-trace.Here we present three different approaches for reconstruction of C-tracesfrom predictable measures. In our first approach [63, 62], the C-trace is positionedon a lattice and a tabu-search algorithm is ...
Elementary algorithms from advanced mechanics
Chin, Siu A
2016-01-01
Most elementary numerical schemes found useful for solving classical trajectory problems are {\\it canonical transformations}. This fact should be make more widely known among teachers of computational physics and Hamiltonian mechanics. It is very surprising that in order to solve a simple second-order differential equation, one has to invoke the deepest part, the Poissonian formulation, of classical mechanics. From the perspective of advanced mechanics, there are no bewildering number of seemingly arbitrary elementary schemes based on Taylor's expansion. There are only {\\it two} canonical second-order algorithms, on the basis of which one can build numerical schemes of any order.
Data clustering algorithms and applications
Aggarwal, Charu C
2013-01-01
Research on the problem of clustering tends to be fragmented across the pattern recognition, database, data mining, and machine learning communities. Addressing this problem in a unified way, Data Clustering: Algorithms and Applications provides complete coverage of the entire area of clustering, from basic methods to more refined and complex data clustering approaches. It pays special attention to recent issues in graphs, social networks, and other domains.The book focuses on three primary aspects of data clustering: Methods, describing key techniques commonly used for clustering, such as fea
Data streams algorithms and applications
Muthukrishnan, S
2014-01-01
Data stream algorithms as an active research agenda emerged only over the past few years, even though the concept of making few passes over the data for performing computations has been around since the early days of Automata Theory. The data stream agenda now pervades many branches of Computer Science including databases, networking, knowledge discovery and data mining, and hardware systems. Industry is in synch too, with Data Stream Management Systems (DSMSs) and special hardware to deal with data speeds. Even beyond Computer Science, data stream concerns are emerging in physics, atmospheric
ALFA: Automated Line Fitting Algorithm
Wesson, R.
2015-12-01
ALFA fits emission line spectra of arbitrary wavelength coverage and resolution, fully automatically. It uses a catalog of lines which may be present to construct synthetic spectra, the parameters of which are then optimized by means of a genetic algorithm. Uncertainties are estimated using the noise structure of the residuals. An emission line spectrum containing several hundred lines can be fitted in a few seconds using a single processor of a typical contemporary desktop or laptop PC. Data cubes in FITS format can be analysed using multiple processors, and an analysis of tens of thousands of deep spectra obtained with instruments such as MUSE will take a few hours.
Ordered subsets algorithms for transmission tomography.
Erdogan, H; Fessler, J A
1999-11-01
The ordered subsets EM (OSEM) algorithm has enjoyed considerable interest for emission image reconstruction due to its acceleration of the original EM algorithm and ease of programming. The transmission EM reconstruction algorithm converges very slowly and is not used in practice. In this paper, we introduce a simultaneous update algorithm called separable paraboloidal surrogates (SPS) that converges much faster than the transmission EM algorithm. Furthermore, unlike the 'convex algorithm' for transmission tomography, the proposed algorithm is monotonic even with nonzero background counts. We demonstrate that the ordered subsets principle can also be applied to the new SPS algorithm for transmission tomography to accelerate 'convergence', albeit with similar sacrifice of global convergence properties as for OSEM. We implemented and evaluated this ordered subsets transmission (OSTR) algorithm. The results indicate that the OSTR algorithm speeds up the increase in the objective function by roughly the number of subsets in the early iterates when compared to the ordinary SPS algorithm. We compute mean square errors and segmentation errors for different methods and show that OSTR is superior to OSEM applied to the logarithm of the transmission data. However, penalized-likelihood reconstructions yield the best quality images among all other methods tested. PMID:10588288
Quantum Algorithm for the Toeplitz Systems
Wan, Lin-Chun; Pan, Shi-Jie; Gao, Fei; Wen, Qiao-Yan
2016-01-01
Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$ given a $n\\times n$ Toeplitz matrix $T_n$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error $\\epsilon$ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions $n$ and in the inverse error $\\epsilon^{-1}$. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of $T_n$ is $O(\\textrm{poly}(\\textrm{log}\\,n))$. Since no assumption on the sparseness of $T_n$ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.
Modified nearest neighbor phase unwrapping algorithm
Institute of Scientific and Technical Information of China (English)
CHEN Jia-feng; CHEN Hai-qing; YANG Zhen-gang
2006-01-01
Phase unwrapping is so important in interferometry that it determines the veracity of the absolute phase value.Goldstein's branch-cut algorithm performs path-independent algorithm that uses a nearest neighbor heuristic to link and balance the residues based on identifying the residues.A modified nearest neighbor algorithm is presented based on the principle,the mathematic formula of the Goldstein's algorithm and in-depth analysis of the key problem of phase unwrapping.It not only holds the advantage of the Goldstein's algorithm but also solves the problem that the Goldstein's algorithm is incapable to be used at high residue densities.Therefore,it extends the application of the Goldstein's algorithm and enhances the precision of phase unwrapping.
Evolutionary Computation Algorithms for Cryptanalysis: A Study
Garg, Poonam
2010-01-01
The cryptanalysis of various cipher problems can be formulated as NP-Hard combinatorial problem. Solving such problems requires time and/or memory requirement which increases with the size of the problem. Techniques for solving combinatorial problems fall into two broad groups - exact algorithms and Evolutionary Computation algorithms. An exact algorithms guarantees that the optimal solution to the problem will be found. The exact algorithms like branch and bound, simplex method, brute force etc methodology is very inefficient for solving combinatorial problem because of their prohibitive complexity (time and memory requirement). The Evolutionary Computation algorithms are employed in an attempt to find an adequate solution to the problem. A Evolutionary Computation algorithm - Genetic algorithm, simulated annealing and tabu search were developed to provide a robust and efficient methodology for cryptanalysis. The aim of these techniques to find sufficient "good" solution efficiently with the characteristics ...
Cryptanalysis of an ergodic chaotic encryption algorithm
International Nuclear Information System (INIS)
In this paper, we present the results for the security and the possible attacks on a new symmetric key encryption algorithm based on the ergodicity property of a logistic map. After analysis, we use mathematical induction to prove that the algorithm can be attacked by a chosen plaintext attack successfully and give an example to show how to attack it. According to the cryptanalysis of the original algorithm, we improve the original algorithm, and make a brief cryptanalysis. Compared with the original algorithm, the improved algorithm is able to resist a chosen plaintext attack and retain a considerable number of advantages of the original algorithm such as encryption speed, sensitive dependence on the key, strong anti-attack capability, and so on. (general)
A Robust Parsing Algorithm For Link Grammars
Grinberg, D; Sleator, D; Grinberg, Dennis; Lafferty, John; Sleator, Daniel
1995-01-01
In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by making three dynamic programming passes. In the first pass, the input is parsed using the original algorithm which enforces the constraints on links to ensure grammaticality. In the second pass, the total cost of each substring of words is computed, where cost is determined by the number of null links necessary to parse the substring. The final pass counts the total number of parses with minimal cost. All of the original pruning techniques have natural counterparts in the robust algorithm. When used together with memoization...
Asynchronous Parallel Evolutionary Algorithms for Constrained Optimizations
Institute of Scientific and Technical Information of China (English)
无
2000-01-01
Recently Guo Tao proposed a stochastic search algorithm in his PhD thesis for solving function op-timization problems. He combined the subspace search method (a general multi-parent recombination strategy) with the population hill-climbing method. The former keeps a global search for overall situation,and the latter keeps the convergence of the algorithm. Guo's algorithm has many advantages ,such as the sim-plicity of its structure ,the higher accuracy of its results, the wide range of its applications ,and the robustness of its use. In this paper a preliminary theoretical analysis of the algorithm is given and some numerical experiments has been done by using Guo's algorithm for demonstrating the theoretical results. Three asynchronous paral-lel evolutionary algorithms with different granularities for MIMD machines are designed by parallelizing Guo's Algorithm.
A Hybrid Chaotic Quantum Evolutionary Algorithm
DEFF Research Database (Denmark)
Cai, Y.; Zhang, M.; Cai, H.
2010-01-01
A hybrid chaotic quantum evolutionary algorithm is proposed to reduce amount of computation, speed up convergence and restrain premature phenomena of quantum evolutionary algorithm. The proposed algorithm adopts the chaotic initialization method to generate initial population which will form...... a perfect distribution in feasible solution space in advantage of randomicity and non-repetitive ergodicity of chaos, the simple quantum rotation gate to update non-optimal individuals of population to reduce amount of computation, and the hybrid chaotic search strategy to speed up its convergence...... and enhance the global search ability. A large number of tests show that the proposed algorithm has higher convergence speed and better optimizing ability than quantum evolutionary algorithm, real-coded quantum evolutionary algorithm and hybrid quantum genetic algorithm. Tests also show that when chaos...
Role of Ranking Algorithms for Information Retrieval
Directory of Open Access Journals (Sweden)
Laxmi Choudhary
2012-07-01
Full Text Available As the use of web is increasing more day by day, the web users get easily lost in the web’s rich hyper structure. The main aim of the owner of the website is to give the relevant information according their needs to the users. We explained the Web mining is used to categorize users and pages by analyzing user’s behavior, the content of pages and then describe Web Structure mining. This paper includes different Page Ranking algorithms and compares those algorithms used for Information Retrieval. Different Page Rank based algorithms like Page Rank (PR, WPR (Weighted Page Rank, HITS (Hyperlink Induced Topic Selection, Distance Rank and EigenRumor algorithms are discussed and compared. Simulation Interface has been designed for PageRank algorithm and Weighted PageRank algorithm but PageRank is the only ranking algorithm on which Google search engine works.
Decryption of pure-position permutation algorithms
Institute of Scientific and Technical Information of China (English)
赵晓宇; 陈刚; 张亶; 王肖虹; 董光昌
2004-01-01
Pure position permutation image encryption algorithms,commonly used as image encryption investigated in this work are unfortunately frail under known-text attack.In view of the weakness of pure position permutation algorithm,we put forward an effective decryption algorithm for all pure-position permutation algorithms.First,a summary of the pure position permutation image encryption algorithms is given by introducing the concept of ergodic matrices.Then,by using probability theory and algebraic principles,the decryption probability of pure-position permutation algorithms is verified theoretically; and then,by defining the operation system of fuzzy ergodic matrices,we improve a specific decryption algorithm.Finally,some simulation results are shown.
Algorithms versus architectures for computational chemistry
Partridge, H.; Bauschlicher, C. W., Jr.
1986-01-01
The algorithms employed are computationally intensive and, as a result, increased performance (both algorithmic and architectural) is required to improve accuracy and to treat larger molecular systems. Several benchmark quantum chemistry codes are examined on a variety of architectures. While these codes are only a small portion of a typical quantum chemistry library, they illustrate many of the computationally intensive kernels and data manipulation requirements of some applications. Furthermore, understanding the performance of the existing algorithm on present and proposed supercomputers serves as a guide for future programs and algorithm development. The algorithms investigated are: (1) a sparse symmetric matrix vector product; (2) a four index integral transformation; and (3) the calculation of diatomic two electron Slater integrals. The vectorization strategies are examined for these algorithms for both the Cyber 205 and Cray XMP. In addition, multiprocessor implementations of the algorithms are looked at on the Cray XMP and on the MIT static data flow machine proposed by DENNIS.
Kernel method-based fuzzy clustering algorithm
Institute of Scientific and Technical Information of China (English)
Wu Zhongdong; Gao Xinbo; Xie Weixin; Yu Jianping
2005-01-01
The fuzzy C-means clustering algorithm(FCM) to the fuzzy kernel C-means clustering algorithm(FKCM) to effectively perform cluster analysis on the diversiform structures are extended, such as non-hyperspherical data, data with noise, data with mixture of heterogeneous cluster prototypes, asymmetric data, etc. Based on the Mercer kernel, FKCM clustering algorithm is derived from FCM algorithm united with kernel method. The results of experiments with the synthetic and real data show that the FKCM clustering algorithm is universality and can effectively unsupervised analyze datasets with variform structures in contrast to FCM algorithm. It is can be imagined that kernel-based clustering algorithm is one of important research direction of fuzzy clustering analysis.
Formal verification of a deadlock detection algorithm
Verbeek, Freek; 10.4204/EPTCS.70.8
2011-01-01
Deadlock detection is a challenging issue in the analysis and design of on-chip networks. We have designed an algorithm to detect deadlocks automatically in on-chip networks with wormhole switching. The algorithm has been specified and proven correct in ACL2. To enable a top-down proof methodology, some parts of the algorithm have been left unimplemented. For these parts, the ACL2 specification contains constrained functions introduced with defun-sk. We used single-threaded objects to represent the data structures used by the algorithm. In this paper, we present details on the proof of correctness of the algorithm. The process of formal verification was crucial to get the algorithm flawless. Our ultimate objective is to have an efficient executable, and formally proven correct implementation of the algorithm running in ACL2.
Microgenetic optimization algorithm for optimal wavefront shaping
Anderson, Benjamin R; Gunawidjaja, Ray; Eilers, Hergen
2015-01-01
One of the main limitations of utilizing optimal wavefront shaping in imaging and authentication applications is the slow speed of the optimization algorithms currently being used. To address this problem we develop a micro-genetic optimization algorithm ($\\mu$GA) for optimal wavefront shaping. We test the abilities of the $\\mu$GA and make comparisons to previous algorithms (iterative and simple-genetic) by using each algorithm to optimize transmission through an opaque medium. From our experiments we find that the $\\mu$GA is faster than both the iterative and simple-genetic algorithms and that both genetic algorithms are more resistant to noise and sample decoherence than the iterative algorithm.
Comparison of fast discrete wavelet transform algorithms
Institute of Scientific and Technical Information of China (English)
MENG Shu-ping; TIAN Feng-chun; XU Xin
2005-01-01
This paper presents an analysis on and experimental comparison of several typical fast algorithms for discrete wavelet transform (DWT) and their implementation in image compression, particularly the Mallat algorithm, FFT-based algorithm, Short-length based algorithm and Lifting algorithm. The principles, structures and computational complexity of these algorithms are explored in details respectively. The results of the experiments for comparison are consistent to those simulated by MATLAB. It is found that there are limitations in the implementation of DWT. Some algorithms are workable only for special wavelet transform, lacking in generality. Above all, the speed of wavelet transform, as the governing element to the speed of image processing, is in fact the retarding factor for real-time image processing.
Design and Implementation of Bidirectional Dijkstra Algorithm
Institute of Scientific and Technical Information of China (English)
付梦印; 李杰; 周培德
2003-01-01
Bidirectional Dijkstra algorithm whose time complexity is (1)/(8)O(n2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.
Direct Model Checking Matrix Algorithm
Institute of Scientific and Technical Information of China (English)
Zhi-Hong Tao; Hans Kleine Büning; Li-Fu Wang
2006-01-01
During the last decade, Model Checking has proven its efficacy and power in circuit design, network protocol analysis and bug hunting. Recent research on automatic verification has shown that no single model-checking technique has the edge over all others in all application areas. So, it is very difficult to determine which technique is the most suitable for a given model. It is thus sensible to apply different techniques to the same model. However, this is a very tedious and time-consuming task, for each algorithm uses its own description language. Applying Model Checking in software design and verification has been proved very difficult. Software architectures (SA) are engineering artifacts that provide high-level and abstract descriptions of complex software systems. In this paper a Direct Model Checking (DMC) method based on Kripke Structure and Matrix Algorithm is provided. Combined and integrated with domain specific software architecture description languages (ADLs), DMC can be used for computing consistency and other critical properties.
Multiservice Vertical Handoff Decision Algorithms
Directory of Open Access Journals (Sweden)
Zhu Fang
2006-01-01
Full Text Available Future wireless networks must be able to coordinate services within a diverse-network environment. One of the challenging problems for coordination is vertical handoff, which is the decision for a mobile node to handoff between different types of networks. While traditional handoff is based on received signal strength comparisons, vertical handoff must evaluate additional factors, such as monetary cost, offered services, network conditions, and user preferences. In this paper, several optimizations are proposed for the execution of vertical handoff decision algorithms, with the goal of maximizing the quality of service experienced by each user. First, the concept of policy-based handoffs is discussed. Then, a multiservice vertical handoff decision algorithm (MUSE-VDA and cost function are introduced to judge target networks based on a variety of user- and network-valued metrics. Finally, a performance analysis demonstrates that significant gains in the ability to satisfy user requests for multiple simultaneous services and a more efficient use of resources can be achieved from the MUSE-VDA optimizations.
The GRAPE aerosol retrieval algorithm
Directory of Open Access Journals (Sweden)
G. E. Thomas
2009-11-01
Full Text Available The aerosol component of the Oxford-Rutherford Aerosol and Cloud (ORAC combined cloud and aerosol retrieval scheme is described and the theoretical performance of the algorithm is analysed. ORAC is an optimal estimation retrieval scheme for deriving cloud and aerosol properties from measurements made by imaging satellite radiometers and, when applied to cloud free radiances, provides estimates of aerosol optical depth at a wavelength of 550 nm, aerosol effective radius and surface reflectance at 550 nm. The aerosol retrieval component of ORAC has several incarnations – this paper addresses the version which operates in conjunction with the cloud retrieval component of ORAC (described by Watts et al., 1998, as applied in producing the Global Retrieval of ATSR Cloud Parameters and Evaluation (GRAPE data-set.
The algorithm is described in detail and its performance examined. This includes a discussion of errors resulting from the formulation of the forward model, sensitivity of the retrieval to the measurements and a priori constraints, and errors resulting from assumptions made about the atmospheric/surface state.
Good covers are algorithmically unrecognizable
Tancer, Martin
2012-01-01
A good cover in R^d is a collection of open contractible sets in R^d such that the intersection of any subcollection is either contractible or empty. Motivated by an analogy with convex sets, intersection patterns of good covers were studied intensively. Our main result is that intersection patterns of good covers are algorithmically unrecognizable. More precisely, the intersection pattern of a good cover can be stored in a simplicial complex called nerve which records which subfamilies of the good cover intersect. A simplicial complex is topologically d-representable if it is isomorphic to the nerve of a good cover in R^d. We prove that it is algorithmically undecidable whether a given simplicial complex is topologically d-representable for any fixed d \\geq 5. As an auxiliary result we prove that if a simplicial complex is PL embeddable into R^d, then it is topologically d-representable. We also supply this result with showing that if a "sufficiently fine" subdivision of a k-dimensional complex is d-represen...
Novel algorithm for iris localization
Wang, Yunxin; Liu, Tiegen; Liu, Li
2007-11-01
With the emerging security demands, biometric identification technology has attracted more and more attention in recent years, and iris recognition is one of the most reliable biometric technologies. Iris localization is a crucial part in the iris recognition, which is quite time-consuming and easily disturbed by various noises, especially the eyelashes. A novel iris localization method is proposed in this paper. In the location of inner iris boundary, the gray curves of a row and a column with the pupil edge are used to estimate the coarse center and radius of pupil, which can reject the eyelash noises. The experiments show this coarse location method has better accuracy and speed than the common gray projection. Edge points of pupil are extracted by a gradient operator and fitted as the iris inner boundary. In the location of outer iris boundary, the image binarization is use to mark most noises, and then the outer iris boundary is extracted by integro-differential operator from the coarseness to fine. Performance experiments have been done, and the results show that about 0.175 second at speed and 99.5% at precision are reached by developed algorithm. In comparison with other classical methods, this algorithm has faster speed and better robustness.
Ligand Identification Scoring Algorithm (LISA)
Zheng, Zheng; Merz, Kenneth M.
2011-01-01
A central problem in de novo drug design is determining the binding affinity of a ligand with a receptor. A new scoring algorithm is presented that estimates the binding affinity of a protein-ligand complex given a three-dimensional structure. The method, LISA (Ligand Identification Scoring Algorithm), uses an empirical scoring function to describe the binding free energy. Interaction terms have been designed to account for van der Waals (VDW) contacts, hydrogen bonding, desolvation effects and metal chelation to model the dissociation equilibrium constants using a linear model. Atom types have been introduced to differentiate the parameters for VDW, H-bonding interactions and metal chelation between different atom pairs. A training set of 492 protein-ligand complexes was selected for the fitting process. Different test sets have been examined to evaluate its ability to predict experimentally measured binding affinities. By comparing with other well known scoring functions, the results show that LISA has advantages over many existing scoring functions in simulating protein-ligand binding affinity, especially metalloprotein-ligand binding affinity. Artificial Neural Network (ANN) was also used in order to demonstrate that the energy terms in LISA are well designed and do not require extra cross terms. PMID:21561101
The Aquarius Salinity Retrieval Algorithm
Meissner, Thomas; Wentz, Frank; Hilburn, Kyle; Lagerloef, Gary; Le Vine, David
2012-01-01
The first part of this presentation gives an overview over the Aquarius salinity retrieval algorithm. The instrument calibration [2] converts Aquarius radiometer counts into antenna temperatures (TA). The salinity retrieval algorithm converts those TA into brightness temperatures (TB) at a flat ocean surface. As a first step, contributions arising from the intrusion of solar, lunar and galactic radiation are subtracted. The antenna pattern correction (APC) removes the effects of cross-polarization contamination and spillover. The Aquarius radiometer measures the 3rd Stokes parameter in addition to vertical (v) and horizontal (h) polarizations, which allows for an easy removal of ionospheric Faraday rotation. The atmospheric absorption at L-band is almost entirely due to molecular oxygen, which can be calculated based on auxiliary input fields from numerical weather prediction models and then successively removed from the TB. The final step in the TA to TB conversion is the correction for the roughness of the sea surface due to wind, which is addressed in more detail in section 3. The TB of the flat ocean surface can now be matched to a salinity value using a surface emission model that is based on a model for the dielectric constant of sea water [3], [4] and an auxiliary field for the sea surface temperature. In the current processing only v-pol TB are used for this last step.
Region processing algorithm for HSTAMIDS
Ngan, Peter; Burke, Sean; Cresci, Roger; Wilson, Joseph N.; Gader, Paul; Ho, Dominic K. C.
2006-05-01
The AN/PSS-14 (a.k.a. HSTAMIDS) has been tested for its performance in South East Asia, Thailand), South Africa (Namibia) and in November of 2005 in South West Asia (Afghanistan). The system has been proven effective in manual demining particularly in discriminating indigenous, metallic artifacts in the minefields. The Humanitarian Demining Research and Development (HD R&D) Program has sought to further improve the system to address specific needs in several areas. One particular area of these improvement efforts is the development of a mine detection/discrimination improvement software algorithm called Region Processing (RP). RP is an innovative technique in processing and is designed to work on a set of data acquired in a unique sweep pattern over a region-of-interest (ROI). The RP team is a joint effort consisting of three universities (University of Florida, University of Missouri, and Duke University), but is currently being led by the University of Florida. This paper describes the state-of-the-art Region Processing algorithm, its implementation into the current HSTAMIDS system, and its most recent test results.
Digital Shaping Algorithms for GODDESS
Lonsdale, Sarah-Jane; Cizewski, Jolie; Ratkiewicz, Andrew; Pain, Steven
2014-09-01
Gammasphere-ORRUBA: Dual Detectors for Experimental Structure Studies (GODDESS) combines the highly segmented position-sensitive silicon strip detectors of ORRUBA with up to 110 Compton-suppressed HPGe detectors from Gammasphere, for high resolution for particle-gamma coincidence measurements. The signals from the silicon strip detectors have position-dependent rise times, and require different forms of pulse shaping for optimal position and energy resolutions. Traditionally, a compromise was achieved with a single shaping of the signals performed by conventional analog electronics. However, there are benefits to using digital acquisition of the detector signals, including the ability to apply multiple custom shaping algorithms to the same signal, each optimized for position and energy, in addition to providing a flexible triggering system, and a reduction in rate-limitation due to pile-up. Recent developments toward creating digital signal processing algorithms for GODDESS will be discussed. This work is supported in part by the U.S. D.O.E. and N.S.F.
A general algorithm for distributing information in a graph
Aji, Srinivas M.; McEliece, Robert J.
1997-01-01
We present a general “message-passing” algorithm for distributing information in a graph. This algorithm may help us to understand the approximate correctness of both the Gallager-Tanner-Wiberg algorithm, and the turbo-decoding algorithm.
Effects of visualization on algorithm comprehension
Mulvey, Matthew
Computer science students are expected to learn and apply a variety of core algorithms which are an essential part of the field. Any one of these algorithms by itself is not necessarily extremely complex, but remembering the large variety of algorithms and the differences between them is challenging. To address this challenge, we present a novel algorithm visualization tool designed to enhance students understanding of Dijkstra's algorithm by allowing them to discover the rules of the algorithm for themselves. It is hoped that a deeper understanding of the algorithm will help students correctly select, adapt and apply the appropriate algorithm when presented with a problem to solve, and that what is learned here will be applicable to the design of other visualization tools designed to teach different algorithms. Our visualization tool is currently in the prototype stage, and this thesis will discuss the pedagogical approach that informs its design, as well as the results of some initial usability testing. Finally, to clarify the direction for further development of the tool, four different variations of the prototype were implemented, and the instructional effectiveness of each was assessed by having a small sample participants use the different versions of the prototype and then take a quiz to assess their comprehension of the algorithm.
A GREEDY GENETIC ALGORITHM FOR UNCONSTRAINED GLOBAL OPTIMIZATION
Institute of Scientific and Technical Information of China (English)
ZHAO Xinchao
2005-01-01
The greedy algorithm is a strong local searching algorithm. The genetica lgorithm is generally applied to the global optimization problems. In this paper, we combine the greedy idea and the genetic algorithm to propose the greedy genetic algorithm which incorporates the global exploring ability of the genetic algorithm and the local convergent ability of the greedy algorithm. Experimental results show that greedy genetic algorithm gives much better results than the classical genetic algorithm.
Scheduling theory, algorithms, and systems
Pinedo, Michael L
2016-01-01
This new edition of the well-established text Scheduling: Theory, Algorithms, and Systems provides an up-to-date coverage of important theoretical models in the scheduling literature as well as important scheduling problems that appear in the real world. The accompanying website includes supplementary material in the form of slide-shows from industry as well as movies that show actual implementations of scheduling systems. The main structure of the book, as per previous editions, consists of three parts. The first part focuses on deterministic scheduling and the related combinatorial problems. The second part covers probabilistic scheduling models; in this part it is assumed that processing times and other problem data are random and not known in advance. The third part deals with scheduling in practice; it covers heuristics that are popular with practitioners and discusses system design and implementation issues. All three parts of this new edition have been revamped, streamlined, and extended. The reference...
Algorithm to Find Clique Graph
Directory of Open Access Journals (Sweden)
A. Ashok Kumar
2012-07-01
Full Text Available Let V = {1, 2, 3, …, n} be the vertex set of a graph G, ( (V the powerset of V and A ∈ V . Then (x1x2x3…xn where xi A can be represented as an ordered n-tuple = 1 if i ∈ A, otherwise xi = 0 (1≤ i ≤ n. This representation is called binary count (or BC representation of a set A and denoted as BC(A. Given a graph G of order n, every integer m in S = {0, 1, 2, …, 2n -1} corresponds to a subset A of V and vice versa. In this paper we introduce and discuss a sequential algorithm to find the clique graph K(G of a graph G using the BC representation.
Algorithm project weight calculation aircraft
Directory of Open Access Journals (Sweden)
Г. В. Абрамова
2013-07-01
Full Text Available The paper describes the process of a complex technical object design on the example of the aircraft, using information technology such as CAD/CAM/CAE-systems, presents the basic models of aircraft which are developed in the process of designing and reflect the different aspects of its structure and function. The idea of control parametric model at complex technical object design is entered, which is a set of initial data for the development of design stations and enables the optimal complex technical object control at all stages of design using modern computer technology. The paper discloses a process of weight design, which is associated with all stages of development aircraft and its production. Usage of a scheduling algorithm that allows to organize weight calculations are carried out at various stages of planning and weighing options to optimize the use of available database of formulas and methods of calculation
Biomimetic use of genetic algorithms
Dessalles, Jean-Louis
2011-01-01
Genetic algorithms are considered as an original way to solve problems, probably because of their generality and of their "blind" nature. But GAs are also unusual since the features of many implementations (among all that could be thought of) are principally led by the biological metaphor, while efficiency measurements intervene only afterwards. We propose here to examine the relevance of these biomimetic aspects, by pointing out some fundamental similarities and divergences between GAs and the genome of living beings shaped by natural selection. One of the main differences comes from the fact that GAs rely principally on the so-called implicit parallelism, while giving to the mutation/selection mechanism the second role. Such differences could suggest new ways of employing GAs on complex problems, using complex codings and starting from nearly homogeneous populations.
Algorithms for Comparing Pedigree Graphs
Kirkpatrick, Bonnie; Finucane, Hilary; Jiang, Haitao; Zhu, Binhai; Karp, Richard M
2010-01-01
Pedigree graphs, which represent family relationships, are often constructed by collecting data from genealogical records to determine which pairs of people are parent and child. This process is expensive, and small mistakes in data collection--for example, one missing parent-child relationship--can cause large differences in the pedigree graphs created. In this paper, we introduce a simple pedigree definition based on a different type of data which is potentially easier to collect. This alternative characterization of a pedigree that describes a pedigree as a list of the descendants of each individual, rather than a list of parent-child relationships. We then introduce an algorithm that generates the pedigree graph from this list of descendants. We also consider the problem of comparing two pedigree graphs, which could be useful to evaluate the differences between pedigrees constructed via different methods. Specifically, this could be useful to evaluate pedigree reconstruction methods. We define the edit di...
Virtual Crystals and Kleber's Algorithm
Okado, Masato; Schilling, Anne; Shimozono, Mark
Kirillov and Reshetikhin conjectured what is now known as the fermionic formula for the decomposition of tensor products of certain finite dimensional modules over quantum affine algebras. This formula can also be extended to the case of q-deformations of tensor product multiplicities as recently conjectured by Hatayama et al. In its original formulation it is difficult to compute the fermionic formula efficiently. Kleber found an algorithm for the simply-laced algebras which overcomes this problem. We present a method which reduces all other cases to the simply-laced case using embeddings of affine algebras. This is the fermionic analogue of the virtual crystal construction by the authors, which is the realization of crystal graphs for arbitrary quantum affine algebras in terms of those of simply-laced type.
Anaphora Resolution Algorithm for Sanskrit
Pralayankar, Pravin; Devi, Sobha Lalitha
This paper presents an algorithm, which identifies different types of pronominal and its antecedents in Sanskrit, an Indo-European language. The computational grammar implemented here uses very familiar concepts such as clause, subject, object etc., which are identified with the help of morphological information and concepts such as precede and follow. It is well known that natural languages contain anaphoric expressions, gaps and elliptical constructions of various kinds and that understanding of natural languages involves assignment of interpretations to these elements. Therefore, it is only to be expected that natural language understanding systems must have the necessary mechanism to resolve the same. The method we adopt here for resolving the anaphors is by exploiting the morphological richness of the language. The system is giving encouraging results when tested with a small corpus.
Stream Deniable-Encryption Algorithms
Directory of Open Access Journals (Sweden)
N.A. Moldovyan
2016-04-01
Full Text Available A method for stream deniable encryption of secret message is proposed, which is computationally indistinguishable from the probabilistic encryption of some fake message. The method uses generation of two key streams with some secure block cipher. One of the key streams is generated depending on the secret key and the other one is generated depending on the fake key. The key streams are mixed with the secret and fake data streams so that the output ciphertext looks like the ciphertext produced by some probabilistic encryption algorithm applied to the fake message, while using the fake key. When the receiver or/and sender of the ciphertext are coerced to open the encryption key and the source message, they open the fake key and the fake message. To disclose their lie the coercer should demonstrate possibility of the alternative decryption of the ciphertext, however this is a computationally hard problem.
Parallel External Memory Graph Algorithms
DEFF Research Database (Denmark)
Arge, Lars Allan; Goodrich, Michael T.; Sitchinava, Nodari
2010-01-01
In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one o f the private-cache chip multiprocessor (CMP) models. We study the fundamental problem of list ranking which leads to efficient solutions to problems on trees, such as computing lowest...... an optimal speedup of Â¿(P) in parallel I/O complexity and parallel computation time, compared to the single-processor external memory counterparts....... common ancestors, tree contraction and expression tree evaluation. We also study the problems of computing the connected and biconnected components of a graph, minimum spanning tree of a connected graph and ear decomposition of a biconnected graph. All our solutions on a P-processor PEM model provide...
Algorithmic synthesis using Python compiler
Cieszewski, Radoslaw; Romaniuk, Ryszard; Pozniak, Krzysztof; Linczuk, Maciej
2015-09-01
This paper presents a python to VHDL compiler. The compiler interprets an algorithmic description of a desired behavior written in Python and translate it to VHDL. FPGA combines many benefits of both software and ASIC implementations. Like software, the programmed circuit is flexible, and can be reconfigured over the lifetime of the system. FPGAs have the potential to achieve far greater performance than software as a result of bypassing the fetch-decode-execute operations of traditional processors, and possibly exploiting a greater level of parallelism. This can be achieved by using many computational resources at the same time. Creating parallel programs implemented in FPGAs in pure HDL is difficult and time consuming. Using higher level of abstraction and High-Level Synthesis compiler implementation time can be reduced. The compiler has been implemented using the Python language. This article describes design, implementation and results of created tools.
RED Algorithm based Iris Recognition
Directory of Open Access Journals (Sweden)
Mayuri M. Memane
2012-07-01
Full Text Available Human iris is one of the most reliable biometric because of its uniqueness, stability and non-invasive nature. Biometrics based human authentication systems are becoming more important as government & corporations worldwide deploy them in such schemes as access & border control, time & attendance record, driving license registration and national ID card schemes. For this various preprocessing steps are carried out on the iris image which also includes segmentation. Normalization deals with polar to rectangular conversion. The edges are detected using canny edge detector. Features are extracted using ridge energy direction algorithm. It uses two directional filters i.e. horizontal and vertical oriented. The final template is generated by comparing the two templates and considering the predominant edge. This final template is match with the stored one using hamming distance and the match ID is displayed.
Hierarchical matrices algorithms and analysis
Hackbusch, Wolfgang
2015-01-01
This self-contained monograph presents matrix algorithms and their analysis. The new technique enables not only the solution of linear systems but also the approximation of matrix functions, e.g., the matrix exponential. Other applications include the solution of matrix equations, e.g., the Lyapunov or Riccati equation. The required mathematical background can be found in the appendix. The numerical treatment of fully populated large-scale matrices is usually rather costly. However, the technique of hierarchical matrices makes it possible to store matrices and to perform matrix operations approximately with almost linear cost and a controllable degree of approximation error. For important classes of matrices, the computational cost increases only logarithmically with the approximation error. The operations provided include the matrix inversion and LU decomposition. Since large-scale linear algebra problems are standard in scientific computing, the subject of hierarchical matrices is of interest to scientists ...
Nakayama, Hiromasa
2006-01-01
We give an algorithm to compute the local $b$ function. In this algorithm, we use the Mora division algorithm in the ring of differential operators and an approximate division algorithm in the ring of differential operators with power series coefficient.
A Quantum Algorithm for Finding a Hamilton Circuit
Institute of Scientific and Technical Information of China (English)
GUO Hao; LONG Gui-Lu; SUN Yang; XIU Xiao-Lin
2001-01-01
A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.
Algebraic Reconstruction Algorithm of Vapor Tomography
Directory of Open Access Journals (Sweden)
HE Lin
2015-01-01
Full Text Available While applying algebraic reconstruction algorithm in vapor tomography, problems have to be solved with respect to constructing the constraint condition, selecting the initial value, calculating optimal relaxation factor and deciding the iteration termination condition. Golden section search method and NCP termination rule are given to solve the latter two problems, respectively. Eight algebraic reconstruction algorithms, including Kaczmarz, Randkaczmarz, Symkaczmarz, SART, Landweber, Cimmino, CAV and DROP algorithm, are comparatively analyzed and tested by the data from SatRef station in Hong Kong. The results show that all the eight algorithms can satisfy the requirements of vapor tomography and the iteration termination condition is more important than the relaxation condition. While the golden section method and NCP method are used, the CAV algorithm performs best, and then the Cimmino algorithm.
Runtime support for parallelizing data mining algorithms
Jin, Ruoming; Agrawal, Gagan
2002-03-01
With recent technological advances, shared memory parallel machines have become more scalable, and offer large main memories and high bus bandwidths. They are emerging as good platforms for data warehousing and data mining. In this paper, we focus on shared memory parallelization of data mining algorithms. We have developed a series of techniques for parallelization of data mining algorithms, including full replication, full locking, fixed locking, optimized full locking, and cache-sensitive locking. Unlike previous work on shared memory parallelization of specific data mining algorithms, all of our techniques apply to a large number of common data mining algorithms. In addition, we propose a reduction-object based interface for specifying a data mining algorithm. We show how our runtime system can apply any of the technique we have developed starting from a common specification of the algorithm.
HUMAN-SIMULATING VEHICLE STEERING CONTROL ALGORITHM
Institute of Scientific and Technical Information of China (English)
XU Youchun; LI Keqiang; CHANG Ming; CHEN Jun
2006-01-01
A new vehicle steering control algorithm is presented. Unlike the traditional methods do,the algorithm uses a sigmoid function to describe the principle of the human driver's steering strategy.Based on this function, a human simulating vehicle steering model, human-simulating steering control(HS) algorithm is designed. In order to improve the adaptability to different environments, a parameter adaptive adjustment algorithm is presented. This algorithm can online modify the value of the key parameters of the HS real time. HS controller is used on a vehicle equipped with computer vision system and computer controlled steering actuator system, the result from the automatic vehicle steering experiment shows that the HS algorithm gives good performance at different speed, even at the maximum speed of 172 km/h.
Fast algorithm on string cross pattern matching
Institute of Scientific and Technical Information of China (English)
Liu Gongshen; Li Jianhua; Li Shenghong
2005-01-01
Given a set U which is consisted of strings defined on alphabet ∑ , string cross pattern matching is to find all the matches between every two strings in U. It is utilized in text processing like removing the duplication of strings.This paper presents a fast string cross pattern matching algorithm based on extracting high frequency strings. Compared with existing algorithms including single-pattern algorithms and multi-pattern matching algorithms, this algorithm is featured by both low time complexityand low space complexity. Because Chinese alphabet is large and the average length of Chinese words is much short, this algorithm is more suitable to process the text written by Chinese, especially when the size of ∑ is large and the number of strings is far more than the maximum length of strings of set U.
Calculating Unknown Eigenvalues with a Quantum Algorithm
Zhou, Xiao-Qi; Ralph, Timothy C; O'Brien, Jeremy L
2011-01-01
Quantum algorithms are able to solve particular problems exponentially faster than conventional algorithms, when implemented on a quantum computer. However, all demonstrations to date have required already knowing the answer to construct the algorithm. We have implemented the complete quantum phase estimation algorithm for a single qubit unitary in which the answer is calculated by the algorithm. We use a new approach to implementing the controlled-unitary operations that lie at the heart of the majority of quantum algorithms that is more efficient and does not require the eigenvalues of the unitary to be known. These results point the way to efficient quantum simulations and quantum metrology applications in the near term, and to factoring large numbers in the longer term. This approach is architecture independent and thus can be used in other physical implementations.
Multicast Routing Based on Hybrid Genetic Algorithm
Institute of Scientific and Technical Information of China (English)
CAO Yuan-da; CAI Gui
2005-01-01
A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.
EPS Confidentiality and Integrity mechanisms Algorithmic Approach
Orhanou, Ghizlane; Bentaleb, Youssef; Laassiri, Jalal
2011-01-01
The Long Term Evolution of UMTS is one of the latest steps in an advancing series of mobile telecommunications systems. Many articles have already been published on the LTE subject but these publications have viewed the subject from particular perspectives. In the present paper, a different approach has been taken. We are interested in the security features and the cryptographic algorithms used to ensure confidentiality and integrity of the transmitted data. A closer look is taken to the two EPS confidentiality and integrity algorithms based on the block cipher algorithm AES: the confidentiality algorithm EEA2 and the integrity algorithm EIA2. Furthermore, we focused on the implementation of both algorithms in C language in respect to the specifications requirements. We have tested our implementations according to the testsets given by the 3rd Generation Partnership Project (3GPP) implementation document. Some examples of the implementation tests are presented bellow.
New algorithms for evaluating parametric surface
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
Through generalization of mathematical model of surface lofting program in the CONSURF system, the definitions for two generalized Ball surfaces and their recursive algorithms are given. Furthermore, the conversion al gorithms from Bézier surface to these two generalized Ball surfaces are presented. On the basis of these algorithms, two more efficient algorithms for evaluating parametric surfaces are also derived. One uses generalized Ball forms directly for evaluating surface, and the other converts the given Bézier surface to a generalized Ball surface firstly, and then evalu ates the surface. Both theoretical analysis and example computations show that the two new algorithms are more efficient than the de Casteljau algorithm. Especially when Wang-Ball surface is used, the time complexity is reduced from cubic to quadratic of the degree of the surface. If these algorithms are applied to displaying, interactive rendering, designing, intersection-finding, offsetting and approximating for surfaces, considerable economic results can be achieved.
Genetic algorithms and fuzzy multiobjective optimization
Sakawa, Masatoshi
2002-01-01
Since the introduction of genetic algorithms in the 1970s, an enormous number of articles together with several significant monographs and books have been published on this methodology. As a result, genetic algorithms have made a major contribution to optimization, adaptation, and learning in a wide variety of unexpected fields. Over the years, many excellent books in genetic algorithm optimization have been published; however, they focus mainly on single-objective discrete or other hard optimization problems under certainty. There appears to be no book that is designed to present genetic algorithms for solving not only single-objective but also fuzzy and multiobjective optimization problems in a unified way. Genetic Algorithms And Fuzzy Multiobjective Optimization introduces the latest advances in the field of genetic algorithm optimization for 0-1 programming, integer programming, nonconvex programming, and job-shop scheduling problems under multiobjectiveness and fuzziness. In addition, the book treats a w...
Detecting Danger: The Dendritic Cell Algorithm
Greensmith, Julie; Cayzer, Steve
2010-01-01
The Dendritic Cell Algorithm (DCA) is inspired by the function of the dendritic cells of the human immune system. In nature, dendritic cells are the intrusion detection agents of the human body, policing the tissue and organs for potential invaders in the form of pathogens. In this research, and abstract model of DC behaviour is developed and subsequently used to form an algorithm, the DCA. The abstraction process was facilitated through close collaboration with laboratory- based immunologists, who performed bespoke experiments, the results of which are used as an integral part of this algorithm. The DCA is a population based algorithm, with each agent in the system represented as an 'artificial DC'. Each DC has the ability to combine multiple data streams and can add context to data suspected as anomalous. In this chapter the abstraction process and details of the resultant algorithm are given. The algorithm is applied to numerous intrusion detection problems in computer security including the detection of p...
Adaptive link selection algorithms for distributed estimation
Xu, Songcen; de Lamare, Rodrigo C.; Poor, H. Vincent
2015-12-01
This paper presents adaptive link selection algorithms for distributed estimation and considers their application to wireless sensor networks and smart grids. In particular, exhaustive search-based least mean squares (LMS) / recursive least squares (RLS) link selection algorithms and sparsity-inspired LMS / RLS link selection algorithms that can exploit the topology of networks with poor-quality links are considered. The proposed link selection algorithms are then analyzed in terms of their stability, steady-state, and tracking performance and computational complexity. In comparison with the existing centralized or distributed estimation strategies, the key features of the proposed algorithms are as follows: (1) more accurate estimates and faster convergence speed can be obtained and (2) the network is equipped with the ability of link selection that can circumvent link failures and improve the estimation performance. The performance of the proposed algorithms for distributed estimation is illustrated via simulations in applications of wireless sensor networks and smart grids.
State transition algorithm for traveling salesman problem
Chunhua, Yang; Xiaojun, Zhou; Weihua, Gui
2012-01-01
Discrete version of state transition algorithm is proposed in order to solve the traveling salesman problem. Three special operators for discrete optimization problem named swap, shift and symmetry transformations are presented. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm simple and efficient, no parameter adjusting is suggested in current version. Experiments are carried out to test the performance of the strategy, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than its counterparts, which indicates that state transition algorithm is with strong adaptability.
A novel algorithm for satellite data transmission
Institute of Scientific and Technical Information of China (English)
ZHANG ShouJuan; ZHOU Ouan
2009-01-01
For remote sensing satellite data transmission, a novel algorithm is proposed in this paper. It integrates different type feature descriptors into multistage recognizers. In the first level, the dynamic clustering algorithm is used. In the second level, the improved support vector machines algorithm demonstrates its validity. In the third level, the shape matrices similarity comparison algorithm shows its excellent performance. The single child recognizers are connected in series, but they are independent of each other. Objects which are not recognized correctly by the lower level recognizers are then put into the higher level recognizers. Experimental results show that the multistage recognition algorithm improves the accuracy greatly with higher level feature descriptors and higher level recognizers. The algorithm may offer a new methodology for high speed satellite data transmission.