README.md
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