# Python wrapper for SuiteSparseQR
This module wraps the [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html)
decomposition function for use with [SciPy](http://www.scipy.org).
This is Matlab's sparse `[Q,R,E] = qr()`.
For some reason, no one ever wrapped that function of SuiteSparseQR for Python.
Also wrapped are the SuiteSparseQR solvers for ``A x = b`` for the cases with sparse `A` and dense or sparse `b`.
This is especially useful for solving sparse overdetermined linear systems in the least-squares sense.
Here `A` is of size m-by-n and `b` is m-by-k (storing `k` different right-hand side vectors, each considered separately).
# Usage
```python
import numpy
import scipy.sparse.linalg
import sparseqr
# QR decompose a sparse matrix M such that Q R = M E
#
M = scipy.sparse.rand( 10, 10, density = 0.1 )
Q, R, E, rank = sparseqr.qr( M )
print( "Should be approximately zero:", abs( Q*R - M*sparseqr.permutation_vector_to_matrix(E) ).sum() )
# Solve many linear systems "M x = b for b in columns(B)"
#
B = scipy.sparse.rand( 10, 5, density = 0.1 ) # many RHS, sparse (could also have just one RHS with shape (10,))
x = sparseqr.solve( M, B, tolerance = 0 )
# Solve an overdetermined linear system A x = b in the least-squares sense
#
# The same routine also works for the usual non-overdetermined case.
#
A = scipy.sparse.rand( 20, 10, density = 0.1 ) # 20 equations, 10 unknowns
b = numpy.random.random(20) # one RHS, dense, but could also have many (in shape (20,k))
x = sparseqr.solve( A, b, tolerance = 0 )
## Call `rz()`:
sparseqr.rz( A, b, tolerance = 0 )
# Solve a linear system M x = B via QR decomposition
#
# This approach is slow due to the explicit construction of Q, but may be
# useful if a large number of systems need to be solved with the same M.
#
M = scipy.sparse.rand( 10, 10, density = 0.1 )
Q, R, E, rank = sparseqr.qr( M )
r = rank # r could be min(M.shape) if M is full-rank
# The system is only solvable if the lower part of Q.T @ B is all zero:
print( "System is solvable if this is zero (unlikely for a random matrix):", abs( (( Q.tocsc()[:,r:] ).T ).dot( B ) ).sum() )
# Systems with large non-square matrices can benefit from "economy" decomposition.
M = scipy.sparse.rand( 20, 5, density=0.1 )
B = scipy.sparse.rand( 20, 5, density = 0.1 )
Q, R, E, rank = sparseqr.qr( M )
print("Q shape (should be 20x20):", Q.shape)
print("R shape (should be 20x5):", R.shape)
Q, R, E, rank = sparseqr.qr( M, economy=True )
print("Q shape (should be 20x5):", Q.shape)
print("R shape (should be 5x5):", R.shape)
R = R.tocsr()[:r,:r] #for best performance, spsolve_triangular() wants the Matrix to be in CSR format.
Q = Q.tocsc()[:,:r] # Use CSC format for fast indexing of columns.
QB = (Q.T).dot(B).todense() # spsolve_triangular() need the RHS in array format.
result = scipy.sparse.linalg.spsolve_triangular(R, QB, lower=False)
# Recover a solution (as a dense array):
x = numpy.zeros( ( M.shape[1], B.shape[1] ), dtype = result.dtype )
x[:r] = result
x[E] = x.copy()
# Recover a solution (as a sparse matrix):
x = scipy.sparse.vstack( ( result, scipy.sparse.coo_matrix( ( M.shape[1] - rank, B.shape[1] ), dtype = result.dtype ) ) )
x.row = E[ x.row ]
```
# Installation
Before installing this module, you must first install [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html). You can do that via conda (`conda install suitesparse`) or your system's package manager (macOS: `brew install suitesparse`; debian/ubuntu linux: `apt-get install libsuitesparse-dev`).
Now you are ready to install this module.
## Via `pip`
From PyPI:
```bash
pip install sparseqr
```
From GitHub:
```bash
pip install git+https://github.com/yig/PySPQR.git
```
## Directly
Copy the three `sparseqr/*.py` files next to your source code,
or leave them in their directory and call it as a module.
# Deploy
1. Change the version in:
```
sparseqr/__init__.py
pyproject.toml
```
2. Update `CHANGELOG.md`
3. Run:
```
flit publish --format sdist
```
We don't publish binary wheels, because it must be compiled against suite-sparse as a system dependency. We could publish a `none-any` wheel, which would cause compilation to happen the first time the module is imported rather than when it is installed. Is there a point to that?
# Known issues
`pip uninstall sparseqr` won't remove the generated libraries. It will list them with a warning.
# Tested on
- Python 3.9, 3.13.
- Conda and not conda.
- macOS, Ubuntu Linux, and Linux Mint.
PYTHONPATH='.:$PYTHONPATH' python3 test/test.py
# Dependencies
These are installed via pip:
* [SciPy/NumPy](http://www.scipy.org)
* [cffi](http://cffi.readthedocs.io/)
These must be installed manually:
* [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html) (macOS: `brew install suitesparse`; debian/ubuntu linux: `apt-get install libsuitesparse-dev`)
# License
Public Domain [CC0](http://creativecommons.org/publicdomain/zero/1.0/)
Raw data
{
"_id": null,
"home_page": null,
"name": "sparseqr",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": null,
"keywords": "suitesparse, bindings, wrapper, scipy, numpy, qr-decomposition, qr-factorisation, sparse-matrix, sparse-linear-system, sparse-linear-solver",
"author": null,
"author_email": "Yotam Gingold <yotam@yotamgingold.com>",
"download_url": "https://files.pythonhosted.org/packages/7f/ab/1123aeb3db1168fa77b6197aedf066d81d252e91adbe25cc9079e130fb92/sparseqr-1.4.tar.gz",
"platform": null,
"description": "# Python wrapper for SuiteSparseQR\n\nThis module wraps the [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html)\ndecomposition function for use with [SciPy](http://www.scipy.org).\nThis is Matlab's sparse `[Q,R,E] = qr()`.\nFor some reason, no one ever wrapped that function of SuiteSparseQR for Python.\n\nAlso wrapped are the SuiteSparseQR solvers for ``A x = b`` for the cases with sparse `A` and dense or sparse `b`.\nThis is especially useful for solving sparse overdetermined linear systems in the least-squares sense.\nHere `A` is of size m-by-n and `b` is m-by-k (storing `k` different right-hand side vectors, each considered separately).\n\n# Usage\n\n```python\nimport numpy\nimport scipy.sparse.linalg\nimport sparseqr\n\n# QR decompose a sparse matrix M such that Q R = M E\n#\nM = scipy.sparse.rand( 10, 10, density = 0.1 )\nQ, R, E, rank = sparseqr.qr( M )\nprint( \"Should be approximately zero:\", abs( Q*R - M*sparseqr.permutation_vector_to_matrix(E) ).sum() ) \n\n# Solve many linear systems \"M x = b for b in columns(B)\"\n#\nB = scipy.sparse.rand( 10, 5, density = 0.1 ) # many RHS, sparse (could also have just one RHS with shape (10,))\nx = sparseqr.solve( M, B, tolerance = 0 )\n\n# Solve an overdetermined linear system A x = b in the least-squares sense\n#\n# The same routine also works for the usual non-overdetermined case.\n#\nA = scipy.sparse.rand( 20, 10, density = 0.1 ) # 20 equations, 10 unknowns\nb = numpy.random.random(20) # one RHS, dense, but could also have many (in shape (20,k))\nx = sparseqr.solve( A, b, tolerance = 0 )\n## Call `rz()`:\nsparseqr.rz( A, b, tolerance = 0 )\n\n# Solve a linear system M x = B via QR decomposition\n#\n# This approach is slow due to the explicit construction of Q, but may be\n# useful if a large number of systems need to be solved with the same M.\n#\nM = scipy.sparse.rand( 10, 10, density = 0.1 )\nQ, R, E, rank = sparseqr.qr( M )\nr = rank # r could be min(M.shape) if M is full-rank\n\n# The system is only solvable if the lower part of Q.T @ B is all zero:\nprint( \"System is solvable if this is zero (unlikely for a random matrix):\", abs( (( Q.tocsc()[:,r:] ).T ).dot( B ) ).sum() )\n\n# Systems with large non-square matrices can benefit from \"economy\" decomposition.\nM = scipy.sparse.rand( 20, 5, density=0.1 )\nB = scipy.sparse.rand( 20, 5, density = 0.1 )\nQ, R, E, rank = sparseqr.qr( M )\nprint(\"Q shape (should be 20x20):\", Q.shape)\nprint(\"R shape (should be 20x5):\", R.shape)\nQ, R, E, rank = sparseqr.qr( M, economy=True )\nprint(\"Q shape (should be 20x5):\", Q.shape)\nprint(\"R shape (should be 5x5):\", R.shape)\n\n\nR = R.tocsr()[:r,:r] #for best performance, spsolve_triangular() wants the Matrix to be in CSR format.\nQ = Q.tocsc()[:,:r] # Use CSC format for fast indexing of columns.\nQB = (Q.T).dot(B).todense() # spsolve_triangular() need the RHS in array format.\nresult = scipy.sparse.linalg.spsolve_triangular(R, QB, lower=False)\n\n# Recover a solution (as a dense array):\nx = numpy.zeros( ( M.shape[1], B.shape[1] ), dtype = result.dtype )\nx[:r] = result\nx[E] = x.copy()\n\n# Recover a solution (as a sparse matrix):\nx = scipy.sparse.vstack( ( result, scipy.sparse.coo_matrix( ( M.shape[1] - rank, B.shape[1] ), dtype = result.dtype ) ) )\nx.row = E[ x.row ]\n```\n\n# Installation\n\nBefore installing this module, you must first install [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html). You can do that via conda (`conda install suitesparse`) or your system's package manager (macOS: `brew install suitesparse`; debian/ubuntu linux: `apt-get install libsuitesparse-dev`).\n\nNow you are ready to install this module.\n\n## Via `pip`\n\nFrom PyPI:\n\n```bash\npip install sparseqr\n```\n\nFrom GitHub:\n\n```bash\npip install git+https://github.com/yig/PySPQR.git\n```\n\n## Directly\n\nCopy the three `sparseqr/*.py` files next to your source code,\nor leave them in their directory and call it as a module.\n\n\n# Deploy\n\n1. Change the version in:\n\n ```\n sparseqr/__init__.py\n pyproject.toml\n ```\n\n2. Update `CHANGELOG.md`\n\n3. Run:\n\n ```\n flit publish --format sdist\n ```\n\nWe don't publish binary wheels, because it must be compiled against suite-sparse as a system dependency. We could publish a `none-any` wheel, which would cause compilation to happen the first time the module is imported rather than when it is installed. Is there a point to that?\n\n# Known issues\n\n`pip uninstall sparseqr` won't remove the generated libraries. It will list them with a warning.\n\n# Tested on\n\n - Python 3.9, 3.13.\n - Conda and not conda.\n - macOS, Ubuntu Linux, and Linux Mint.\n\n PYTHONPATH='.:$PYTHONPATH' python3 test/test.py\n\n# Dependencies\n\nThese are installed via pip:\n\n* [SciPy/NumPy](http://www.scipy.org)\n* [cffi](http://cffi.readthedocs.io/)\n\nThese must be installed manually:\n\n* [SuiteSparseQR](http://faculty.cse.tamu.edu/davis/suitesparse.html) (macOS: `brew install suitesparse`; debian/ubuntu linux: `apt-get install libsuitesparse-dev`)\n\n# License\n\nPublic Domain [CC0](http://creativecommons.org/publicdomain/zero/1.0/)\n",
"bugtrack_url": null,
"license": null,
"summary": "Python wrapper for SuiteSparseQR",
"version": "1.4",
"project_urls": {
"homepage": "https://github.com/yig/PySPQR",
"source": "https://github.com/yig/PySPQR"
},
"split_keywords": [
"suitesparse",
" bindings",
" wrapper",
" scipy",
" numpy",
" qr-decomposition",
" qr-factorisation",
" sparse-matrix",
" sparse-linear-system",
" sparse-linear-solver"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "7fab1123aeb3db1168fa77b6197aedf066d81d252e91adbe25cc9079e130fb92",
"md5": "e09cb865f13fa5cff0b09f4a4f658bc4",
"sha256": "084d72287b88218d147d66f5c4d2fe86cb91abd04eb849c684ba8092464f4aa4"
},
"downloads": -1,
"filename": "sparseqr-1.4.tar.gz",
"has_sig": false,
"md5_digest": "e09cb865f13fa5cff0b09f4a4f658bc4",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 18549,
"upload_time": "2025-01-29T03:45:57",
"upload_time_iso_8601": "2025-01-29T03:45:57.154848Z",
"url": "https://files.pythonhosted.org/packages/7f/ab/1123aeb3db1168fa77b6197aedf066d81d252e91adbe25cc9079e130fb92/sparseqr-1.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-01-29 03:45:57",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "yig",
"github_project": "PySPQR",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "sparseqr"
}
JSON
