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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Minimizing I/O in Toom-Cook algorithms 30th

Minimizing I/O in Toom-Cook Algorithms

引用

30th European Conference on Parallel and Distributed Processing (Euro-Par)

作者： Nissim, Roy Schwartz, Oded Spiizer, Yuval Hebrew Univ Jerusalem Jerusalem Israel Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9783031695827;9783031695834

Long integer multiplication is a fundamental kernel in many linear algebra and cryptography computations. Toom-Cook-k (k is an element of N) are a family of fast long integer multiplication algorithms frequently used in many applications, particularly for small k sizes (2, 3, and 4). Previous studies focus on minimizing Toom-Cook's arithmetic cost, sometimes at the expense of asymptotically higher communication costs and memory footprint. For many high-performance computing applications, the bottleneck is communication rather than arithmetic. We propose new versions of Toom-Cook-k algorithms that simultaneously reduce their arithmetic cost, communication cost, and memory footprint. We obtain these results by utilizing the alternative basis and Toom-Graph techniques. The arithmetic costs of the new algorithms are only slightly higher than that of the best previous solution, while the communication costs and memory footprint are significantly reduced and proved to be optimal.

关键词： Fast Long Integer Multiplication I/O Complexity Alternative Basis Method bilinear algorithms Toom-Cook Toom-Graph

来源：评论

学校读者我要写书评

暂无评论

Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation 23

Towards Practical Fast Matrix Multiplication based on Trilin...

引用

48th International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Hadas, Tor Schwartz, Oded Hebrew Univ Jerusalem Jerusalem Israel

ISBN: (纸本)9798400700392

Pan's four decades old fast matrix multiplication algorithms have the lowest asymptotic complexity of all currently known algorithms applicable to matrices of feasible dimensions. However, the large coefficients in the arithmetic cost of these algorithms make them impractical. We reduce these coefficients by 90%-98%, in some cases to a value of 2, the same leading coefficient as the classical, cubic time algorithm. For this purpose, we utilize fast recursive transformations with sparsification of the linear operators of Pan's algorithms. Existing decomposition methods cannot be applied to Pan's algorithms due to their large base cases. We describe two new methods for finding such decompositions, by utilizing the underlying symmetries of the algorithms, and the linear transformations within the algorithms. With these tools, we obtain algorithms with the same asymptotic complexity as Pan's algorithms, but with small leading coefficients, often the same as that of the cubic time algorithm. In practice, these new algorithms have the potential to outperform the fastest currently known matrix multiplication algorithms on feasible sized inputs. Matched against known lower bounds, we show that our results are optimal or close to being optimal.

关键词： Matrix Multiplication bilinear algorithms Trilinear Aggregation Fast Basis Transformation Fast Recursive Transformation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Faster Matrix Multiplication via Sparse Decomposition 19

Faster Matrix Multiplication via Sparse Decomposition

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Beniamini, Gal Schwartz, Oded Hebrew Univ Jerusalem Jerusalem Israel

ISBN: (纸本)9781450361842

Fast matrix multiplication algorithms are of practical use only if the leading coefficient of their arithmetic complexity is sufficiently small. Many algorithms with low asymptotic cost have large leading coefficients, and are thus impractical. Karstadt and Schwartz have recently demonstrated a technique that reduces the leading coefficient by introducing fast O(n(2) logn) basis transformations, applied to the input and output matrices. We generalize their technique, by allowing larger bases for the transformations while maintaining low overhead. Thus we accelerate several matrix multiplication algorithms, beyond what is known to be possible using the previous technique. Of particular interest are a few new sub-cubic algorithms with leading coefficient 2, matching that of classical matrix multiplication. For example, we obtain an algorithm with arithmetic complexity of 2n(log3) (23) + o(n(log3) (23)) compared to 2n(3) - n(2) of the classical algorithm. Such new algorithms can outperform previous ones (classical included) even on relatively small matrices. We obtain lower bounds matching the coefficient of several of our algorithms, proving them to be optimal.

关键词： Fast Matrix Multiplication bilinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Matrix Multiplication, a Little Faster

引用

JOURNAL OF THE ACM 2020年第1期67卷 1-1页

作者： Karstadt, Elaye Schwartz, Oded Hebrew Univ Jerusalem Sch Comp Sci & Engn Rothberg Family BldgEdmond J Safra Campus IL-9190416 Jerusalem Israel

Strassen's algorithm (1969) was the first sub-cubic matrix multiplication algorithm. Winograd (1971) improved the leading coefficient of its complexity from 6 to 7. There have been many subsequent asymptotic improvements. Unfortunately, most of these have the disadvantage of very large, often gigantic, hidden constants. Consequently, Strassen-Winograd's O(n(log2)(7)) algorithm often outperforms other fast matrix multiplication algorithms for all feasible matrix dimensions. The leading coefficient of Strassen-Winograd's algorithm has been generally believed to be optimal for matrix multiplication algorithms with a 2 x 2 base case, due to the lower bounds by Probert (1976) and Bshouty (1995). 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 leading 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 also prove a generalization of Probert's and Bshouty's lower bounds 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, and is therefore optimal We apply our method to other fast matrix multiplication algorithms, improving their arithmetic and communication costs by significant constant factors.

关键词： Fast matrix multiplication bilinear algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：