Ticket #1411 (closed enhancement: fixed)
Speed up spatially varying convolution by interpolating over a specified block size
Reported by: | rowen | Owned by: | rowen |
---|---|---|---|
Priority: | normal | Milestone: | |
Component: | afw | Keywords: | |
Cc: | rhl, rowen, bick, jarvis | Blocked By: | |
Blocking: | Project: | LSST | |
Version Number: | 3.6.0 | ||
How to repeat: |
not applicable |
Description
My attempt to use linear interpolation by detecting the block size over which to convolve did not work. Somebody suggested simply specifying the block size over which to convolve and this seems like an excellent idea to me. Very simple and it should work. I hope to also support the piecewise constant approximation since it requires very similar code and parameters and will allow direct performance comparison with Andy Becker's HOTPANTS code.
Change History
comment:2 Changed 9 years ago by rowen
To expand on "did not work": my test for whether linear interpolation was suitably accurate at a given scale almost always failed, so linear interpolation was rarely used. I could try a fancier test, but would prefer to try a simpler alternative.
comment:4 Changed 9 years ago by rhl
- Cc jarvis added
How are you planning to confirm that the scale chosen is correct? This sounds like a dangerous option to me.
I'm surprised that, given the known functional form of the Kernel variation, you cannot figure out the interpolation scale without the expense that you are currently going to. What does Mike Jarvis do?
comment:5 Changed 9 years ago by rowen
- Status changed from assigned to closed
- Resolution set to fixed
I expect convolution over a spatial scale of 10 pixels should be safe and I doubt interpolating over larger scales is not likely to supply much additional speedup. Thus I have implemented it as stated. Martin wanted something fancier with kernels presenting their spatial scale and will make that a new ticket, but I do not plan to implement it for PT 1.1 and I doubt we need it at all.
Here are my timings on lsst8
afw ticket 1411: -bash-3.2$ examples/timeSpatiallyVaryingConvolve.py $AFWDATA_DIR/871034p_1_MI All kernels use a spatial model of a Polynomial2 of order 3 AnalyticKernel using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 33.85 2112 4644 11 11 142.92 2112 4644 19 19 418.49 AnalyticKernel using linear interpolation over 10 x 10 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 8.47 2112 4644 11 11 29.52 2112 4644 19 19 82.82 AnalyticKernel using linear interpolation over 20 x 20 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 6.11 2112 4644 11 11 25.60 2112 4644 19 19 75.52 SeparableKernel using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 16.57 2112 4644 11 11 45.07 2112 4644 19 19 103.94 LinearCombinationKernel with 5 Gaussian Basis Kernels using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 14.02 2112 4644 11 11 38.74 2112 4644 19 19 102.46 LinearCombinationKernel with 5 Gaussian Basis Kernels using linear interpolation over 10 x 10 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 8.16 2112 4644 11 11 27.26 2112 4644 19 19 72.75 LinearCombinationKernel with 5 Gaussian Basis Kernels using linear interpolation over 20 x 20 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 5.98 2112 4644 11 11 24.03 2112 4644 19 19 68.03 LinearCombinationKernel with Delta Function Basis using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 21.72 2112 4644 11 11 55.07 2112 4644 19 19 144.88 LinearCombinationKernel with Delta Function Basis using linear interpolation over 10 x 10 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 8.26 2112 4644 11 11 27.39 2112 4644 19 19 73.05 LinearCombinationKernel with Delta Function Basis using linear interpolation over 20 x 20 pixels ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 6.01 2112 4644 11 11 24.09 2112 4644 19 19 68.11 afw 3.6.0 I did not run interpolation tests since interpolation was rarely if ever used in afw 3.6.0 (the issue this ticket attempts to correct). -bash-3.2$ python timeOldSpatiallyVaryingConvolve.py All kernels use a spatial model of a Polynomial2 of order 3 -bash-3.2$ python timeOldSpatiallyVaryingConvolve.py $AFWDATA_DIR/871034p_1_MI All kernels use a spatial model of a Polynomial2 of order 3 AnalyticKernel using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 35.79 2112 4644 11 11 143.49 2112 4644 19 19 416.57 SeparableKernel using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 16.22 2112 4644 11 11 43.45 2112 4644 19 19 102.90 LinearCombinationKernel with 5 Gaussian Basis Kernels using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 21.13 2112 4644 11 11 50.76 2112 4644 19 19 119.59 LinearCombinationKernel with Delta Function Basis using no interpolation ImWid ImHt KerWid KerHt Sec/Cnv 2112 4644 5 5 72.98 2112 4644 11 11 356.12 2112 4644 19 19 1062.69
Comments:
- afw 3.6.0 has a specialization for delta function kernels but it is clearly not as fast as the Kreso algorithm for speeding up LinearCombinationKernels? by reducing the number of basis kernels. I removed that specialization in afw ticket 1411. (Kreso's algorithm was added in ticket #1437, which came after afw 3.6.0).
- The speedup is not as large as I had hoped (except for LinearCombinationKernels made up of delta function basis, where Kreso's algorithm is providing most of the gin). I will run profiling to see what is going on. One known issue is that I reallocate space for many kernel images during the interpolation (because the current design of KernelImagesForRegion does not permit reusing existing kernel image memory). That could certainly be changed, but I want proof that it is a significant problem first, since it is a safety feature.