forked from DrTimothyAldenDavis/SuiteSparse
-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathREADME.txt
335 lines (267 loc) · 14.6 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
UMFPACK, Copyright (c) 1995-2023 by Timothy A. Davis,
http://www.suitesparse.com
UMFPACK : a set of routines solving sparse linear systems via LU
factorization. Requires three other packages: the BLAS (dense matrix
operations), AMD (sparse matrix minimum degree ordering), and
SuiteSparse_config.
Includes a C-callable and MATLAB interface, and a basic FORTRAN 77
interface to a subset of the C-callable routines. Requires AMD.
Unless you compile with UMFPACK_USE_CHOLMOD set to OFF, addtional packages
are required: CHOLMOD, CAMD, CCOLAMD, COLAMD, and
CHOLMOD/SuiteSparse_metis.
The AMD, SuiteSparse_config, and UMFPACK directories must all reside in the
same parent directory. If UMFPACK_USE_CHOLMOD is ON, the CHOLMOD, CAMD,
CCOLAMD, and COLAMD directories must also exist in the same parent.
Quick start:
To compile and install the library for system-wide usage:
make
sudo make install
To compile/install for local usage (SuiteSparse/lib and SuiteSparse/include)
make local
make install
To run the demos
make demos
Quick start (for MATLAB users);
To compile, test, and install the UMFPACK mexFunction, cd to the
UMFPACK/MATLAB directory and type umfpack_install at the MATLAB prompt.
Then save your path for future sessions.
--------------------------------------------------------------------------------
UMFPACK is available under alternate licences; contact T. Davis for details.
UMFPACK License: See UMFPACK/Doc/License.txt for the license.
Availability:
http://www.suitesparse.com
UMFPACK (including versions 2.2.1 and earlier, in FORTRAN) is available at
http://www.suitesparse.com. MA38 is available in the Harwell
Subroutine Library. This version of UMFPACK includes a modified form of
COLAMD Version 2.0, originally released on Jan. 31, 2000, also available at
http://www.suitesparse.com. COLAMD V2.0 is also incorporated
as a built-in function in MATLAB version 6.1, by The MathWorks, Inc.
(http://www.mathworks.com). COLAMD V1.0 appears as a column-preordering
in SuperLU (SuperLU is available at http://www.netlib.org).
UMFPACK v4.0 is a built-in routine in MATLAB 6.5.
UMFPACK v4.3 is a built-in routine in MATLAB 7.1.
--------------------------------------------------------------------------------
Refer to ../AMD/Doc/License.txt for the License for AMD, which is a separate
package for ordering sparse matrices that is required by UMFPACK.
UMFPACK v4.5 cannot use AMD v1.1 or earlier. UMFPACK 5.x
requires AMD v2.0 or later.
--------------------------------------------------------------------------------
This is the UMFPACK README.txt file. It is a terse overview of UMFPACK.
Refer to the User Guide (Doc/UserGuide.pdf) for how to install and use UMFPACK,
or to the Quick Start Guide, QuickStart.pdf.
Description:
UMFPACK is a set of routines for solving unsymmetric sparse linear systems,
Ax=b, using the Unsymmetric MultiFrontal method. Written in ANSI/ISO C,
with a MATLAB (Version 6.0 or later) interface.
For best performance, UMFPACK requires an optimized BLAS library. It can
also be compiled without any BLAS at all. UMFPACK requires AMD Version 2.0.
Authors:
Timothy A. Davis ([email protected])
Includes a modified version of COLAMD V2.0, by Stefan I. Larimore and
Timothy A. Davis. The COLAMD algorithm was developed
in collaboration with John Gilbert, Xerox Palo Alto Research Center, and
Esmond Ng, Lawrence Berkeley National Laboratory.
Includes AMD, by Timothy A. Davis, Patrick R. Amestoy, and Iain S. Duff.
UMFPACK Version 2.2.1 (MA38 in the Harwell Subroutine Library) is
co-authored with Iain S. Duff, Rutherford Appleton Laboratory.
Acknowledgements:
This work was supported by the National Science Foundation, under
grants DMS-9504974, DMS-9803599, and CCR-0203270.
Portions of this work were done while on sabbatical at Stanford University
and Lawrence Berkeley National Laboratory (with funding from the SciDAC
program). I would like to thank Gene Golub, Esmond Ng, and Horst Simon
for making this sabbatical possible.
I would also like to thank the many researchers who provided sparse
matrices from a wide range of domains and used earlier versions of UMFPACK/
MA38 in their applications, and thus assisted in the practical development
of the algorithm (see http://www.suitesparse.com, future
contributions of matrices are always welcome).
The MathWorks, Inc., provided a pre-release of MATLAB V6 which allowed me
to release the first umfpack mexFunction (v3.0) about 6 months earlier than
I had originally planned. They also supported the extension of UMFPACK to
complex, singular, and rectangular matrices (UMFPACK v4.0).
Penny Anderson (The MathWorks, Inc.), Anshul Gupta (IBM), and Friedrich
Grund (WAIS) assisted in porting UMFPACK to different platforms. Penny
Anderson also incorporated UMFPACK v4.0 into MATLAB, for lu, backslash (\),
and forward slash (/).
David Bateman (Motorola) wrote the initial version of the packed complex
input option, and umfpack_get_determinant.
--------------------------------------------------------------------------------
Files and directories in the UMFPACK distribution:
--------------------------------------------------------------------------------
----------------------------------------------------------------------------
Subdirectories of the UMFPACK directory:
----------------------------------------------------------------------------
Doc documentation
Source primary source code
Include include files for use in your code that calls UMFPACK
Demo demo programs. also serves as test of the UMFPACK installation.
MATLAB UMFPACK mexFunction for MATLAB, and supporting m-files
build where the compiled libraries and demos are placed
Config source file to construct umfpack.h
----------------------------------------------------------------------------
Files in the UMFPACK directory:
----------------------------------------------------------------------------
Makefile a very simple Makefile (optional); just for simplifying cmake
CMakeLists.txt cmake script for building UMFPACK
README.txt this file
----------------------------------------------------------------------------
Doc directory: documentation
----------------------------------------------------------------------------
ChangeLog change log
License.txt the UMFPACK License (GPL)
gpl.txt the GNU GPL
Makefile for creating the documentation
UMFPACK_QuickStart.tex Quick Start guide (source)
UMFPACK_QuickStart.pdf Quick Start guide (PDF)
UserGuide.bib User Guide (references)
UMFPACK_UserGuide.tex User Guide (LaTeX)
UMFPACK_UserGuide.pdf User Guide (PDF)
----------------------------------------------------------------------------
Source2 directory:
----------------------------------------------------------------------------
This directory contains all source files used directly in CMakeLists.txt.
Each of them sets various #define's, and then #include's files in the
Source/ directory.
----------------------------------------------------------------------------
Source directory:
----------------------------------------------------------------------------
umfpack_col_to_triplet.c convert col form to triplet
umfpack_defaults.c set Control defaults
umfpack_free_numeric.c free Numeric object
umfpack_free_symbolic.c free Symbolic object
umfpack_get_determinant.c compute determinant from Numeric object
umfpack_get_lunz.c get nz's in L and U
umfpack_get_numeric.c get Numeric object
umfpack_get_symbolic.c get Symbolic object
umfpack_load_numeric.c load Numeric object from file
umfpack_load_symbolic.c load Symbolic object from file
umfpack_numeric.c numeric factorization
umfpack_qsymbolic.c symbolic factorization, user Q
umfpack_report_control.c print Control settings
umfpack_report_info.c print Info statistics
umfpack_report_matrix.c print col or row-form sparse matrix
umfpack_report_numeric.c print Numeric object
umfpack_report_perm.c print permutation
umfpack_report_status.c print return status
umfpack_report_symbolic.c print Symbolic object
umfpack_report_triplet.c print triplet matrix
umfpack_report_vector.c print dense vector
umfpack_save_numeric.c save Numeric object to file
umfpack_save_symbolic.c save Symbolic object to file
umfpack_scale.c scale a vector
umfpack_solve.c solve a linear system
umfpack_symbolic.c symbolic factorization
umfpack_tictoc.c timer
umfpack_timer.c timer
umfpack_transpose.c transpose a matrix
umfpack_triplet_to_col.c convert triplet to col form
umf_config.h configuration file (BLAS, memory, timer)
umf_internal.h definitions internal to UMFPACK
umf_version.h version definitions (int/int64_t, real/complex)
umf_analyze.[ch] symbolic factorization of A'*A
umf_apply_order.[ch] apply column etree postorder
umf_assemble.[ch] assemble elements into current front
umf_blas3_update.[ch] rank-k update. Uses level-3 BLAS
umf_build_tuples.[ch] construct tuples for elements
umf_colamd.[ch] COLAMD pre-ordering, modified for UMFPACK
umf_cholmod.[ch] interface to CHOLMOD
umf_create_element.[ch] create a new element
umf_dump.[ch] debugging routines, not normally active
umf_extend_front.[ch] extend the current frontal matrix
umf_free.[ch] free memory
umf_fsize.[ch] determine largest front in each subtree
umf_garbage_collection.[ch] compact Numeric->Memory
umf_get_memory.[ch] make Numeric->Memory bigger
umf_grow_front.[ch] make current frontal matrix bigger
umf_init_front.[ch] initialize a new frontal matrix
umf_is_permutation.[ch] checks the validity of a permutation vector
umf_kernel.[ch] the main numeric factorization kernel
umf_kernel_init.[ch] initializations for umf_kernel
umf_kernel_wrapup.[ch] wrapup for umf_kernel
umf_local_search.[ch] local row and column pivot search
umf_lsolve.[ch] solve Lx=b
umf_ltsolve.[ch] solve L'x=b and L.'x=b
umf_malloc.[ch] malloc some memory
umf_mem_alloc_element.[ch] allocate element in Numeric->Memory
umf_mem_alloc_head_block.[ch] alloc. block at head of Numeric->Memory
umf_mem_alloc_tail_block.[ch] alloc. block at tail of Numeric->Memory
umf_mem_free_tail_block.[ch] free block at tail of Numeric->Memory
umf_mem_init_memoryspace.[ch] initialize Numeric->Memory
umf_realloc.[ch] realloc memory
umf_report_perm.[ch] print a permutation vector
umf_report_vector.[ch] print a double vector
umf_row_search.[ch] look for a pivot row
umf_scale.[ch] scale the pivot column
umf_scale_column.[ch] move pivot row & column into place, log P and Q
umf_set_stats.[ch] set statistics (final or estimates)
umf_singletons.[ch] find all zero-cost pivots
umf_solve.[ch] solve a linear system
umf_start_front.[ch] start a new frontal matrix for one frontal chain
umf_store_lu.[ch] store LU factors of current front
umf_symbolic_usage.[ch] determine memory usage for Symbolic object
umf_transpose.[ch] transpose a matrix in row or col form
umf_triplet.[ch] convert triplet to column form
umf_tuple_lengths.[ch] determine the tuple list lengths
umf_usolve.[ch] solve Ux=b
umf_utsolve.[ch] solve U'x=b and U.'x=b
umf_valid_numeric.[ch] checks the validity of a Numeric object
umf_valid_symbolic.[ch] check the validity of a Symbolic object
----------------------------------------------------------------------------
Include directory:
----------------------------------------------------------------------------
umfpack.h include file for user programs. Also serves as
source-code level documentation.
----------------------------------------------------------------------------
Demo directory:
----------------------------------------------------------------------------
Makefile to compile the demos
umfpack_simple.c a simple demo
umpack_xx_demo.c template to create the demo codes below
umfpack_di_demo.sed for creating umfpack_di_demo.c
umfpack_dl_demo.sed for creating umfpack_dl_demo.c
umfpack_zi_demo.sed for creating umfpack_zi_demo.c
umfpack_zl_demo.sed for creating umfpack_zl_demo.c
umfpack_di_demo.c a full demo (real/int version)
umfpack_dl_demo.c a full demo (real/int64_t version)
umfpack_zi_demo.c a full demo (complex/int version)
umfpack_zl_demo.c a full demo (complex/int64_t version)
umfpack_di_demo.out umfpack_di_demo output
umfpack_dl_demo.out umfpack_dl_demo output
umfpack_zi_demo.out umfpack_zi_demo output
umfpack_zl_demo.out umfpack_zl_demo output
umf4.c a demo (real/int) for Harwell/Boeing matrices
umf4.out output of "make hb"
HB/ directory of sample Harwell/Boeing matrices
readhb.f reads HB matrices, keeps zero entries
readhb_nozeros.f reads HB matrices, removes zero entries
readhb_size.f reads HB matrix dimension, nnz
umf4_f77wrapper.c a simple FORTRAN interface for UMFPACK.
compile with "make fortran"
umf4hb.f a demo of the FORTRAN interface
umf4hb.out output of "make fortran"
umf4_f77zwrapper.c a simple FORTRAN interface for the complex
UMFPACK routines. compile with "make fortran"
umf4zhb.f a demo of the FORTRAN interface (complex)
umf4zhb.out output of umf4zhb with HB/qc324.cua
umf4hb64.f 64-bit version of umf4hb.f
----------------------------------------------------------------------------
MATLAB directory:
----------------------------------------------------------------------------
Contents.m for "help umfpack" listing of toolbox contents
lu_normest.m 1-norm estimate of A-L*U (by Hager & Davis).
luflop.m for "help luflop"
luflopmex.c luflop mexFunction, for computing LU flop count
umfpack.m for "help umfpack"
umfpack_btf.m solve Ax=b using umfpack and dmperm
umfpack_demo.m a full umfpack demo
umfpack_details.m the details of how to use umfpack
umfpack_make.m compile the umfpack mexFunction within MATLAB
umfpack_report.m report statistics
umfpack_simple.m a simple umfpack demo
umfpack_solve.m x=A\b or b/A for arbitrary b
umfpack_test.m extensive test, requires ssget
umfpackmex.c the umfpack mexFunction
west0067.mat sparse matrix for umfpack_demo.m
umfpack_demo.m.out output of umfpack_demo.m
umfpack_simple.m.out output of umfpack_simple