# 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.
Raw data
{
"_id": null,
"home_page": "https://github.com/RichieHakim/sparse_convolution",
"name": "sparse-convolution",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "sparse convolution Toeplitz python",
"author": "Richard Hakim",
"author_email": "richhakim@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/3a/9a/1ba292348b356c6b8c3504caa074babcfac57f8571c9058ae774d8570f03/sparse_convolution-0.1.1.tar.gz",
"platform": "Any",
"description": "# sparse_convolution\nSparse convolution in python. \\\nUses Toeplitz convolutional matrix multiplication to perform sparse convolution. \\\nThis allows for extremely fast convolution when: \n- The kernel is small (<= 30x30)\n- The input array is sparse (<= 1% density)\n- Many arrays are convolved with the same kernel\n\n## Install: \n`git clone https://github.com/RichieHakim/sparse_convolution` \\\n`cd sparse_convolution` \\\n`pip install -e .` \n\n\n## Basic usage: \nConvolve a single sparse 2D array with a 2D kernel.\n```\nimport sparse_convolution as sc\nimport numpy as np\nimport scipy.sparse\n\n# Create a single sparse matrix\nA = scipy.sparse.rand(100, 100, density=0.1)\n\n# Create a dense kernel\nB = np.random.rand(3, 3)\n\n# Prepare class\nconv = Toeplitz_convolution2d(\n x_shape=A.shape,\n k=B,\n mode='same',\n dtype=np.float32,\n)\n\n# Convolve\nC = conv(\n x=A,\n batching=False,\n mode='same',\n).toarray()\n```\n\n\n## Batching usage: \nConvolve multiple sparse 2D arrays with a 2D kernel. \\\nThe input arrays must be reshaped into flattened vectors and stacked into a single sparse array of shape: `(n_arrays, height * width)`. \n```\nimport sparse_convolution as sc\nimport numpy as np\nimport scipy.sparse\n\n# Create multiple sparse matrices\n# note that the shape of A will be (3, 100**2)\nA = scipy.sparse.vstack([\n scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),\n scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),\n scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),\n]).tocsr()\n\n# Create a dense kernel\nB = np.random.rand(3, 3)\n\n# Prepare class\nconv = sc.Toeplitz_convolution2d(\n x_shape=(100, 100), # note that the input shape here is (100, 100)\n k=B,\n mode='same',\n dtype=np.float32,\n)\n\n# Convolve\nC = conv(\n x=A,\n batching=True,\n mode='same',\n)\n\n# Reshape the output back to (3, 100, 100)\nC_reshaped = np.stack([c.reshape(100, 100).toarray() for c in C], axis=0)\n```\n\n## References\n- See: https://stackoverflow.com/a/51865516 and https://github.com/alisaaalehi/convolution_as_multiplication\n for a nice illustration.\n- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.convolution_matrix.html \n for 1D version.\n- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.matmul_toeplitz.html#scipy.linalg.matmul_toeplitz \n for potential ways to make this implementation faster.\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Sparse convolution in python using Toeplitz convolution matrix multiplication.",
"version": "0.1.1",
"project_urls": {
"Homepage": "https://github.com/RichieHakim/sparse_convolution"
},
"split_keywords": [
"sparse",
"convolution",
"toeplitz",
"python"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "3caeeaa1b31e12ae486d36c83f5890a8f1278323febd57519c5bda079eac9f8f",
"md5": "a8b20d5df98f99070b62c913edd266c2",
"sha256": "52530c64b6941127e3f3732e59a5c805505db7b5b0024d54a5e20f2e5da1246c"
},
"downloads": -1,
"filename": "sparse_convolution-0.1.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "a8b20d5df98f99070b62c913edd266c2",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 5622,
"upload_time": "2024-01-30T20:35:50",
"upload_time_iso_8601": "2024-01-30T20:35:50.151989Z",
"url": "https://files.pythonhosted.org/packages/3c/ae/eaa1b31e12ae486d36c83f5890a8f1278323febd57519c5bda079eac9f8f/sparse_convolution-0.1.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "3a9a1ba292348b356c6b8c3504caa074babcfac57f8571c9058ae774d8570f03",
"md5": "29210210806bf82a0fc7c98bbd8e510e",
"sha256": "5cc837ed0573e212b79e5a7b39ccca1c04b4004281d38a70f86eb4853871dfd8"
},
"downloads": -1,
"filename": "sparse_convolution-0.1.1.tar.gz",
"has_sig": false,
"md5_digest": "29210210806bf82a0fc7c98bbd8e510e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 6901,
"upload_time": "2024-01-30T20:35:51",
"upload_time_iso_8601": "2024-01-30T20:35:51.295624Z",
"url": "https://files.pythonhosted.org/packages/3a/9a/1ba292348b356c6b8c3504caa074babcfac57f8571c9058ae774d8570f03/sparse_convolution-0.1.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-30 20:35:51",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "RichieHakim",
"github_project": "sparse_convolution",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [],
"lcname": "sparse-convolution"
}
JSON
