Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Convolution: Math, Graphics, and Discrete Signals01:24

Convolution: 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...
262
Convolution Properties I01:20

Convolution 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:
152
Convolution Properties II01:17

Convolution 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...
203
Fast Fourier Transform01:10

Fast 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)log⁡2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
330
Ampere-Maxwell's Law: Problem-Solving01:17

Ampere-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...
631
Vector Operations01:20

Vector 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.
1.3K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Improved Distance Queries and Cycle Counting by Frobenius Normal Form.

Theory of computing systems·2019
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Jul 6, 2025

Deep Neural Networks for Image-Based Dietary Assessment
13:19

Deep Neural Networks for Image-Based Dietary Assessment

Published on: March 13, 2021

9.2K

Computing Generalized Convolutions Faster Than Brute Force.

Barış Can Esmer1, Ariel Kulik1, Dániel Marx1

  • 1CISPA Helmholtz Center for Information Security, Saarbrücken, Germany.

Algorithmica
|January 8, 2024
PubMed
Summary
This summary is machine-generated.

We introduce a generalized convolution, the f-Convolution, applicable to various discrete structures. Our research provides an efficient algorithm to compute f-Convolution in polynomial time, significantly improving upon naive methods.

Keywords:
Fast Fourier TransformFast Subset ConvolutionGeneralized ConvolutionOrthogonal Vectors

More Related Videos

An Experimental Protocol for Assessing the Performance of New Ultrasound Probes Based on CMUT Technology in Application to Brain Imaging
16:01

An 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
Automated Midline Shift and Intracranial Pressure Estimation based on Brain CT Images
14:08

Automated Midline Shift and Intracranial Pressure Estimation based on Brain CT Images

Published on: April 13, 2013

42.6K

Related Experiment Videos

Last Updated: Jul 6, 2025

Deep Neural Networks for Image-Based Dietary Assessment
13:19

Deep Neural Networks for Image-Based Dietary Assessment

Published on: March 13, 2021

9.2K
An Experimental Protocol for Assessing the Performance of New Ultrasound Probes Based on CMUT Technology in Application to Brain Imaging
16:01

An 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
Automated Midline Shift and Intracranial Pressure Estimation based on Brain CT Images
14:08

Automated Midline Shift and Intracranial Pressure Estimation based on Brain CT Images

Published on: April 13, 2013

42.6K

Area of Science:

  • Discrete Mathematics
  • Theoretical Computer Science
  • Algorithm Analysis

Background:

  • Introduces a generalized convolution operation, termed f-Convolution, defined over finite domains and vector spaces.
  • This operation unifies and extends several known convolution types, including Subset Convolution, XOR Product, Covering Product, and Packing Product.
  • The naive brute-force computation of f-Convolution has a time complexity of O(n^d), where d is the domain size.

Purpose of the Study:

  • To develop a more efficient algorithm for computing the generalized f-Convolution.
  • To analyze the computational complexity of the proposed algorithm and compare it with the naive approach.
  • To introduce and solve the f-Query problem, a generalization of the Orthogonal Vectors problem.

Main Methods:

  • Proposes an exact computation of f-Convolution in O(n^(d/2)) time for constant d when the domain has even cardinality.
  • Utilizes a novel technique involving cyclic partitions of functions to accelerate the convolution computation.
  • Develops an O(n^d * M(n^(1-1/d))) algorithm for the f-Query problem, where M(k) is the time for k x k matrix multiplication.

Main Results:

  • Achieves a significant asymptotic improvement for f-Convolution computation over the brute-force method.
  • Demonstrates the existence of suitable cyclic partitions for any function f.
  • Provides an efficient solution for the f-Query problem, generalizing the Orthogonal Vectors problem.

Conclusions:

  • The proposed cyclic partition method offers a substantial speedup for computing generalized convolutions.
  • The f-Query problem can be solved efficiently, with its complexity related to state-of-the-art matrix multiplication.
  • This work opens new avenues for efficiently solving problems involving generalized convolution operations in theoretical computer science.