1----------------------------------------------------------------------------- 2SuiteSparse: A Suite of Sparse matrix packages at http://suitesparse.com 3----------------------------------------------------------------------------- 4 5May 17, 2021. SuiteSparse VERSION 5.10.1 6 7 Now includes GraphBLAS, SLIP_LU, and a new interface to the SuiteSparse 8 Matrix Collection (ssget), via MATLAB and a Java GUI, to 9 http://sparse.tamu.edu. 10 11Primary author of SuiteSparse (codes and algorithms, excl. METIS): Tim Davis 12 13Code co-authors, in alphabetical order (not including METIS): 14 15 Patrick Amestoy, David Bateman, Jinhao Chen. Yanqing Chen, Iain Duff, 16 Les Foster, William Hager, Scott Kolodziej, Chris Lourenco, Stefan 17 Larimore, Erick Moreno-Centeno, Ekanathan Palamadai, Sivasankaran 18 Rajamanickam, Sanjay Ranka, Wissam Sid-Lakhdar, Nuri Yeralan. 19 20Additional algorithm designers: Esmond Ng and John Gilbert. 21 22Refer to each package for license, copyright, and author information. All 23codes are authored or co-authored by Timothy A. Davis. 24 25----------------------------------------------------------------------------- 26About the BLAS and LAPACK libraries 27----------------------------------------------------------------------------- 28 29*NOTE: Use of the Intel MKL BLAS is strongly recommended. A recent OpenBLAS 30can result in severe performance degradation. The reason for this is being 31investigated, and this may be resolved in the near future. Ignore the comments 32about OpenBLAS in the various user guides; those are out of date.* 33 34------------------ 35SuiteSparse/README 36------------------ 37 38Packages in SuiteSparse, and files in this directory: 39 40 GraphBLAS graph algorithms in the language of linear algebra. 41 https://graphblas.org 42 A stand-alone package that uses cmake to compile; see 43 GraphBLAS/README.txt. The rest of SuiteSparse still uses 44 'make'. A cmake setup for all of SuiteSparse is in progress. 45 author: Tim Davis 46 47 SLIP_LU solves sparse linear systems in exact arithmetic. 48 Requires the GNU GMP and MPRF libraries. 49 50 AMD approximate minimum degree ordering. This is the built-in AMD 51 function in MATLAB. 52 authors: Tim Davis, Patrick Amestoy, Iain Duff 53 54 bin where the metis-5.1.0 programs are placed when METIS is compiled 55 56 BTF permutation to block triangular form 57 authors: Tim Davis, Ekanathan Palamadai 58 59 CAMD constrained approximate minimum degree ordering 60 authors: Tim Davis, Patrick Amestoy, Iain Duff, Yanqing Chen 61 62 CCOLAMD constrained column approximate minimum degree ordering 63 authors: Tim Davis, Sivasankaran Rajamanickam, Stefan Larimore. 64 Algorithm design collaborators: Esmond Ng, John Gilbert 65 (for COLAMD) 66 67 ChangeLog a summary of changes to SuiteSparse. See */Doc/ChangeLog 68 for details for each package. 69 70 CHOLMOD sparse Cholesky factorization. Requires AMD, COLAMD, CCOLAMD, 71 the BLAS, and LAPACK. Optionally uses METIS. This is chol and 72 x=A\b in MATLAB. 73 author for all modules: Tim Davis 74 CHOLMOD/Modify module authors: Tim Davis and William W. Hager 75 76 COLAMD column approximate minimum degree ordering. This is the 77 built-in COLAMD function in MATLAB. 78 authors (of the code): Tim Davis and Stefan Larimore 79 Algorithm design collaborators: Esmond Ng, John Gilbert 80 81 Contents.m a list of contents for 'help SuiteSparse' in MATLAB. 82 83 CSparse a concise sparse matrix package, developed for my 84 book, "Direct Methods for Sparse Linear Systems", 85 published by SIAM. Intended primarily for teaching. 86 It does have a 'make install' but I recommend using 87 CXSparse instead. In particular, both CSparse and CXSparse 88 have the same include filename: cs.h. 89 90 This package is used for the built-in DMPERM in MATLAB. 91 author: Tim Davis 92 93 CSparse_to_CXSparse 94 a Perl script to create CXSparse from CSparse and 95 CXSparse_newfiles 96 author: David Bateman, Motorola 97 98 CXSparse CSparse Extended. Includes support for complex matrices 99 and both int or long integers. Use this instead of CSparse 100 for production use; it creates a libcsparse.so (or *dylib on 101 the Mac) with the same name as CSparse. It is a superset 102 of CSparse. Any code that links against CSparse should 103 also be able to link against CXSparse instead. 104 author: Tim Davis, David Bateman 105 106 CXSparse_newfiles 107 Files unique to CXSparse 108 author: Tim Davis, David Bateman 109 110 share 'make' places documentation for each package here 111 112 include 'make' places user-visible include fomes for each package here 113 114 KLU sparse LU factorization, primarily for circuit simulation. 115 Requires AMD, COLAMD, and BTF. Optionally uses CHOLMOD, 116 CAMD, CCOLAMD, and METIS. 117 authors: Tim Davis, Ekanathan Palamadai 118 119 LDL a very concise LDL' factorization package 120 author: Tim Davis 121 122 lib 'make' places shared libraries for each package here 123 124 Makefile to compile all of SuiteSparse 125 make compiles SuiteSparse libraries and runs demos 126 make install compiles SuiteSparse and installs in the 127 current directory (./lib, ./include). 128 Use "sudo make INSTALL=/usr/local" to install 129 in /usr/local/lib and /usr/local/include. 130 make uninstall undoes 'make install' 131 make library compiles SuiteSparse libraries (not demos) 132 make distclean removes all files not in distribution, including 133 ./bin, ./share, ./lib, and ./include. 134 make purge same as 'make distclean' 135 make clean removes all files not in distribution, but 136 keeps compiled libraries and demoes, ./lib, 137 ./share, and ./include. 138 make config displays parameter settings; does not compile 139 140 Each individual package also has each of the above 'make' 141 targets. Doing 'make config' in each package */Lib directory 142 displays the exact shared and static library names. 143 144 Things you don't need to do: 145 make cx creates CXSparse from CSparse 146 make docs creates user guides from LaTeX files 147 make cov runs statement coverage tests (Linux only) 148 make metis compiles METIS (also done by 'make') 149 150 MATLAB_Tools various m-files for use in MATLAB 151 author: Tim Davis (all parts) 152 for spqr_rank: author Les Foster and Tim Davis 153 154 Contents.m list of contents 155 dimacs10 loads matrices for DIMACS10 collection 156 Factorize object-oriented x=A\b for MATLAB 157 find_components finds connected components in an image 158 GEE simple Gaussian elimination 159 getversion.m determine MATLAB version 160 gipper.m create MATLAB archive 161 hprintf.m print hyperlinks in command window 162 LINFACTOR predecessor to Factorize package 163 MESHND nested dissection ordering of regular meshes 164 pagerankdemo.m illustrates how PageRank works 165 SFMULT C=S*F where S is sparse and F is full 166 shellgui display a seashell 167 sparseinv sparse inverse subset 168 spok check if a sparse matrix is valid 169 spqr_rank SPQR_RANK package. MATLAB toolbox for rank 170 deficient sparse matrices: null spaces, 171 reliable factorizations, etc. With Leslie 172 Foster, San Jose State Univ. 173 SSMULT C=A*B where A and B are both sparse 174 SuiteSparseCollection for the SuiteSparse Matrix Collection 175 waitmex waitbar for use inside a mexFunction 176 177 The SSMULT and SFMULT functions are the basis for the 178 built-in C=A*B functions in MATLAB. 179 180 Mongoose graph partitioning. 181 authors: Nuri Yeralan, Scott Kolodziej, William Hager, Tim Davis 182 183 metis-5.1.0 a modified version of METIS. See the README.txt files for 184 details. 185 author: George Karypis; not an integral component of 186 SuiteSparse, however. This is just a copy included with 187 SuiteSparse via the open-source license provided by 188 George Karypis 189 190 RBio read/write sparse matrices in Rutherford/Boeing format 191 author: Tim Davis 192 193 README.txt this file 194 195 SPQR sparse QR factorization. This the built-in qr and x=A\b in 196 MATLAB. 197 author of the CPU code: Tim Davis 198 author of GPU modules: Tim Davis, Nuri Yeralan, 199 Wissam Sid-Lakhdar, Sanjay Ranka 200 201 SPQR/GPUQREngine: GPU support package for SPQR 202 (not built into MATLAB, however) 203 authors: Tim Davis, Nuri Yeralan, Sanjay Ranka, 204 Wissam Sid-Lakhdar 205 206 SuiteSparse_config configuration file for all the above packages. The 207 SuiteSparse_config/SuiteSparse_config.mk is included in the 208 Makefile's of all packages. CSparse and MATLAB_Tools do not 209 use SuiteSparse_config. 210 author: Tim Davis 211 212 SuiteSparse_GPURuntime GPU support package for SPQR and CHOLMOD 213 (not builtin to MATLAB, however). 214 215 SuiteSparse_install.m install SuiteSparse for MATLAB 216 217 SuiteSparse_test.m exhaustive test for SuiteSparse in MATLAB 218 219 ssget MATLAB interface to the SuiteSparse Matrix Collection 220 (formerly called the UF Sparse Matrix Collection). 221 Includes a UFget function for backward compatibility. 222 author: Tim Davis 223 224 UMFPACK sparse LU factorization. Requires AMD and the BLAS. 225 This is the built-in lu and x=A\b in MATLAB. 226 author: Tim Davis 227 algorithm design collaboration: Iain Duff 228 229Some codes optionally use METIS 5.1.0. This package is located in SuiteSparse 230in the metis-5.1.0 directory. Its use is optional, so you can remove it before 231compiling SuiteSparse, if you desire. The use of METIS will improve the 232ordering quality. METIS has been slightly modified for use in SuiteSparse; see 233the metis-5.1.0/README.txt file for details. SuiteSparse can use the 234unmodified METIS 5.1.0, however. To use your own copy of METIS, or a 235pre-installed copy of METIS use 'make MY_METIS_LIB=-lmymetis' or 236'make MY_METIS_LIB=/my/stuff/metis-5.1.0/whereeveritis/libmetis.so 237 MY_METIS_INC=/my/stuff/metis-5.1.0/include'. 238If you want to use METIS in MATLAB, however, you MUST use the version provided 239here, in SuiteSparse/metis-5.1.0. The MATLAB interface to METIS required some 240small changes in METIS itself to get it to work. The original METIS 5.1.0 241will segfault MATLAB. 242 243Refer to each package for license, copyright, and author information. All 244codes are authored or co-authored by Timothy A. Davis. 245email: davis@tamu.edu 246 247Licenses for each package are located in the following files, all in 248PACKAGENAME/Doc/License.txt: 249 250 AMD/Doc/License.txt 251 BTF/Doc/License.txt 252 CAMD/Doc/License.txt 253 CCOLAMD/Doc/License.txt 254 CHOLMOD/Doc/License.txt 255 COLAMD/Doc/License.txt 256 CSparse/Doc/License.txt 257 CXSparse/Doc/License.txt 258 GPUQREngine/Doc/License.txt 259 KLU/Doc/License.txt 260 LDL/Doc/License.txt 261 MATLAB_Tools/Doc/License.txt 262 Mongoose/Doc/License.txt 263 RBio/Doc/License.txt 264 SPQR/Doc/License.txt 265 SuiteSparse_GPURuntime/Doc/License.txt 266 ssget/Doc/License.txt 267 UMFPACK/Doc/License.txt 268 GraphBLAS/Doc/License.txt 269 270These files are also present, but they are simply copies of the above license 271files for CXSparse and ssget: 272 273 CXSparse_newfiles/Doc/License.txt 274 CSparse/MATLAB/ssget/Doc/License.txt 275 CXSparse/MATLAB/ssget/Doc/License.txt 276 277METIS 5.0.1 is distributed with SuiteSparse, and is Copyright (c) 278by George Karypis. Please refer to that package for its License. 279 280----------------------------------------------------------------------------- 281QUICK START FOR MATLAB USERS (Linux, Mac, or Windows): 282----------------------------------------------------------------------------- 283 284Uncompress the SuiteSparse.zip or SuiteSparse.tar.gz archive file (they contain 285the same thing). Next, compile the GraphBLAS library (see instructions in 286GraphBLAS/Doc). Then in the MATLAB Command Window, cd to the SuiteSparse 287directory and type SuiteSparse_install. All packages will be compiled, and 288several demos will be run. To run a (long!) exhaustive test, do 289SuiteSparse_test. 290 291----------------------------------------------------------------------------- 292QUICK START FOR THE C/C++ LIBRARIES: 293----------------------------------------------------------------------------- 294 295For just GraphBLAS, do this: 296 297 cd GraphBLAS/build ; cmake .. ; make ; cd ../Demo ; ./demo 298 cd ../build ; sudo make install 299 300For all other packages, type 'make' in this directory. All libraries will be 301created and copied into SuiteSparse/lib. All include files need by the 302applications that use SuiteSparse are copied into SuiteSparse/include. All 303user documenation is copied into SuiteSparse/share/doc. 304 305Be sure to first install all required libraries: BLAS and LAPACK for UMFPACK, 306CHOLMOD, and SPQR, and GMP and MPFR for SLIP_LU. Be sure to use the latest 307libraries; SLIP_LU requires MPFR 4.0 for example. 308 309When compiling the libraries, do NOT use the INSTALL=... options for 310installing. Just do: 311 312 make 313 314or to compile just the libraries without running the demos, do: 315 316 make library 317 318Any program that uses SuiteSparse can thus use a simpler rule as compared to 319earlier versions of SuiteSparse. If you add /home/myself/SuiteSparse/lib to 320your library search patch, you can do the following (for example): 321 322 S = /home/myself/SuiteSparse 323 cc myprogram.c -I$(S)/include -lumfpack -lamd -lcholmod -lsuitesparseconfig -lm 324 325To change the C and C++ compilers, and to compile in parallel use: 326 327 AUTOCC=no CC=gcc CX=g++ JOBS=32 make 328 329for example, which changes the compiler to gcc and g++, and runs make with 330'make -j32', in parallel with 32 jobs. 331 332Now you can install the libraries, if you wish, in a location other than 333SuiteSparse/lib, SuiteSparse/include, and SuiteSparse/share/doc, using 334'make install INSTALL=...' 335 336Do 'make install' if you want to install the libraries and include files in 337SuiteSparse/lib and SuiteSparse/include, and the documentation in 338SuiteSparse/doc/suitesparse-VERSION. 339This will work on Linux/Unix and the Mac. It should automatically detect if 340you have the Intel compilers or not, and whether or not you have CUDA. If this 341fails, see the SuiteSparse_config/SuiteSparse_config.mk file. There are many 342options that you can either list on the 'make' command line, or you can just 343edit that file. For example, to compile with your own BLAS: 344 345 make BLAS=-lmyblaslibraryhere 346 347NOTE: Use of the Intel MKL BLAS is strongly recommended. The OpenBLAS can 348result in severe performance degradation, in CHOLMOD in particular. 349 350To list all configuration options (but not compile anything), do: 351 352 make config 353 354Any parameter you see in the output of 'make config' with an equal sign 355can be modified at the 'make' command line. 356 357If you do "make install" by itself, then the packages are all installed in 358SuiteSparse/lib (libraries), SuiteSparse/include (include .h files), and 359SuiteSparse/doc/suitesparse-VERSION (documentation). To install in 360/usr/local, the default location for Linux, do: 361 362 make library 363 sudo make install INSTALL=/usr/local 364 365If you want to install elsewhere, say in /my/path, first ensure that /my/path 366is in your LD_LIBRARY_PATH. How to do that depends on your system, but in the 367bash shell, add this to your ~/.bashrc file: 368 369 LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/my/path 370 export LD_LIBRARY_PATH 371 372You may also need to add SuiteSparse/lib to your path. If your copy of 373SuiteSparse is in /home/me/SuiteSparse, for example, then add this to your 374~/.bashrc file: 375 376 LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/me/SuiteSparse/lib:/my/path 377 export LD_LIBRARY_PATH 378 379Then do the following (use "sudo make ..." if needed): 380 381 make library 382 make install INSTALL=/my/path 383 384which puts the files in /my/path/lib, /my/path/include, and /my/path/doc. 385If you want to selectively put the libraries, include files, and doc files 386in different locations, do: 387 388 make install INSTALL_LIB=/my/libs INSTALL_INCLUDE=/myotherstuff/include INSTALL_DOC=/mydocs 389 390for example. Any term not defined will be set to its default, so if you don't 391want to install the documentation, but wish to install the libraries and 392includes in /usr/local/lib and /usr/local/include, do: 393 394 make install INSTALL_DOC=/tmp/doc 395 396which copies the documentation to /tmp/doc where you can then remove it later. 397 398Both the static (.a) and shared (.so) libraries are compiled. The lib.a 399libraries are left in the package Lib folder (AMD/Lib/libamd.a for example). 400The main exception to this rule is the SuiteSparse_config library, which is in 401SuiteSparse/libsuiteSparseconfig.a. SuiteSparse_config is required by all 402packages. The (extremely) optional xerbla library is also an exception, but it 403is highly unlikely that you need that library. 404 405The 'make uninstall' takes the same command-line arguments. 406 407---------------------------------- 408Step-by-step details: 409---------------------------------- 410 411(1) Use the right BLAS and LAPACK libraries. 412 Determine where your BLAS and LAPACK libraries are. If the default 413 'make' does not find them, use 414 'make BLAS=-lmyblaslibraryhere LAPACK=-lmylapackgoeshere' 415 416(2) Install Intel's Threading Building Blocks (TBB). 417 This is optionally used by SuiteSparseQR. Refer to the User Guide in 418 SuiteSparse/SPQR/Doc/spqr_user_guide.pdf for details. 419 420(3) Determine what other command line options you need for 'make'. All options 421 can be set at the 'make' command line without the need to edit this file. 422 Browse that file to see what options you can control. If you choose 423 different options and wish to recompile, be sure to do 'make distclean' in 424 this directory first, to remove all files not in the original distribution. 425 426(4) Type "make" in this directory. All packages will be be compiled. METIS 427 5.1.0 will be compiled if you have it (note that METIS require CMake to 428 build it). Several demos will be run. To compile just the libraries, 429 without running any demos, use "make library". The libraries will appear 430 in */Lib/*.so.* (*.dylib for the Mac). Include files, as needed by user 431 programs that use CHOLMOD, AMD, CAMD, COLAMD, CCOLAMD, BTF, KLU, UMFPACK, 432 LDL, etc. are in */Include/*.h. The include files required by user 433 programs are then copied into SuiteSparse/include, and the compiled 434 libraries are copied into SuiteSparse/lib. Documentation is copied into 435 SuiteSparse/doc. The GraphBLAS libraries are created by cmake and placed 436 in GraphBLAS/build. NOTE: on Linux, you may see some errors when you 437 compile METIS ('make: *** No rule to make target 'w'.). You can safely 438 ignore those errors. 439 440(6) To install, type "make install". This will place copies of all 441 libraries in SuiteSparse/lib, and all include files in SuiteSparse/include, 442 and all documentation in SuiteSparse/doc/suitesparse-VERSION. You can 443 change the install location by "make install INSTALL=/my/path" which puts 444 the libraries in /my/path/lib, the include files in /my/path/include, and 445 documentation in /my/path/doc. These directories are created if they do 446 not already exist. 447 448(7) To uninstall, type "make uninstall", which reverses "make install" 449 by removing the SuiteSparse libraries, include files, and documentation 450 from the place they were installed. If you pass INSTALL_***= options 451 to 'make install', you must pass the same to 'make uninstall'. 452 453