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

12th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Hirota, Yusuke Imamura, Toshiyuki RIKEN Adv Inst Computat Sci Kobe Hyogo Japan

ISBN: (纸本)9783319780245;9783319780238

We present a new parallel divide-and-conquer (DC) algorithm based on an execution scheduling by batched kernels for solving real-symmetric tridiagonal eigenvalue problems on manycore systems. Our algorithm has higher parallelism and requires less global synchronizations than a conventional algorithm. We compared the performance of the solver based on our algorithm with that of Intel MKL's DC solver and PLASMA's one on Xeon E5, Xeon Phi Knights Corner, and Xeon Phi Knights Landing. The numerical tests show that the implementation of our algorithm is comparable to Intel MKL on Xeon E5 and outperforms Intel MKL and PLASMA on the two Xeon Phi systems.

关键词： divide-and-conquer algorithm Eigenvalue problem Manycore Xeon Phi

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer algorithm FOR FINDING A MOST RELIABLE SOURCE ON A RING-EMBEDDED TREE NETWORK WITH UNRELIABLE EDGES

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2011年第4期3卷 503-516页

作者： Ding, Wei Xue, Guoliang Zhejiang Water Conservancy & Hydropower Coll Hangzhou 310018 Zhejiang Peoples R China Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

Given an unreliable communication network, we seek a most reliable source (MRS) of the network, which maximizes the expected number of nodes that are reachable from it. The problem of computing an MRS in general graphs is # P-hard. However, this problem in tree networks has been solved in a linear time. A tree network has a weakness of low capability of failure tolerance. Embedding rings into it by adding some additional certain edges to it can enhance its failure tolerance, resulting in another class of sparse networks, called the ring-tree networks. This class of network also has an underlying tree-like topology, leading to its advantage of being easily administrated. This paper concerns with an important case whose underlying topology is a strip graph, called lambda-rings network, and focuses on an unreliable lambda-rings network where each link has an independent operational probability while all nodes are immune to failures. We apply the divide-and-conquer approach to design a fast algorithm for computing an MRS, and employ a binary division tree (BDT) to analyze its time complexity to be O(parallel to lambda parallel to(2)(2) + [log vertical bar lambda vertical bar] center dot parallel to lambda parallel to).

关键词： Most reliable source ring-tree underlying topology divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer algorithm for Computing a Most Reliable Source on an Unreliable Ring-Embedded Tree

A Divide-and-Conquer Algorithm for Computing a Most Reliable...

引用

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Ding, Wei Xue, Guoliang Zhejiang Water Conservancy & Hydropower Coll Hangzhou Zhejiang Peoples R China Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

ISBN: (纸本)9783642174605

Given an unreliable communication network, we seek a most reliable source (MRS) of the network, which maximizes the expected number of nodes that are reachable from it. The problem of computing an MRS in general graphs is #P-hard. However, this problem in tree networks has been solved in a linear time. A tree network has a weakness of low capability of failure tolerance. Embedding rings into it by adding some additional certain edges to it can enhance its failure tolerance, resulting in another class of sparse networks, called the ring-tree networks. This class of network also has an underlying tree-like topology, leading to its advantage of being easily administrated. This paper concerns with an important case whose underlying topology is a strip graph, called lambda-rings network, and focuses on an unreliable lambda-rings network where each link has an independent operational probability while all nodes are immune to failures. We apply the divide-and-conquer approach to design a fast algorithm for computing its an MRS, and employ a binary division tree (BDT) to analyze its time complexity to be O(parallel to lambda parallel to(2)(2) + inverted right perpendicularlog vertical bar lambda vertical bar inverted left perpendicular . parallel to lambda parallel to(1))

关键词： Most reliable source ring-tree underlying topology divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

Ray-Tracing-Assisted Calibration Based on divide-and-conquer algorithm in Macrocellular Environment 14

Ray-Tracing-Assisted Calibration Based on Divide-and-Conquer...

引用

14th International Symposium on Antennas Propagation and EM Theory

作者： Lu, Jun-Yang Liu, Zhong-Yu Guo, Li-Xin Xidian Univ Sch Phys Xian Peoples R China

ISBN: (纸本)9798350353129;9798350353136

In addressing the significant influence of material dielectric parameters on outdoor three-dimensional ray tracing predictions, an algorithm based on divide-and-conquer strategy for calibrating the dielectric properties of materials is proposed. The algorithm segments the solution space for dielectric parameters into smaller sub-spaces, resolving each incrementally to arrive at the global optimal solution. It employs a prudent convergence strategy for the solution space, discarding those sub-spaces that have a low probability of containing the optimum. The results indicate that this algorithm not only maintains high accuracy but also facilitates rapid calibration of dielectric parameters.

关键词： ray tracing divide-and-conquer algorithm calibration of dielectric parameters convergence strategy

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer algorithm for curve fitting

引用

COMPUTER-AIDED DESIGN 2022年 151卷

作者： Buchinger, Diego Rosso Jr, Roberto Silvio Ubertino Santa Catarina State Univ Coll Technol Sci BR-89219710 Joinville SC Brazil

Curve fitting is still an open problem which draws attention from many applications, such as computer-aided design, computer-aided manufacturing and reverse engineering. Splines such as Bezier, B-Spline and NURBS curves are usually employed in engineering applications and are intensively used for fitting purposes. The optimization of their shapes and localization parameters, however, is a very complex task. The literature presents many methods which empirically set some important parameters, such as the number of control points. As guessing such a value is difficult, this paper presents a new method to choose it through a multi-curve fitting method, based on linear least square optimizations, using a divide-and-conquer algorithm and an error tolerance threshold. Four prime procedures compose the method: the conquer step fits curves over subset point clouds;the combine step glues curve segments together with some selective continuity;the divide step splits subsets which are not properly fitted yet;and the merge step blends curve segments together. Several curve setups were tested in well-known benchmarks, using four-division strategies: bisection, error balance, point with the greatest curvature and point with the smallest curvature. The developed method allows for fast computation even for larger point clouds, and it was able to properly reconstruct each tested shape, even with the addition of synthetic noise. We also demonstrate that it can be significantly faster than a single-curve fitting using the same number of control points.(c) 2022 Elsevier Ltd. All rights reserved.

关键词： Data fitting Curve reconstruction B?zier B-splines divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer algorithm for distributed optimization on networks

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2024年 70卷

作者： Emirov, Nazar Song, Guohui Sun, Qiyu Boston Coll Dept Comp Sci Chestnut Hill MA 02467 USA Old Dominion Univ Dept Math & Stat Norfolk VA 23529 USA Univ Cent Florida Dept Math Orlando FL 32816 USA

In this paper, we consider networks with topologies described by some connected undirected graph G = (V, E) and with some agents (fusion centers) equipped with processing power and local peer-to-peer communication, and optimization problem mini {F(i) = n-ary sumation ��is an element of V f ��(i)} with local objective functions f �� depending only on neighboring variables of the vertex �� is an element of V. We introduce a divide-and-conquer algorithm to solve the above optimization problem in a distributed and decentralized manner. The proposed divide-and-conquer algorithm has exponential convergence, its computational cost is almost linear with respect to the size of the network, and it can be fully implemented at fusion centers of the network. In addition, our numerical demonstrations indicate that the proposed divide-and-conquer algorithm has superior performance than popular decentralized optimization methods in solving the least squares problem, both with and without the ��1 penalty, and exhibits great performance on networks equipped with asynchronous local peer-to-peer communication.

关键词： divide-and-conquer algorithm Distributed optimization Graph signal processing

来源：评论

学校读者我要写书评

暂无评论

divide-and-conquer-based approach for the reaction uniqueness analysis in overconstrained multibody systems

引用

MULTIBODY SYSTEM DYNAMICS 2025年第3期63卷 367-396页

作者： Pekal, Marcin Malczyk, Pawel Wojtyra, Marek Fraczek, Janusz Warsaw Univ Technol Inst Aeronaut & Appl Mech Warsaw Poland

For rigid multibody systems with redundant constraints, mathematical modeling and physical interpretation of the obtained results are impeded due to the nonuniqueness of the calculated reactions, which-in the case of load-dependent joint friction-may additionally lead to unrealistic simulated motion. It makes the uniqueness analysis crucial for assessing the fidelity of the results. The developed methods so far for the uniqueness examination-based on the modified mobility equation, the constraint matrix, or the free-body diagram-are not well suited for multibody systems described by relative coordinates. The novel method discussed in this paper breaks this limitation. The proposed approach is based on the divide-and-conquer algorithm (DCA)-a low-order recursive method for dynamic simulations of complex multibody systems. The devised method may be used for checking the joint-reaction uniqueness of holonomic systems with ideal constraints that fulfill some additional assumptions. The reaction-uniqueness analysis is performed when the main pass of the DCA is completed. An eight-step algorithm is proposed. In the case of the single-joint connections, it is sufficient to study the appropriate equations of motion. However, if the multijoint connection is present, then one of the numerical methods-known from the constraint-matrix-based or the free-body-diagram-based approach-has to be used, namely the rank-comparison, QR-decomposition, SVD, or nullspace methods;all of these approaches are discussed. To illustrate the devised method, a spatial parallelogram mechanism with a triple pendulum is analyzed.

关键词： Multibody Uniqueness analysis Overconstrained system Rigid system Reactions divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

AVERAGE COMPLEXITY OF divide-and-conquer algorithmS

引用

INFORMATION PROCESSING LETTERS 1988年第6期29卷 319-326页

作者： VEROY, BS Department of Computer and Information Sciences New Jersey Institute of Technology Newark NJ 07102 U.S.A.

The goal of this paper is to describe a rather general approach for constructing upper and lower bounds for the average computational complexity of divide-and-conquer algorithms.

关键词： divide-and-conquer algorithm average computational complexity upper and lower bounds unicrossing pair of functions

来源：评论

学校读者我要写书评

暂无评论

New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2016年第4期23卷 656-673页

作者： Li, Shengguo Liao, Xiangke Liu, Jie Jiang, Hao Natl Univ Def Technol Coll Comp Changsha 410073 Hunan Peoples R China Natl Univ Def Technol Sci & Technol Parallel & Distributed Proc Lab Changsha 410073 Hunan Peoples R China Natl Univ Def Technol State Key Lab High Performance Comp Changsha 410073 Hunan Peoples R China

In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N(2)r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multi-threaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright (C) 2016 John Wiley & Sons, Ltd.

关键词： HSS matrices cauchy-like matrices eigenvalue problems Schur complements divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：