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

A bilinear algorithm of length 22 for approximate multiplication of 2 x 7 and 7 x 2 matrices

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2015年第4期55卷 541-545页

作者： Smirnov, A. V. Russian Fed Ctr Forens Examinat Dept Justice Moscow 109028 Russia

A bilinear algorithm of bilinear complexity 22 for approximate multiplication of 2 x 7 and 7 x 2 matrices is presented. An upper bound is given for the bilinear complexity of approximate multiplication of 2 x 2 and 2 ... 详细信息

关键词： matrix multiplication fast algorithm for multiplying matrices bilinear algorithm approximate bilinear algorithm bilinear complexity length of algorithm

来源：评论

学校读者我要写书评

暂无评论

Half-Unit Weighted bilinear algorithm for Image Contrast Enhancement in Capsule Endoscopy 9

Half-Unit Weighted Bilinear Algorithm for Image Contrast Enh...

引用

9th International Conference on Graphic and Image Processing (ICGIP)

作者： Rukundo, Olivier Norwegian Univ Sci & Technol Dept Comp Sci Trondheim Norway

ISBN: (数字)9781510617421

ISBN: (纸本)9781510617421

This paper proposes a novel enhancement method based exclusively on the bilinear interpolation algorithm for capsule endoscopy images. The proposed method does not convert the original RBG image components to HSV or any other color space or model;instead, it processes directly RGB components. In each component, a group of four adjacent pixels and half-unit weight in the bilinear weighting function are used to calculate the average pixel value, identical for each pixel in that particular group. After calculations, groups of identical pixels are overlapped successively in horizontal and vertical directions to achieve a preliminary-enhanced image. The final-enhanced image is achieved by halving the sum of the original and preliminary-enhanced image pixels. Quantitative and qualitative experiments were conducted focusing on pairwise comparisons between original and enhanced images. Final-enhanced images have generally the best diagnostic quality and gave more details about the visibility of vessels and structures in capsule endoscopy images.

关键词： half-unit weight bilinear algorithm capsule endoscopy color image enhancement diagnostic quality

来源：评论

学校读者我要写书评

暂无评论

Communication Lower Bounds for Nested bilinear algorithms via Rank Expansion of Kronecker Products

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2025年第1期25卷 55-101页

作者： Ju, Caleb Zhang, Yifan Solomonik, Edgar Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Texas Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Univ Illinois Dept Comp Sci Champaign IL 61801 USA

We develop lower bounds on communication in the memory hierarchy or between processors for nested bilinear algorithms, such as Strassen's algorithm for matrix multiplication. We build on a previous framework that establishes communication lower bounds by use of the rank expansion, or the minimum rank of any fixed size subset of columns of a matrix, for each of the three matrices encoding a bilinear algorithm. This framework provides lower bounds for a class of dependency directed acyclic graphs (DAGs) corresponding to the execution of a given bilinear algorithm, in contrast to other approaches that yield bounds for specific DAGs. However, our lower bounds only apply to executions that do not compute the same DAG node multiple times. Two bilinear algorithms can be nested by taking Kronecker products between their encoding matrices. Our main result is a lower bound on the rank expansion of a matrix constructed by a Kronecker product derived from lower bounds on the rank expansion of the Kronecker product's operands. We apply the rank expansion lower bounds to obtain novel communication lower bounds for nested Toom-Cook convolution, Strassen's algorithm, and fast algorithms for contraction of partially symmetric tensors.

关键词： Communication lower bounds bilinear algorithm Kronecker product Rank expansion Strassen's algorithm Convolution Tensor contraction

来源：评论

学校读者我要写书评

暂无评论

Quantum circuit implementation for F28 multiplication based on algebraic curve method

引用

QUANTUM INFORMATION PROCESSING 2025年第5期24卷 1-28页

作者： Liao, Haoyu Luo, Qingbin Zheng, Yuanmeng Lv, Yi Ding, Lang Hubei Minzu Univ Sch Math & Stat Enshi 445000 Hubei Peoples R China Hubei Minzu Univ Coll Intelligent Syst Sci & Engn Enshi 445000 Hubei Peoples R China

Binary field multiplication is widely used in quantum information processing, such as quantum algorithms, cryptanalysis and mathematical arithmetic. The core quantum resources of binary field multiplication are the qubit count and Toffoli depth of its quantum circuit, both of which are largely dependent on the Toffoli gate count. In this paper, we analyze the multiplicative complexity of binary field and present quantum circuits for F28 multiplication from the perspective of time and space. We find that the Toffoli gate count of quantum circuit corresponds to the bilinear complexity in F2n multiplication. The Toffoli gate count obtained by the algebraic curve method increases linearly with n, which is slower than the sub-quadratic complexity of Karatsuba algorithm and the iterated logarithm complexity of Chinese remainder theorem (CRT). To demonstrate the advantages of the algebraic curve method, we use elliptic curve bilinear algorithm in F(22)4 and composite field arithmetic (CFA) to present two types quantum circuits for F28 multiplication, both of which have 24 Toffoli gates and are the lowest at present. The Toffoli depth of the time-efficient quantum circuit is only 1, and the product D.W of the depth and width of the circuit is 72, which is lower than before. The space-efficient quantum circuits require 24 qubits and maintain the Toffoli depth of 4, their D.W and Toffoli depth are reduced by at least 77.8% compared with the most advanced research.

关键词： Quantum circuit Binary field multiplication Algebraic curve bilinear algorithm Multiplicative complexity Composite field arithmetic

来源：评论

学校读者我要写书评

暂无评论

Parallel matrix multiplication on a linear array with a reconfigurable pipelined bus system

引用

IEEE TRANSACTIONS ON COMPUTERS 2001年第5期50卷 519-525页

作者： Li, KQ Pan, VY SUNY Coll New Paltz Dept Comp Sci New Paltz NY 12561 USA CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

The known fast sequential algorithms for multiplying two N x N matrices lover an arbitrary ring) have time complexity O(N(alpha)), where 2 p less than or equal to N(alpha), multiplying two N x N matrices can be perf... 详细信息

The known fast sequential algorithms for multiplying two N x N matrices lover an arbitrary ring) have time complexity O(N(alpha)), where 2 < < 3. The current best value of a is less than 2.3755. We show that, for all 1 p less than or equal to N(alpha), multiplying two N x N matrices can be performed on a p-processor linear array with a reconfigurable pipelined bus system (LARPBS) in O(N(alpha)/p + (N(2)/p(2)/alpha) log p) time. This is currently the fastest parallelization of the best known sequential matrix multiplication algorithm on a distributed memory parallel system. In particular, for all 1 less than or equal to P less than or equal to N(2.3755), multiplying two iii x N matrices can be performed on a p-processor LARPBS in O(N(2.3755)/p + (N(2)/p(2)/alpha) log p) time and linear speedup can be achieved for p as large as O(N(2.3755)/(log N)(6.3262)). Furthermore. multiplying two N x N matrices can be performed on an LARPBS with O(N(alpha)) processors in O(log N) time. This compares favorably with the performance on a PRAM.

关键词： bilinear algorithm cost-optimality distributed memory system linear array matrix multiplication optical pipelined bus PRAM reconfigurable system speedup

来源：评论

学校读者我要写书评

暂无评论

Fast rectangular matrix multiplication and some applications

引用

Science China Mathematics 2008年第3期51卷 389-406页

作者： Victor Y PAN Department of Mathematics and Computer Science.Lehman College City University of New York BronxNew York 10468 USA

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.

关键词： rectangular matrix multiplication asymptotic arithmetic complexity bilinear algorithm polynomial factorization over finite fields 68Q25 11Y16

来源：评论

学校读者我要写书评

暂无评论

PEBBLING GAME AND ALTERNATIVE BASIS FOR HIGH PERFORMANCE MATRIX MULTIPLICATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2023年第6期45卷 C277-C303页

作者： Schwartz, Oded Vaknin, Noa Hebrew Univ Jerusalem Rachel & Selim Benin Sch Comp Sci & Engn Jerusalem Israel

Matrix multiplication is one of the most extensively used kernels in scientific computing. Although subcubic algorithms exist, most high performance implementations are based on the classical \Theta (n3) matrix multiplication. Designing an algorithm that obtains even modest improvements in performance over existing implementations, requires carefully addressing challenges such as reducing computation costs, communication costs, and memory footprint. We provide the first high performance general matrix-matrix multiplication that utilizes the alternative basis method on Strassen's algorithm. We reduce the basis transformation overheads and decrease the memory footprint of the bilinear phase by using the pebbling game optimization scheme, consequentially improving both arithmetic and communication costs. Our algorithm outperforms DGEMM on feasible matrix dimensions starting at n = 96. It obtains an increasing speedup of up to nearly \times 2 speedup for larger matrix dimensions when running sequentially, and even larger speedups for certain matrix dimensions when running in parallel.

关键词： fast matrix multiplication bilinear algorithm pebbling game alternative basis method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：