alpar@9: NOTE: Files in this subdirectory are NOT part of the GLPK package, but
alpar@9:       are used with GLPK.
alpar@9: 
alpar@9:       The original code was modified according to GLPK requirements by
alpar@9:       Andrew Makhorin <mao@gnu.org>.
alpar@9: ************************************************************************
alpar@9: COLAMD/SYMAMD Version 2.7, Copyright (C) 1998-2007, Timothy A. Davis,
alpar@9: All Rights Reserved.
alpar@9: 
alpar@9: Description:
alpar@9: 
alpar@9:    colamd:  an approximate minimum degree column ordering algorithm,
alpar@9:             for LU factorization of symmetric or unsymmetric matrices,
alpar@9:             QR factorization, least squares, interior point methods for
alpar@9:             linear programming problems, and other related problems.
alpar@9: 
alpar@9:    symamd:  an approximate minimum degree ordering algorithm for
alpar@9:             Cholesky factorization of symmetric matrices.
alpar@9: 
alpar@9: Purpose:
alpar@9: 
alpar@9:    Colamd computes a permutation Q such that the Cholesky factorization
alpar@9:    of (AQ)'(AQ) has less fill-in and requires fewer floating point
alpar@9:    operations than A'A.  This also provides a good ordering for sparse
alpar@9:    partial pivoting methods, P(AQ) = LU, where Q is computed prior to
alpar@9:    numerical factorization, and P is computed during numerical
alpar@9:    factorization via conventional partial pivoting with row
alpar@9:    interchanges.  Colamd is the column ordering method used in SuperLU,
alpar@9:    part of the ScaLAPACK library.  It is also available as built-in
alpar@9:    function in MATLAB Version 6, available from MathWorks, Inc.
alpar@9:    (http://www.mathworks.com).  This routine can be used in place of
alpar@9:    colmmd in MATLAB.
alpar@9: 
alpar@9:    Symamd computes a permutation P of a symmetric matrix A such that
alpar@9:    the Cholesky factorization of PAP' has less fill-in and requires
alpar@9:    fewer floating point operations than A.  Symamd constructs a matrix
alpar@9:    M such that M'M has the same nonzero pattern of A, and then orders
alpar@9:    the columns of M using colmmd.  The column ordering of M is then
alpar@9:    returned as the row and column ordering P of A.
alpar@9: 
alpar@9: Authors:
alpar@9: 
alpar@9:    The authors of the code itself are Stefan I. Larimore and Timothy A.
alpar@9:    Davis (davis at cise.ufl.edu), University of Florida.  The algorithm
alpar@9:    was developed in collaboration with John Gilbert, Xerox PARC, and
alpar@9:    Esmond Ng, Oak Ridge National Laboratory.
alpar@9: 
alpar@9: Acknowledgements:
alpar@9: 
alpar@9:    This work was supported by the National Science Foundation, under
alpar@9:    grants DMS-9504974 and DMS-9803599.
alpar@9: 
alpar@9: License:
alpar@9: 
alpar@9:    This library is free software; you can redistribute it and/or
alpar@9:    modify it under the terms of the GNU Lesser General Public License
alpar@9:    as published by the Free Software Foundation; either version 2.1 of
alpar@9:    the License, or (at your option) any later version.
alpar@9: 
alpar@9:    This library is distributed in the hope that it will be useful,
alpar@9:    but WITHOUT ANY WARRANTY; without even the implied warranty of
alpar@9:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
alpar@9:    Lesser General Public License for more details.
alpar@9: 
alpar@9:    You should have received a copy of the GNU Lesser General Public
alpar@9:    License along with this library; if not, write to the Free Software
alpar@9:    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
alpar@9:    USA.
alpar@9: 
alpar@9:    Permission is hereby granted to use or copy this program under the
alpar@9:    terms of the GNU LGPL, provided that the Copyright, this License,
alpar@9:    and the Availability of the original version is retained on all
alpar@9:    copies.  User documentation of any code that uses this code or any
alpar@9:    modified version of this code must cite the Copyright, this License,
alpar@9:    the Availability note, and "Used by permission."  Permission to
alpar@9:    modify the code and to distribute modified code is granted, provided
alpar@9:    the Copyright, this License, and the Availability note are retained,
alpar@9:    and a notice that the code was modified is included.
alpar@9: 
alpar@9:    COLAMD is also available under alternate licenses, contact T. Davis
alpar@9:    for details.
alpar@9: 
alpar@9: Availability:
alpar@9: 
alpar@9:    The colamd/symamd library is available at:
alpar@9: 
alpar@9:    http://www.cise.ufl.edu/research/sparse/colamd/
alpar@9: 
alpar@9: References:
alpar@9: 
alpar@9:    T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, An approximate
alpar@9:    column minimum degree ordering algorithm, ACM Transactions on
alpar@9:    Mathematical Software, vol. 30, no. 3., pp. 353-376, 2004.
alpar@9: 
alpar@9:    T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, Algorithm 836:
alpar@9:    COLAMD, an approximate column minimum degree ordering algorithm, ACM
alpar@9:    Transactions on Mathematical Software, vol. 30, no. 3., pp. 377-380,
alpar@9:    2004.