extern/colamd/README.txt

   1 The COLAMD ordering method - Version 2.7
   2 -------------------------------------------------------------------------------
   3
   4 The COLAMD column approximate minimum degree ordering algorithm computes
   5 a permutation vector P such that the LU factorization of A (:,P)
   6 tends to be sparser than that of A.  The Cholesky factorization of
   7 (A (:,P))'*(A (:,P)) will also tend to be sparser than that of A'*A.
   8 SYMAMD is a symmetric minimum degree ordering method based on COLAMD,
   9 available as a MATLAB-callable function.  It constructs a matrix M such
  10 that M'*M has the same pattern as A, and then uses COLAMD to compute a column
  11 ordering of M.  Colamd and symamd tend to be faster and generate better
  12 orderings than their MATLAB counterparts, colmmd and symmmd.
  13
  14 To compile and test the colamd m-files and mexFunctions, just unpack the
  15 COLAMD/ directory from the COLAMD.tar.gz file, and run MATLAB from
  16 within that directory.  Next, type colamd_test to compile and test colamd
  17 and symamd.  This will work on any computer with MATLAB (Unix, PC, or Mac).
  18 Alternatively, type "make" (in Unix) to compile and run a simple example C
  19 code, without using MATLAB.
  20
  21 To compile and install the colamd m-files and mexFunctions, just cd to
  22 COLAMD/MATLAB and type colamd_install in the MATLAB command window.
  23 A short demo will run.  Optionally, type colamd_test to run an extensive tests.
  24 Type "make" in Unix in the COLAMD directory to compile the C-callable
  25 library and to run a short demo.
  26
  27 If you have MATLAB 7.2 or earlier, you must first edit UFconfig/UFconfig.h to
  28 remove the "-largeArrayDims" option from the MEX command (or just use
  29 colamd_make.m inside MATLAB).
  30
  31 Colamd is a built-in routine in MATLAB, available from The
  32 Mathworks, Inc.  Under most cases, the compiled COLAMD from Versions 2.0 to the
  33 current version do not differ.  Colamd Versions 2.2 and 2.3 differ only in their
  34 mexFunction interaces to MATLAB.  v2.4 fixes a bug in the symamd routine in
  35 v2.3.  The bug (in v2.3 and earlier) has no effect on the MATLAB symamd
  36 mexFunction.  v2.5 adds additional checks for integer overflow, so that
  37 the "int" version can be safely used with 64-bit pointers.  Refer to the
  38 ChangeLog for more details.
  39
  40 To use colamd and symamd within an application written in C, all you need are
  41 colamd.c, colamd_global.c, and colamd.h, which are the C-callable
  42 colamd/symamd codes.  See colamd.c for more information on how to call
  43 colamd from a C program.
  44
  45 Requires UFconfig, in the ../UFconfig directory relative to this directory.
  46
  47         Copyright (c) 1998-2007, Timothy A. Davis, All Rights Reserved.
  48
  49         See http://www.cise.ufl.edu/research/sparse/colamd (the colamd.c
  50         file) for the License.
  51
  52
  53 Related papers:
  54
  55         T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, An approximate column
  56         minimum degree ordering algorithm, ACM Transactions on Mathematical
  57         Software, vol. 30, no. 3., pp. 353-376, 2004.
  58
  59         T. A. Davis, J. R. Gilbert, S. Larimore, E. Ng, Algorithm 836: COLAMD,
  60         an approximate column minimum degree ordering algorithm, ACM
  61         Transactions on Mathematical Software, vol. 30, no. 3., pp. 377-380,
  62         2004.
  63
  64         "An approximate minimum degree column ordering algorithm",
  65         S. I. Larimore, MS Thesis, Dept. of Computer and Information
  66         Science and Engineering, University of Florida, Gainesville, FL,
  67         1998.  CISE Tech Report TR-98-016.  Available at
  68         ftp://ftp.cise.ufl.edu/cis/tech-reports/tr98/tr98-016.ps
  69         via anonymous ftp.
  70
  71         Approximate Deficiency for Ordering the Columns of a Matrix,
  72         J. L. Kern, Senior Thesis, Dept. of Computer and Information
  73         Science and Engineering, University of Florida, Gainesville, FL,
  74         1999.  Available at http://www.cise.ufl.edu/~davis/Kern/kern.ps
  75
  76
  77 Authors:  Stefan I. Larimore and Timothy A. Davis, University of Florida,
  78 in collaboration with John Gilbert, Xerox PARC (now at UC Santa Barbara),
  79 and Esmong Ng, Lawrence Berkeley National Laboratory (much of this work
  80 he did while at Oak Ridge National Laboratory).
  81
  82 COLAMD files:
  83
  84     Demo            simple demo
  85     Doc             additional documentation (see colamd.c for more)
  86     Include         include file
  87     Lib             compiled C-callable library
  88     Makefile        primary Unix Makefile
  89     MATLAB          MATLAB functions
  90     README.txt      this file
  91     Source          C source code
  92
  93     ./Demo:
  94     colamd_example.c        simple example
  95     colamd_example.out      output of colamd_example.c
  96     colamd_l_example.c      simple example, long integers
  97     colamd_l_example.out    output of colamd_l_example.c
  98     Makefile                Makefile for C demos
  99
 100     ./Doc:
 101     ChangeLog       change log
 102     lesser.txt      license
 103
 104     ./Include:
 105     colamd.h        include file
 106
 107     ./Lib:
 108     Makefile        Makefile for C-callable library
 109
 110     ./MATLAB:
 111     colamd2.m           MATLAB interface for colamd2
 112     colamd_demo.m       simple demo
 113     colamd_install.m    compile and install colamd2 and symamd2
 114     colamd_make.m       compile colamd2 and symamd2
 115     colamdmex.ca        MATLAB mexFunction for colamd2
 116     colamd_test.m       extensive test
 117     colamdtestmex.c     test function for colamd
 118     Contents.m          contents of the MATLAB directory
 119     luflops.m           test code
 120     Makefile            Makefile for MATLAB functions
 121     symamd2.m           MATLAB interface for symamd2
 122     symamdmex.c         MATLAB mexFunction for symamd2
 123     symamdtestmex.c     test function for symamd
 124
 125     ./Source:
 126     colamd.c            primary source code
 127     colamd_global.c     globally defined function pointers (malloc, free, ...)