相关实验视频
Updated: Jul 6, 2025
13:19
Deep Neural Networks for Image-Based Dietary Assessment
Published on: March 13, 2021
9.2K
计算通用卷积比原始力更快
Barış Can Esmer1, Ariel Kulik1, Dániel Marx1
1CISPA Helmholtz Center for Information Security, Saarbrücken, Germany.
Algorithmica
|January 8, 2024
概括
我们介绍了一个通用的卷积,f-卷积,适用于各种离散结构. 我们的研究提供了一个高效的算法来计算f-Convolution在多项式时间,显著改进了天真的方法.
科学领域:
- 离散数学 离散数学 离散数学
- 理论计算机科学 理论计算机科学
- 算法分析 算法分析
背景情况:
- 介绍了一个通用的卷积运算,称为f-Convolution,定义在有限的域和向量空间上.
- 这个操作统一和扩展了几个已知的卷积类型,包括子集卷积,XOR产品,覆盖产品和包装产品.
- f-Convolution 的天真粗暴力计算的时间复杂度为 O ((n^d),其中 d 是域大小.
研究的目的:
- 开发一种更有效的算法来计算一般化的f-Convolution.
- 分析拟议的算法的计算复杂性,并将其与天真方法进行比较.
- 为了介绍和解决f-Query问题,对直角向量问题的概括.
主要方法:
- 提出了一个精确的计算f-Convolution在O(n^(d/2)) 时间的常数d当域有偶数的枢纽.
- 使用一种涉及函数循环分区的新技术来加速卷积计算.
- 开发了一个O(n^d * M(n^(1-1/d))) 算法用于f-Query问题,其中M(k) 是k x k矩阵乘法的时间.
主要成果:
- 在f-Convolution计算中比原始力方法取得了显著的非对称改进.
- 证明任何函数 f. 存在合适的循环分区.
- 为 f-Query 问题提供了一个有效的解决方案,将直角向量问题概括起来.
结论:
- 拟议的循环分区方法为计算通用卷积提供了相当大的加速.
- 可以有效地解决f-Query问题,其复杂性与最先进的矩阵乘法有关.
- 这项工作为有效解决理论计算机科学中涉及一般化卷积运算的问题开辟了新的途径.
更多相关视频
16:01An Experimental Protocol for Assessing the Performance of New Ultrasound Probes Based on CMUT Technology in Application to Brain Imaging
Published on: September 24, 2017
10.5K
14:08Automated Midline Shift and Intracranial Pressure Estimation based on Brain CT Images
Published on: April 13, 2013
42.6K
相关概念视频
01:24Convolution: Math, Graphics, and Discrete Signals
262
In any LTI (Linear Time-Invariant) system, the convolution of two signals is denoted using a convolution operator, assuming all initial conditions are zero. The convolution integral can be divided into two parts: the zero-input or natural response and the zero-state or forced response, with t0 indicating the initial time.
To simplify the convolution integral, it is assumed that both the input signal and impulse response are zero for negative time values. The graphical convolution process...
To simplify the convolution integral, it is assumed that both the input signal and impulse response are zero for negative time values. The graphical convolution process...
262
01:20Convolution Properties I
152
Convolution computations can be simplified by utilizing their inherent properties.
The commutative property reveals that the input and the impulse response of an LTI (Linear Time-Invariant) system can be interchanged without affecting the output:
The commutative property reveals that the input and the impulse response of an LTI (Linear Time-Invariant) system can be interchanged without affecting the output:
152
01:17Convolution Properties II
203
The important convolution properties include width, area, differentiation, and integration properties.
The width property indicates that if the durations of input signals are T1 and T2, then the width of the output response equals the sum of both durations, irrespective of the shapes of the two functions. For instance, convolving two rectangular pulses with durations of 2 seconds and 1 second results in a function with a width of 3 seconds.
The area property asserts that the area under the...
The width property indicates that if the durations of input signals are T1 and T2, then the width of the output response equals the sum of both durations, irrespective of the shapes of the two functions. For instance, convolving two rectangular pulses with durations of 2 seconds and 1 second results in a function with a width of 3 seconds.
The area property asserts that the area under the...
203
01:10Fast Fourier Transform
330
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
The computational efficiency of the FFT becomes...
330
01:17Ampere-Maxwell's Law: Problem-Solving
631
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
631
01:20Vector Operations
1.3K
Vectors are physical quantities that have both magnitude and direction. The vector operations include addition, subtraction, and scalar multiplication.
A vector multiplied by a scalar value is called scalar multiplication. The result obtained is a new vector with a different magnitude. If the scalar is positive, the direction of the vector remains the same, but if it is negative, the direction of the vector is reversed. For example, the product of the mass and velocity yields the momentum.
A vector multiplied by a scalar value is called scalar multiplication. The result obtained is a new vector with a different magnitude. If the scalar is positive, the direction of the vector remains the same, but if it is negative, the direction of the vector is reversed. For example, the product of the mass and velocity yields the momentum.
1.3K