1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
function [p,stats] = colamd2 (S, knobs)
%COLAMD2 Column approximate minimum degree permutation.
% P = COLAMD2(S) returns the column approximate minimum degree permutation
% vector for the sparse matrix S. For a non-symmetric matrix S, S(:,P)
% tends to have sparser LU factors than S. The Cholesky factorization of
% S(:,P)'*S(:,P) also tends to be sparser than that of S'*S. The ordering
% is followed by a column elimination tree post-ordering.
%
% Note that this function is the source code for the built-in MATLAB colamd
% function. It has been renamed here to colamd2 to avoid a filename clash.
% colamd and colamd2 are identical.
%
% See also COLAMD, AMD, SYMAMD, SYMAMD2.
%
% Example:
% P = colamd2 (S)
% [P, stats] = colamd2 (S, knobs)
%
% knobs is an optional one- to three-element input vector. If S is m-by-n,
% then rows with more than max(16,knobs(1)*sqrt(n)) entries are ignored.
% Columns with more than max(16,knobs(2)*sqrt(min(m,n))) entries are
% removed prior to ordering, and ordered last in the output permutation P.
% Only completely dense rows or columns are removed if knobs(1) and knobs(2)
% are < 0, respectively. If knobs(3) is nonzero, stats and knobs are
% printed. The default is knobs = [10 10 0]. Note that knobs differs from
% earlier versions of colamd.
% COLAMD, Copyright (c) 1998-2022, Timothy A. Davis, and Stefan Larimore.
% SPDX-License-Identifier: BSD-3-clause
% Developed in collaboration with J. Gilbert and E. Ng.
% Acknowledgements: This work was supported by the National Science Foundation,
% under grants DMS-9504974 and DMS-9803599.
%-------------------------------------------------------------------------------
% Perform the colamd ordering:
%-------------------------------------------------------------------------------
if (nargout <= 1 & nargin == 1) %#ok
p = colamd2mex (S) ;
elseif (nargout <= 1 & nargin == 2) %#ok
p = colamd2mex (S, knobs) ;
elseif (nargout == 2 & nargin == 1) %#ok
[p, stats] = colamd2mex (S) ;
elseif (nargout == 2 & nargin == 2) %#ok
[p, stats] = colamd2mex (S, knobs) ;
else
error ('colamd: incorrect number of input and/or output arguments') ;
end
%-------------------------------------------------------------------------------
% column elimination tree post-ordering:
%-------------------------------------------------------------------------------
[ignore, q] = etree (S (:,p), 'col') ;
p = p (q) ;
% stats is an optional 20-element output vector that provides data about the
% ordering and the validity of the input matrix S. Ordering statistics are
% in stats (1:3). stats (1) and stats (2) are the number of dense or empty
% rows and columns ignored by COLAMD and stats (3) is the number of
% garbage collections performed on the internal data structure used by
% COLAMD (roughly of size 2.2*nnz(S) + 4*m + 7*n integers).
%
% MATLAB built-in functions are intended to generate valid sparse matrices,
% with no duplicate entries, with ascending row indices of the nonzeros
% in each column, with a non-negative number of entries in each column (!)
% and so on. If a matrix is invalid, then COLAMD may or may not be able
% to continue. If there are duplicate entries (a row index appears two or
% more times in the same column) or if the row indices in a column are out
% of order, then COLAMD can correct these errors by ignoring the duplicate
% entries and sorting each column of its internal copy of the matrix S (the
% input matrix S is not repaired, however). If a matrix is invalid in other
% ways then COLAMD cannot continue, an error message is printed, and no
% output arguments (P or stats) are returned. COLAMD is thus a simple way
% to check a sparse matrix to see if it's valid.
%
% stats (4:7) provide information if COLAMD was able to continue. The
% matrix is OK if stats (4) is zero, or 1 if invalid. stats (5) is the
% rightmost column index that is unsorted or contains duplicate entries,
% or zero if no such column exists. stats (6) is the last seen duplicate
% or out-of-order row index in the column index given by stats (5), or zero
% if no such row index exists. stats (7) is the number of duplicate or
% out-of-order row indices.
%
% stats (8:20) is always zero in the current version of COLAMD (reserved
% for future use).
|
