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

randomized GPU algorithms FOR THE CONSTRUCTION OF HIERARCHICAL MATRICES FROM MATRIX-VECTOR OPERATIONS

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第4期41卷 C339-C366页

作者： Boukaram, Wajih Turkiyyah, George Keyes, David King Abdullah Univ Sci & Technol Extreme Comp Res Ctr Thuwal 239556900 Saudi Arabia Amer Univ Beirut Dept Comp Sci Beirut 11072020 Lebanon

randomized algorithms for the generation of low rank approximations of large dense matrices have become popular methods in scientific computing and machine learning. In this paper, we extend the scope of these methods and present batched GPU randomized algorithms for the efficient generation of low rank representations of large sets of small dense matrices, as well as their generalization to the construction of hierarchically low rank symmetric H-2 matrices with general partitioning structures. In both cases, the algorithms need to access the matrices only through matrix-vector multiplication operations which can be done in blocks to increase the arithmetic intensity and substantially boost the resulting performance. The batched GPU kernels are adaptive, allow nonuniform sizes in the matrices of the batch, and are more effective than SVD factorizations on matrices with fast decaying spectra. The hierarchical matrix generation consists of two phases, interleaved at every level of the matrix hierarchy. A first phase adaptively generates low rank approximations of matrix blocks through randomized matrix-vector sampling. A second phase accumulates and compresses these blocks into a hierarchical matrix that is incrementally constructed. The accumulation expresses the low rank blocks of a given level as a set of local low rank updates that are performed simultaneously on the whole matrix allowing high-performance batched kernels to be used in the compression operations. When the ranks of the blocks generated in the first phase are too large to be processed in a single operation, the low rank updates can be split into smaller-sized updates and applied in sequence. Assuming representative rank k, the resulting matrix has optimal O(kN) asymptotic storage complexity because of the nested bases it uses. The ability to generate an H-2 matrix from matrix-vector products allows us to support a general randomized matrix-matrix multiplication operation, an important kernel in hiera

关键词： hierarchical matrices GPU randomized algorithms low rank factorization low rank updates batched algorithms matrix-matrix multiplication matrix compression nested bases

来源：评论

学校读者我要写书评

暂无评论

Deconstructing randomized algorithms Using Darn

Deconstructing Randomized Algorithms Using Darn

引用

2011 13th IEEE Joint International Computer Science and Information Technology Conference(JICSIT 2011)

作者： GAO Yuan School of Electronic and Computer Science and Technology North University of China Taiyuan,ChinaWANG Dong School of Electronic and Computer Science and Technology North University of China Taiyuan,China

Many people worldwide would agree that,had it not been for suffix trees,the simulation of journaling file systems might never have *** the current status of cooperative technology,system administrators daringly desire the study of digital-to-analog converters,which embodies the significant principles of operating *** our research we deconstruct randomized algorithms using *** prove that though the location-identity split and spreadsheets are always incompatible,wide-area networks can be made"fuzzy", ambimorphic,and compact.

关键词： randomized algorithms darn deconstructing

来源：评论

学校读者我要写书评

暂无评论

randomized COMPETITIVE algorithms FOR THE LIST UPDATE PROBLEM

引用

ALGORITHMICA 1994年第1期11卷 15-32页

作者： REINGOLD, N WESTBROOK, J SLEATOR, DD YALE UNIV DEPT COMP SCINEW HAVENCT 06520 CARNEGIE MELLON UNIV PITTSBURGHPA 15213

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constant d. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.

关键词： SEQUENTIAL SEARCH LIST-UPDATE ONLINE algorithms COMPETITIVE ANALYSIS randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized and quantum algorithms yield a speed-up for initial-value problems

引用

JOURNAL OF COMPLEXITY 2004年第6期20卷 821-834页

作者： Kacewicz, B AGH Univ Sci & Technol Dept Appl Math PL-30059 Krakow Poland

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem. (C) 2004 Elsevier Inc. All rights reserved.

关键词： randomized algorithms quantum algorithms initial-value problems

来源：评论

学校读者我要写书评

暂无评论

An Investigation on Wide-Area Networks Based on randomized algorithms

An Investigation on Wide-Area Networks Based on Randomized A...

引用

2009 Asia-Pacific Conference on Information Processing

作者： Xuejun Yang Library Changsha University of Science and Technology Changsha 410004,China Hong Wang School of Civil Engineering Hunan University Changsha 410082,China

Many scholars would agree that,had it not been for the evaluation of gigabit switches,the analysis of massive multiplayer online role-playing games might never have *** fact,few experts would disagree with the intuitive unification of superblocks and the location-identity split,which embodies the confirmed principles of *** construct new heterogeneous communication(BACK),which we use to verify that red-black trees and the location-identity split are rarely incompatible.

关键词： wide-area networks randomized algorithms heterogeneous communication

来源：评论

学校读者我要写书评

暂无评论

Learning Sequential and Parallel Runtime Distributions for randomized algorithms

Learning Sequential and Parallel Runtime Distributions for R...

引用

International Conference on Tools with Artificial Intelligence

作者： Alejandro Arbelaez Charlotte Truchet Barry O'Sullivan Insight Centre for Data Analytics Univ. Coll. Cork Cork Ireland LINA Univ. of Nantes Nantes France

ISBN: (纸本)9781509044603

In cloud systems, computation time can be rented by the hour and for a given number of processors. Thus, accurate predictions of the behaviour of both sequential and parallel algorithms has become an important issue, in particular in the case of costly methods such as randomized combinatorial optimization tools. In this work, our objective is to use machine learning to predict performance of sequential and parallel local search algorithms. In addition to classical features of the instances used by other machine learning tools, we consider data on the sequential runtime distributions of a local search method. This allows us to predict with a high accuracy the parallel computation time of a large class of instances, by learning the behaviour of the sequential version of the algorithm on a small number of instances. Experiments with three solvers on SAT and TSP instances indicate that our method works well, with a correlation coefficient of up to 0.85 for SAT instances and up to 0.95 for TSP instances.

关键词： Runtime Algorithm design and analysis Prediction algorithms Parallel algorithms Machine learning algorithms Approximation algorithms Search problems Runtime Algorithm design and analysis Parallel algorithms tabu search Machine learning algorithms Prediction algorithms Sequential Approximation algorithms randomized algorithms Search methods SEMI-AUTOMATIC TRIM College Entrance Examination Board Scholastic Aptitude Test

来源：评论

学校读者我要写书评

暂无评论

Dispersion of mass and the complexity of randomized geometric algorithms

引用

ADVANCES IN MATHEMATICS 2008年第3期219卷 1037-1069页

作者： Rademacher, Luis Vempala, Santosh Georgia Tech Atlanta GA 30332 USA

How much can randomness help computation? Motivated by this general question and by volume computation. one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in R" (the current best algorithm has complexity roughly n(4), conjectured to be n(3)). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body. are of independent interest and applicable more generally in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing. (C) 2008 Elsevier Inc. All rights reserved.

关键词： Volume computation Lower bounds randomized algorithms Variance hypothesis Dispersion of mass Determinant computation

来源：评论

学校读者我要写书评

暂无评论

randomized parallel algorithms for the multidimensional assignment problem

引用

APPLIED NUMERICAL MATHEMATICS 2004年第1期49卷 117-133页

作者： Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： multidimensional assignment problem parallel algorithms randomized algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

randomized Gossip algorithms for Solving Laplacian Systems

Randomized Gossip Algorithms for Solving Laplacian Systems

引用

European Control Conference (ECC)

作者： Zouzias, Anastasios Freris, Nikolaos M. IBM Res Zurich Dept Math & Computat Sci Ruschlikon Switzerland New York Univ Abu Dhabi Div Engn Abu Dhabi U Arab Emirates

ISBN: (纸本)9783952426937

We consider the problem of solving a Laplacian system of equations Lx = b in a distributed fashion, where L is the Laplacian of the communication graph. Solving Laplacian systems arises in a number of applications including consensus, distributed control, clock synchronization, localization and calculating effective resistances, to name a few. We leverage our analysis on a randomized variant of Kaczmarz's algorithm to propose a distributed asynchronous gossip algorithm with expected exponential convergence. We quantify the convergence rate depending solely on properties of the network topology, and further propose an accelerated version that scales favorably for larger networks. Our approach naturally extends to least-squares estimation of general linear systems where each row/column is assigned to nodes of a given network. Last but not least, we show that average consensus is a special case in our framework.

关键词： Gossip algorithms Laplacian systems Consensus Distributed algorithms Cyberphysical systems randomized algorithms Clock synchronization

来源：评论

学校读者我要写书评

暂无评论

randomized parallel algorithms for the multidimensional assignment problem

Randomized parallel algorithms for the multidimensional assi...

引用

3rd Workshop of the ERCIM-Working-Group-on-Matrix-Computations-and-Statitsics

作者： Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

关键词： multidimensional assignment problem parallel algorithms randomized algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：