检索结果-内蒙古大学图书馆

6th International Conference on Automation, Robotics and Applications (ICARA)

作者： Ghosh, Tushar K. Nguyen, Luong A. Quiocho, Leslie J. Natl Secur Solut Commun L 3 Houston TX 77058 USA NASA Software Robot & Simulat Div Johnson Space Ctr Houston TX USA

ISBN: (纸本)9781479964666

This paper describes a multibody dynamics algorithm formulated for parallel implementation on multiprocessor computing platforms using the divide-and-conquer approach. The system of interest is a general topology of rigid and elastic articulated bodies with or without loops. The algorithm divides the multibody system into a number of smaller sets of bodies in chain or tree structures, called "branches" at convenient joints called "connection points", and uses an Order-N (O (N)) approach to formulate the dynamics of each branch in terms of the unknown spatial connection forces. The equations of motion for the branches, leaving the connection forces as unknowns, are implemented in separate processors in parallel for computational efficiency, and the equations for all the unknown connection forces are synthesized and solved in one or several processors. The performances of two implementations of this divide-and-conquer algorithm in multiple processors are compared with an existing method implemented on a single processor.

关键词： Multibody dynamics multiple processors divide-and-conquer algorithm computational efficiency Order-N

来源：评论

学校读者我要写书评

暂无评论

divide-and-conquer algorithms for Partitioning Hypergraphs and Submodular Systems

引用

algorithmICA 2012年第3-4期62卷 787-806页

作者： Okumoto, Kazumasa Fukunaga, Takuro Nagamochi, Hiroshi Univ Tokyo Grad Sch Econ Tokyo 1130033 Japan Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V (1),V (2),aEuro broken vertical bar,V (k) so that E-i=1(k) f(V-i) is minimized where f is a non-negative submodular function on V. In this paper, we design an approximation algorithm for the problem with fixed k. We also analyze the approximation factor of our algorithm for the hypergraph k-cut problem, which is a problem contained by the submodular system k-partition problem.

关键词： divide-and-conquer algorithm Hypergraph Multicut Submodular function

来源：评论

学校读者我要写书评

暂无评论

Model transitions and optimization problem in multi-flexible-body systems: Application to modeling molecular systems

引用

COMPUTER PHYSICS COMMUNICATIONS 2013年第7期184卷 1717-1728页

作者： Khan, I. M. Poursina, M. Anderson, K. S. Rensselaer Polytech Inst Dept Mech Aerosp & Nucl Engn Computat Dynam Lab Troy NY 12180 USA

This paper presents an efficient algorithm for the simulation of multi-flexible-body systems undergoing discontinuous changes in model definition. The equations governing the dynamics of the transitions from a higher to a lower fidelity model and vice versa are formulated through imposing/removing certain constraints on/from the system model. The issue of the non-uniqueness of the results associated with the transition from a lower to a higher fidelity model may be handled by solving an optimization problem. This optimization problem is subjected to the satisfaction of the constraint imposed by the generalized impulse-momentum equations. The divide-and-conquer algorithm (DCA) is applied to formulate the jumps in the system states resulting from the model transition. The DCA formulation in its basic form is both time and processor optimal and results in linear and logarithmic complexity when implemented in serial and parallel with O(n) processors, respectively. As such, its application can reduce the effective computational cost of formulating and solving the optimization problem in the transitions to the finer models. The principal aspects of the mathematics for the algorithm implementation is developed and numerical examples are provided to validate the method. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Multi-flexible-body dynamics Model transitions divide-and-conquer algorithm Molecular dynamics Adaptive simulations

来源：评论

学校读者我要写书评

暂无评论

A logarithmic complexity floating frame of reference formulation with interpolating splines for articulated multi-flexible-body dynamics

引用

INTERNATIONAL JOURNAL OF NON-LINEAR MECHANICS 2013年 57卷 146-153页

作者： Khan, I. M. Ahn, W. Anderson, K. S. De, S. Rensselaer Polytech Inst Dept Mech Aerosp & Nucl Engn Computat Dynam Lab Troy NY 12180 USA Rensselaer Polytech Inst Dept Mech Aerosp & Nucl Engn Ctr Modeling Simulat & Imaging Med Troy NY 12180 USA

An interpolating spline-based approach is presented for modeling multi-flexible-body systems in the divide-and-conquer (DCA) scheme. This algorithm uses the floating frame of reference formulation and piecewise spline functions to construct and solve the non-linear equations of motion of the multi-flexible-body system undergoing large rotations and translations. The new approach is compared with the flexible DCA (FDCA) that uses the assumed modes method [1]. The FDCA, in many cases, must resort to sub-structuring to accurately model the deformation of the system. We demonstrate, through numerical examples, that the interpolating spline-based approach is comparable in accuracy and superior in efficiency to the FDCA. The present approach is appropriate for modeling flexible mechanisms with thin 1D bodies undergoing large rotations and translations, including those with irregular shapes. As such, the present approach extends the current capability of the DCA to model deformable systems. The algorithm retains the theoretical logarithmic complexity inherent in the DCA when implemented in parallel. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Multi-flexible-body systems Logarithmic complexity divide-and-conquer algorithm Interpolating splines

来源：评论

学校读者我要写书评

暂无评论

Fast Construction of Assembly Trees for Molecular Graphs

引用

JOURNAL OF COMPUTATIONAL CHEMISTRY 2011年第8期32卷 1589-1598页

作者： Artemova, Svetlana Grudinin, Sergei Redon, Stephane INRIA Grenoble Rhone Alpes Res Ctr NANO D F-38334 Saint Ismier Montbonnot France Lab Jean Kuntzmann F-38041 Grenoble 9 France

A number of modeling and simulation algorithms using internal coordinates rely on hierarchical representations of molecular systems. Given the potentially complex topologies of molecular systems, though, automatically generating such hierarchical decompositions may be difficult. In this article, we present a fast general algorithm for the complete construction of a hierarchical representation of a molecular system. This two-step algorithm treats the input molecular system as a graph in which vertices represent atoms or pseudo-atoms, and edges represent covalent bonds. The first step contracts all cycles in the input graph. The second step builds an assembly tree from the reduced graph. We analyze the complexity of this algorithm and show that the first step is linear in the number of edges in the input graph, whereas the second one is linear in the number of edges in the graph without cycles, but dependent on the branching factor of the molecular graph. We demonstrate the performance of our algorithm on a set of specifically tailored difficult cases as well as on a large subset of molecular graphs extracted from the protein data bank. In particular, we experimentally show that both steps behave linearly in the number of edges in the input graph (the branching factor is fixed for the second step). Finally, we demonstrate an application of our hierarchy construction algorithm to adaptive torsion-angle molecular mechanics. (C) 2011 Wiley Periodicals, Inc. J Comput Chem 32: 1589-1598, 2011

关键词： assembly tree divide-and-conquer algorithm adaptive algorithm molecular graphs molecular simulations internal coordinates

来源：评论

学校读者我要写书评

暂无评论

Fast calculation approach to semi-empirical molecular orbital method using real space division method

引用

COMPUTATIONAL MATERIALS SCIENCE 2011年第12期50卷 3346-3349页

作者： Igarashi, Takahiro Nakazawa, Tetsuya Suzuki, Chikashi Tsuru, Tomohito Kaji, Yoshiyuki Japan Atom Energy Agcy Tokai Ibaraki 3191195 Japan

The authors have developed a new approach for large-scale systems including over 100,000 atoms to obtain physical strength from the viewpoint of atom-atom bonding energy. Combining the semi-empirical molecular orbital method with real space division method makes it possible to estimate structural parameters, electronic structures and bonding energy for various large systems. With this method, various quantum physical properties can be obtained quickly using the semi-empirical molecular orbital method, while adopting real space division improves the computational efficiency of parallelization. In this study, the authors applied this method to SiH4 molecule and crystalline silica system, and carried out bond order and bonding energy analyses. In this analysis, the developed method offered almost the same analytical accuracy as the first principle method, while its calculation speed was much faster than that of the latter. The developed method was also suitable for parallel computing. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Semi-empirical molecular orbital method divide-and-conquer algorithm Parallel computing Large-scale quantum calculation Crystalline silica cluster Bonding energy

来源：评论

学校读者我要写书评

暂无评论

divide-and-conquer algorithm for ClustalW-MPI

Divide-and-conquer algorithm for ClustalW-MPI

引用

19th IEEE Canadian Conference on Electrical and Computer Engineering

作者： Rezaei, Siamak Monwar, Md. Maruf Univ Northern British Columbia Prince George BC V2L 5P2 Canada

ISBN: (纸本)9781424400379

Multiple sequence alignment continues to be an active field of research in Computational Biology and the most widely used tool for multiple sequence alignment is ClustalW, which achieves alignment via three steps: pair wise alignment, guide tree generation and progressive alignment. ClustalW-MPI is a parallel implementation of ClustalW. In this paper, a new approach, divide-and-conquer, is implemented which uses ClustalW-MPI for sequence alignment but it gets a better speed up performance than ClustalW-MPI. In this approach, the sequences are first cut down into smaller subsequences by divide-and-conquer technique to minimize the computational space. Then these subsequences are sent to different available processors using Message Passing Interface technique. Those processors align the subsequences by executing ClustalW-MPI simultaneously. After aligning, the results are then sent to the main processor to be concatenated to produce the final alignment. But some quality of the alignment may be compromised in this approach for the introduction of gaps at the start or end of subsequences aligned. Therefore, some heuristic methods for fixing the cut points were suggested for future improvement, such as overlapping alignment and sliding window alignment.

关键词： multiple sequence alignment message passing interface divide-and-conquer algorithm multiple tree alignment

来源：评论

学校读者我要写书评

暂无评论

Factors affecting the performance of parallel mining of minimal unique itemsets on diverse architectures

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2009年第9期21卷 1131-1158页

作者： Haglin, D. J. Mayes, K. R. Manning, A. M. Feo, J. Gurd, J. R. Elliot, M. Keane, J. A. Mankato State Univ Dept Comp Sci Mankato MN 56001 USA Univ Manchester Sch Comp Sci Manchester M13 9PL Lancs England Cray Res Inc Seattle WA 98104 USA Univ Manchester Sch Social Sci Cathie Marsh Ctr Census & Survey Res Manchester M13 9PL Lancs England

Three parallel implementations of a divide-and-conquer search algorithm (called SUDA2) for finding minimal unique itemsets (MUIs) are compared in this paper. The identification of MUIs is used by national statistics agencies for statistical disclosure assessment. The first parallel implementation adapts SUDA2 to a symmetric multi-processor cluster using the message passing interface (MPI), which we call an MPI cluster;the second optimizes the code for the Cray MTA2 (a shared-memory, multi-threaded architecture) and the third uses a heterogeneous 'group' of workstations connected by LAN. Each implementation considers the parallel structure of SUDA2, and how the subsearch computation times and sequence of subsearches affect load balancing. All three approaches scale with the number of processors, enabling SUDA2 to handle larger problems than before. For example, the MPT implementation is able to achieve nearly two orders of magnitude improvement with 132 processors. Performance results are given for a number of data sets. Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： performance itemset mining divide-and-conquer algorithm load balancing parallel architecture

来源：评论

学校读者我要写书评

暂无评论

Competitive graph searches

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期393卷 72-80页

作者： Bui-Xuan, Binh-Minh Habib, Michel Paul, Christophe Univ Montpellier 2 CNRS LIRMM F-34392 Montpellier 5 France Univ Paris Diderot LIAFA CNRS F-75251 Paris 05 France

We exemplify an optimization criterion for divide-and-conquer algorithms with a technique called generic competitive graph search. The technique is then applied to solve two problems arising from biocomputing, so-called Common Connected Components and Cograph Sandwich. The first problem can be defined as follows: given two graphs on the same set of n vertices, find the coarsest partition of the vertex set into subsets which induce connected subgraphs in both input graphs. The second problem is an instance of sandwich problems: given a partial subgraph G(1) of G(2), find a partial subgraph G of G(2) that is partial supergraph of G(1) (sandwich), and that is a cograph. For the former problem our generic algorithm not only achieves the current best known performance on arbitrary graphs and forests, but also improves by a log it factor when the input is made of planar graphs. However, our complexity for intervals graphs is slightly lower than a recent result. For the latter problem, we first study the relationship between the common connected components problem and the cograph sandwich problem, then, using our competitive graph search paradigm, we improve the computation of cograph sandwiches from O(n (n + m)) down to O(n + m log(2) n), where n is the number of vertices and m of total edges. (C) 2007 Elsevier B.V. All rights reserved.

关键词： graph search divide-and-conquer algorithm common connected graph component sandwich graph problem

来源：评论

学校读者我要写书评

暂无评论

Fixed parameter algorithms for the minimum weight triangulation problem

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2008年第3期18卷 185-220页

作者： Borgelt, Magdalene Grantson Borgelt, Christian Levcopoulos, Christos Dept Informat & Comp Sci NL-3508 TA Utrecht Netherlands European Ctr Soft Comp Mieres 33600 Spain Lund Univ Dept Comp Sci S-221 Lund Sweden

We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n - k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation.

关键词： minimum weight triangulation fixed parameter algorithm dynamic programming divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：