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 . 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.