lemon-project-template-glpk

view deps/glpk/src/colamd/README @ 9:33de93886c88

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