search

DrTimothyAldenDavis / SuiteSparse

The official SuiteSparse library: a suite of sparse matrix algorithms authored or co-authored by Tim Davis, Texas A&M University.
https://people.engr.tamu.edu/davis/suitesparse.html
Other
1.11k stars 256 forks source link
c cholmod colamd cpp csparse graph-algorithms graphblas klu mathematics matlab sparse-matrix spqr suitesparse umfpack

readme

SuiteSparse: A Suite of Sparse matrix packages at http://suitesparse.com

Mar 22, 2024, SuiteSparse VERSION 7.7.0

SuiteSparse is a set of sparse-matrix-related packages written or co-authored by Tim Davis, available at https://github.com/DrTimothyAldenDavis/SuiteSparse .

Primary author of SuiteSparse (codes and algorithms, excl. METIS): Tim Davis

Code co-authors, in alphabetical order (not including METIS or LAGraph): Patrick Amestoy, Mohsen Aznaveh, David Bateman, Jinhao Chen, Yanqing Chen, Iain Duff, Joe Eaton, Les Foster, William Hager, Raye Kimmerer, Scott Kolodziej, Chris Lourenco, Stefan Larimore, Lorena Mejia Domenzain, Erick Moreno-Centeno, Markus Mützel, Corey Nolel, Ekanathan Palamadai, Sivasankaran Rajamanickam, Sanjay Ranka, Wissam Sid-Lakhdar, and Nuri Yeralan.

LAGraph has been developed by the highest number of developers of any of the packages in SuiteSparse and deserves its own list. The list also appears in LAGraph/Contibutors.txt:

Janos B. Antal,    Budapest University of Technology and Economics, Hungary
Mohsen Aznaveh,    Texas A&M University
David A. Bader     New Jersey Institute of Technology
Aydin Buluc,       Lawrence Berkeley National Lab
Jinhao Chen,       Texas A&M University
Tim Davis,         Texas A&M University
Florentin Dorre,   Technische Univeritat Dresden, Neo4j
Marton Elekes,     Budapest University of Technology and Economics, Hungary
Balint Hegyi,      Budapest University of Technology and Economics, Hungary
Tanner Hoke,       Texas A&M University
James Kitchen,     Anaconda
Scott Kolodziej,   Texas A&M University
Pranav Konduri,    Texas A&M University
Roi Lipman,        Redis Labs (now FalkorDB)
Tze Meng Low,      Carnegie Mellon University
Tim Mattson,       Intel
Scott McMillan,    Carnegie Mellon University
Markus Muetzel
Michel Pelletier,  Graphegon
Gabor Szarnyas,    CWI Amsterdam, The Netherlands
Erik Welch,        Anaconda, NVIDIA
Carl Yang,         University of California at Davis, Waymo
Yongzhe Zhang,     SOKENDAI, Japan

METIS is authored by George Karypis.

Additional algorithm designers: Esmond Ng and John Gilbert.

Refer to each package for license, copyright, and author information.

Documentation

Refer to each package for the documentation on each package, typically in the Doc subfolder.

SuiteSparse branches

SuiteSparse Packages

Packages in SuiteSparse, and files in this directory:

Refer to each package for license, copyright, and author information. All codes are authored or co-authored by Timothy A. Davis (email: davis@tamu.edu), except for METIS (by George Karypis), GraphBLAS/cpu_features (by Google), GraphBLAS/lz4, zstd, and xxHash (by Yann Collet, now at Facebook), and GraphBLAS/CUDA/jitify.hpp (by NVIDIA). Parts of GraphBLAS/CUDA are Copyright (c) by NVIDIA. Please refer to each of these licenses.

For distro maintainers (Linux, homebrew, spack, R, Octave, Trilinos, ...):

Thanks for packaging SuiteSparse! Here are some suggestions:

How to cite the SuiteSparse meta-package and its component packages:

SuiteSparse is a meta-package of many packages, each with their own published papers. To cite the whole collection, use the URLs:

Please also cite the specific papers for the packages you use. This is a long list; if you want a shorter list, just cite the most recent "Algorithm XXX:" papers in ACM TOMS, for each package.

About the BLAS and LAPACK libraries

NOTE: if you use OpenBLAS, be sure to use version 0.3.27 or later.

To select your BLAS/LAPACK, see the instructions in SuiteSparseBLAS.cmake in SuiteSparse_config/cmake_modules. If SuiteSparse_config finds a BLAS with 64-bit integers (such as the Intel MKL ilp64 BLAS), it configures SuiteSparse_config.h with the SUITESPARSE_BLAS_INT defined as int64_t. Otherwise, if a 32-bit BLAS is found, this type is defined as int32_t. If later on, UMFPACK, CHOLMOD, or SPQR are compiled and linked with a BLAS that has a different integer size, you must override the definition with -DBLAS64 (to assert the use of 64-bit integers in the BLAS) or -DBLAS32, (to assert the use of 32-bit integers in the BLAS).

The size of the BLAS integer has nothing to do with sizeof(void *).

When distributed in a binary form (such as a Debian, Ubuntu, Spack, or Brew package), SuiteSparse should probably be compiled to expect a 32-bit BLAS, since this is the most common case. The default is to use a 32-bit BLAS, but this can be changed by setting the cmake variable SUITESPARSE_USE_64BIT_BLAS to ON.

By default, SuiteSparse hunts for a suitable BLAS library. To enforce a particular BLAS library use either:

CMAKE_OPTIONS="-DBLA_VENDOR=OpenBLAS" make
cd Package ; cmake -DBLA_VENDOR=OpenBLAS .. make

To use the default (hunt for a BLAS), do not set BLA_VENDOR, or set it to ANY. In this case, if SUITESPARSE_USE_64BIT_BLAS is ON, preference is given to a 64-bit BLAS, but a 32-bit BLAS library will be used if no 64-bit library is found. However, if both SUITESPARSE_USE_64BIT_BLAS and SUITESPARSE_USE_STRICT are ON, then only a 64-bit BLAS is considered.

When selecting a particular BLAS library, the SUITESPARSE_USE_64BIT_BLAS setting is strictly followed. If set to true, only a 64-bit BLAS library will be used. If false (the default), only a 32-bit BLAS library will be used. If no such BLAS is found, the build will fail.

QUICK START FOR THE C/C++ LIBRARIES:

Type the following in this directory (requires system priviledge to do the sudo make install):

    mkdir -p build && cd build
    cmake ..
    cmake --build .
    sudo cmake --install .

All libraries will be created and installed into the default system-wide folder (/usr/local/lib on Linux). All include files needed by the applications that use SuiteSparse are installed into /usr/local/include/suitesparse (on Linux).

To build only a subset of libraries, set SUITESPARSE_ENABLE_PROJECTS when configuring with CMake. E.g., to build and install CHOLMOD and CXSparse (including their dependencies), use the following commands:

    mkdir -p build && cd build
    cmake -DSUITESPARSE_ENABLE_PROJECTS="cholmod;cxsparse" ..
    cmake --build .
    sudo cmake --install .

For Windows (MSVC), import the CMakeLists.txt file into MS Visual Studio. Be sure to specify the build type as Release; for example, to build SuiteSparse on Windows in the command window, run:

    mkdir -p build && cd build
    cmake ..
    cmake --build . --config Release
    cmake --install .

Be sure to first install all required libraries: BLAS and LAPACK for UMFPACK, CHOLMOD, and SPQR, and GMP and MPFR for SPEX. Be sure to use the latest libraries; SPEX requires MPFR 4.0.2 and GMP 6.1.2 (these version numbers do NOT correspond to the X.Y.Z suffix of libgmp.so.X.Y.Z and libmpfr.so.X.Y.Z; see the SPEX user guide for details).

To compile the libraries and install them only in SuiteSparse/lib (not /usr/local/lib), do this instead in the top-level of SuiteSparse:

    mkdir -p build && cd build
    cmake -DCMAKE_INSTALL_PREFIX=.. ..
    cmake --build .
    cmake --install .

If you add /home/me/SuiteSparse/lib to your library search path (LD_LIBRARY_PATH in Linux), you can do the following (for example):

    S = /home/me/SuiteSparse
    cc myprogram.c -I$(S)/include/suitesparse -lumfpack -lamd -lcholmod -lsuitesparseconfig -lm

To change the C and C++ compilers, and to compile in parallel use:

    cmake -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER==g++ ..

for example, which changes the compiler to gcc and g++.

This will work on Linux/Unix and the Mac. It should automatically detect if you have the Intel compilers or not, and whether or not you have CUDA.

See SuiteSparse_config/cmake_modules/SuiteSparsePolicy.cmake to select your BLAS.

You may also need to add SuiteSparse/lib to your path. If your copy of SuiteSparse is in /home/me/SuiteSparse, for example, then add this to your ~/.bashrc file:

LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/me/SuiteSparse/lib
export LD_LIBRARY_PATH

For the Mac, use this instead:

DYLD_LIBRARY_PATH=$DYLD_LIBRARY_PATH:/home/me/SuiteSparse/lib
export DYLD_LIBRARY_PATH

Default install location of files is below, where PACKAGE is one of the packages in SuiteSparse:

* `CMAKE_INSTALL_PREFIX/include/suitesparse/`: include files
* `CMAKE_INSTALL_PREFIX/lib/`: compiled libraries
* `CMAKE_INSTALL_PREFIX/lib/cmake/SuiteSparse/`: `*.cmake` scripts
    for all of SuiteSparse
* `CMAKE_INSTALL_PREFIX/lib/cmake/PACKAGE/`: `*Config.cmake` scripts for a
    specific package
* `CMAKE_INSTALL_PREFIX/lib/pkgconfig/PACKAGE.pc`: `.pc` scripts for
    a specific package pkgconfig

QUICK START FOR MATLAB USERS (Linux or Mac):

Suppose you place SuiteSparse in the /home/me/SuiteSparse folder.

Add the SuiteSparse/lib folder to your run-time library path. On Linux, add this to your ~/.bashrc script, assuming /home/me/SuiteSparse is the location of your copy of SuiteSparse:

    LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/me/SuiteSparse/lib
    export LD_LIBRARY_PATH

For the Mac, use this instead, in your ~/.zshrc script, assuming you place SuiteSparse in /Users/me/SuiteSparse:

    DYLD_LIBRARY_PATH=$DYLD_LIBRARY_PATH:/Users/me/SuiteSparse/lib
    export DYLD_LIBRARY_PATH

Compile all of SuiteSparse with make local.

Next, compile the GraphBLAS MATLAB library. In the system shell while in the SuiteSparse folder, type make gbmatlab if you want to install it system-wide with make install, or make gblocal if you want to use the library in your own SuiteSparse/lib.

Then in the MATLAB Command Window, cd to the SuiteSparse directory and type SuiteSparse_install. All packages will be compiled, and several demos will be run. To run a (long!) exhaustive test, do SuiteSparse_test.

Save your MATLAB path for future sessions with the MATLAB pathtool or savepath commands. If those methods fail because you don't have system-wide permission, add the new paths to your startup.m file, normally in Documents/MATLAB/startup.m. You can also use the SuiteSparse_paths m-file to set all your paths at the start of each MATLAB session.

Compilation options

You can set specific options for CMake with the command (for example):

    cmake -DCHOLMOD_PARTITION=OFF -DBUILD_STATIC_LIBS=OFF -DCMAKE_BUILD_TYPE=Debug ..

That command will compile all of SuiteSparse except for CHOLMOD/Partition Module (because of -DCHOLMOD_PARTITION=OFF). Debug mode will be used (the build type). The static libraries will not be built (since -DBUILD_STATIC_LIBS=OFF is set).

Additional options are available for specific packages:

CHOLMOD is composed of a set of Modules that can be independently selected; all options default to ON:

Possible build/install issues

One common issue can affect all packages: getting the right #include files that match the current libraries being built. It's possible that your Linux distro has an older copy of SuiteSparse headers in /usr/include or /usr/local/include, or that Homebrew has installed its suite-sparse bundle into /opt/homebrew/include or other places. Old libraries can appear in in /usr/local/lib, /usr/lib, etc. When building a new copy of SuiteSparse, the cmake build system is normally (or always?) able to avoid these, and use the right header for the right version of each library.

As an additional guard against this possible error, each time one SuiteSparse package #include's a header from another one, it checks the version number in the header file, and reports an #error to the compiler if a stale version is detected. In addition, the Example package checks both the header version and the library version (by calling a function in each library). If the versions mismatch in any way, the Example package reports an error at run time.

For example, CHOLMOD 5.1.0 requires AMD 3.3.0 or later. If it detects an older one in amd.h, it will report an #error:

    #include "amd.h"
    #if ( ... AMD version is stale ... )
    #error "CHOLMOD 5.1.0 requires AMD 3.3.0 or later"
    #endif

and the compilation will fail. The Example package makes another check, by calling amd_version and comparing it with the versions from the amd.h header file.

If this error or one like it occurs, check to see if you have an old copy of SuiteSparse, and uninstall it before compiling your new copy of SuiteSparse.

There are other many possible build/install issues that are covered by the corresponding user guides for each package, such as finding the right BLAS, OpenMP, and other libraries, and how to compile on the Mac when using GraphBLAS inside MATLAB, and so on. Refer to the User Guides for more details.

Interfaces to SuiteSparse

MATLAB/Octave/R/Mathematica interfaces:

Many built-in methods in MATLAB and Octave rely on SuiteSparse, including C=A*B x=A\b, L=chol(A), [L,U,P,Q]=lu(A), R=qr(A), dmperm(A), p=amd(A), p=colamd(A), ... See also Mathematica, R, and many many more. The list is too long.

Julia interface:

https://github.com/JuliaSparse/SparseArrays.jl

python interface to GraphBLAS by Anaconda and NVIDIA:

https://pypi.org/project/python-graphblas

Intel's Go interface to GraphBLAS:

https://pkg.go.dev/github.com/intel/forGraphBLASGo

See scikit-sparse and scikit-umfpack for the Python interface via SciPy:

https://github.com/scikit-sparse/scikit-sparse https://github.com/scikit-umfpack/scikit-umfpack

See math.js by Jos de Jong for a JavaScript port of CSparse:

https://github.com/josdejong/mathjs

See russell for a Rust interface:

https://github.com/cpmech/russell

Acknowledgements

Markus Mützel contributed the most recent update of the SuiteSparse build system for all SuiteSparse packages, extensively porting it and modernizing it.

I would also like to thank François Bissey, Sebastien Villemot, Erik Welch, Jim Kitchen, and Fabian Wein for their valuable feedback on the SuiteSparse build system and how it works with various Linux / Python distros and other package managers. If you are a maintainer of a SuiteSparse packaging for a Linux distro, conda-forge, R, spack, brew, vcpkg, etc, please feel free to contact me if there's anything I can do to make your life easier. I would also like to thank Raye Kimmerer for adding support for 32-bit row/column indices in SPQR v4.2.0.

See also the various Acknowledgements within each package.