SciPy seeks to provide access

• from Python
• to implementations of fundamental scientific computing algorithms,
• especially when there is need unmet by other permissively-licensed packages.

This issue summarizes the status of SciPy's support for sparse linear algebra and optimization, and it details what I propose to add.

Linear Algebra

SciPy has some support for sparse linear algebra:

• SciPy vendors the permissively-licensed direct LU solver SuperLU.
• scipy.sparse.linalg.spsolve uses SuperLU unless scikit-umfpack can be imported, in which case it uses scikit-umfpack's interface to the GPL-licensed UMFPACK, the LU solver from SuiteSparse.
• SciPy vendors the permissively-licensed eigenvalue problem solver ARPACK and includes an implementation of LOBPCG.
• scipy.sparse.linalg provides interfaces to these for solving eigenvalue and singular value problems.
• SciPy includes many iterative methods for solving sparse linear systems.

SciPy lacks sparse support for other fundamental linear algebra algorithms, most notably Cholesky decomposition and QR decomposition. Also, better support for sparse SVD has been desired for years (scipygh-857). There is some support for solving these problems in the greater scientific Python ecosystem, but there are also unmet needs. Following the model of SciPy's scipy.sparse.linalg.spsolve, my goal is to enable easy access to both permissively-licensed implementations and more performant (potentially copyleft-licensed) implementations of algorithms for these problems from Linux, Mac, and (the oft forgotten) Windows.

• scikit-sparse provides an interface to the LGPL-licensed CHOLMOD, the Cholesky routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below), and scikit-sparse does not appear to be actively maintained. I propose to

  • add a permissively-licensed sparse Cholesky implementation to SciPy using the ideas (not the code) from Tim Davis' book Direct Methods for Sparse Linear Systems.
  • ensure that there is an actively maintained wrapper for CHOLMOD that can be installed on Linux, Mac, and Windows. This may mean reviving scikit-sparse, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.sparse.linalg interface to both the permissively-licensed implementation and the more performant CHOLMOD.

• sparseqr/PySPQR provides an interface to the GPL-licensed SPQR, the QR routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below). I propose to:

  • add a permissively-licensed sparse QR implementation to SciPy using the ideas (not the code) from Tim Davis' book Direct Methods for Sparse Linear Systems.
  • ensure that there is an actively maintained wrapper for SPQR that can be installed on Linux, Mac, and Windows. This may mean working with sparseqr/PySPQR, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.sparse.linalg interface to both the permissively-licensed implementation and the more performant SPQR.

• scikit-umfpack provides an interface to the GPL-licensed UMFPACK, the LU routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below), and scikit-umfpack does not appear to be actively maintained. I propose to:

  • ensure that there is an actively maintained wrapper for UMFPACK that can be installed on Linux, Mac, and Windows. This may mean reviving scikit-umfpack, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.

• For improved sparse SVD support, @WarrenWeckesser has also indicated interest in vendoring PROPACK, finishing the pypropack wrapper, and including an interface in scipy.sparse.linalg.svd

Optimization

SciPy has some support for sparse optimization: scipy.optimize.minimize(method='trust-constr') and scipy.optimize.linprog(method='interior-point') exploit sparsity, and SciPy 1.6 will vendor the linear programming software HiGHS and add an interface via linprog. However, these offerings are substantially less powerful than copyleft-licensed counterparts, and convenient Python interfaces to the copyleft software is not available on all platforms. Following the model of SciPy's scipy.sparse.linalg.spsolve, my goal is to enable access to both permissively-licensed implementations and more performant (potentially copyleft-licensed) implementations of these solvers from Mac, Linux, and Windows.

• CyLP provides an interface to COIN-OR's Eclipse 2.0-licensed linear and mixed-integer program solvers, including CLP (the highest performance open-source linear programming solver) and CBC (one of the best open-source mixed-integer programming solvers). Installation on Windows is easy via pip, but is not available via conda. Also, the interface uses a modeling language approach rather than the direct approach more familiar to users of Matlab and SciPy, and the documentation is not very friendly. I propose to:

  • ensure that there is an actively maintained wrapper for CLP/CBC that can be installed on Linux, Mac, and Windows. This may mean working with CyLP, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.optimize interface to the CLP/CBC solvers.
  • add a scipy.optimize interface to HiGHS' mixed-integer programming capabilities.

• cyipopt and Gekko both provide interfaces to COIN-OR's Eclipse 2.0-licensed nonlinear programming solver IPOPT, the highest performance open-source linear programming solver. Installation of cyipopt on Windows is problematic (see Installation Notes below), and Gekko's interface uses a modeling language approach rather than the direct approach more familiar to users of Matlab and SciPy. I propose to:

  • ensure that there is an actively maintained wrapper for IPOPT that can be installed on Linux, Mac, and Windows. This may mean working with cyipopt, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.minimize interface to IPOPT.

Installation Notes

Notes from attempts to install the software above on Windows 11/30/2020:

• conda install suitesparse works
• conda install -c conda-forge scikit-umfpack fails
• pip install scikit-umfpack reports success, but from scikits import umfpack fails
• conda install -c conda-forge scikit-sparse fails
• pip install scikit-sparse fails
• sparseqr is not available on conda-forge
• pip install git+https://github.com/yig/PySPQR.git fails
• pip install sparseqr fails
• pip install cylp works, and the software works
• cylp is not available on conda-forge
• pip install ortools works, and the software works
• conda install -c conda-forge ipopt works
• conda install -c conda-forge cyipopt fails
• pip install ipopt fails