1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/colamd/README Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,98 @@
1.4 +NOTE: Files in this subdirectory are NOT part of the GLPK package, but
1.5 + are used with GLPK.
1.6 +
1.7 + The original code was modified according to GLPK requirements by
1.8 + Andrew Makhorin <mao@gnu.org>.
1.9 +************************************************************************
1.10 +COLAMD/SYMAMD Version 2.7, Copyright (C) 1998-2007, Timothy A. Davis,
1.11 +All Rights Reserved.
1.12 +
1.13 +Description:
1.14 +
1.15 + colamd: an approximate minimum degree column ordering algorithm,
1.16 + for LU factorization of symmetric or unsymmetric matrices,
1.17 + QR factorization, least squares, interior point methods for
1.18 + linear programming problems, and other related problems.
1.19 +
1.20 + symamd: an approximate minimum degree ordering algorithm for
1.21 + Cholesky factorization of symmetric matrices.
1.22 +
1.23 +Purpose:
1.24 +
1.25 + Colamd computes a permutation Q such that the Cholesky factorization
1.26 + of (AQ)'(AQ) has less fill-in and requires fewer floating point
1.27 + operations than A'A. This also provides a good ordering for sparse
1.28 + partial pivoting methods, P(AQ) = LU, where Q is computed prior to
1.29 + numerical factorization, and P is computed during numerical
1.30 + factorization via conventional partial pivoting with row
1.31 + interchanges. Colamd is the column ordering method used in SuperLU,
1.32 + part of the ScaLAPACK library. It is also available as built-in
1.33 + function in MATLAB Version 6, available from MathWorks, Inc.
1.34 + (http://www.mathworks.com). This routine can be used in place of
1.35 + colmmd in MATLAB.
1.36 +
1.37 + Symamd computes a permutation P of a symmetric matrix A such that
1.38 + the Cholesky factorization of PAP' has less fill-in and requires
1.39 + fewer floating point operations than A. Symamd constructs a matrix
1.40 + M such that M'M has the same nonzero pattern of A, and then orders
1.41 + the columns of M using colmmd. The column ordering of M is then
1.42 + returned as the row and column ordering P of A.
1.43 +
1.44 +Authors:
1.45 +
1.46 + The authors of the code itself are Stefan I. Larimore and Timothy A.
1.47 + Davis (davis at cise.ufl.edu), University of Florida. The algorithm
1.48 + was developed in collaboration with John Gilbert, Xerox PARC, and
1.49 + Esmond Ng, Oak Ridge National Laboratory.
1.50 +
1.51 +Acknowledgements:
1.52 +
1.53 + This work was supported by the National Science Foundation, under
1.54 + grants DMS-9504974 and DMS-9803599.
1.55 +
1.56 +License:
1.57 +
1.58 + This library is free software; you can redistribute it and/or
1.59 + modify it under the terms of the GNU Lesser General Public License
1.60 + as published by the Free Software Foundation; either version 2.1 of
1.61 + the License, or (at your option) any later version.
1.62 +
1.63 + This library is distributed in the hope that it will be useful,
1.64 + but WITHOUT ANY WARRANTY; without even the implied warranty of
1.65 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1.66 + Lesser General Public License for more details.
1.67 +
1.68 + You should have received a copy of the GNU Lesser General Public
1.69 + License along with this library; if not, write to the Free Software
1.70 + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
1.71 + USA.
1.72 +
1.73 + Permission is hereby granted to use or copy this program under the
1.74 + terms of the GNU LGPL, provided that the Copyright, this License,
1.75 + and the Availability of the original version is retained on all
1.76 + copies. User documentation of any code that uses this code or any
1.77 + modified version of this code must cite the Copyright, this License,
1.78 + the Availability note, and "Used by permission." Permission to
1.79 + modify the code and to distribute modified code is granted, provided
1.80 + the Copyright, this License, and the Availability note are retained,
1.81 + and a notice that the code was modified is included.
1.82 +
1.83 + COLAMD is also available under alternate licenses, contact T. Davis
1.84 + for details.
1.85 +
1.86 +Availability:
1.87 +
1.88 + The colamd/symamd library is available at:
1.89 +
1.90 + http://www.cise.ufl.edu/research/sparse/colamd/
1.91 +
1.92 +References:
1.93 +
1.94 + T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, An approximate
1.95 + column minimum degree ordering algorithm, ACM Transactions on
1.96 + Mathematical Software, vol. 30, no. 3., pp. 353-376, 2004.
1.97 +
1.98 + T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, Algorithm 836:
1.99 + COLAMD, an approximate column minimum degree ordering algorithm, ACM
1.100 + Transactions on Mathematical Software, vol. 30, no. 3., pp. 377-380,
1.101 + 2004.