# Computing linear convolution efficiently

**URL:** <https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496>\
**Category:** New to Julia\
**Tags:** dsp\
**Created:** [August 16, 2021, 3:33pm UTC](https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496 "2021-08-16T15:33:47Z")\
**Posts on this page:** 3\
**Page:** 2

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [August 17, 2021, 8:06pm UTC](https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496/21 "2021-08-17T20:06:32Z")

</div>

Fair enough. But if you want to do repeated computations with the same kernel you will benefit from saving the invariant parts (for both options).

---

<div class="post-metadata">

**Author:** ![apo383](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/apo383/32/11272_2.png) [@apo383](https://discourse.julialang.org/u/apo383)\
**Post date:** [August 17, 2021, 9:01pm UTC](https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496/22 "2021-08-17T21:01:24Z")

</div>

I got a very modest 16 MB savings in allocations by using a view:

```julia
myconv(f,g) = @view DSP.conv(fftshift(f),g)[N:2N-1]
julia> @btime directconv($f,$g);
  305.838 ms (88 allocations: 183.11 MiB)
julia> @btime myconv($f,$g);
  295.373 ms (87 allocations: 167.85 MiB)

```

Part of what @GunnarFarneback was referring to is your definition of `F` outside of the function, which hides its allocations, about 38 MB, and therefore sees unfair advantage over the other methods.

```julia
julia> @btime toepconv($F,$g);
  393.324 ms (79 allocations: 106.82 MiB)
julia> toepconv2(f,g) = Toeplitz(f[1:N],f[vcat(1,2N-1:-1:N+1)])*g;
julia> @btime toepconv2($f,$g);
  388.091 ms (91 allocations: 144.96 MiB)

```

I do suspect it should be possible to simultaneously get the speed of `DSP.conv` and the allocations of `toepconv2`. For example, `fftshift(f)` allocates 30 MB by itself, which is more than the gap with `myconv` above. Perhaps it could be done in-place, or the convolution altered to avoid shifting at all. Or, there may be a way avoid the reflection in definition of `F`.

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [August 18, 2021, 5:24pm UTC](https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496/23 "2021-08-18T17:24:50Z")

</div>

Depending on your datatype you can also save a factor of 2 by using real valued FFTs `rfft`.

If you need performant wrappers for FFT convolution planning (depending on the type), you can also check out [FourierTools.jl](https://bionanoimaging.github.io/FourierTools.jl/dev/convolutions/#FourierTools.plan_conv) (no paid advertisement 😄)

We provide a wrapper to get a planned convolution similar to `plan_fft`, etc. That provides a little bit of speedup.

If you want to bring memory consumption to almost zero, you can also try `fft!` but which only works on complex arrays.

```julia
julia> using FFTW

julia> function plan_conv!(v; flags=FFTW.MEASURE)
           v_ft = fft(v)
           p = plan_fft!(copy(v), flags=flags)
           function conv!(u)
               u .= (p * u) .* v_ft
               return inv(p) * u
           end
           return conv!
       end
plan_in_place (generic function with 2 methods)

julia> v = randn(ComplexF32, (1024, 1024));

julia> u = randn(ComplexF32, (1024, 1024));

julia> @time my_conv! = plan_conv!(v);
  0.043965 seconds (25.53 k allocations: 9.676 MiB, 14.00% compilation time)

julia> @time my_conv! = plan_conv!(v);
  0.039729 seconds (65 allocations: 8.005 MiB)

julia> @time my_conv!(u);
  0.028485 seconds (21.88 k allocations: 8.962 MiB, 72.59% compilation time)

julia> @time my_conv!(u);
  0.007707 seconds (2 allocations: 160 bytes)

```

Edit: Note, that `plan_fft!` might overwrite the provided array with zeros. Hence we should copy it before!

EditEdit: I added now a generic version to [FourierTools.jl](https://github.com/bionanoimaging/FourierTools.jl/blob/d2b90f09777c97fd5fc3f27c3efc0dea14a9ae4e/src/convolutions.jl#L161) which works without any allocations during convolution itself (excluding planning).

[Previous page](https://discourse.julialang.org/t/computing-linear-convolution-efficiently/66496.md?page=1)
