Menu ▾ ▴

#765 Improve the 'filter()' function by using FFT

v1.1.x
closed
Erik Hänel
internal (109) function (25) matrix (13)
v1.1.5
Change Request
2023-03-01
2022-11-26
Erik Hänel
No

The filter() function is a relatively slow convolution of the matrix with the filter kernel. Evaluate, whether and when it is reasonable to use FFT/iFFT to calculate the convolution.

Analysis:

As discussed lately, we have to evaluate, when it is faster to use FFT combined with the necessary extension of the matrices (with zeros, clamped or reflected values) instead of manual convolution. The break-even might be quite early so that it is reasonable to completely replace the old implementation.

Implementation:

  • Implementation: Implemented the fft version of the matrix filter method and a wrapper function that automatically selects the fastest method depending on the kernel size.
  • Revision: [r1345]
  • Implementation test: Tested the new method with various random matrices. Detected and removed a bug where matrices with uneven dimensions would cause a crash. Tested the runtime of the two versions in a loop setup and iteratively decided on a threshold for the method selection. The threshold can definitely be improved, maybe even considering other factors than just kernel size.

Documentation:

  • [x] ChangesLog updated
  • [x] Code changes commented
  • Documentation articles:
    • [ ] corresponding documentation articles updated
    • [ ] new documentation articles created
    • [x] not needed
  • Language files:
    • [ ] corresponding language files updated
    • [x] not needed

Tests:

Speed up was tested in the automatic SW tests. No deviation detected.

Related

Commit: [r1345]

Discussion

  • Erik Hänel

    Erik Hänel - 2022-11-26
    • labels: --> internal, function, matrix
    • status: open --> accepted
     

  • Erik Hänel

    Erik Hänel - 2022-11-26
    • Description has changed:

    Diff:

    --- old
+++ new
@@ -1 +1,23 @@
 The `filter()` function is a relatively slow convolution of the matrix with the filter kernel. Evaluate, whether and when it is reasonable to use FFT/iFFT to calculate the convolution.
+
+###Analysis:
+(*Describe, what's the issue and which changes have to be made*)
+
+###Implementation:
+* Implementation: (*Describe, what you've changed*) 
+* Revision: [rXXX]
+* Implementation test: (*Describe the type of test, which you performed, and if it was successful*)
+
+###Documentation:
+* [ ] ChangesLog updated
+* [ ] Code changes commented
+* **Documentation articles:**

+    * [ ] corresponding documentation articles updated
+    * [ ] new documentation articles created
+    * [ ] not needed
+* **Language files:**
+    * [ ] corresponding language files updated
+    * [ ] not needed
+
+###Tests:
+(*Describe, which tests you performed and their outcome*)
    • status: accepted --> analyzing
     

  • Erik Hänel

    Erik Hänel - 2023-01-25
    • Description has changed:

    Diff:

    --- old
+++ new
@@ -1,7 +1,7 @@
 The `filter()` function is a relatively slow convolution of the matrix with the filter kernel. Evaluate, whether and when it is reasonable to use FFT/iFFT to calculate the convolution.

 ###Analysis:
-(*Describe, what's the issue and which changes have to be made*)
+As discussed lately, we have to evaluate, when it is faster to use FFT combined with the necessary extension of the matrices (with zeros, clamped or reflected values) instead of manual convolution. The break-even might be quite early so that it is reasonable to completely replace the old implementation.

 ###Implementation:

 * Implementation: (*Describe, what you've changed*)
    • status: analyzing --> implementing
    • assigned_to: Erik Hänel --> Raphael Zehner
     

  • Raphael Zehner

    Raphael Zehner - 2023-02-27
    • Description has changed:

    Diff:

    --- old
+++ new
@@ -4,20 +4,20 @@
 As discussed lately, we have to evaluate, when it is faster to use FFT combined with the necessary extension of the matrices (with zeros, clamped or reflected values) instead of manual convolution. The break-even might be quite early so that it is reasonable to completely replace the old implementation.

 ###Implementation:
-* Implementation: (*Describe, what you've changed*) 
-* Revision: [rXXX]
-* Implementation test: (*Describe the type of test, which you performed, and if it was successful*)
+* Implementation: Implemented the fft version of the matrix filter method and a wrapper function that automatically selects the fastest method depending on the kernel size.
+* Revision: [r1345]
+* Implementation test: Tested the new method with various random matrices. Detected and removed a bug where matrices with uneven dimensions would cause a crash. Tested the runtime of the two versions in a loop setup and iteratively decided on a threshold for the method selection. The threshold can definitely be improved, maybe even considering other factors than just kernel size.

 ###Documentation:
-* [ ] ChangesLog updated
-* [ ] Code changes commented
+* [x] ChangesLog updated
+* [x] Code changes commented

 * **Documentation articles:**
     * [ ] corresponding documentation articles updated
     * [ ] new documentation articles created
-    * [ ] not needed
+    * [x] not needed
 * **Language files:**
     * [ ] corresponding language files updated
-    * [ ] not needed
+    * [x] not needed

 ###Tests:
 (*Describe, which tests you performed and their outcome*)
    • status: implementing --> testing
    • assigned_to: Raphael Zehner --> Erik Hänel
     

    Related

    Commit: [r1345]

  • Erik Hänel

    Erik Hänel - 2023-03-01
    • Description has changed:

    Diff:

    --- old
+++ new
@@ -20,4 +20,4 @@

     * [x] not needed

 ###Tests:
-(*Describe, which tests you performed and their outcome*)
+Speed up was tested in the automatic SW tests. No deviation detected.
    • status: testing --> closed
     

Anonymous
Anonymous

Add attachments
Cancel





MongoDB Logo MongoDB