| rev |
line source |
|
alpar@9
|
1 NOTE: Files in this subdirectory are NOT part of the GLPK package, but
|
|
alpar@9
|
2 are used with GLPK.
|
|
alpar@9
|
3
|
|
alpar@9
|
4 The original code was modified according to GLPK requirements by
|
|
alpar@9
|
5 Andrew Makhorin <mao@gnu.org>.
|
|
alpar@9
|
6 ************************************************************************
|
|
alpar@9
|
7 COLAMD/SYMAMD Version 2.7, Copyright (C) 1998-2007, Timothy A. Davis,
|
|
alpar@9
|
8 All Rights Reserved.
|
|
alpar@9
|
9
|
|
alpar@9
|
10 Description:
|
|
alpar@9
|
11
|
|
alpar@9
|
12 colamd: an approximate minimum degree column ordering algorithm,
|
|
alpar@9
|
13 for LU factorization of symmetric or unsymmetric matrices,
|
|
alpar@9
|
14 QR factorization, least squares, interior point methods for
|
|
alpar@9
|
15 linear programming problems, and other related problems.
|
|
alpar@9
|
16
|
|
alpar@9
|
17 symamd: an approximate minimum degree ordering algorithm for
|
|
alpar@9
|
18 Cholesky factorization of symmetric matrices.
|
|
alpar@9
|
19
|
|
alpar@9
|
20 Purpose:
|
|
alpar@9
|
21
|
|
alpar@9
|
22 Colamd computes a permutation Q such that the Cholesky factorization
|
|
alpar@9
|
23 of (AQ)'(AQ) has less fill-in and requires fewer floating point
|
|
alpar@9
|
24 operations than A'A. This also provides a good ordering for sparse
|
|
alpar@9
|
25 partial pivoting methods, P(AQ) = LU, where Q is computed prior to
|
|
alpar@9
|
26 numerical factorization, and P is computed during numerical
|
|
alpar@9
|
27 factorization via conventional partial pivoting with row
|
|
alpar@9
|
28 interchanges. Colamd is the column ordering method used in SuperLU,
|
|
alpar@9
|
29 part of the ScaLAPACK library. It is also available as built-in
|
|
alpar@9
|
30 function in MATLAB Version 6, available from MathWorks, Inc.
|
|
alpar@9
|
31 (http://www.mathworks.com). This routine can be used in place of
|
|
alpar@9
|
32 colmmd in MATLAB.
|
|
alpar@9
|
33
|
|
alpar@9
|
34 Symamd computes a permutation P of a symmetric matrix A such that
|
|
alpar@9
|
35 the Cholesky factorization of PAP' has less fill-in and requires
|
|
alpar@9
|
36 fewer floating point operations than A. Symamd constructs a matrix
|
|
alpar@9
|
37 M such that M'M has the same nonzero pattern of A, and then orders
|
|
alpar@9
|
38 the columns of M using colmmd. The column ordering of M is then
|
|
alpar@9
|
39 returned as the row and column ordering P of A.
|
|
alpar@9
|
40
|
|
alpar@9
|
41 Authors:
|
|
alpar@9
|
42
|
|
alpar@9
|
43 The authors of the code itself are Stefan I. Larimore and Timothy A.
|
|
alpar@9
|
44 Davis (davis at cise.ufl.edu), University of Florida. The algorithm
|
|
alpar@9
|
45 was developed in collaboration with John Gilbert, Xerox PARC, and
|
|
alpar@9
|
46 Esmond Ng, Oak Ridge National Laboratory.
|
|
alpar@9
|
47
|
|
alpar@9
|
48 Acknowledgements:
|
|
alpar@9
|
49
|
|
alpar@9
|
50 This work was supported by the National Science Foundation, under
|
|
alpar@9
|
51 grants DMS-9504974 and DMS-9803599.
|
|
alpar@9
|
52
|
|
alpar@9
|
53 License:
|
|
alpar@9
|
54
|
|
alpar@9
|
55 This library is free software; you can redistribute it and/or
|
|
alpar@9
|
56 modify it under the terms of the GNU Lesser General Public License
|
|
alpar@9
|
57 as published by the Free Software Foundation; either version 2.1 of
|
|
alpar@9
|
58 the License, or (at your option) any later version.
|
|
alpar@9
|
59
|
|
alpar@9
|
60 This library is distributed in the hope that it will be useful,
|
|
alpar@9
|
61 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
alpar@9
|
62 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
alpar@9
|
63 Lesser General Public License for more details.
|
|
alpar@9
|
64
|
|
alpar@9
|
65 You should have received a copy of the GNU Lesser General Public
|
|
alpar@9
|
66 License along with this library; if not, write to the Free Software
|
|
alpar@9
|
67 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
|
|
alpar@9
|
68 USA.
|
|
alpar@9
|
69
|
|
alpar@9
|
70 Permission is hereby granted to use or copy this program under the
|
|
alpar@9
|
71 terms of the GNU LGPL, provided that the Copyright, this License,
|
|
alpar@9
|
72 and the Availability of the original version is retained on all
|
|
alpar@9
|
73 copies. User documentation of any code that uses this code or any
|
|
alpar@9
|
74 modified version of this code must cite the Copyright, this License,
|
|
alpar@9
|
75 the Availability note, and "Used by permission." Permission to
|
|
alpar@9
|
76 modify the code and to distribute modified code is granted, provided
|
|
alpar@9
|
77 the Copyright, this License, and the Availability note are retained,
|
|
alpar@9
|
78 and a notice that the code was modified is included.
|
|
alpar@9
|
79
|
|
alpar@9
|
80 COLAMD is also available under alternate licenses, contact T. Davis
|
|
alpar@9
|
81 for details.
|
|
alpar@9
|
82
|
|
alpar@9
|
83 Availability:
|
|
alpar@9
|
84
|
|
alpar@9
|
85 The colamd/symamd library is available at:
|
|
alpar@9
|
86
|
|
alpar@9
|
87 http://www.cise.ufl.edu/research/sparse/colamd/
|
|
alpar@9
|
88
|
|
alpar@9
|
89 References:
|
|
alpar@9
|
90
|
|
alpar@9
|
91 T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, An approximate
|
|
alpar@9
|
92 column minimum degree ordering algorithm, ACM Transactions on
|
|
alpar@9
|
93 Mathematical Software, vol. 30, no. 3., pp. 353-376, 2004.
|
|
alpar@9
|
94
|
|
alpar@9
|
95 T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, Algorithm 836:
|
|
alpar@9
|
96 COLAMD, an approximate column minimum degree ordering algorithm, ACM
|
|
alpar@9
|
97 Transactions on Mathematical Software, vol. 30, no. 3., pp. 377-380,
|
|
alpar@9
|
98 2004.
|
