# 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 (<= 100x100)
- The input array is sparse (<= 1% density)
- The input array is small (<= 1000x1000)
- Many arrays are convolved with the same kernel (large batch size >= 1000)
## Install:
The package is available on PyPI. \
`pip install sparse_convolution`
<br>
Alternatively, you can install from source. \
`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 = sc.Toeplitz_convolution2d(
x_shape=A.shape,
k=B,
mode='same',
dtype=np.float32,
)
# Convolve
C = conv(
x=A,
batching=False,
).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,
)
# 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": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "sparse convolution Toeplitz python",
"author": "Richard Hakim",
"author_email": "richhakim@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/06/dd/6249388abfec5dfff27e7eca2290b4c5499aedf4808caac5798f24bb8ade/sparse_convolution-0.1.5.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 (<= 100x100)\n- The input array is sparse (<= 1% density)\n- The input array is small (<= 1000x1000)\n- Many arrays are convolved with the same kernel (large batch size >= 1000)\n\n## Install: \nThe package is available on PyPI. \\\n`pip install sparse_convolution`\n\n<br>\n\nAlternatively, you can install from source. \\\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 = sc.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).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)\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.5",
"project_urls": {
"Homepage": "https://github.com/RichieHakim/sparse_convolution"
},
"split_keywords": [
"sparse",
"convolution",
"toeplitz",
"python"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c8952dec6a83d935c210e0928c2d127a6d34ea3f57486e7a20e3d1b98cd11cd0",
"md5": "c5bd92ed04da621eee4802d0e7d627a5",
"sha256": "d3bc4714a71d539aeed48529b5f0243f06adff0dec5528a7e8e75fa9b231fe79"
},
"downloads": -1,
"filename": "sparse_convolution-0.1.5-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c5bd92ed04da621eee4802d0e7d627a5",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 6197,
"upload_time": "2024-11-12T19:57:35",
"upload_time_iso_8601": "2024-11-12T19:57:35.364516Z",
"url": "https://files.pythonhosted.org/packages/c8/95/2dec6a83d935c210e0928c2d127a6d34ea3f57486e7a20e3d1b98cd11cd0/sparse_convolution-0.1.5-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "06dd6249388abfec5dfff27e7eca2290b4c5499aedf4808caac5798f24bb8ade",
"md5": "6eee6b4f714add1b2e6349a80d115a4e",
"sha256": "2ce8d1375d0770a18bce714208225d242be2bd28e9c2e70b79b73be6c239b822"
},
"downloads": -1,
"filename": "sparse_convolution-0.1.5.tar.gz",
"has_sig": false,
"md5_digest": "6eee6b4f714add1b2e6349a80d115a4e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 7843,
"upload_time": "2024-11-12T19:57:37",
"upload_time_iso_8601": "2024-11-12T19:57:37.286639Z",
"url": "https://files.pythonhosted.org/packages/06/dd/6249388abfec5dfff27e7eca2290b4c5499aedf4808caac5798f24bb8ade/sparse_convolution-0.1.5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-11-12 19:57:37",
"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
