Blame view
fvn_sparse/UMFPACK/Doc/QuickStart.tex
42.7 KB
422234dc3
git-svn-id: https...
|
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 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 |
%-------------------------------------------------------------------------------
% The QuickStart.tex file.
%-------------------------------------------------------------------------------
\documentclass[11pt]{article}
ewcommand{\m}[1]{{\bf{#1}}} % for matrices and vectors
ewcommand{\tr}{^{\sf T}} % transpose
\topmargin 0in
\textheight 9in
\oddsidemargin 0pt
\evensidemargin 0pt
\textwidth 6.5in
\begin{document}
\author{Timothy A. Davis \\
Dept. of Computer and Information Science and Engineering \\
Univ. of Florida, Gainesville, FL}
\title{UMFPACK Version 5.1 Quick Start Guide}
\date{May 31, 2007}
\maketitle
%-------------------------------------------------------------------------------
\begin{abstract}
UMFPACK is a set of routines for solving unsymmetric sparse linear
systems, $\m{Ax}=\m{b}$, using the Unsymmetric-pattern 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).
This is a ``quick start'' guide for Unix users of the C interface.
\end{abstract}
%-------------------------------------------------------------------------------
UMFPACK Version 5.1, Copyright\copyright 1995-2006 by Timothy A. Davis.
All Rights Reserved. Refer to the UMFPACK User Guide
for the License. See
ewline
http://www.cise.ufl.edu/research/sparse/umfpack
for the code and full documentation.
%-------------------------------------------------------------------------------
\section{Overview}
%-------------------------------------------------------------------------------
UMFPACK is a set of routines for solving systems of linear
equations, $\m{Ax}=\m{b}$, when $\m{A}$ is sparse and unsymmetric.
The sparse matrix $\m{A}$ can be square or rectangular, singular
or non-singular, and real or complex (or any combination). Only square
matrices $\m{A}$ can be used to solve $\m{Ax}=\m{b}$ or related systems.
Rectangular matrices can only be factorized.
UMFPACK is a built-in routine in MATLAB used by the forward and
backslash operator, and the {\tt lu} routine.
The following is a short
introduction to Unix users of the C interface of UMFPACK.
%-------------------------------------------------------------------------------
The C-callable UMFPACK library consists of 32 user-callable routines and one
include file. Twenty-eight of the routines come in four versions, with
different sizes of integers and for real or complex floating-point numbers.
This Quick Start Guide assumes you are working with real matrices
(not complex) and with {\tt int}'s as integers (not {\tt long}'s).
Refer to the User Guide for information about the complex and
long integer versions. The include file {\tt umfpack.h}
must be included in any C program that uses UMFPACK.
For more details, see:
{\em A column pre-ordering strategy for the unsymmetric-pattern multifrontal method},
Davis, T. A.,
ACM Trans. Math. Software, vol 30. no 2, 2004, pp. 165-195, and
{\em Algorithm 832: {UMFPACK}, an unsymmetric-pattern multifrontal method},
same issue, pp. 196-199.
%-------------------------------------------------------------------------------
\section{Primary routines, and a simple example}
%-------------------------------------------------------------------------------
Five primary UMFPACK routines are required to factorize $\m{A}$ or
solve $\m{Ax}=\m{b}$. An overview of the primary features of the routines
is given in Section~\ref{Primary}.
Additional routines are available for passing a different column ordering
to UMFPACK, changing default parameters, manipulating sparse matrices,
getting the LU factors, save and loading the LU factors from a file,
computing the determinant,
and reporting results. See the User Guide for more information.
\begin{itemize}
\item {\tt umfpack\_di\_symbolic}:
Pre-orders the columns of $\m{A}$ to reduce fill-in and performs a
symbolic analysis.
Returns an opaque {\tt Symbolic} object as a {\tt void *}
pointer. The object contains the symbolic analysis and is needed for the
numerical factorization.
\item {\tt umfpack\_di\_numeric}:
Numerically scales and then factorizes a sparse matrix
$\m{PAQ}$, $\m{PRAQ}$, or $\m{PR}^{-1}\m{AQ}$ into the product $\m{LU}$,
where
$\m{P}$ and $\m{Q}$ are permutation matrices, $\m{R}$ is a diagonal
matrix of scale factors, $\m{L}$ is lower triangular with unit diagonal,
and $\m{U}$ is upper triangular. Requires the
symbolic ordering and analysis computed by {\tt umfpack\_di\_symbolic}.
Returns an opaque {\tt Numeric} object as a
{\tt void *} pointer. The object contains the numerical factorization and
is used by {\tt umfpack\_di\_solve}.
\item {\tt umfpack\_di\_solve}:
Solves a sparse linear system ($\m{Ax}=\m{b}$, $\m{A}\tr\m{x}=\m{b}$, or
systems involving just $\m{L}$ or $\m{U}$), using the numeric factorization
computed by {\tt umfpack\_di\_numeric}.
\item {\tt umfpack\_di\_free\_symbolic}:
Frees the {\tt Symbolic} object created by {\tt umfpack\_di\_symbolic}.
\item {\tt umfpack\_di\_free\_numeric}:
Frees the {\tt Numeric} object created by {\tt umfpack\_di\_numeric}.
\end{itemize}
The matrix $\m{A}$ is represented in compressed column form, which is
identical to the sparse matrix representation used by MATLAB. It consists
of three arrays, where the matrix is {\tt m}-by-{\tt n},
with {\tt nz} entries:
{\footnotesize
\begin{verbatim}
int Ap [n+1] ;
int Ai [nz] ;
double Ax [nz] ;
\end{verbatim}
}
All nonzeros are entries, but an entry may be numerically zero. The row indices
of entries in column {\tt j} are stored in
{\tt Ai[Ap[j]} ... {\tt Ap[j+1]-1]}.
The corresponding numerical values are stored in
{\tt Ax[Ap[j]} ... {\tt Ap[j+1]-1]}.
No duplicate row indices may be present, and the row indices in any given
column must be sorted in ascending order. The first entry {\tt Ap[0]} must be
zero. The total number of entries in the matrix is thus {\tt nz = Ap[n]}.
Except for the fact that extra zero entries can be included, there is thus a
unique compressed column representation of any given matrix $\m{A}$.
Here is a simple main program, {\tt umfpack\_simple.c}, that illustrates the
basic usage of UMFPACK.
{\footnotesize
\begin{verbatim}
#include <stdio.h>
#include "umfpack.h"
int n = 5 ;
int Ap [ ] = {0, 2, 5, 9, 10, 12} ;
int Ai [ ] = { 0, 1, 0, 2, 4, 1, 2, 3, 4, 2, 1, 4} ;
double Ax [ ] = {2., 3., 3., -1., 4., 4., -3., 1., 2., 2., 6., 1.} ;
double b [ ] = {8., 45., -3., 3., 19.} ;
double x [5] ;
int main (void)
{
double *null = (double *) NULL ;
int i ;
void *Symbolic, *Numeric ;
(void) umfpack_di_symbolic (n, n, Ap, Ai, Ax, &Symbolic, null, null) ;
(void) umfpack_di_numeric (Ap, Ai, Ax, Symbolic, &Numeric, null, null) ;
umfpack_di_free_symbolic (&Symbolic) ;
(void) umfpack_di_solve (UMFPACK_A, Ap, Ai, Ax, x, b, Numeric, null, null) ;
umfpack_di_free_numeric (&Numeric) ;
for (i = 0 ; i < n ; i++) printf ("x [%d] = %g
", i, x [i]) ;
return (0) ;
}
\end{verbatim}
}
The {\tt Ap}, {\tt Ai}, and {\tt Ax} arrays represent the matrix
\[
\m{A} = \left[
\begin{array}{rrrrr}
2 & 3 & 0 & 0 & 0 \\
3 & 0 & 4 & 0 & 6 \\
0 & -1 & -3 & 2 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 4 & 2 & 0 & 1 \\
\end{array}
\right].
\]
and the solution is $\m{x} = [1 \, 2 \, 3 \, 4 \, 5]\tr$. The program uses
default control settings and does not return any statistics about the ordering,
factorization, or solution ({\tt Control} and {\tt Info} are both
{\tt (double *) NULL}).
For routines to manipulate a simpler ``triplet-form'' data structure for your
sparse matrix $\m{A}$, refer to the UMFPACK User Guide.
%-------------------------------------------------------------------------------
\section{Synopsis of primary C-callable routines}
\label{Synopsis}
%-------------------------------------------------------------------------------
The matrix $\m{A}$ is {\tt m}-by-{\tt n} with {\tt nz} entries.
The optional {\tt umfpack\_di\_defaults} routine loads the default control
parameters into the {\tt Control} array. The settings can then be modified
before passing the array to the other routines. Refer to Section~\ref{Primary}
for more details.
{\footnotesize
\begin{verbatim}
#include "umfpack.h"
int status, sys, n, m, nz, Ap [n+1], Ai [nz] ;
double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], Ax [nz], X [n], B [n] ;
void *Symbolic, *Numeric ;
status = umfpack_di_symbolic (m, n, Ap, Ai, Ax, &Symbolic, Control, Info) ;
status = umfpack_di_numeric (Ap, Ai, Ax, Symbolic, &Numeric, Control, Info) ;
status = umfpack_di_solve (sys, Ap, Ai, Ax, X, B, Numeric, Control, Info) ;
umfpack_di_free_symbolic (&Symbolic) ;
umfpack_di_free_numeric (&Numeric) ;
umfpack_di_defaults (Control) ;
\end{verbatim}
}
%-------------------------------------------------------------------------------
\section{Installation}
\label{Install}
%-------------------------------------------------------------------------------
You will need to install both UMFPACK v5.1 and AMD v2.2 to use UMFPACK.
Note that UMFPACK v5.1 cannot use AMD v1.2 or earlier.
The {\tt UMFPACK} and {\tt AMD} subdirectories must be placed side-by-side
within the same parent directory. AMD is a stand-alone package that
is required by UMFPACK. UMFPACK can be compiled without the
BLAS but your performance will be much less than what it should be.
System-dependent configurations are in the {\tt UFconfig/UFconfig.mk}
file. The default
settings will work on most systems, except for the BLAS definition.
Sample configurations are provided
for Linux, Sun Solaris, SGI IRIX, IBM AIX, and the DEC/Compaq Alpha.
To compile and install both packages,
go to the UMFPACK directory and type {\tt make}. This will compile the
libraries ({\tt AMD/Lib/libamd.a} and {\tt UMFPACK/Lib/libumfpack.a}).
A demo of the AMD ordering routine will be compiled and tested in
the {\tt AMD/Demo} directory, and five demo programs will then be
compiled and tested in the {\tt UMFPACK/Demo} directory.
The outputs of these demo programs will then be compared with output
files in the distribution. Expect to see a few differences, such as
residual norms, compile-time control settings, and perhaps memory usage
differences.
To use {\tt make} to compile the MATLAB mexFunctions for MATLAB
and AMD, you can either type {\tt make mex} in the UMFPACK directory.
You may first need to edit the {\tt UFconfig/UFconfig.mk} file to
modify the definition of the {\tt MEX}, if you have a version of MATLAB
older than Version 7.2. Remove the {\tt -largeArrayDims} definition.
If you use the MATLAB command {\tt umfpack\_make} in the MATLAB directory,
then this case is handled for you automatically.
If you compile UMFPACK and AMD and then later change the
{\tt UFconfig/UFconfig.mk} file
then you should type {\tt make purge} and then {\tt make} to recompile.
Here are the various parameters that you can control in your
{\tt UFconfig/UFconfig.mk} file:
\begin{itemize}
\item {\tt CC = } your C compiler, such as {\tt cc}.
\item {\tt RANLIB = } your system's {\tt ranlib} program, if needed.
\item {\tt CFLAGS = } optimization flags, such as {\tt -O}.
\item {\tt UMFPACK\_CONFIG = } configuration settings, for the BLAS,
memory allocation routines, and timing routines.
\item {\tt LIB = } your libraries, such as {\tt -lm} or {\tt -lblas}.
\item {\tt RM =} the command to delete a file.
\item {\tt MV =} the command to rename a file.
\item {\tt MEX =} the command to compile a MATLAB mexFunction.
\item {\tt F77 =} the command to compile a Fortran program (optional).
\item {\tt F77FLAGS =} the Fortran compiler flags (optional).
\item {\tt F77LIB =} the Fortran libraries (optional).
\end{itemize}
The {\tt UMFPACK\_CONFIG} string can include combinations of the following;
most deal with how the BLAS are called:
\begin{itemize}
\item {\tt -DNBLAS} if you do not have any BLAS at all.
\item {\tt -DNSUNPERF} if you are on Solaris but do not have the Sun
Performance Library.
\item {\tt -DLONGBLAS} if your BLAS takes non-{\tt int} integer arguments.
\item {\tt -DBLAS\_INT = } the integer used by the BLAS.
\item {\tt -DBLAS\_NO\_UNDERSCORE}
for controlling how C calls the Fortran BLAS.
This is set automatically for Windows,
Sun Solaris, SGI Irix, Red Hat Linux, Compaq Alpha, and
AIX (the IBM RS 6000).
\item {\tt -DGETRUSAGE} if you have the {\tt getrusage} function.
\item {\tt -DNPOSIX} if you do not have the POSIX-compliant
{\tt sysconf} and {\tt times} routines.
\item {\tt -DNRECIPROCAL} controls a trade-off between speed and accuracy.
This is off by default (speed preferred over accuracy) except when
compiling for MATLAB.
\end{itemize}
When you compile your program that uses the C-callable UMFPACK library,
you need to add the both {\tt UMFPACK/Lib/libumfpack.a} and
{\tt AMD/Lib/libamd.a}
libraries, and you need to tell your compiler to look in the
directories {\tt UMFPACK/Include} and {\tt AMD/Include} for include
files. See {\tt UMFPACK/Demo/Makefile} for an example.
You do not need to directly include any AMD include files in your
program, unless you directly call AMD routines. You only need the
\begin{verbatim}
#include "umfpack.h"
\end{verbatim}
statement, as described in Section~\ref{Synopsis}.
%-------------------------------------------------------------------------------
ewpage
\section{The primary UMFPACK routines}
\label{Primary}
%-------------------------------------------------------------------------------
\subsection{umfpack\_di\_symbolic}
{\footnotesize
\begin{verbatim}
int umfpack_di_symbolic
(
int n_row,
int n_col,
const int Ap [ ],
const int Ai [ ],
const double Ax [ ],
void **Symbolic,
const double Control [UMFPACK_CONTROL],
double Info [UMFPACK_INFO]
) ;
Purpose:
Given nonzero pattern of a sparse matrix A in column-oriented form,
umfpack_di_symbolic performs a column pre-ordering to reduce fill-in
(using COLAMD or AMD) and a symbolic factorization. This is required
before the matrix can be numerically factorized with umfpack_di_numeric.
For the following discussion, let S be the submatrix of A obtained after
eliminating all pivots of zero Markowitz cost. S has dimension
(n_row-n1-nempty_row) -by- (n_col-n1-nempty_col), where
n1 = Info [UMFPACK_COL_SINGLETONS] + Info [UMFPACK_ROW_SINGLETONS],
nempty_row = Info [UMFPACK_NEMPTY_ROW] and
nempty_col = Info [UMFPACK_NEMPTY_COL].
Returns:
The status code is returned. See Info [UMFPACK_STATUS], below.
Arguments:
int n_row ; Input argument, not modified.
int n_col ; Input argument, not modified.
A is an n_row-by-n_col matrix. Restriction: n_row > 0 and n_col > 0.
int Ap [n_col+1] ; Input argument, not modified.
Ap is an integer array of size n_col+1. On input, it holds the
"pointers" for the column form of the sparse matrix A. Column j of
the matrix A is held in Ai [(Ap [j]) ... (Ap [j+1]-1)]. The first
entry, Ap [0], must be zero, and Ap [j] <= Ap [j+1] must hold for all
j in the range 0 to n_col-1. The value nz = Ap [n_col] is thus the
total number of entries in the pattern of the matrix A. nz must be
greater than or equal to zero.
int Ai [nz] ; Input argument, not modified, of size nz = Ap [n_col].
The nonzero pattern (row indices) for column j is stored in
Ai [(Ap [j]) ... (Ap [j+1]-1)]. The row indices in a given column j
must be in ascending order, and no duplicate row indices may be present.
Row indices must be in the range 0 to n_row-1 (the matrix is 0-based).
double Ax [nz] ; Optional input argument, not modified.
The numerical values of the sparse matrix A. The nonzero pattern (row
indices) for column j is stored in Ai [(Ap [j]) ... (Ap [j+1]-1)], and
the corresponding numerical values are stored in
Ax [(Ap [j]) ... (Ap [j+1]-1)]. Used only by the 2-by-2 strategy to
determine whether entries are "large" or "small". You do not have to
pass the same numerical values to umfpack_di_numeric. If Ax is not
present (a (double *) NULL pointer), then any entry in A is assumed to
be "large".
void **Symbolic ; Output argument.
**Symbolic is the address of a (void *) pointer variable in the user's
calling routine (see Syntax, above). On input, the contents of this
variable are not defined. On output, this variable holds a (void *)
pointer to the Symbolic object (if successful), or (void *) NULL if
a failure occurred.
double Control [UMFPACK_CONTROL] ; Input argument, not modified.
If a (double *) NULL pointer is passed, then the default control
settings are used. Only the primary parameters are listed below:
Control [UMFPACK_STRATEGY]: This is the most important control
parameter. It determines what kind of ordering and pivoting
strategy that UMFPACK should use. It is new to Version 4.1
There are 4 options:
UMFPACK_STRATEGY_AUTO: This is the default. The input matrix is
analyzed to determine how symmetric the nonzero pattern is, and
how many entries there are on the diagonal. It then selects one
of the following strategies. Refer to the User Guide for a
description of how the strategy is automatically selected.
UMFPACK_STRATEGY_UNSYMMETRIC: Use the unsymmetric strategy. COLAMD
is used to order the columns of A, followed by a postorder of
the column elimination tree. No attempt is made to perform
diagonal pivoting. The column ordering is refined during
factorization. This strategy was the only one provided with
UMFPACK V4.0.
In the numerical factorization, the
Control [UMFPACK_SYM_PIVOT_TOLERANCE] parameter is ignored. A
pivot is selected if its magnitude is >=
Control [UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the
largest entry in its column.
UMFPACK_STRATEGY_SYMMETRIC: Use the symmetric strategy (new to
Version 4.1). In this method, the approximate minimum degree
ordering (AMD) is applied to A+A', followed by a postorder of
the elimination tree of A+A'. UMFPACK attempts to perform
diagonal pivoting during numerical factorization. No refinement
of the column preordering is performed during factorization.
In the numerical factorization, a nonzero entry on the diagonal
is selected as the pivot if its magnitude is >= Control
[UMFPACK_SYM_PIVOT_TOLERANCE] (default 0.001) times the largest
entry in its column. If this is not acceptable, then an
off-diagonal pivot is selected with magnitude >= Control
[UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the largest entry
in its column.
UMFPACK_STRATEGY_2BY2: a row permutation P2 is found that places
large entries on the diagonal. The matrix P2*A is then
factorized using the symmetric strategy, described above.
Refer to the User Guide for more information.
Control [UMFPACK_2BY2_TOLERANCE]: a diagonal entry S (k,k) is
considered "small" if it is < tol * max (abs (S (:,k))), where S a
submatrix of the scaled input matrix, with pivots of zero Markowitz
cost removed.
Control [UMFPACK_SCALE]: This parameter is new to V4.1. See
umfpack_numeric.h for a description. Only affects the 2-by-2
strategy. Default: UMFPACK_SCALE_SUM.
double Info [UMFPACK_INFO] ; Output argument, not defined on input.
Contains statistics about the symbolic analysis. If a (double *) NULL
pointer is passed, then no statistics are returned in Info (this is not
an error condition). The entire Info array is cleared (all entries set
to -1) and then the following statistics are computed (only the
primary statistics are listed):
Info [UMFPACK_STATUS]: status code. This is also the return value,
whether or not Info is present.
UMFPACK_OK
Each column of the input matrix contained row indices
in increasing order, with no duplicates. Only in this case
does umfpack_di_symbolic compute a valid symbolic factorization.
For the other cases below, no Symbolic object is created
(*Symbolic is (void *) NULL).
UMFPACK_ERROR_n_nonpositive
n is less than or equal to zero.
UMFPACK_ERROR_invalid_matrix
Number of entries in the matrix is negative, Ap [0] is nonzero,
a column has a negative number of entries, a row index is out of
bounds, or the columns of input matrix were jumbled (unsorted
columns or duplicate entries).
UMFPACK_ERROR_out_of_memory
Insufficient memory to perform the symbolic analysis. If the
analysis requires more than 2GB of memory and you are using
the 32-bit ("int") version of UMFPACK, then you are guaranteed
to run out of memory. Try using the 64-bit version of UMFPACK.
UMFPACK_ERROR_argument_missing
One or more required arguments is missing.
UMFPACK_ERROR_internal_error
Something very serious went wrong. This is a bug.
Please contact the author (davis@cise.ufl.edu).
Info [UMFPACK_SIZE_OF_UNIT]: the number of bytes in a Unit,
for memory usage statistics below.
Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]: the amount of memory (in Units)
required for umfpack_di_symbolic to complete. This count includes
the size of the Symbolic object itself, which is also reported in
Info [UMFPACK_SYMBOLIC_SIZE].
Info [UMFPACK_NUMERIC_SIZE_ESTIMATE]: an estimate of the final size (in
Units) of the entire Numeric object (both fixed-size and variable-
sized parts), which holds the LU factorization (including the L, U,
P and Q matrices).
Info [UMFPACK_PEAK_MEMORY_ESTIMATE]: an estimate of the total amount of
memory (in Units) required by umfpack_di_symbolic and
umfpack_di_numeric to perform both the symbolic and numeric
factorization. This is the larger of the amount of memory needed
in umfpack_di_numeric itself, and the amount of memory needed in
umfpack_di_symbolic (Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]). The
count includes the size of both the Symbolic and Numeric objects
themselves. It can be a very loose upper bound, particularly when
the symmetric or 2-by-2 strategies are used.
Info [UMFPACK_FLOPS_ESTIMATE]: an estimate of the total floating-point
operations required to factorize the matrix. This is a "true"
theoretical estimate of the number of flops that would be performed
by a flop-parsimonious sparse LU algorithm. It assumes that no
extra flops are performed except for what is strictly required to
compute the LU factorization. It ignores, for example, the flops
performed by umfpack_di_numeric to add contribution blocks of
frontal matrices together. If L and U are the upper bound on the
pattern of the factors, then this flop count estimate can be
represented in MATLAB (for real matrices, not complex) as:
Lnz = full (sum (spones (L))) - 1 ; % nz in each col of L
Unz = full (sum (spones (U')))' - 1 ; % nz in each row of U
flops = 2*Lnz*Unz + sum (Lnz) ;
The actual "true flop" count found by umfpack_di_numeric will be
less than this estimate.
Info [UMFPACK_LNZ_ESTIMATE]: an estimate of the number of nonzeros in
L, including the diagonal. Since L is unit-diagonal, the diagonal
of L is not stored. This estimate is a strict upper bound on the
actual nonzeros in L to be computed by umfpack_di_numeric.
Info [UMFPACK_UNZ_ESTIMATE]: an estimate of the number of nonzeros in
U, including the diagonal. This estimate is a strict upper bound on
the actual nonzeros in U to be computed by umfpack_di_numeric.
Info [UMFPACK_SYMBOLIC_TIME]: The CPU time taken, in seconds.
Info [UMFPACK_STRATEGY_USED]: The ordering strategy used:
UMFPACK_STRATEGY_SYMMETRIC, UMFPACK_STRATEGY_UNSYMMETRIC, or
UMFPACK_STRATEGY_2BY2.
\end{verbatim}
}
%-------------------------------------------------------------------------------
ewpage
\subsection{umfpack\_di\_numeric}
{\footnotesize
\begin{verbatim}
int umfpack_di_numeric
(
const int Ap [ ],
const int Ai [ ],
const double Ax [ ],
void *Symbolic,
void **Numeric,
const double Control [UMFPACK_CONTROL],
double Info [UMFPACK_INFO]
) ;
Purpose:
Given a sparse matrix A in column-oriented form, and a symbolic analysis
computed by umfpack_di_symbolic, the umfpack_di_numeric routine performs the
numerical factorization, PAQ=LU, PRAQ=LU, or P(R\A)Q=LU, where P and Q are
permutation matrices (represented as permutation vectors), R is the row
scaling, L is unit-lower triangular, and U is upper triangular. This is
required before the system Ax=b (or other related linear systems) can be
solved. umfpack_di_numeric can be called multiple times for each call to
umfpack_di_symbolic, to factorize a sequence of matrices with identical
nonzero pattern. Simply compute the Symbolic object once, with
umfpack_di_symbolic, and reuse it for subsequent matrices.
umfpack_di_numeric safely detects if the pattern changes, and sets an
appropriate error code.
Returns:
The status code is returned. See Info [UMFPACK_STATUS], below.
Arguments:
int Ap [n_col+1] ; Input argument, not modified.
This must be identical to the Ap array passed to umfpack_di_symbolic.
The value of n_col is what was passed to umfpack_di_symbolic (this is
held in the Symbolic object).
int Ai [nz] ; Input argument, not modified, of size nz = Ap [n_col].
This must be identical to the Ai array passed to umfpack_di_symbolic.
double Ax [nz] ; Input argument, not modified, of size nz = Ap [n_col].
The numerical values of the sparse matrix A. The nonzero pattern (row
indices) for column j is stored in Ai [(Ap [j]) ... (Ap [j+1]-1)], and
the corresponding numerical values are stored in
Ax [(Ap [j]) ... (Ap [j+1]-1)].
void *Symbolic ; Input argument, not modified.
The Symbolic object, which holds the symbolic factorization computed by
umfpack_di_symbolic. The Symbolic object is not modified by
umfpack_di_numeric.
void **Numeric ; Output argument.
**Numeric is the address of a (void *) pointer variable in the user's
calling routine (see Syntax, above). On input, the contents of this
variable are not defined. On output, this variable holds a (void *)
pointer to the Numeric object (if successful), or (void *) NULL if
a failure occurred.
double Control [UMFPACK_CONTROL] ; Input argument, not modified.
If a (double *) NULL pointer is passed, then the default control
settings are used. Only the primary parameters are listed below:
Control [UMFPACK_PIVOT_TOLERANCE]: relative pivot tolerance for
threshold partial pivoting with row interchanges. In any given
column, an entry is numerically acceptable if its absolute value is
greater than or equal to Control [UMFPACK_PIVOT_TOLERANCE] times
the largest absolute value in the column. A value of 1.0 gives true
partial pivoting. If less than or equal to zero, then any nonzero
entry is numerically acceptable as a pivot (this is changed from
Version 4.0). Default: 0.1.
Smaller values tend to lead to sparser LU factors, but the solution
to the linear system can become inaccurate. Larger values can lead
to a more accurate solution (but not always), and usually an
increase in the total work.
Control [UMFPACK_SYM_PIVOT_TOLERANCE]: This parameter is new to V4.1.
If diagonal pivoting is attempted (the symmetric or symmetric-2by2
strategies are used) then this parameter is used to control when the
diagonal entry is selected in a given pivot column. The absolute
value of the entry must be >= Control [UMFPACK_SYM_PIVOT_TOLERANCE]
times the largest absolute value in the column. A value of zero
will ensure that no off-diagonal pivoting is performed, except that
zero diagonal entries are not selected if there are any off-diagonal
nonzero entries.
If an off-diagonal pivot is selected, an attempt is made to restore
symmetry later on. Suppose A (i,j) is selected, where i != j.
If column i has not yet been selected as a pivot column, then
the entry A (j,i) is redefined as a "diagonal" entry, except that
the tighter tolerance (Control [UMFPACK_PIVOT_TOLERANCE]) is
applied. This strategy has an effect similar to 2-by-2 pivoting
for symmetric indefinite matrices. If a 2-by-2 block pivot with
nonzero structure
i j
i: 0 x
j: x 0
is selected in a symmetric indefinite factorization method, the
2-by-2 block is inverted and a rank-2 update is applied. In
UMFPACK, this 2-by-2 block would be reordered as
j i
i: x 0
j: 0 x
In both cases, the symmetry of the Schur complement is preserved.
Control [UMFPACK_SCALE]: This parameter is new to V4.1. Version 4.0
did not scale the matrix. Note that the user's input matrix is
never modified, only an internal copy is scaled.
There are three valid settings for this parameter. If any other
value is provided, the default is used.
UMFPACK_SCALE_NONE: no scaling is performed.
UMFPACK_SCALE_SUM: each row of the input matrix A is divided by
the sum of the absolute values of the entries in that row.
The scaled matrix has an infinity norm of 1.
UMFPACK_SCALE_MAX: each row of the input matrix A is divided by
the maximum the absolute values of the entries in that row.
In the scaled matrix the largest entry in each row has
a magnitude exactly equal to 1.
Scaling is very important for the "symmetric" strategy when
diagonal pivoting is attempted. It also improves the performance
of the "unsymmetric" strategy.
Default: UMFPACK_SCALE_SUM.
double Info [UMFPACK_INFO] ; Output argument.
Contains statistics about the numeric factorization. If a
(double *) NULL pointer is passed, then no statistics are returned in
Info (this is not an error condition). The following statistics are
computed in umfpack_di_numeric (only the primary statistics are listed):
Info [UMFPACK_STATUS]: status code. This is also the return value,
whether or not Info is present.
UMFPACK_OK
Numeric factorization was successful. umfpack_di_numeric
computed a valid numeric factorization.
UMFPACK_WARNING_singular_matrix
Numeric factorization was successful, but the matrix is
singular. umfpack_di_numeric computed a valid numeric
factorization, but you will get a divide by zero in
umfpack_di_solve. For the other cases below, no Numeric object
is created (*Numeric is (void *) NULL).
UMFPACK_ERROR_out_of_memory
Insufficient memory to complete the numeric factorization.
UMFPACK_ERROR_argument_missing
One or more required arguments are missing.
UMFPACK_ERROR_invalid_Symbolic_object
Symbolic object provided as input is invalid.
UMFPACK_ERROR_different_pattern
The pattern (Ap and/or Ai) has changed since the call to
umfpack_di_symbolic which produced the Symbolic object.
Info [UMFPACK_NUMERIC_SIZE]: the actual final size (in Units) of the
entire Numeric object, including the final size of the variable
part of the object. Info [UMFPACK_NUMERIC_SIZE_ESTIMATE],
an estimate, was computed by umfpack_di_symbolic. The estimate is
normally an upper bound on the actual final size, but this is not
guaranteed.
Info [UMFPACK_PEAK_MEMORY]: the actual peak memory usage (in Units) of
both umfpack_di_symbolic and umfpack_di_numeric. An estimate,
Info [UMFPACK_PEAK_MEMORY_ESTIMATE], was computed by
umfpack_di_symbolic. The estimate is normally an upper bound on the
actual peak usage, but this is not guaranteed. With testing on
hundreds of matrix arising in real applications, I have never
observed a matrix where this estimate or the Numeric size estimate
was less than the actual result, but this is theoretically possible.
Please send me one if you find such a matrix.
Info [UMFPACK_FLOPS]: the actual count of the (useful) floating-point
operations performed. An estimate, Info [UMFPACK_FLOPS_ESTIMATE],
was computed by umfpack_di_symbolic. The estimate is guaranteed to
be an upper bound on this flop count. The flop count excludes
"useless" flops on zero values, flops performed during the pivot
search (for tentative updates and assembly of candidate columns),
and flops performed to add frontal matrices together.
Info [UMFPACK_LNZ]: the actual nonzero entries in final factor L,
including the diagonal. This excludes any zero entries in L,
although some of these are stored in the Numeric object. The
Info [UMFPACK_LU_ENTRIES] statistic does account for all
explicitly stored zeros, however. Info [UMFPACK_LNZ_ESTIMATE],
an estimate, was computed by umfpack_di_symbolic. The estimate is
guaranteed to be an upper bound on Info [UMFPACK_LNZ].
Info [UMFPACK_UNZ]: the actual nonzero entries in final factor U,
including the diagonal. This excludes any zero entries in U,
although some of these are stored in the Numeric object. The
Info [UMFPACK_LU_ENTRIES] statistic does account for all
explicitly stored zeros, however. Info [UMFPACK_UNZ_ESTIMATE],
an estimate, was computed by umfpack_di_symbolic. The estimate is
guaranteed to be an upper bound on Info [UMFPACK_UNZ].
Info [UMFPACK_NUMERIC_TIME]: The CPU time taken, in seconds.
\end{verbatim}
}
%-------------------------------------------------------------------------------
ewpage
\subsection{umfpack\_di\_solve}
{\footnotesize
\begin{verbatim}
int umfpack_di_solve
(
int sys,
const int Ap [ ],
const int Ai [ ],
const double Ax [ ],
double X [ ],
const double B [ ],
void *Numeric,
const double Control [UMFPACK_CONTROL],
double Info [UMFPACK_INFO]
) ;
Purpose:
Given LU factors computed by umfpack_di_numeric (PAQ=LU, PRAQ=LU, or
P(R\A)Q=LU) and the right-hand-side, B, solve a linear system for the
solution X. Iterative refinement is optionally performed. Only square
systems are handled. Singular matrices result in a divide-by-zero for all
systems except those involving just the matrix L. Iterative refinement is
not performed for singular matrices.
In the discussion below, n is equal to n_row and n_col, because only
square systems are handled.
Returns:
The status code is returned. See Info [UMFPACK_STATUS], below.
Arguments:
int sys ; Input argument, not modified.
Defines which system to solve. (') is the linear algebraic transpose.
sys value system solved
UMFPACK_A Ax=b
UMFPACK_At A'x=b
UMFPACK_Pt_L P'Lx=b
UMFPACK_L Lx=b
UMFPACK_Lt_P L'Px=b
UMFPACK_Lt L'x=b
UMFPACK_U_Qt UQ'x=b
UMFPACK_U Ux=b
UMFPACK_Q_Ut QU'x=b
UMFPACK_Ut U'x=b
Iterative refinement can be optionally performed when sys is any of
the following:
UMFPACK_A Ax=b
UMFPACK_At A'x=b
For the other values of the sys argument, iterative refinement is not
performed (Control [UMFPACK_IRSTEP], Ap, Ai, and Ax are ignored).
int Ap [n+1] ; Input argument, not modified.
int Ai [nz] ; Input argument, not modified.
double Ax [nz] ; Input argument, not modified.
If iterative refinement is requested (Control [UMFPACK_IRSTEP] >= 1,
Ax=b or A'x=b is being solved, and A is nonsingular), then
these arrays must be identical to the same ones passed to
umfpack_di_numeric. The umfpack_di_solve routine does not check the
contents of these arguments, so the results are undefined if Ap, Ai, Ax,
are modified between the calls the umfpack_di_numeric and
umfpack_di_solve. These three arrays do not need to be present (NULL
pointers can be passed) if Control [UMFPACK_IRSTEP] is zero, or if a
system other than Ax=b or A'x=b is being solved, or if A is
singular, since in each of these cases A is not accessed.
double X [n] ; Output argument.
The solution to the linear system, where n = n_row = n_col is the
dimension of the matrices A, L, and U.
double B [n] ; Input argument, not modified.
The right-hand side vector, b, stored as a conventional array of size n
(or two arrays of size n for complex versions). This routine does not
solve for multiple right-hand-sides, nor does it allow b to be stored in
a sparse-column form.
void *Numeric ; Input argument, not modified.
Numeric must point to a valid Numeric object, computed by
umfpack_di_numeric.
double Control [UMFPACK_CONTROL] ; Input argument, not modified.
If a (double *) NULL pointer is passed, then the default control
settings are used.
Control [UMFPACK_IRSTEP]: The maximum number of iterative refinement
steps to attempt. A value less than zero is treated as zero. If
less than 1, or if Ax=b or A'x=b is not being solved, or
if A is singular, then the Ap, Ai, and Ax arguments are not
accessed. Default: 2.
double Info [UMFPACK_INFO] ; Output argument.
Contains statistics about the solution factorization. If a
(double *) NULL pointer is passed, then no statistics are returned in
Info (this is not an error condition). The following statistics are
computed in umfpack_di_solve (only the primary statistics are listed):
Info [UMFPACK_STATUS]: status code. This is also the return value,
whether or not Info is present.
UMFPACK_OK
The linear system was successfully solved.
UMFPACK_WARNING_singular_matrix
A divide-by-zero occurred. Your solution will contain Inf's
and/or NaN's. Some parts of the solution may be valid. For
example, solving Ax=b with
A = [2 0] b = [ 1 ] returns x = [ 0.5 ]
[0 0] [ 0 ] [ Inf ]
UMFPACK_ERROR_out_of_memory
Insufficient memory to solve the linear system.
UMFPACK_ERROR_argument_missing
One or more required arguments are missing. The B and X
arguments are always required. Info and Control are not
required. Ap, Ai and Ax are required if Ax=b or
A'x=b is to be solved, the (default) iterative
refinement is requested, and the matrix A is nonsingular.
UMFPACK_ERROR_invalid_system
The sys argument is not valid, or the matrix A is not square.
UMFPACK_ERROR_invalid_Numeric_object
The Numeric object is not valid.
Info [UMFPACK_SOLVE_FLOPS]: the number of floating point operations
performed to solve the linear system. This includes the work
taken for all iterative refinement steps, including the backtrack
(if any).
Info [UMFPACK_SOLVE_TIME]: The time taken, in seconds.
\end{verbatim}
}
%-------------------------------------------------------------------------------
ewpage
\subsection{umfpack\_di\_free\_symbolic}
{\footnotesize
\begin{verbatim}
void umfpack_di_free_symbolic
(
void **Symbolic
) ;
Purpose:
Deallocates the Symbolic object and sets the Symbolic handle to NULL.
Arguments:
void **Symbolic ; Input argument, deallocated and Symbolic is
set to (void *) NULL on output.
\end{verbatim}
}
%-------------------------------------------------------------------------------
\subsection{umfpack\_di\_free\_numeric}
{\footnotesize
\begin{verbatim}
void umfpack_di_free_numeric
(
void **Numeric
) ;
Purpose:
Deallocates the Numeric object and sets the Numeric handle to NULL.
Arguments:
void **Numeric ; Input argument, deallocated and Numeric is
set to (void *) NULL on output.
\end{verbatim}
}
%-------------------------------------------------------------------------------
\subsection{umfpack\_di\_defaults}
{\footnotesize
\begin{verbatim}
void umfpack_di_defaults
(
double Control [UMFPACK_CONTROL]
) ;
Purpose:
Sets the default control parameter settings.
Arguments:
double Control [UMFPACK_CONTROL] ; Output argument.
Control is set to the default control parameter settings.
\end{verbatim}
}
\end{document}
|