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

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 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

来源：评论

学校读者我要写书评

暂无评论

Separators in graphs with negative and multiple vertex weights

引用

algorithmICA 1999年第1期23卷 57-71页

作者： Djidjev, HN Gilbert, JR Rice Univ Dept Comp Sci Houston TX 77005 USA Xerox Corp Palo Alto Res Ctr Palo Alto CA 94304 USA

A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems hold for several classes of graphs, including graphs of bounded genus and chordal graphs. We show that any separator theorem implies Various weighted separator theorems. In particular, we show that if the vertices of the graph have real-valued weights, which may be positive or negative, then the graph can be divided exactly in half according to weight. If k unrelated sets of weights are given, the graph can be divided simultaneously by all k sets of weights. These results considerably strengthen earlier results of Gilbert, Lipton, and Tarjan: (1) for k = 1 with the weights restricted to being nonnegative, and (2) for k > 1, nonnegative weights, and simultaneous division within a factor of (1 + epsilon) of exactly in half.

关键词： graph separator cutset divide-and-conquer algorithm separator theorem graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for constructing knight's tours on arbitrary nxm chessboards

引用

DISCRETE APPLIED MATHEMATICS 2005年第3期146卷 219-232页

作者： Lin, SS Wei, CL Natl Taiwan Normal Univ Grad Inst Comp Sci & Informat Engn Taipei Taiwan Natl Taiwan Normal Univ Dept Informat & Comp Educ Taipei Taiwan

The knight's tour problem is an ancient puzzle whose goal is to find out how to construct a series of legal moves made by a knight so that it visits every square of a chessboard exactly once. In previous works. researchers have partially solved this problem by offering algorithms for subsets of chessboards. For example, among prior studies, Parberry proposed a divided-and-conquer algorithm that can build a closed knight's tour on an n x n, an n x (n + 1) or an n x (n + 2) chessboard in O(n(2)) (i.e.. linear in area) time on a sequential processor. In this paper we completely solve this problem by presenting new methods that can construct a closed knight's tour or an open knight's tour on an arbitrary n x in chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor. (C) 2004 Elsevier B.V. All rights reserved.

关键词： divide-and-conquer algorithm knight's tour problem optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

On Kemeny's constant and stochastic complement

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2024年 703卷 137-162页

作者： Bini, Dario Andrea Durastante, Fabio Kim, Sooyeong Meini, Beatrice Univ Pisa Math Dept Largo Bruno Pontecorvo 5 I-56127 Pisa PI Italy York Univ Dept Math & Stat 4700 Keele St Toronto ON M3J 1P3 Canada

Given a stochastic matrix P partitioned in four blocks P-ij, i, j = 1, 2, Kemeny's constant kappa(P) is expressed in terms of Kemeny's constants of the stochastic complements P-1 = P(1)1+ P-12(I-P-22)-1P(21), and P-2 = P-22+P-21(I-P-11)-1P(12). Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real world problems show the high efficiency and reliability of this algorithm. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

关键词： Markov chains Kemeny's constant divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

Systematic enumeration of two-dimensional layered aluminophosphates with [Al₃P₄O₁₆]^3- stoichiometry

引用

COMPUTERS & CHEMISTRY 1999年第6期23卷 555-563页

作者： Zhou, B Li, JY Yu, JH Xu, YH Xu, WG Shi, N Qiu, SL Xu, RR Jilin Univ Key Lab Inorgan Synthesis & Preparat Chem Changchun 130023 Peoples R China

In this paper, we provide a systematic method to generate the sheets of two-dimensional layered aluminophosphates with Al3P4O163- stoichiometry. Our approach adopts the divide-and-conquer algorithm to reduce the degree of combination explosion caused by simple enumeration. We use Coordination Sequences to identify the same topological meshes in order to get the distinct sheets. We relax the generated sheets using Genetic algorithm, then minimize the energies of the sheets to choose the lower energy sheets which may be synthesized. This approach can generate systemically more than 4,000 distinct sheets by the computer. Some sheets have been synthesized, while some new hypothetical sheets resemble lower energy as the known 2D Al3P4O163- compounds. We further discuss the structural features of 2D Al3P4O163- nets. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： aluminophosphates 3.4-connected nets enumeration divide-and-conquer algorithm genetic algorithm energy calculation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A general limit theorem for recursive algorithms and combinatorial structures

引用

ANNALS OF APPLIED PROBABILITY 2004年第1期14卷 378-418页

作者： Neininger, R Rüschendorf, L McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada Univ Freiburg Inst Math Stochast D-79104 Freiburg Germany

Limit laws are proven by the contraction method for random vectors of a recursive nature as they arise as parameters of combinatorial structures such as random trees or recursive algorithms, where we use the Zolotarev metric. In comparison to previous applications of this method, a general transfer theorem is derived which allows us to establish a limit law on the basis of the recursive structure and the asymptotics of the first and second moments of the sequence. In particular, a general asymptotic normality result is obtained by this theorem which typically cannot be handled by the more common l(2) metrics. As applications we derive quite automatically many asymptotic limit results ranging from the size of tries or m-ary search trees and path lengths in digital structures to mergesort and parameters of random recursive trees, which were previously shown by different methods one by one. We also obtain a related local density approximation result as well as a global approximation result. For the proofs of these results we establish that a smoothed density distance as well as a smoothed total variation distance can be estimated from above by the Zolotarev metric, which is the main tool in this article.

关键词： contraction method multivariate limit law asymptotic normality random trees recursive algorithms divide-and-conquer algorithm random recursive structures Zolotarev metric

来源：评论

学校读者我要写书评

暂无评论

Computation of Gauss-Kronrod quadrature rules

引用

MATHEMATICS OF COMPUTATION 2000年第231期69卷 1035-1052页

作者： Calvetti, D Golub, GH Gragg, WB Reichel, L Case Western Reserve Univ Dept Math Cleveland OH 44106 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA USN Postgrad Sch Dept Math Monterey CA 93943 USA

Recently Laurie presented a new algorithm for the computation of (2n + 1)-point Gauss-Kronrod quadrature rules with real nodes and positive weights. This algorithm first determines a symmetric tridiagonal matrix of order 2n + 1 from certain mixed moments, and then computes a partial spectral factorization. We describe a new algorithm that does not require the entries of the tridiagonal matrix to be determined, and thereby avoids computations that can be sensitive to perturbations. Our algorithm uses the consolidation phase of a divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. We also discuss how the algorithm can be applied to compute Kronrod extensions of Gauss-Radau and Gauss-Lobatto quadrature rules. Throughout the paper we emphasize how the structure of the algorithm makes efficient implementation on parallel computers possible. Numerical examples illustrate the performance of the algorithm.

关键词： Jacobi matrix inverse eigenvalue problem divide-and-conquer algorithm generalized Gauss-Kronrod rule

来源：评论

学校读者我要写书评

暂无评论

Recognition of Robinsonian dissimilarities

引用

JOURNAL OF CLASSIFICATION 1997年第2期14卷 311-325页

作者： Chepoi, V Laboratoire de Biomathématiques Faculté de Médecine Univesité d’Aix Marseille II Marseille Cedex 5 France

We present an O(n(3))-time, O(n(2))-space algorithm to test whether a dissimilarity d on an n-object set X is Robinsonian, i.e., X admits an ordering such that i less than or equal to j less than or equal to k implies... 详细信息

关键词： Robinsonian dissimilarities order compatible with a dissimilarity divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：