 |
GNU Octave
3.8.0
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
|
#include <cstdlib>#include <string>#include <vector>#include "ov.h"#include "defun-dld.h"#include "pager.h"#include "ov-re-mat.h"#include "ov-re-sparse.h"#include "ov-cx-sparse.h"#include "oct-sparse.h"#include "oct-locbuf.h"
Go to the source code of this file.
Macros | |
| #define | COLAMD_NAME(name) colamd ## name |
| #define | SYMAMD_NAME(name) symamd ## name |
Functions | |
| static void | coletree (const octave_idx_type *ridx, const octave_idx_type *colbeg, octave_idx_type *colend, octave_idx_type *parent, octave_idx_type nr, octave_idx_type nc) |
| DEFUN_DLD (colamd, args, nargout,"-*- texinfo -*-\n\ @deftypefn {Loadable Function} {@var{p} =} colamd (@var{S})\n\ @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{S}, @var{knobs})\n\ @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S})\n\ @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S}, @var{knobs})\n\ \n\ Column approximate minimum degree permutation.\n\ @code{@var{p} = colamd (@var{S})} returns the column approximate minimum\n\ degree permutation vector for the sparse matrix @var{S}. For a\n\ non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have\n\ sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of\n\ @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser\n\ than that of @code{@var{S}' * @var{S}}.\n\ \n\ @var{knobs} is an optional one- to three-element input vector. If @var{S} is\n\ m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\ entries are ignored. Columns with more than\n\ @code{max (16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to\n\ ordering, and ordered last in the output permutation @var{p}. Only\n\ completely dense rows or columns are removed if @code{@var{knobs}(1)} and\n\ @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is\n\ nonzero, @var{stats} and @var{knobs} are printed. The default is\n\ @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\ versions of colamd.\n\ \n\ @var{stats} is an optional 20-element output vector that provides data\n\ about the ordering and the validity of the input matrix @var{S}. Ordering\n\ statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and\n\ @code{@var{stats}(2)} are the number of dense or empty rows and columns\n\ ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage\n\ collections performed on the internal data structure used by @sc{colamd}\n\ (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\ integers).\n\ \n\ Octave built-in functions are intended to generate valid sparse matrices,\n\ with no duplicate entries, with ascending row indices of the nonzeros\n\ in each column, with a non-negative number of entries in each column (!)\n\ and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\ to continue. If there are duplicate entries (a row index appears two or\n\ more times in the same column) or if the row indices in a column are out\n\ of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\ entries and sorting each column of its internal copy of the matrix\n\ @var{S} (the input matrix @var{S} is not repaired, however). If a matrix\n\ is invalid in other ways then @sc{colamd} cannot continue, an error message\n\ is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\ @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\ valid.\n\ \n\ @code{@var{stats}(4:7)} provide information if COLAMD was able to\n\ continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\ invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\ unsorted or contains duplicate entries, or zero if no such column exists.\n\ @code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\ index in the column index given by @code{@var{stats}(5)}, or zero if no\n\ such row index exists. @code{@var{stats}(7)} is the number of duplicate\n\ or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\ the current version of @sc{colamd} (reserved for future use).\n\ \n\ The ordering is followed by a column elimination tree post-ordering.\n\ \n\ The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ Ng, Oak Ridge National Laboratory. (see\n\ @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ @seealso{colperm, symamd, ccolamd}\n\ @end deftypefn") | |
| DEFUN_DLD (symamd, args, nargout,"-*- texinfo -*-\n\ @deftypefn {Loadable Function} {@var{p} =} symamd (@var{S})\n\ @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{S}, @var{knobs})\n\ @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S})\n\ @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S}, @var{knobs})\n\ \n\ For a symmetric positive definite matrix @var{S}, returns the permutation\n\ vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a\n\ sparser Cholesky@tie{}factor than @var{S}. Sometimes @code{symamd} works\n\ well for symmetric indefinite matrices too. The matrix @var{S} is assumed\n\ to be symmetric; only the strictly lower triangular part is referenced.\n\ @var{S} must be square.\n\ \n\ @var{knobs} is an optional one- to two-element input vector. If @var{S} is\n\ n-by-n, then rows and columns with more than\n\ @code{max (16,@var{knobs}(1)*sqrt(n))} entries are removed prior to ordering,\n\ and ordered last in the output permutation @var{p}. No rows/columns are\n\ removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\ @code{stats} and @var{knobs} are printed. The default is @code{@var{knobs}\n\ = [10 0]}. Note that @var{knobs} differs from earlier versions of symamd.\n\ \n\ @var{stats} is an optional 20-element output vector that provides data\n\ about the ordering and the validity of the input matrix @var{S}. Ordering\n\ statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1) =\n\ @var{stats}(2)} is the number of dense or empty rows and columns\n\ ignored by SYMAMD and @code{@var{stats}(3)} is the number of garbage\n\ collections performed on the internal data structure used by SYMAMD\n\ (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}\n\ integers).\n\ \n\ Octave built-in functions are intended to generate valid sparse matrices,\n\ with no duplicate entries, with ascending row indices of the nonzeros\n\ in each column, with a non-negative number of entries in each column (!)\n\ and so on. If a matrix is invalid, then SYMAMD may or may not be able\n\ to continue. If there are duplicate entries (a row index appears two or\n\ more times in the same column) or if the row indices in a column are out\n\ of order, then SYMAMD can correct these errors by ignoring the duplicate\n\ entries and sorting each column of its internal copy of the matrix S (the\n\ input matrix S is not repaired, however). If a matrix is invalid in\n\ other ways then SYMAMD cannot continue, an error message is printed, and\n\ no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is\n\ thus a simple way to check a sparse matrix to see if it's valid.\n\ \n\ @code{@var{stats}(4:7)} provide information if SYMAMD was able to\n\ continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\ if invalid. @code{@var{stats}(5)} is the rightmost column index that\n\ is unsorted or contains duplicate entries, or zero if no such column\n\ exists. @code{@var{stats}(6)} is the last seen duplicate or out-of-order\n\ row index in the column index given by @code{@var{stats}(5)}, or zero\n\ if no such row index exists. @code{@var{stats}(7)} is the number of\n\ duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is\n\ always zero in the current version of SYMAMD (reserved for future use).\n\ \n\ The ordering is followed by a column elimination tree post-ordering.\n\ \n\ The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ Ng, Oak Ridge National Laboratory. (see\n\ @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ @seealso{colperm, colamd}\n\ @end deftypefn") | |
| DEFUN_DLD (etree, args, nargout,"-*- texinfo -*-\n\ @deftypefn {Loadable Function} {@var{p} =} etree (@var{S})\n\ @deftypefnx {Loadable Function} {@var{p} =} etree (@var{S}, @var{typ})\n\ @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})\n\ \n\ Return the elimination tree for the matrix @var{S}. By default @var{S}\n\ is assumed to be symmetric and the symmetric elimination tree is\n\ returned. The argument @var{typ} controls whether a symmetric or\n\ column elimination tree is returned. Valid values of @var{typ} are\n\ @qcode{\"sym\"} or @qcode{\"col\"}, for symmetric or column elimination tree\n\ respectively.\n\ \n\ Called with a second argument, @code{etree} also returns the postorder\n\ permutations on the tree.\n\ @end deftypefn") | |
| static octave_idx_type | etdfs (octave_idx_type v, octave_idx_type *first_kid, octave_idx_type *next_kid, octave_idx_type *post, octave_idx_type postnum) |
| static octave_idx_type | find (octave_idx_type i, octave_idx_type *pp) |
| static octave_idx_type | link (octave_idx_type s, octave_idx_type t, octave_idx_type *pp) |
| static octave_idx_type | make_set (octave_idx_type i, octave_idx_type *pp) |
| static void | symetree (const octave_idx_type *ridx, const octave_idx_type *cidx, octave_idx_type *Parent, octave_idx_type *P, octave_idx_type n) |
| static void | tree_postorder (octave_idx_type n, octave_idx_type *parent, octave_idx_type *post) |
| #define COLAMD_NAME | ( | name | ) | colamd ## name |
Definition at line 51 of file colamd.cc.
Referenced by DEFUN_DLD().
| #define SYMAMD_NAME | ( | name | ) | symamd ## name |
Definition at line 52 of file colamd.cc.
Referenced by DEFUN_DLD().
|
static |
Definition at line 166 of file colamd.cc.
References find(), link(), make_set(), and OCTAVE_LOCAL_BUFFER.
Referenced by DEFUN_DLD().
| DEFUN_DLD | ( | colamd | , |
| args | , | ||
| nargout | |||
| ) |
Definition at line 212 of file colamd.cc.
References A, COLAMD_NAME, coletree(), Sparse< T >::cols(), error(), octave_value_list::length(), Array< T >::length(), Sparse< T >::nnz(), OCTAVE_LOCAL_BUFFER, octave_stdout, print_usage(), real, Sparse< T >::rows(), tree_postorder(), Sparse< T >::xcidx(), and Sparse< T >::xridx().
| DEFUN_DLD | ( | symamd | , |
| args | , | ||
| nargout | |||
| ) |
Definition at line 453 of file colamd.cc.
References COLAMD_NAME, Sparse< T >::cols(), error(), octave_value_list::length(), Array< T >::length(), OCTAVE_LOCAL_BUFFER, octave_stdout, print_usage(), real, Sparse< T >::rows(), SYMAMD_NAME, symetree(), tree_postorder(), Sparse< T >::xcidx(), and Sparse< T >::xridx().
| DEFUN_DLD | ( | etree | , |
| args | , | ||
| nargout | |||
| ) |
Definition at line 647 of file colamd.cc.
References coletree(), Sparse< T >::cols(), error(), octave_value_list::length(), OCTAVE_LOCAL_BUFFER, print_usage(), Sparse< T >::rows(), symetree(), tree_postorder(), Sparse< T >::xcidx(), and Sparse< T >::xridx().
|
static |
|
inlinestatic |
Definition at line 111 of file colamd.cc.
Referenced by coletree(), Octave_map::del(), jit_operation::do_generate(), jit_typeinfo::find_builtin(), symbol_table::fcn_info::fcn_info_rep::find_function(), install_find_fcns(), and property_list::lookup().
|
inlinestatic |
Definition at line 104 of file colamd.cc.
Referenced by coletree(), main(), and octave_link().
|
inlinestatic |
Definition at line 97 of file colamd.cc.
Referenced by coletree().
|
static |
|
static |
Definition at line 143 of file colamd.cc.
References etdfs(), and OCTAVE_LOCAL_BUFFER.
Referenced by DEFUN_DLD().
1.8.1.2