Skip to main content

Python wrapper for SuiteSparseQR

Project description

Python wrapper for SuiteSparseQR

This module wraps the SuiteSparseQR decomposition function for use with SciPy. 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

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. 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:

pip install sparseqr

From GitHub:

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:

These must be installed manually:

  • SuiteSparseQR (macOS: brew install suitesparse; debian/ubuntu linux: apt-get install libsuitesparse-dev)

License

Public Domain CC0

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

sparseqr-1.4.1.tar.gz (18.6 kB view details)

Uploaded Source

File details

Details for the file sparseqr-1.4.1.tar.gz.

File metadata

  • Download URL: sparseqr-1.4.1.tar.gz
  • Upload date:
  • Size: 18.6 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: python-requests/2.32.3

File hashes

Hashes for sparseqr-1.4.1.tar.gz
Algorithm Hash digest
SHA256 3c1f0ad101f601f780af9ddb0d06e78d4ffe8dd9605f5fd2c73e4cbf4de9b6b9
MD5 31576ea26439f6cf80ec272ac6205475
BLAKE2b-256 0b5a032078d1c456b679f1d1d3f654a6c7392e215c3f6e2479cf1bec14f7469c

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page