Sparse convolution in python using Toeplitz convolution matrix multiplication.
Project description
sparse_convolution
Sparse convolution in python.
Uses Toeplitz convolutional matrix multiplication to perform sparse convolution.
This allows for extremely fast convolution when:
- The kernel is small (<= 30x30)
- The input array is sparse (<= 1% density)
- Many arrays are convolved with the same kernel
Install:
git clone https://github.com/RichieHakim/sparse_convolution
cd sparse_convolution
pip install -e .
Basic usage:
Convolve a single sparse 2D array with a 2D kernel.
import sparse_convolution as sc
import numpy as np
import scipy.sparse
# Create a single sparse matrix
A = scipy.sparse.rand(100, 100, density=0.1)
# Create a dense kernel
B = np.random.rand(3, 3)
# Prepare class
conv = Toeplitz_convolution2d(
x_shape=A.shape,
k=B,
mode='same',
dtype=np.float32,
)
# Convolve
C = conv(
x=A,
batching=False,
mode='same',
).toarray()
Batching usage:
Convolve multiple sparse 2D arrays with a 2D kernel.
The input arrays must be reshaped into flattened vectors and stacked into a single sparse array of shape: (n_arrays, height * width)
.
import sparse_convolution as sc
import numpy as np
import scipy.sparse
# Create multiple sparse matrices
# note that the shape of A will be (3, 100**2)
A = scipy.sparse.vstack([
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
]).tocsr()
# Create a dense kernel
B = np.random.rand(3, 3)
# Prepare class
conv = sc.Toeplitz_convolution2d(
x_shape=(100, 100), # note that the input shape here is (100, 100)
k=B,
mode='same',
dtype=np.float32,
)
# Convolve
C = conv(
x=A,
batching=True,
mode='same',
)
# Reshape the output back to (3, 100, 100)
C_reshaped = np.stack([c.reshape(100, 100).toarray() for c in C], axis=0)
References
- See: https://stackoverflow.com/a/51865516 and https://github.com/alisaaalehi/convolution_as_multiplication for a nice illustration.
- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.convolution_matrix.html for 1D version.
- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.matmul_toeplitz.html#scipy.linalg.matmul_toeplitz for potential ways to make this implementation faster.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Close
Hashes for sparse_convolution-0.1.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 52530c64b6941127e3f3732e59a5c805505db7b5b0024d54a5e20f2e5da1246c |
|
MD5 | a8b20d5df98f99070b62c913edd266c2 |
|
BLAKE2b-256 | 3caeeaa1b31e12ae486d36c83f5890a8f1278323febd57519c5bda079eac9f8f |