第1页 / 共140页
第2页 / 共140页
第3页 / 共140页
第4页 / 共140页
第5页 / 共140页
第6页 / 共140页
第7页 / 共140页
第8页 / 共140页
UMFPack 5.51 UserGuide.pdf
UMFPACK User Guide
Dept. of Computer and Information Science and Engineering
Timothy A. Davis
Univ. of Florida, Gainesville, FL
VERSION 5.5.1, Jan 25, 2011
Abstract
UMFPACK is a set of routines for solving unsymmetric sparse linear systems, Ax = b,
using the Unsymmetric MultiFrontal method and direct sparse LU factorization. It is written in
ANSI/ISO C, with a MATLAB interface. UMFPACK relies on the Level-3 Basic Linear Algebra
Subprograms (dense matrix multiply) for its performance. This code works on Windows and
many versions of Unix (Sun Solaris, Red Hat Linux, IBM AIX, SGI IRIX, and Compaq Alpha).
Technical Report TR-04-003 (revised)
Copyright c1995-2009 by Timothy A. Davis. All Rights Reserved. UMFPACK is available
under alternate licences; contact T. Davis for details.
UMFPACK License: Your use or distribution of UMFPACK or any modified version of
UMFPACK implies that you agree to this License.
This library is free software; you can redistribute it and/or modify it under the terms of the
GNU General Public License as published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this library; if
not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-
1301 USA
Permission is hereby granted to use or copy this program under the terms of the GNU GPL,
provided that the Copyright, this License, and the Availability of the original version is retained on
all copies. User documentation of any code that uses this code or any modified version of this code
must cite the Copyright, this License, the Availability note, and ”Used by permission.” Permission
to modify the code and to distribute modified code is granted, provided the Copyright, this License,
and the Availability note are retained, and a notice that the code was modified is included.
Availability: http://www.cise.ufl.edu/research/sparse/umfpack
Acknowledgments:
This work was supported by the National Science Foundation, under grants DMS-9504974,
DMS-9803599, and CCR-0203270. The upgrade to Version 4.1 and the inclusion of the symmetric
and 2-by-2 pivoting strategies were done while the author was on sabbatical at Stanford University
and Lawrence Berkeley National Laboratory.
1
Contents
1 Overview
2 Availability
3 Primary changes from prior versions
3.1 Version 5.5.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Version 5.4.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Version 5.3.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Version 5.2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Version 5.1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Version 5.0.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Version 5.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Version 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Version 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Version 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11 Version 4.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.12 Version 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.13 Version 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Using UMFPACK in MATLAB
5
7
7
7
7
7
7
7
8
8
8
8
8
8
8
8
9
5 Using UMFPACK in a C program
12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1 The size of an integer
5.2 Real and complex floating-point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.3 Primary routines, and a simple example . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4 A note about zero-sized arrays
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.5 Alternative routines
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.6 Matrix manipulation routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.7 Getting the contents of opaque objects . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.8 Reporting routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.9 Utility routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.10 Control parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.11 Error codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.12 Larger examples
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Synopsis of C-callable routines
25
6.1 Primary routines: real/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Alternative routines: real/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.3 Matrix manipulation routines: real/int . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.4 Getting the contents of opaque objects: real/int . . . . . . . . . . . . . . . . . . . . 26
6.5 Reporting routines: real/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.6 Primary routines: complex/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.7 Alternative routines: complex/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.8 Matrix manipulation routines: complex/int . . . . . . . . . . . . . . . . . . . . . . . 27
2
6.9 Getting the contents of opaque objects: complex/int . . . . . . . . . . . . . . . . . . 28
6.10 Reporting routines: complex/int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.11 Utility routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.12 AMD ordering routines
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7 Using UMFPACK in a Fortran program
29
8 Installation
31
Installing the C library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
8.1
Installing the MATLAB interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.2
8.3
Installing the Fortran interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.4 Known Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
9 Future work
35
10 The primary UMFPACK routines
37
10.1 umfpack * symbolic
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
10.2 umfpack * numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
10.3 umfpack * solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10.4 umfpack * free symbolic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
10.5 umfpack * free numeric
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
11 Alternative routines
67
11.1 umfpack * defaults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
11.2 umfpack * qsymbolic and umfpack * fsymbolic . . . . . . . . . . . . . . . . . . . . . 69
11.3 umfpack * wsolve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
12 Matrix manipulation routines
76
12.1 umfpack * col to triplet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
12.2 umfpack * triplet to col
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
12.3 umfpack * transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
12.4 umfpack * scale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
13 Getting the contents of opaque objects
89
13.1 umfpack * get lunz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
13.2 umfpack * get numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
13.3 umfpack * get symbolic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
13.4 umfpack * save numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
13.5 umfpack * load numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
13.6 umfpack * save symbolic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
13.7 umfpack * load symbolic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
13.8 umfpack * get determinant
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3
14 Reporting routines
115
14.1 umfpack * report status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
14.2 umfpack * report control
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
14.3 umfpack * report info . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
14.4 umfpack * report matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
14.5 umfpack * report numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
14.6 umfpack * report perm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
14.7 umfpack * report symbolic
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
14.8 umfpack * report triplet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
14.9 umfpack * report vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
15 Utility routines
137
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
15.1 umfpack timer
15.2 umfpack tic and umfpack toc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4
1 Overview
UMFPACK1 is a set of routines for solving systems of linear equations, Ax = b, when A is sparse
and unsymmetric. It is based on the Unsymmetric-pattern MultiFrontal method [6, 7]. UMFPACK
factorizes PAQ, PRAQ, or PR−1AQ into the product LU, where L and U are lower and upper
triangular, respectively, P and Q are permutation matrices, and R is a diagonal matrix of row
scaling factors (or R = I if row-scaling is not used). Both P and Q are chosen to reduce fill-in (new
nonzeros in L and U that are not present in A). The permutation P has the dual role of reducing
fill-in and maintaining numerical accuracy (via relaxed partial pivoting and row interchanges).
The sparse matrix A can be square or rectangular, singular or non-singular, and real or complex
(or any combination). Only square matrices A can be used to solve Ax = b or related systems.
Rectangular matrices can only be factorized.
UMFPACK first finds a column pre-ordering that reduces fill-in, without regard to numerical
values. It scales and analyzes the matrix, and then automatically selects one of two strategies for
pre-ordering the rows and columns: unsymmetric and symmetric. These strategies are described
below.
First, all pivots with zero Markowitz cost are eliminated and placed in the LU factors. The
remaining submatrix S is then analyzed. The following rules are applied, and the first one that
matches defines the strategy.
• Rule 1: A rectangular → unsymmetric.
• Rule 2: If the zero-Markowitz elimination results in a rectangular S, or an S whose diagonal
has not been preserved, the unsymmetric strategy is used.
• The symmetry σ1 of S is computed.
It is defined as the number of matched off-diagonal
entries, divided by the total number of off-diagonal entries. An entry sij is matched if sji is
also an entry. They need not be numerically equal. An entry is a value in A which is present
in the input data structure. All nonzeros are entries, but some entries may be numerically
zero. Let d be the number of nonzero entries on the diagonal of S. Let S be ν-by-ν. Rule 3:
(σ1 ≥ 0.5) ∧ (d ≥ 0.9ν) → symmetric. The matrix has a nearly symmetric nonzero pattern
(50% or more), and a mostly-zero-free diagonal (90% or more nonzero).
• Rule 4: Otherwise, the unsymmetric strategy is used.
Each strategy is described below:
• unsymmetric: The column pre-ordering of S is computed by a modified version of COLAMD
[8, 9, 27]. The method finds a symmetric permutation Q of the matrix STS (without forming
STS explicitly). This is a good choice for Q, since the Cholesky factors of (SQ)T(SQ) are
an upper bound (in terms of nonzero pattern) of the factor U for the unsymmetric LU
factorization (PSQ = LU) regardless of the choice of P [19, 20, 22]. This modified version
of COLAMD also computes the column elimination tree and post-orders the tree. It finds
the upper bound on the number of nonzeros in L and U. It also has a different threshold for
determining dense rows and columns. During factorization, the column pre-ordering can be
modified. Columns within a single super-column can be reshuffled, to reduce fill-in. Threshold
1Pronounced with two syllables: umph-pack
5
partial pivoting is used with no preference given to the diagonal entry. Within a given pivot
column j, an entry aij can be chosen if |aij| ≥ 0.1 max|a∗j|. Among those numerically
acceptable entries, the sparsest row i is chosen as the pivot row.
• symmetric: The column ordering is computed from AMD [1, 2], applied to the pattern of S +
ST followed by a post-ordering of the supernodal elimination tree of S + ST. No modification
of the column pre-ordering is made during numerical factorization. Threshold partial pivoting
is used, with a strong preference given to the diagonal entry. The diagonal entry is chosen
if ajj ≥ 0.001 max|a∗j|. Otherwise, a sparse row is selected, using the same method used by
the unsymmetric strategy.
The symmetric strategy, and their automatic selection, are new to Version 4.1. Version 4.0 only
used the unsymmetric strategy. Versions 4.1 through 5.3 included a 2-by-2 ordering strategy, but
this option has been disabled in Version 5.4.
Once the strategy is selected, the factorization of the matrix A is broken down into the fac-
torization of a sequence of dense rectangular frontal matrices. The frontal matrices are related
to each other by a supernodal column elimination tree, in which each node in the tree represents
one frontal matrix. This analysis phase also determines upper bounds on the memory usage, the
floating-point operation count, and the number of nonzeros in the LU factors.
UMFPACK factorizes each chain of frontal matrices in a single working array, similar to how
the unifrontal method [18] factorizes the whole matrix. A chain of frontal matrices is a sequence
of fronts where the parent of front i is i+1 in the supernodal column elimination tree. For the
nonsingular matrices factorized with the unsymmetric strategy, there are exactly the same number
of chains as there are leaves in the supernodal column elimination tree. UMFPACK is an outer-
product based, right-looking method. At the k-th step of Gaussian elimination, it represents the
updated submatrix Ak as an implicit summation of a set of dense sub-matrices (referred to as
elements, borrowing a phrase from finite-element methods) that arise when the frontal matrices are
factorized and their pivot rows and columns eliminated.
Each frontal matrix represents the elimination of one or more columns; each column of A will
be eliminated in a specific frontal matrix, and which frontal matrix will be used for which column
is determined by the pre-analysis phase. The pre-analysis phase also determines the worst-case size
of each frontal matrix so that they can hold any candidate pivot column and any candidate pivot
row. From the perspective of the analysis phase, any candidate pivot column in the frontal matrix
is identical (in terms of nonzero pattern), and so is any row. However, the numeric factorization
phase has more information than the analysis phase. It uses this information to reorder the columns
within each frontal matrix to reduce fill-in. Similarly, since the number of nonzeros in each row and
column are maintained (more precisely, COLMMD-style approximate degrees [21]), a pivot row can
be selected based on sparsity-preserving criteria (low degree) as well as numerical considerations
(relaxed threshold partial pivoting).
When the symmetric strategy are used, the column preordering is not refined during numeric
factorization. Row pivoting for sparsity and numerical accuracy is performed if the diagonal entry
is too small.
More details of the method, including experimental results, are described in [5, 4], available at
http://www.cise.ufl.edu/tech-reports.
6
2 Availability
In addition to appearing as a Collected Algorithm of the ACM, UMFPACK is available at
http://www.cise.ufl.edu/research/sparse. It is included as a built-in routine in MATLAB. Version
4.0 (in MATLAB 6.5) does not have the symmetric strategy and it takes less advantage of the
level-3 BLAS [11, 12, 28, 25]. Versions 5.x through v4.1 tend to be much faster than Version
4.0, particularly on unsymmetric matrices with mostly symmetric nonzero pattern (such as finite
element and circuit simulation matrices). Version 3.0 and following make use of a modified ver-
sion of COLAMD V2.0 by Timothy A. Davis, Stefan Larimore, John Gilbert, and Esmond Ng.
The original COLAMD V2.1 is available in as a built-in routine in MATLAB V6.0 (or later),
and at http://www.cise.ufl.edu/research/sparse. These codes are also available in Netlib [13] at
http://www.netlib.org. UMFPACK Versions 2.2.1 and earlier, co-authored with Iain Duff, are avail-
able at http://www.cise.ufl.edu/research/sparse and as MA38 (functionally equivalent to Version
2.2.1) in the Harwell Subroutine Library.
NOTE: you must use the correct version of AMD with UMFPACK; using an old
version of AMD with a newer version of UMFPACK can fail.
3 Primary changes from prior versions
A detailed list of changes is in the ChangeLog file.
3.1 Version 5.5.0
Added more user ordering options (interface to CHOLMOD and METIS orderings, and the ability
to pass in a user ordering function). Minor change to how the 64-bit BLAS is used. Added an
option to disable the search for singletons.
3.2 Version 5.4.0
Disabled the 2-by-2 ordering strategy. Bug fix for umfpack_make.m for Windows.
3.3 Version 5.3.0
A bug fix for structurally singular matrices, and a compiler workaround for gcc versions 4.2.(3 and
4).
3.4 Version 5.2.0
Change of license from GNU Lesser GPL to the GNU GPL.
3.5 Version 5.1.0
Port of MATLAB interface to 64-bit MATLAB.
7
3.6 Version 5.0.3
Renamed the MATLAB function to umfpack2, so as not to confict with itself (the MATLAB built-in
version of UMFPACK).
3.7 Version 5.0
Changed long to UF long, controlled by the UFconfig.h file. A UF long is normally just long,
except on the Windows 64 (WIN64) platform. In that case, it becomes
int64.
3.8 Version 4.6
Added additional options to umf solve.c.
3.9 Version 4.5
Added function pointers for malloc, calloc, realloc, free, printf, hypot, and complex divisiion, so
that these functions can be redefined at run-time. Added a version number so you can determine
the version of UMFPACK at run time or compile time. UMFPACK requires AMD v2.0 or later.
3.10 Version 4.4
Bug fix in strategy selection in umfpack * qsymbolic. Added packed complex case for all complex
input/output arguments. Added umfpack get determinant. Added minimal support for Microsoft
Visual Studio (the umf multicompile.c file).
3.11 Version 4.3.1
Minor bug fix in the forward/backsolve. This bug had the effect of turning off iterative refinement
when solving ATx = b after factorizing A. UMFPACK mexFunction now factorizes AT in its
forward-slash operation.
3.12 Version 4.3
No changes are visible to the C or MATLAB user, except the presence of one new control parameter
in the Control array, and three new statistics in the Info array. The primary change is the addition
of an (optional) drop tolerance.
3.13 Version 4.1
The following is a summary of the main changes that are visible to the C or MATLAB user:
1. New ordering strategies added. No changes are required in user code (either C or MATLAB) to
use the new default strategy, which is an automatic selection of the unsymmetric, symmetric,
or 2-by-2 strategies.
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
