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