1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/colamd/README	Sun Nov 06 20:59:10 2011 +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.