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

Derivation and Analysis of Fast bilinear algorithms for Convolution

SIAM REVIEW 2020年第4期62卷 743-777页

作者： Ju, Caleb Solomonik, Edgar Univ Illinois Dept Comp Sci Urbana IL 61801 USA

The prevalence of convolution in applications within signal processing, deep neural networks, and numerical solvers has motivated the development of numerous fast convolution algorithms. In many of these problems, convolution is performed on terabytes or petabyte.s of data, so even constant factors of improvement can significantly reduce the computation time. We leverage the formalism of bilinear algorithms to describe and analyze all of the most popular approaches. This unified lens permits us to study the relationship between different variants of convolution as well as to derive error bounds and analyze the cost of the various algorithms. We provide new derivations, which predominantly leverage matrix and tensor algebra, to describe the Winograd family of convolution algorithms as well as reductions between ID and multidimensional convolution. We provide cost and error bounds as well as experimental numerical studies. Our experiments for two of these algorithms, the overlap-add approach and Winograd convolution algorithm with polynomials of degree greater than one, show that fast convolution algorithms can rival the accuracy of the fast Fourier transform without using complex arithmetic. These algorithms can be used for convolution problems with multidimensional inputs or for filters larger than size of four, extending the state of the art in Winograd-based convolution algorithms.

关键词： convolution bilinear algorithms Winograd convolution convolutional neural networks

来源：评论

学校读者我要写书评

暂无评论

COMMUNICATION LOWER BOUNDS OF bilinear algorithms FOR SYMMETRIC TENSOR CONTRACTIONS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第5期43卷 A3328-A3356页

作者： Solomonik, Edgar Demmel, James Hoefler, Torsten Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Calif Berkeley Dept EECS Div Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Swiss Fed Inst Technol Dept Comp Sci CH-8092 Zurich Switzerland

We introduce a new theoretical framework for deriving lower bounds on data movement in bilinear algorithms. bilinear algorithms are a general representation of fast algorithms for bilinear functions, which include computation of matrix multiplication, convolution, and symmetric tensor contractions. A bilinear algorithm is described by three matrices. Our communication lower bounds are based on quantifying the minimal matrix ranks of matching subsets of columns of these matrices. This infrastructure yields new lower bounds for symmetric tensor contraction algorithms, which provide new qualitative insights. Tensor symmetry (invariance under permutation of modes) is common to many applications of tensor computations (e.g., tensor representation of hypergraphs, analysis of high-order moments in data, as well as tensors modeling interactions of electrons in computational chemistry). Tensor symmetry enables reduction in representation size as well as contraction cost by factors that scale with the number of equivalent permutations. However, we derive lower bounds showing that these cost and memory reductions can necessitate increases in data movement by factors that scale with the size of the tensors.

关键词： communication lower bounds bilinear algorithms tensor contractions tensor symmetry quantum chemistry

来源：评论

学校读者我要写书评

暂无评论

On bilinear algorithms over fields of different characteristics

引用

Moscow University Computational Mathematics and Cybernetics 2013年第4期37卷 189-194页

作者： Lysikov, V.V. Moscow State University Moscow 119991 Russian Federation

关键词： algebraic complexity theory bilinear algorithms

来源：评论

学校读者我要写书评

暂无评论

THE LOWER BOUNDS ON THE ADDITIVE COMPLEXITY OF bilinear PROBLEMS IN TERMS OF SOME ALGEBRAIC QUANTITIES

引用

INFORMATION PROCESSING LETTERS 1981年第2期13卷 71-72页

作者： PAN, VY STANFORD UNIV DEPT COMP SCISTANFORDCA 94305

Until very recently, the lower bounds on the additive complexity of intensively studied linear and bilinear arithmetic algorithms for arithmetic computational problems have relied on the active operation-basic substitution argument. Consequently, these bounds have not exceeded the dimension of the problems that is the total number of input variables and outputs. Another approach to the problem follows from the method presented by J. Morgenstern. A third approach reduces the problem to the study of a strong regularity of matrices. Mathematical notation.

关键词： Additive complexity bilinear algorithms tensor rank

来源：评论

学校读者我要写书评

暂无评论

On the approximate bilinear complexity of matrix multiplication

引用

Moscow University Computational Mathematics and Cybernetics 2014年第4期38卷 177-180页

作者： Trefilov, A.P. Department of Computational Mathematics and Cybernetics Moscow State University Moscow 119991 Russian Federation

It is shown that the approximate bilinear complexity of multiplying matrices of the order 2 × 2 by a matrix of the order 2 × 6 does not exceed 19. An approximate bilinear algorithm of complexity 19 is presen... 详细信息

关键词： approximate algorithms bilinear algorithms matrix multiplication matrix tensors

来源：评论

学校读者我要写书评

暂无评论

On bilinear Techniques for Similarity Search and Boolean Matrix Multiplication

On Bilinear Techniques for Similarity Search and Boolean Mat...

引用

作者： Karppa, Matti Aalto University

学位级别：博士

algorithms are the art of efficient computation: it is by the power of algorithms that solving problems becomes feasible, and that we may harness the power of computing machinery. Efficient algorithms translate directly to savings in resources, such as time, storage space, and electricity, and thus money. With the end of the exponential increase in the computational power of hardware, the value of efficient algorithms may be greater than ever. This thesis presents advancements in multiple fields of algorithms, related through the application of bilinear techniques. Functions that map elements from a pair of vector spaces to a third vector space with the property that they are linear in their arguments, or bilinear maps, are a ubiquitous and fundamental mathematical tool, the canonical example being the matrix multiplication. We address both the applications that make use of bilinear maps and the computation of the bilinear maps itself, Boolean matrix multiplication in particular. In the field of similarity search, we improve on Valiant’s randomized algorithm [FOCS 2012; J. ACM 2015] for finding correlated vectors by (i) presenting an improved sampling scheme that enables faster processing by using fast matrix multiplication, and (ii) derandomizing Valiant’s algorithm. These results are mostly of theoretical nature since they rely on fast matrix multiplication. We also present (iii) an adaptive prefix-assignment method for symmetry breaking. An instantiation of McKay’s canonical extension framework [J. algorithms 1998], the method produces a set of partial assignments with respect to a sequence of a prefix of variables in a system of constraints, such that all generated assignments are pairwise nonisomorphic. The method breaks the symmetries completely with respect to the prefix sequence, and can benefit from an auxiliary representation of symmetries in the form of a colored graph. We also provide an implementation that works as a preprocessor for Boolean satisfiabil

关键词： bilinear algorithms matrix multiplication similarity search symmetry breaking bilineaarialgoritmit matriisikertolasku samankaltaisuushaku symmetrian särkeminen

来源：评论

学校读者我要写书评

暂无评论

An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第10期59卷 6845-6850页

作者： Kaminski, Michael Xing, Chaoping Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Nanyang Technol Univ Div Math Sci Singapore 639798 Singapore

Let mu(q2)(n, k)denote the minimum number of multiplications required to compute the coefficients of the product of two degree nk - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the q(2) element field F-q2. It is shown that for all odd q and all n = 1,2,..., lim inf(k ->infinity) mu(q2)(n, k)/kn <= 2(1 + 1/q - 2). For the proof of this upper bound, we show that for an odd prime power q, all algebraic function fields in the Garcia-Stichtenoth tower F-q2 over have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.

关键词： Algebraic function fields bilinear algorithms finite fields polynomial multiplication the Garcia-Stichtenoth tower

来源：评论

学校读者我要写书评

暂无评论

Fast rectangular matrix multiplication and applications

引用

JOURNAL OF COMPLEXITY 1998年第2期14卷 257-299页

作者： Huang, XH Pan, VY CUNY Grad Sch & Univ Ctr Program Math New York NY 10036 USA CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of an n x n matrix by an n x n(2) matrix in arithmetic time O(n(omega)), omega = 3.333953..., which is less by 0.041 than the previous record 3.375477.... Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results: (a) we decrease from 2.851 to 2.837 the known exponent of *** bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n x n matrix, as well as for the solution to a nonsingular linear system of n equations, (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod x(n), yielding the complexity bound O(n(1.667)) versus the old record of O(n(1.688)), and for the univariate polynomial factorization over a finite field, and (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem with n constraints and n variables. (C) 1998 Academic Press.

关键词： rectangular matrix multiplication asymptotic arithmetic complexity bilinear algorithms parallel complexity polynomial composition polynomial factorization over finite fields linear programming

来源：评论

学校读者我要写书评

暂无评论

Matrix Multiplication, a Little Faster 17

Matrix Multiplication, a Little Faster

引用

29th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Karstadt, Elaye Schwartz, Oded Hebrew Univ Jerusalem Jerusalem Israel

ISBN: (纸本)9781450345934

Strassen's algorithm (1969) was the first sub-cubic matrix multiplication algorithm. Winograd (1971) improved its complexity by a constant factor. Many asymptotic improvements followed. Unfortunately, most of them have done so at the cost of very large, often gigantic, hidden constants. Consequently, Strassen-Winograd's O(n(log27)) algorithm often outperforms other matrix multiplication algorithms for all feasible matrix dimensions. The leading coefficient of Strassen-Winograd's algorithm was believed to be optimal for matrix multiplication algorithms with 2 x 2 base case, due to a lower bound of Probert (1976). Surprisingly, we obtain a faster matrix multiplication algorithm, with the same base case size and asymptotic complexity as Strassen-Winograd's algorithm, but with the coefficient reduced from 6 to 5. To this end, we extend Bodrato's (2010) method for matrix squaring, and transform matrices to an alternative basis. We prove a generalization of Probert's lower bound that holds under change of basis, showing that for matrix multiplication algorithms with a 2 x 2 base case, the leading coefficient of our algorithm cannot be further reduced, hence optimal. We apply our technique to other Strassen-like algorithms, improving their arithmetic and communication costs by significant constant factors.

关键词： Fast Matrix Multiplication bilinear algorithms

来源：评论

学校读者我要写书评

暂无评论

On Symmetries of Tensor Decompositions for the Commutator of 2 × 2 Matrices

引用

Computational Mathematics and Modeling 2019年第1期30卷 48-54页

作者： Lysikov, V.V. Chokaev, B.V. Saarland University Saarbrücken Germany Chechen State University Grozny Russian Federation

We consider symmetries of tensor decompositions related to an algorithm for computing the commutator of 2 × 2 matrices using 5 multiplications. © 2019, Springer Science+Business Media, LLC, part of Springer ... 详细信息

关键词： bilinear algorithms polyadic decompositions symmetries tensors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：