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

Multidimensional phase recovery and interpolative decomposition butterfly factorization

JOURNAL OF COMPUTATIONAL PHYSICS 2020年 412卷 109427-109427页

作者： Chen, Ze Zhang, Juan Ho, Kenneth L. Yang, Haizhao Natl Univ Singapore Dept Math Singapore Singapore Xiangtan Univ Dept Math & Computat Sci Xiangtan Peoples R China Flatiron Inst Ctr Computat Math New York NY USA Purdue Univ Dept Math W Lafayette IN 47907 USA

This paper focuses on the fast evaluation of the matrix-vector multiplication (matvec) g= Kf for K is an element of C-NxN, which is the discretization of a multidimensional oscillatory integral transform g(x) = similar to K(x,xi) f(xi)d xi with a kernel function K(x, xi) = e(2 pi i Phi(x,xi)), where Phi(x, xi) is a piecewise smooth phase function with x and xi in R-d for d = 2 or 3. A new framework is introduced to compute Kfwith O ( Nlog(N)) time and memories complexity in the case that only indirect access to the phase function Phi is available. This framework consists of two main steps: 1) an O (Nlog(N)) algorithm for recovering the multidimensional phase function Phi from indirect access is proposed;2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec Kfwith an O (Nlog( N)) complexity once Phi is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Data-sparse matrix Butterfly factorization Interpolative decomposition Operator compression randomized algorithm Matrix completion

来源：评论

学校读者我要写书评

暂无评论

Pass-efficient methods for compression of high-dimensional turbulent flow data

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2020年 423卷 109704-109704页

作者： Dunton, Alec M. Jofre, Lluis Iaccarino, Gianluca Doostan, Alireza Univ Colorado Appl Math Boulder CO 80309 USA Stanford Univ Ctr Turbulence Res Stanford CA 94305 USA Tech Univ Catalonia BarcelonaTech Dept Fluid Mech Barcelona 08019 Spain Univ Colorado Smead Aerosp Engn Sci Boulder CO 80309 USA

The future of high-performance computing, specifically on future Exascale computers, will presumably see memory capacity and bandwidth fail to keep pace with data generated, for instance, from massively parallel partial differential equation (PDE) systems. Current strategies proposed to address this bottleneck entail the omission of large fractions of data, as well as the incorporation of in situ compression algorithms to avoid overuse of memory. To ensure that post-processing operations are successful, this must be done in a way that a sufficiently accurate representation of the solution is stored. Moreover, in situations where the input/output system becomes a bottleneck in analysis, visualization, etc., or the execution of the PDE solver is expensive, the number of passes made over the data must be minimized. In the interest of addressing this problem, this work focuses on the utility of pass-efficient, parallelizable, low-rank, matrix decomposition methods in compressing high-dimensional simulation data from turbulent flows. A particular emphasis is placed on using coarse representation of the data - compatible with the PDE discretization grid - to accelerate the construction of the low-rank factorization. This includes the presentation of a novel single-pass matrix decomposition algorithm for computing the so-called interpolative decomposition. The methods are described extensively and numerical experiments on two turbulent channel flow data are performed. In the first (unladen) channel flow case, compression factors exceeding 400 are achieved while maintaining accuracy with respect to first- and second-order flow statistics. In the particle-laden case, compression factors of 100 are achieved and the compressed data is used to recover particle velocities. These results show that these compression methods can enable efficient computation of various quantities of interest in both the carrier and disperse phases. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Big-data compression Interpolative decomposition Low-rank approximation Particle-laden turbulence randomized algorithm Single-pass algorithm

来源：评论

学校读者我要写书评

暂无评论

A MAPREDUCE algorithm FOR MINIMUM VERTEX COVER PROBLEMS AND ITS RANDOMIZATION

引用

COMPUTING AND INFORMATICS 2020年第5期39卷 952-972页

作者： Nakamura, Morikazu Kinjo, Daiki Yoshida, Takeo Univ Ryukyus Fac Engn Nishihara Okinawa 9030213 Japan

MapReduce is a programming paradigm for large-scale distributed information processing. This paper proposes a MapReduce algorithm for the minimum vertex cover problem, which is known to be NP-hard. The MapReduce algorithm can efficiently obtain a minimal vertex cover in a small number of rounds. We show the effectiveness of the algorithm through experimental evaluation and comparison with exact and approximate algorithms which demonstrates a high quality in a small number of MapReduce rounds. We also confirm from experimentation that the algorithm has good scalability allowing high-quality solutions under restricted computation times due to increased graph size. Moreover, we extend our algorithm to randomized one to obtain a good expected approximate ratio.

关键词： MapReduce minimum vertex cover Hadoop optimization algorithm design randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized nonnegative matrix factorization

引用

PATTERN RECOGNITION LETTERS 2018年 104卷 1-7页

作者： Erichson, N. Benjamin Mendible, Ariana Wihlborn, Sophie Kutz, J. Nathan Univ Washington Dept Appl Math Seattle WA 98195 USA Fidel Int London England

Nonnegative matrix factorization (NMF) is a powerful tool for data mining. However, the emergence of 'big data' has severely challenged our ability to compute this fundamental decomposition using deterministic algorithms. This paper presents a randomized hierarchical alternating least squares (HALS) algorithm to compute the NMF. By deriving a smaller matrix from the nonnegative input data, a more efficient nonnegative decomposition can be computed. Our algorithm scales to big data applications while attaining a near-optimal factorization, i.e., the algorithm scales with the target rank of the data rather than the ambient dimension of measurement space. The proposed algorithm is evaluated using synthetic and real world data and shows substantial speedups compared to deterministic HALS. (c) 2018 Elsevier B.V. All rights reserved.

关键词： NMF randomized algorithm Dimension reduction

来源：评论

学校读者我要写书评

暂无评论

COMPUTING LOW-RANK APPROXIMATIONS OF LARGE-SCALE MATRICES WITH THE TENSOR NETWORK randomized SVD

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2018年第3期39卷 1221-1244页

作者： Batselier, Kim Yu, Wenjian Daniel, Luca Wong, Ngai Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China Tsinghua Univ Dept Comp Sci & Technol BNRist Beijing 100084 Peoples R China MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

We propose a new algorithm for the computation of a singular value decomposition (SVD) low-rank approximation of a matrix in the matrix product operator (MPO) format, also called the tensor train matrix format. Our tensor network randomized SVD (TNrSVD) algorithm is an MPO implementation of the randomized SVD algorithm that is able to compute dominant singular values and their corresponding singular vectors. In contrast to the state-of-the-art tensor-based alternating least squares SVD (ALS-SVD) and modified alternating least squares SVD (MALS-SVD) matrix approximation methods, TNrSVD can be up to 13 times faster while achieving better accuracy. In addition, our TNrSVD algorithm also produces accurate approximations in particular cases where both ALS-SVD and MALS-SVD fail to converge. We also propose a new algorithm for the fast conversion of a sparse matrix into its corresponding MPO form, which is up to 509 times faster than the standard tensor train SVD method while achieving machine precision accuracy. The efficiency and accuracy of both algorithms are demonstrated in numerical experiments.

关键词： curse of dimensionality low-rank tensor approximation matrix factorization matrix product operator singular value decompositon (SVD) tensor network tensor train (TT) decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized approximation algorithms for planar visibility counting problem

引用

THEORETICAL COMPUTER SCIENCE 2018年 707卷 46-55页

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Sharif Univ Technol Dept Comp Engn Tehran Iran Sharif Univ Technol Dept Math Sci Tehran Iran Inst Res Fundamental Sci IPM Sch Math Tehran Iran

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O (log n) query time using O(n(4) log n) preprocessing time and O(n(4)) space. Gudmundsson and Morin (2010) [101 proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 <= alpha <= 1, their algorithm answers any query in O-epsilon (m((1-alpha)/2)) time with O (epsilon)(M1+alpha) of preprocessing time and space, where epsilon > 0 is a constant that can be made arbitrarily small and O-epsilon (f (n)) = O (f (n)n(epsilon)) and in m = O (n(2)) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 <= beta <= 2/3 and 0 < delta <= 1, and the expected preprocessing time, the expected space, and the expected query time are O (m(2-3 beta/2) log m), O(m(2-3 beta/2)), and O (1/delta(2)m(beta/2) log m), respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p, denoted by m(p), exactly, if m(p) <= 3/delta(2)m(beta/2) log(2m). Otherwise, it computes an approximated value, m(p), such that with the probability of at least 1 - 1/m, we have (1 - delta)m(p) <= m'(p) <= (2 + 2 delta)m(p). The preprocessing time and space of the second algorithm are O(n(2) log n) and O(n(2)), respectively. This algorithm computes the exact value of m(p) if m(p) <= 1/delta(2) root n log n, otherwise it returns an approximated value m ''(p) in expected O(1/delta(2)root n log n) time, such that with the probability at least 1 - 1/log n, we

关键词： Computational geometry Visibility randomized algorithm Approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

Equal-Subset-Sum Faster Than the Meet-in-the-Middle 27

Equal-Subset-Sum Faster Than the Meet-in-the-Middle

引用

27th Annual European Symposium on algorithms (ESA)

作者： Mucha, Marcin Nederlof, Jesper Pawlewicz, Jakub Wegrzycki, Karol Univ Warsaw Inst Informat Warsaw Poland Eindhoven Univ Technol Eindhoven Netherlands

ISBN: (纸本)9783959771245

In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B subset of S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O*(3(n/2)) <= O*(1.7321(n)) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O*(1.7088(n)) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O*(3(n)) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O*(2.6817(n)) time and polynomial space.

关键词： Equal-Subset-Sum Subset-Sum meet-in-the-middle enumeration technique randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Note on Leader Election algorithms. Preliminary Report 5

A Note on Leader Election Algorithms. Preliminary Report

引用

IEEE Asia Pacific Conference on Wireless and Mobile (APWiMob)

作者： Bojko, Dominik Cichon, Jacek Wroclaw Univ Sci & Technol Fac Fundamental Problems Technol Dept Comp Sci Wroclaw Poland

ISBN: (纸本)9781728148656

In this paper we discuss a leader election algorithm which depends on two parameters p, L. The first one is a probability parameter of geometric distribution used during a draw of identity and the latter one is a maximal number of bits of memory that each node can develop in order to save identity of a potential leader. We consider a family {v(1), ...,v(n)} of nodes. In this algorithm each node v, generates independently a random number x, from a geometric distribution with parameter p and furtherly calculates the number y(i) = min(x(i), L). Nodes which choose the biggest number become candidates for a leader. This procedure successfully elects the leader if there is exactly one candidate. We fix a number N and epsilon > 0. Our goal is to determine such parameters p and L which guarantee that the considered algorithm will be accurate i.e. it will be successful with a probability at least 1 - epsilon, for an arbitrary number of nodes 1 <= n <= N. This strong requirement distinguishes our considerations from many other analysis of leader election algorithms, which often focus only on theirs asymptotic correctness and properties. Our algorithm can be implemented either in single hop or in multi hop environment. In the single hop case it needs log(2) L rounds to select a leader with required probability of success and may be adapted to the multi hop environment, where it needs O (d log(2) L) rounds, where d denotes an upper bound for a diameter of the network.

关键词： leader election extrema propagation randomized algorithm geometric distribution single-hop network multi-hop network

来源：评论

学校读者我要写书评

暂无评论

Interaction Testing, Fault Location, and Anonymous Attribute-Based Authorization

Interaction Testing, Fault Location, and Anonymous Attribute...

引用

作者： Lanus, Erin Arizona State University

学位级别：Ph.D.

This dissertation studies three classes of combinatorial arrays with practical applications in testing, measurement, and security. Covering arrays are widely studied in software and hardware testing to indicate the presence of faulty interactions. Locating arrays extend covering arrays to achieve identification of the interactions causing a fault by requiring additional conditions on how interactions are covered in rows. This dissertation introduces a new class, the anonymizing arrays, to guarantee a degree of anonymity by bounding the probability a particular row is identified by the interaction presented. Similarities among these arrays lead to common algorithmic techniques for their construction which this dissertation explores. Differences arising from their application domains lead to the unique features of each class, requiring tailoring the techniques to the specifics of each problem. One contribution of this work is a conditional expectation algorithm to build covering arrays via an intermediate combinatorial object. Conditional expectation efficiently finds intermediate-sized arrays that are particularly useful as ingredients for additional recursive algorithms. A cut-and-paste method creates large arrays from small ingredients. Performing transformations on the copies makes further improvements by reducing redundancy in the composed arrays and leads to fewer rows. This work contains the first algorithm for constructing locating arrays for general values of d and t. A randomized computational search algorithmic framework verifies if a candidate array is (&dmacr;,t)-locating by partitioning the search space and performs random resampling if a candidate fails. algorithmic parameters determine which columns to resample and when to add additional rows to the candidate array. Additionally, analysis is conducted on the performance of the algorithmic parameters to provide guidance on how to tune parameters to prioritize speed, accuracy, or a combination of both. T

关键词： Computer science attribute-based access control combinatorial testing covering array locating array randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized GENERATION OF ERROR CONTROL CODES WITH AUTOMATA AND TRANSDUCERS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2018年第2-4期52卷 169-184页

作者： Konstantinidis, Stavros Moreira, Nelma Reis, Rogerio St Marys Univ Dept Math & Comp Sci Halifax NS Canada Univ Porto CMUP Fac Ciencias Rua Campo Alegre P-4169007 Porto Portugal Univ Porto DCC Fac Ciencias Rua Campo Alegre P-4169007 Porto Portugal

We introduce the concept of an f-maximal error-detecting block code, for some parameter f in (0,1), in order to formalize the situation where a block code is close to maximal with respect to being error-detecting. Our motivation for this is that it is computationally hard to decide whether an error-detecting block code is maximal. We present an output-polynomial time randomized algorithm that takes as input two positive integers N, l and a specification of the errors permitted in some application, and generates an error-detecting, or error-correcting, block code of length l that is 99%-maximal, or contains N words with a high likelihood. We model error specifications as (nondeterministic) transducers, which allow one to represent any rational combination of substitution and synchronization errors. We also present some elements of our implementation of various error-detecting properties and their associated methods. Then, we show several tests of the implemented randomized algorithm on various error specifications. A methodological contribution is the presentation of how various desirable error combinations can be expressed formally and processed algorithmically.

关键词： randomized algorithm output polynomial time algorithm error control codes maximal codes synchronization errors combinatorial channels

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：