Data

Tools

Indexes

Applications

Experiments

Open Source Science

spex

https://github.com/clouren/spex

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 9 DOI reference(s) in README
  • ✓
    Academic publication links
    Links to: acm.org
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (8.3%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

Basic Info
  • Host: GitHub
  • Owner: clouren
  • License: other
  • Language: C
  • Default Branch: stable
  • Size: 95.2 MB
Statistics
  • Stars: 11
  • Watchers: 5
  • Forks: 3
  • Open Issues: 0
  • Releases: 10
Created over 5 years ago · Last pushed 7 months ago
Metadata Files
Readme Contributing License Citation

README.md

SPEX is a software package for SParse EXact algebra

Feb 20, 2025

Files and folders in this distribution:

README.md           this file

AMD                 Approximate minimum degree ordering for
                    preordering matrices prior to factorization.
                    Please see www.suitesparse.com for more information

COLAMD              Column approximate minimum degree ordering
                    for preordering matrices prior to factorization.
                    Please see www.suitesparse.com for more information

include             Header files for SPEX that are generated by
                    the general makefile

SPEX                Folder containing the SPEX package

SuiteSparse_config  Configuration for all SuiteSparse functions.
                    Please see www.suitesparse.com for information

Dependencies of SPEX:

AMD                 approximate minimum degree ordering

COLAMD              column approximate minimum degree ordering

SuiteSparse_config  configuration for all of SuiteSparse

GNU GMP             GNU Multiple Precision Arithmetic Library
                    for big integer operations

GNU MPFR            GNU Multiple Precision Floating-Point Reliable
                    Library for arbitrary precision floating point
                    operations

Default 'local' instalation locations:

include
lib
bin

To compile SPEX and its dependencies, a very simple top-level Makefile is provided. All it does is use cmake to build each of the packages.

Makefile    to compile all of SPEX and its dependencies

            make            compiles SuiteSparse libraries.
                            Subsequent "make install" will install
                            in just /usr/local/lib.
                            Normally requires "sudu make install"

            make local      compiles SuiteSparse.
                            Subsequent "make install will install only
                            in ./lib, ./include only.  No sudo required.
                            Does not install in /usr/local/lib.

            make global     compiles SuiteSparse libraries.
                            Subsequent "make install" will install in
                            just /usr/local/lib (or whatever your
                            CMAKE_INSTALL_PREFIX is).
                            Normally requires "sudu make install"
                            Does not install in ./lib and ./include.

            make install    installs in the current directory
                            (./lib, ./include), and/or in
                            /usr/local/lib and /usr/local/include,
                            depending on whether "make", "make local",
                            "make global", or "make both",
                            etc has been done.

            make demos      run a few short demos

            make uninstall  undoes 'make install'

            make distclean  removes all files not in distribution, including
                            ./bin, ./lib, and ./include.

            make purge      same as 'make distclean'

            make clean      removes all files not in distribution, but
                            keeps compiled libraries and demoes, ./lib
                            and ./include.

You can also use cmake or ccmake directly. For example, try:

cd AMD/build
ccmake ..
make

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

  • for AMD:

P. Amestoy, T. A. Davis, and I. S. Duff, Algorithm 837: An approximate minimum degree ordering algorithm, ACM Trans. on Mathematical Software, 30(3), 2004, pp. 381--388. https://dl.acm.org/doi/abs/10.1145/1024074.1024081

P. Amestoy, T. A. Davis, and I. S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Analysis and Applications, 17(4), 1996, pp. 886--905. https://doi.org/10.1137/S0895479894278952

  • for COLAMD:

T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, Algorithm 836: COLAMD, an approximate column minimum degree ordering algorithm, ACM Trans. on Mathematical Software, 30(3), 2004, pp. 377--380. https://doi.org/10.1145/1024074.1024080

T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, A column approximate minimum degree ordering algorithm, ACM Trans. on Mathematical Software, 30(3), 2004, pp. 353--376. https://doi.org/10.1145/1024074.1024079

  • for SPEX:

Christopher Lourenco, Jinhao Chen, Erick Moreno-Centeno, and T. A. Davis. 2022. Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-Looking Integer-Preserving LU Factorization. ACM Trans. Math. Softw. June 2022. https://doi.org/10.1145/3519024

Compilation options

You can set specific options for CMake with the command (for example): cmake -DBUILD_STATIC_LIBS=OFF -DCMAKE_BUILD_TYPE=Debug ..

That command will compile SPEX, AMD, COLAMD, and SuiteSparse_config. Debug mode will be used (the build type). The static libraries will not be built (since -DBUILD_STATIC_LIBS=OFF is set).

  • SUITESPARSE_ENABLE_PROJECTS:

Semicolon separated list of projects to be built or all. Default: all in which case the following projects are built:

suitesparse_config;amd;colamd;spex

  • CMAKE_BUILD_TYPE:

Default: Release, use Debug for debugging.

  • SUITESPARSE_USE_STRICT:

SuiteSparse has many user-definable settings of the form SUITESPARSE_USE_* or (package)_USE_* for some particular package. In general, these settings are not strict. For example, if SUITESPARSE_USE_OPENMP is ON then OpenMP is preferred, but SuiteSparse can be used without OpenMP so no error is generated if OpenMP is not found. However, if SUITESPARSE_USE_STRICT is ON then all *_USE_* settings are treated strictly and an error occurs if any are set to ON but the corresponding package or setting is not available. The *_USE_SYSTEM_* settings are always treated as strict. Default: OFF.

  • CMAKE_INSTALL_PREFIX:

Defines the install location (default on Linux is /usr/local). For example, this command while in a folder build in the top level SuiteSparse folder will set the install directory to /stuff, used by the subsequent sudo cmake --install .: cmake -DCMAKE_INSTALL_PREFIX=/stuff .. sudo cmake --install .

  • SUITESPARSE_PKGFILEDIR:

Directory where CMake Config and pkg-config files will be installed. By default, CMake Config files will be installed in the subfolder cmake of the directory where the (static) libraries will be installed (e.g., lib). The .pc files for pkg-config will be installed in the subfolder pkgconfig of the directory where the (static) libraries will be installed.

This option allows to install them at a location different from the (static) libraries. This allows to install multiple configurations of the SuiteSparse libraries at the same time (e.g., by also setting a different CMAKE_RELEASE_POSTFIX and CMAKE_INSTALL_LIBDIR for each of them). To pick up the respective configuration in downstream projects, set, e.g., CMAKE_PREFIX_PATH (for CMake) or PKG_CONFIG_PATH (for build systems using pkg-config) to the path containing the respective CMake Config files or pkg-config files.

  • SUITESPARSE_INCLUDEDIR_POSTFIX:

Postfix for installation target of header from SuiteSparse. Default: suitesparse, so the default include directory is: CMAKE_INSTALL_PREFIX/include/suitesparse

  • BUILD_SHARED_LIBS:

If ON, shared libraries are built. Default: ON.

  • BUILD_STATIC_LIBS:

If ON, static libraries are built. Default: ON, except for GraphBLAS, which takes a long time to compile so the default for GraphBLAS is OFF unless BUILD_SHARED_LIBS is OFF.

  • SUITESPARSE_USE_OPENMP:

If ON, OpenMP is used by default if it is available. Default: ON. SPEX relies on OpenMP for its thread safety.

  • SUITESPARSE_CONFIG_USE_OPENMP:

If ON, SuiteSparse_config uses OpenMP if it is available. Default: SUITESPARSE_USE_OPENMP. It is not essential and only used to let SuiteSparse_time call omp_get_wtime.

  • SPEX_USE_OPENMP:

If ON, OpenMP is used in SPEX if it is available. Default: SUITESPARSE_USE_OPENMP.

  • SUITESPARSE_DEMOS:

If ON, build the demo programs for each package. Default: OFF.

  • SUITESPARSE_USE_SYSTEM_AMD:

If ON, use AMD libraries installed on the build system. If OFF, automatically build AMD as dependency if needed. Default: OFF.

  • SUITESPARSE_USE_SYSTEM_COLAMD:

If ON, use COLAMD libraries installed on the build system. If OFF, automatically build COLAMD as dependency if needed. Default: OFF.

  • SUITESPARSE_USE_SYSTEM_SUITESPARSE_CONFIG:

If ON, use SuiteSparse_config libraries installed on the build system. If OFF, automatically build SuiteSparse_config as dependency if needed. Default: OFF.

Acknowledgements

We would like to thank François Bissey, Sebastien Villemot, Erik Welch, Jim Kitchen, Markus Mützel, 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 us if there's anything we can do to make your life easier.

See also the various Acknowledgements within each package.

Primary Author of SPEX: Chris Lourenco

SPEX Coauthors (alphabetical order):

Jinhao Chen
Timothy A Davis
Lorena Mejia Domenzain
Erick Moreno-Centeno

Owner

  • Name: Chris Lourenco
  • Login: clouren
  • Kind: user

Assistant Professor at US Naval Academy. Currently working on efficient methods to solve sparse linear systems using only integer arithmetic.

Citation (CITATION.bib) 

@article{10.1145/1024074.1024081,
author = {Amestoy, Patrick R. and Davis, Timothy A. and Duff, Iain S.},
title = {Algorithm 837: AMD, an Approximate Minimum Degree Ordering Algorithm},
year = {2004},
issue_date = {September 2004},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {30},
number = {3},
issn = {0098-3500},
url = {https://doi.org/10.1145/1024074.1024081},
doi = {10.1145/1024074.1024081},
abstract = {AMD is a set of routines that implements the approximate minimum degree ordering algorithm to permute sparse matrices prior to numerical factorization. There are versions written in both C and Fortran 77. A MATLAB interface is included.},
journal = {ACM Trans. Math. Softw.},
month = {sep},
pages = {381–388},
numpages = {8},
keywords = {sparse matrices, Linear equations, ordering methods, minimum degree}
}

@article{doi:10.1137/S0895479894278952,
author = {Amestoy, Patrick R. and Davis, Timothy A. and Duff, Iain S.},
title = {An Approximate Minimum Degree Ordering Algorithm},
journal = {SIAM Journal on Matrix Analysis and Applications},
volume = {17},
number = {4},
pages = {886-905},
year = {1996},
doi = {10.1137/S0895479894278952},
URL = { https://doi.org/10.1137/S0895479894278952 },
eprint = { https://doi.org/10.1137/S0895479894278952 } ,
    abstract = { Abstract. An approximate minimum degree (AMD), ordering algorithm for preordering a symmetric sparse matrix prior to numerical factorization is presented. We use techniques based on the quotient graph for matrix factorization that allow us to obtain computationally cheap bounds for the minimum degree. We show that these bounds are often equal to the actual degree. The resulting algorithm is typically much faster than previous minimum degree ordering algorithms and produces results that are comparable in quality with the best orderings from other minimum degree algorithms. }
}


@article{10.1145/1024074.1024080,
author = {Davis, Timothy A. and Gilbert, John R. and Larimore, Stefan I. and Ng, Esmond G.},
title = {Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm},
year = {2004},
issue_date = {September 2004},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {30},
number = {3},
issn = {0098-3500},
url = {https://doi.org/10.1145/1024074.1024080},
doi = {10.1145/1024074.1024080},
abstract = {Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, and (2) sparse Cholesky factorization, which requires a symmetric permutation of both the rows and columns of the matrix being factorized. These orderings are computed by COLAMD and SYMAMD, respectively. The ordering from COLAMD is also suitable for sparse QR factorization, and the factorization of matrices of the form ATA and AAT, such as those that arise in least-squares problems and interior point methods for linear programming problems. The two routines are available both in MATLAB and C-callable forms. They appear as built-in routines in MATLAB Version 6.0.},
journal = {ACM Trans. Math. Softw.},
month = {sep},
pages = {377–380},
numpages = {4},
keywords = {sparse nonsymmetric matrices, ordering methods, Linear equations}
}

@article{10.1145/1024074.1024079,
author = {Davis, Timothy A. and Gilbert, John R. and Larimore, Stefan I. and Ng, Esmond G.},
title = {A Column Approximate Minimum Degree Ordering Algorithm},
year = {2004},
issue_date = {September 2004},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {30},
number = {3},
issn = {0098-3500},
url = {https://doi.org/10.1145/1024074.1024079},
doi = {10.1145/1024074.1024079},
abstract = {Sparse Gaussian elimination with partial pivoting computes the factorization PAQ = LU of a sparse matrix A, where the row ordering P is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column preordering, Q, based solely on the nonzero pattern of A, that limits the worst-case number of nonzeros in the factorization. The fill-in also depends on P, but Q is selected to reduce an upper bound on the fill-in for any subsequent choice of P. The choice of Q can have a dramatic impact on the number of nonzeros in L and U. One scheme for determining a good column ordering for A is to compute a symmetric ordering that reduces fill-in in the Cholesky factorization of ATA. A conventional minimum degree ordering algorithm would require the sparsity structure of ATA to be computed, which can be expensive both in terms of space and time since ATA may be much denser than A. An alternative is to compute Q directly from the sparsity structure of A; this strategy is used by MATLAB's COLMMD preordering algorithm. A new ordering algorithm, COLAMD, is presented. It is based on the same strategy but uses a better ordering heuristic. COLAMD is faster and computes better orderings, with fewer nonzeros in the factors of the matrix.},
journal = {ACM Trans. Math. Softw.},
month = {sep},
pages = {353–376},
numpages = {24},
keywords = {linear equations, Sparse nonsymmetric matrices, ordering methods}
}

@article{10.1145/3519024,
author = {Lourenco, Christopher and Chen, Jinhao and Moreno-Centeno, Erick and Davis, Timothy A.},
title = {Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-Looking Integer-Preserving LU Factorization},
year = {2022},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
issn = {0098-3500},
url = {https://doi.org/10.1145/3519024},
doi = {10.1145/3519024},
abstract = {SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix, A, whose entries are integral, rational, or decimal, and provides a solution to the system Ax = b which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrix A with a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute the L and U matrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers, and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this paper evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time on easy instances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of SuiteSparse.},
journal = {ACM Trans. Math. Softw.},
month = {jun},
keywords = {exact matrix factorization, sparse linear systems, sparse matrix algorithms, exactly solving linear systems, roundoff errors}
}

GitHub Events

Total
  • Watch event: 2
  • Delete event: 6
  • Issue comment event: 6
  • Push event: 51
  • Pull request event: 14
  • Create event: 10
  • Commit comment event: 1
Last Year
  • Watch event: 2
  • Delete event: 6
  • Issue comment event: 6
  • Push event: 51
  • Pull request event: 14
  • Create event: 10
  • Commit comment event: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time
  • Total issues: 0
  • Total pull requests: 6
  • Average time to close issues: N/A
  • Average time to close pull requests: 26 days
  • Total issue authors: 0
  • Total pull request authors: 2
  • Average comments per issue: 0
  • Average comments per pull request: 0.67
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 4
Past Year
  • Issues: 0
  • Pull requests: 6
  • Average time to close issues: N/A
  • Average time to close pull requests: 26 days
  • Issue authors: 0
  • Pull request authors: 2
  • Average comments per issue: 0
  • Average comments per pull request: 0.67
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 4
View more stats
Top Authors
Issue Authors
  • DrTimothyAldenDavis (1)
Pull Request Authors
  • dependabot[bot] (8)
  • DrTimothyAldenDavis (8)
  • clouren (1)
Top Labels
Issue Labels
Pull Request Labels
dependencies (8) github_actions (1)

Dependencies

SPEX/Python/SPEXpy/setup.py pypi
  • numpy *
  • scipy *
.github/workflows/build-arch-emu.yaml actions
  • actions/cache/restore v4 composite
  • actions/cache/save v4 composite
  • actions/checkout v4 composite
  • jirutka/setup-alpine v1 composite
.github/workflows/build.yaml actions
  • actions/cache/restore v4 composite
  • actions/cache/save v4 composite
  • actions/checkout v4 composite
  • msys2/setup-msys2 v2 composite
.github/workflows/codeql-analysis.yaml actions
  • actions/checkout v4 composite
  • github/codeql-action/analyze v3 composite
  • github/codeql-action/init v3 composite
  • msys2/setup-msys2 v2 composite
.github/workflows/macos.yaml actions
  • actions/cache/restore v4 composite
  • actions/cache/save v4 composite
  • actions/checkout v4 composite
.github/workflows/root-cmakelists.yaml actions
  • Jimver/cuda-toolkit v0.2.14 composite
  • actions/cache/restore v4 composite
  • actions/cache/save v4 composite
  • actions/checkout v4 composite
  • conda-incubator/setup-miniconda v3 composite
  • ilammy/msvc-dev-cmd v1 composite
  • msys2/setup-msys2 v2 composite