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

DYNAMICALLY ADAPTIVE SIMULATIONS WITH MINIMAL memory REQUIREMENT-SOLVING THE SHALLOW WATER EQUATIONS USING SIERPINSKI CURVES

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2010年第1期32卷 212-228页

作者： Bader, Michael Boeck, Christian Schwaiger, Johannes Vigh, Csaba Tech Univ Munich Inst Informat D-85748 Garching Germany

We present an approach to the numerical simulation of dynamically adaptive problems on recursively structured adaptive triangular grids. The intended application is the simulation of oceanic wave propagation (e.g., tsunami simulation) based on the shallow water equations. For the required 2D dynamically adaptive discretization, we adopt a grid generation process based on recursive bisection of triangles along marked edges. The recursive grid generation may be described via a respective refinement tree, which is sequentialized according to a Sierpinski space-filling curve. This allows a storage scheme for the adaptive grid that requires only a minimal amount of memory. Moreover, the sequentialization and, hence, the locality properties induced by the space-filling curve are retained throughout adaptive refinement and coarsening of the grid. Conforming adaptive refinement and coarsening, as well as time-stepping techniques for time-dependent systems of partial differential equations, are implemented using an inherently cache-efficient processing scheme, which is based on the use of stacks and stream-like data structures and a traversal of the adaptively refined grid along the Sierpinski curve. We demonstrate the computational efficiency of the approach on the solution of a simplified version of the shallow water equations, for which we use a discontinuous Galerkin discretization. Special attention is paid to the memory efficiency of the implementation.

关键词： simulation on adaptive grids dynamic remeshing space-filling curves Sierpinski curve shallow water equations discontinuous Galerkin method memory-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploration with Limited memory: Streaming algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits 2020

Exploration with Limited Memory: Streaming Algorithms for Co...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Assadi, Sepehr Wang, Chen Rutgers Univ New Brunswick Piscataway NJ 08854 USA

ISBN: (纸本)9781450369794

Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point - any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only O(log n) coins and then iteratively refine it further and further, leading to algorithms with O(log log (n)) memory, O(log*(n)) memory, and finally a one that only stores a single extra coin in memory - the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the k most biased coins as well as other exploration problems such as finding top-k elements using noisy comparisons or finding an e-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.

关键词： Streaming algorithms Pure Exploration memory-efficient algorithms Noisy Comparison Multi-Armed Bandits

来源：评论

学校读者我要写书评

暂无评论

DYNAMICALLY ADAPTIVE SIMULATIONS WITH MINIMAL memory REQUIREMENT-SOLVING THE SHALLOW WATER EQUATIONS USING SIERPINSKI CURVES

DYNAMICALLY ADAPTIVE SIMULATIONS WITH MINIMAL MEMORY REQUIRE...

引用

10th Copper Mountain Conference on Iterative Methods

作者： Bader, Michael Boeck, Christian Schwaiger, Johannes Vigh, Csaba Tech Univ Munich Inst Informat D-85748 Garching Germany

关键词： simulation on adaptive grids dynamic remeshing space-filling curves Sierpinski curve shallow water equations discontinuous Galerkin method memory-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Picasso: memory-efficient Graph Coloring Using Palettes With Applications in Quantum Computing 38

Picasso: Memory-Efficient Graph Coloring Using Palettes With...

引用

International Parallel and Distributed Processing Symposium (IPDPS)

作者： Ferdous, S. M. Neff, Reece Peng, Bo Shuvo, Salman Minutoli, Marco Mukherjee, Sayak Kowalski, Karol Becchi, Michela Halappanavar, Mahantesh Pacif Northwest Natl Lab Richland WA 99354 USA North Carolina State Univ Raleigh NC USA

ISBN: (纸本)9798350387117;9798350387124

A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm's parameters considering these trade-offs. We provide a sequential and parallel implementation of the proposed algorithm. We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68x memory savings. On massive datasets, we demonstrate that GPU-accelerated Picasso can process inputs with 49.5x more Pauli strings (vertex set in our graph) and 2,478x more edges than state-of-the-art parallel approaches.

关键词： Graph coloring quantum computing memory-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：