Mercurial > octave-nkf
annotate src/DLD-FUNCTIONS/colamd.cc @ 11523:fd0a3ac60b0e
update copyright notices
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Fri, 14 Jan 2011 05:47:45 -0500 |
parents | a4f482e66b65 |
children | 01f703952eff |
rev | line source |
---|---|
5164 | 1 /* |
2 | |
11523 | 3 Copyright (C) 2004-2011 David Bateman |
4 Copyright (C) 1998-2004 Andy Adler | |
7016 | 5 |
6 This file is part of Octave. | |
5164 | 7 |
8 Octave is free software; you can redistribute it and/or modify it | |
9 under the terms of the GNU General Public License as published by the | |
7016 | 10 Free Software Foundation; either version 3 of the License, or (at your |
11 option) any later version. | |
5164 | 12 |
13 Octave is distributed in the hope that it will be useful, but WITHOUT | |
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 for more details. | |
17 | |
18 You should have received a copy of the GNU General Public License | |
7016 | 19 along with Octave; see the file COPYING. If not, see |
20 <http://www.gnu.org/licenses/>. | |
5164 | 21 |
22 */ | |
23 | |
24 // This is the octave interface to colamd, which bore the copyright given | |
25 // in the help of the functions. | |
26 | |
27 #ifdef HAVE_CONFIG_H | |
28 #include <config.h> | |
29 #endif | |
30 | |
31 #include <cstdlib> | |
32 | |
33 #include <string> | |
34 #include <vector> | |
35 | |
36 #include "ov.h" | |
37 #include "defun-dld.h" | |
38 #include "pager.h" | |
39 #include "ov-re-mat.h" | |
40 | |
41 #include "ov-re-sparse.h" | |
42 #include "ov-cx-sparse.h" | |
43 | |
5451 | 44 #include "oct-sparse.h" |
8377
25bc2d31e1bf
improve OCTAVE_LOCAL_BUFFER
Jaroslav Hajek <highegg@gmail.com>
parents:
7924
diff
changeset
|
45 #include "oct-locbuf.h" |
5164 | 46 |
5440 | 47 #ifdef IDX_TYPE_LONG |
48 #define COLAMD_NAME(name) colamd_l ## name | |
49 #define SYMAMD_NAME(name) symamd_l ## name | |
50 #else | |
51 #define COLAMD_NAME(name) colamd ## name | |
52 #define SYMAMD_NAME(name) symamd ## name | |
53 #endif | |
54 | |
5164 | 55 // The symmetric column elimination tree code take from the Davis LDL code. |
56 // Copyright given elsewhere in this file. | |
7924 | 57 static void |
58 symetree (const octave_idx_type *ridx, const octave_idx_type *cidx, | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
59 octave_idx_type *Parent, octave_idx_type *P, octave_idx_type n) |
5164 | 60 { |
5440 | 61 OCTAVE_LOCAL_BUFFER (octave_idx_type, Flag, n); |
62 OCTAVE_LOCAL_BUFFER (octave_idx_type, Pinv, (P ? n : 0)); | |
5164 | 63 if (P) |
64 // If P is present then compute Pinv, the inverse of P | |
5440 | 65 for (octave_idx_type k = 0 ; k < n ; k++) |
5164 | 66 Pinv [P [k]] = k ; |
67 | |
5440 | 68 for (octave_idx_type k = 0 ; k < n ; k++) |
5164 | 69 { |
70 // L(k,:) pattern: all nodes reachable in etree from nz in A(0:k-1,k) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
71 Parent [k] = n ; // parent of k is not yet known |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
72 Flag [k] = k ; // mark node k as visited |
5440 | 73 octave_idx_type kk = (P) ? (P [k]) : (k) ; // kth original, or permuted, column |
74 octave_idx_type p2 = cidx [kk+1] ; | |
75 for (octave_idx_type p = cidx [kk] ; p < p2 ; p++) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
76 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
77 // A (i,k) is nonzero (original or permuted A) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
78 octave_idx_type i = (Pinv) ? (Pinv [ridx [p]]) : (ridx [p]) ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
79 if (i < k) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
80 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
81 // follow path from i to root of etree, stop at flagged node |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
82 for ( ; Flag [i] != k ; i = Parent [i]) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
83 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
84 // find parent of i if not yet determined |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
85 if (Parent [i] == n) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
86 Parent [i] = k ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
87 Flag [i] = k ; // mark i as visited |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
88 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
89 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
90 } |
5164 | 91 } |
92 } | |
93 | |
94 // The elimination tree post-ordering code below is taken from SuperLU | |
7924 | 95 static inline octave_idx_type |
96 make_set (octave_idx_type i, octave_idx_type *pp) | |
5164 | 97 { |
98 pp[i] = i; | |
99 return i; | |
100 } | |
101 | |
7924 | 102 static inline octave_idx_type |
103 link (octave_idx_type s, octave_idx_type t, octave_idx_type *pp) | |
5164 | 104 { |
105 pp[s] = t; | |
106 return t; | |
107 } | |
108 | |
7924 | 109 static inline octave_idx_type |
110 find (octave_idx_type i, octave_idx_type *pp) | |
5164 | 111 { |
5440 | 112 register octave_idx_type p, gp; |
5164 | 113 |
114 p = pp[i]; | |
115 gp = pp[p]; | |
7924 | 116 |
117 while (gp != p) | |
118 { | |
119 pp[i] = gp; | |
120 i = gp; | |
121 p = pp[i]; | |
122 gp = pp[p]; | |
123 } | |
124 | |
125 return p; | |
5164 | 126 } |
127 | |
7924 | 128 static octave_idx_type |
129 etdfs (octave_idx_type v, octave_idx_type *first_kid, | |
130 octave_idx_type *next_kid, octave_idx_type *post, | |
131 octave_idx_type postnum) | |
5164 | 132 { |
7924 | 133 for (octave_idx_type w = first_kid[v]; w != -1; w = next_kid[w]) |
5164 | 134 postnum = etdfs (w, first_kid, next_kid, post, postnum); |
7924 | 135 |
5164 | 136 post[postnum++] = v; |
137 | |
138 return postnum; | |
139 } | |
140 | |
7924 | 141 static void |
142 tree_postorder (octave_idx_type n, octave_idx_type *parent, | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
143 octave_idx_type *post) |
5164 | 144 { |
145 // Allocate storage for working arrays and results | |
5440 | 146 OCTAVE_LOCAL_BUFFER (octave_idx_type, first_kid, n+1); |
147 OCTAVE_LOCAL_BUFFER (octave_idx_type, next_kid, n+1); | |
5164 | 148 |
149 // Set up structure describing children | |
7924 | 150 for (octave_idx_type v = 0; v <= n; first_kid[v++] = -1) |
151 /* do nothing */; | |
152 | |
5440 | 153 for (octave_idx_type v = n-1; v >= 0; v--) |
5164 | 154 { |
5440 | 155 octave_idx_type dad = parent[v]; |
5164 | 156 next_kid[v] = first_kid[dad]; |
157 first_kid[dad] = v; | |
158 } | |
159 | |
160 // Depth-first search from dummy root vertex #n | |
161 etdfs (n, first_kid, next_kid, post, 0); | |
162 } | |
163 | |
7924 | 164 static void |
165 coletree (const octave_idx_type *ridx, const octave_idx_type *colbeg, | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
166 octave_idx_type *colend, octave_idx_type *parent, |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
167 octave_idx_type nr, octave_idx_type nc) |
5164 | 168 { |
5440 | 169 OCTAVE_LOCAL_BUFFER (octave_idx_type, root, nc); |
170 OCTAVE_LOCAL_BUFFER (octave_idx_type, pp, nc); | |
171 OCTAVE_LOCAL_BUFFER (octave_idx_type, firstcol, nr); | |
5164 | 172 |
173 // Compute firstcol[row] = first nonzero column in row | |
7924 | 174 for (octave_idx_type row = 0; row < nr; firstcol[row++] = nc) |
175 /* do nothing */; | |
176 | |
5440 | 177 for (octave_idx_type col = 0; col < nc; col++) |
178 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++) | |
5164 | 179 { |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
180 octave_idx_type row = ridx[p]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
181 if (firstcol[row] > col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
182 firstcol[row] = col; |
5164 | 183 } |
184 | |
185 // Compute etree by Liu's algorithm for symmetric matrices, | |
186 // except use (firstcol[r],c) in place of an edge (r,c) of A. | |
187 // Thus each row clique in A'*A is replaced by a star | |
188 // centered at its first vertex, which has the same fill. | |
5440 | 189 for (octave_idx_type col = 0; col < nc; col++) |
5164 | 190 { |
5440 | 191 octave_idx_type cset = make_set (col, pp); |
5164 | 192 root[cset] = col; |
193 parent[col] = nc; | |
5440 | 194 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
195 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
196 octave_idx_type row = firstcol[ridx[p]]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
197 if (row >= col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
198 continue; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
199 octave_idx_type rset = find (row, pp); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
200 octave_idx_type rroot = root[rset]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
201 if (rroot != col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
202 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
203 parent[rroot] = col; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
204 cset = link (cset, rset, pp); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
205 root[cset] = col; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
206 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
207 } |
5164 | 208 } |
209 } | |
210 | |
211 DEFUN_DLD (colamd, args, nargout, | |
212 "-*- texinfo -*-\n\ | |
10840 | 213 @deftypefn {Loadable Function} {@var{p} =} colamd (@var{s})\n\ |
5164 | 214 @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{s}, @var{knobs})\n\ |
215 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{s})\n\ | |
216 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{s}, @var{knobs})\n\ | |
217 \n\ | |
10840 | 218 Column approximate minimum degree permutation.\n\ |
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
219 @code{@var{p} = colamd (@var{s})} returns the column approximate minimum\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
220 degree permutation vector for the sparse matrix @var{s}. For a\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
221 non-symmetric matrix @var{s}, @code{@var{s} (:,@var{p})} tends to have\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
222 sparser LU factors than @var{s}. The Cholesky factorization of\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
223 @code{@var{s}(:,@var{p})' * @var{s} (:,@var{p})} also tends to be sparser\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
224 than that of @code{@var{s}' * @var{s}}.\n\ |
5164 | 225 \n\ |
5440 | 226 @var{knobs} is an optional one- to three-element input vector. If @var{s} is\n\ |
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
227 m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
228 entries are ignored. Columns with more than\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
229 @code{max(16,knobs(2)*sqrt(min(m,n)))} entries are removed prior to\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
230 ordering, and ordered last in the output permutation @var{p}. Only\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
231 completely dense rows or columns are removed if @code{@var{knobs} (1)} and\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
232 @code{@var{knobs} (2)} are < 0, respectively. If @code{@var{knobs} (3)} is\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
233 nonzero, @var{stats} and @var{knobs} are printed. The default is\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
234 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
235 versions of colamd\n\ |
5164 | 236 \n\ |
237 @var{stats} is an optional 20-element output vector that provides data\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
238 about the ordering and the validity of the input matrix @var{s}. Ordering\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
239 statistics are in @code{@var{stats} (1:3)}. @code{@var{stats} (1)} and\n\ |
5164 | 240 @code{@var{stats} (2)} are the number of dense or empty rows and columns\n\ |
10840 | 241 ignored by @sc{colamd} and @code{@var{stats} (3)} is the number of garbage\n\ |
242 collections performed on the internal data structure used by @sc{colamd}\n\ | |
5164 | 243 (roughly of size @code{2.2 * nnz(@var{s}) + 4 * @var{m} + 7 * @var{n}}\n\ |
244 integers).\n\ | |
245 \n\ | |
246 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
247 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
248 in each column, with a non-negative number of entries in each column (!)\n\ | |
10840 | 249 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\ |
5164 | 250 to continue. If there are duplicate entries (a row index appears two or\n\ |
251 more times in the same column) or if the row indices in a column are out\n\ | |
10840 | 252 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\ |
5164 | 253 entries and sorting each column of its internal copy of the matrix\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
254 @var{s} (the input matrix @var{s} is not repaired, however). If a matrix\n\ |
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
255 is invalid in other ways then @sc{colamd} cannot continue, an error message\n\ |
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
256 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\ |
10840 | 257 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\ |
5164 | 258 valid.\n\ |
259 \n\ | |
260 @code{@var{stats} (4:7)} provide information if COLAMD was able to\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
261 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1 if\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
262 invalid. @code{@var{stats} (5)} is the rightmost column index that is\n\ |
5164 | 263 unsorted or contains duplicate entries, or zero if no such column exists.\n\ |
264 @code{@var{stats} (6)} is the last seen duplicate or out-of-order row\n\ | |
265 index in the column index given by @code{@var{stats} (5)}, or zero if no\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
266 such row index exists. @code{@var{stats} (7)} is the number of duplicate\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
267 or out-of-order row indices. @code{@var{stats} (8:20)} is always zero in\n\ |
10840 | 268 the current version of @sc{colamd} (reserved for future use).\n\ |
5164 | 269 \n\ |
270 The ordering is followed by a column elimination tree post-ordering.\n\ | |
271 \n\ | |
272 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ | |
10840 | 273 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ |
5164 | 274 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
275 Ng, Oak Ridge National Laboratory. (see\n\ |
5164 | 276 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
5642 | 277 @seealso{colperm, symamd}\n\ |
278 @end deftypefn") | |
5164 | 279 { |
280 octave_value_list retval; | |
5451 | 281 |
282 #ifdef HAVE_COLAMD | |
283 | |
5164 | 284 int nargin = args.length (); |
285 int spumoni = 0; | |
286 | |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
287 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 288 print_usage (); |
5164 | 289 else |
290 { | |
291 // Get knobs | |
5440 | 292 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); |
293 COLAMD_NAME (_set_defaults) (knobs); | |
5164 | 294 |
295 // Check for user-passed knobs | |
296 if (nargin == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
297 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
298 NDArray User_knobs = args(1).array_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
299 int nel_User_knobs = User_knobs.length (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
300 |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
301 if (nel_User_knobs > 0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
302 knobs [COLAMD_DENSE_ROW] = User_knobs (0); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
303 if (nel_User_knobs > 1) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
304 knobs [COLAMD_DENSE_COL] = User_knobs (1) ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
305 if (nel_User_knobs > 2) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
306 spumoni = static_cast<int> (User_knobs (2)); |
5440 | 307 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
308 // print knob settings if spumoni is set |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
309 if (spumoni) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
310 { |
5440 | 311 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
312 octave_stdout << "\ncolamd version " << COLAMD_MAIN_VERSION << "." |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
313 << COLAMD_SUB_VERSION << ", " << COLAMD_DATE << ":\n"; |
5164 | 314 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
315 if (knobs [COLAMD_DENSE_ROW] >= 0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
316 octave_stdout << "knobs(1): " << User_knobs (0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
317 << ", rows with > max(16," |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
318 << knobs [COLAMD_DENSE_ROW] << "*sqrt(size(A,2)))" |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
319 << " entries removed\n"; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
320 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
321 octave_stdout << "knobs(1): " << User_knobs (0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
322 << ", only completely dense rows removed\n"; |
5440 | 323 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
324 if (knobs [COLAMD_DENSE_COL] >= 0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
325 octave_stdout << "knobs(2): " << User_knobs (1) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
326 << ", cols with > max(16," |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
327 << knobs [COLAMD_DENSE_COL] << "*sqrt(size(A)))" |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
328 << " entries removed\n"; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
329 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
330 octave_stdout << "knobs(2): " << User_knobs (1) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
331 << ", only completely dense columns removed\n"; |
5440 | 332 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
333 octave_stdout << "knobs(3): " << User_knobs (2) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
334 << ", statistics and knobs printed\n"; |
5440 | 335 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
336 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
337 } |
5164 | 338 |
5440 | 339 octave_idx_type n_row, n_col, nnz; |
340 octave_idx_type *ridx, *cidx; | |
5164 | 341 SparseComplexMatrix scm; |
342 SparseMatrix sm; | |
343 | |
5631 | 344 if (args(0).is_sparse_type ()) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
345 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
346 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
347 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
348 scm = args(0). sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
349 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
350 n_col = scm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
351 nnz = scm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
352 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
353 cidx = scm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
354 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
355 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
356 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
357 sm = args(0).sparse_matrix_value (); |
5164 | 358 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
359 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
360 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
361 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
362 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
363 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
364 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
365 } |
5164 | 366 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
367 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
368 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
369 sm = SparseMatrix (real (args(0).complex_matrix_value ())); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
370 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
371 sm = SparseMatrix (args(0).matrix_value ()); |
5164 | 372 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
373 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
374 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
375 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
376 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
377 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
378 } |
5164 | 379 |
380 // Allocate workspace for colamd | |
5440 | 381 OCTAVE_LOCAL_BUFFER (octave_idx_type, p, n_col+1); |
382 for (octave_idx_type i = 0; i < n_col+1; i++) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
383 p[i] = cidx [i]; |
5164 | 384 |
5440 | 385 octave_idx_type Alen = COLAMD_NAME (_recommended) (nnz, n_row, n_col); |
386 OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen); | |
387 for (octave_idx_type i = 0; i < nnz; i++) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
388 A[i] = ridx [i]; |
5164 | 389 |
390 // Order the columns (destroys A) | |
5440 | 391 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); |
392 if (! COLAMD_NAME () (n_row, n_col, Alen, A, p, knobs, stats)) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
393 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
394 COLAMD_NAME (_report) (stats) ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
395 error ("colamd: internal error!"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
396 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
397 } |
5164 | 398 |
399 // column elimination tree post-ordering (reuse variables) | |
5440 | 400 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col + 1); |
401 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col + 1); | |
402 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); | |
5164 | 403 |
5440 | 404 for (octave_idx_type i = 0; i < n_col; i++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
405 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
406 colbeg[i] = cidx[p[i]]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
407 colend[i] = cidx[p[i]+1]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
408 } |
5164 | 409 |
410 coletree (ridx, colbeg, colend, etree, n_row, n_col); | |
411 | |
412 // Calculate the tree post-ordering | |
7924 | 413 tree_postorder (n_col, etree, colbeg); |
5164 | 414 |
415 // return the permutation vector | |
416 NDArray out_perm (dim_vector (1, n_col)); | |
5440 | 417 for (octave_idx_type i = 0; i < n_col; i++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
418 out_perm(i) = p [colbeg [i]] + 1; |
5164 | 419 |
7924 | 420 retval(0) = out_perm; |
5164 | 421 |
422 // print stats if spumoni > 0 | |
423 if (spumoni > 0) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
424 COLAMD_NAME (_report) (stats) ; |
5164 | 425 |
426 // Return the stats vector | |
427 if (nargout == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
428 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
429 NDArray out_stats (dim_vector (1, COLAMD_STATS)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
430 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
431 out_stats (i) = stats [i] ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
432 retval(1) = out_stats; |
5164 | 433 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
434 // fix stats (5) and (6), for 1-based information on |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
435 // jumbled matrix. note that this correction doesn't |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
436 // occur if symamd returns FALSE |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
437 out_stats (COLAMD_INFO1) ++ ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
438 out_stats (COLAMD_INFO2) ++ ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
439 } |
5164 | 440 } |
441 | |
5451 | 442 #else |
443 | |
444 error ("colamd: not available in this version of Octave"); | |
445 | |
446 #endif | |
447 | |
5164 | 448 return retval; |
449 } | |
450 | |
451 DEFUN_DLD (symamd, args, nargout, | |
452 "-*- texinfo -*-\n\ | |
10840 | 453 @deftypefn {Loadable Function} {@var{p} =} symamd (@var{s})\n\ |
5164 | 454 @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{s}, @var{knobs})\n\ |
455 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{s})\n\ | |
456 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{s}, @var{knobs})\n\ | |
457 \n\ | |
458 For a symmetric positive definite matrix @var{s}, returns the permutation\n\ | |
459 vector p such that @code{@var{s} (@var{p}, @var{p})} tends to have a\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
460 sparser Cholesky factor than @var{s}. Sometimes SYMAMD works well for\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
461 symmetric indefinite matrices too. The matrix @var{s} is assumed to be\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
462 symmetric; only the strictly lower triangular part is referenced. @var{s}\n\ |
5164 | 463 must be square.\n\ |
464 \n\ | |
5440 | 465 @var{knobs} is an optional one- to two-element input vector. If @var{s} is\n\ |
466 n-by-n, then rows and columns with more than\n\ | |
467 @code{max(16,@var{knobs}(1)*sqrt(n))} entries are removed prior to ordering,\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
468 and ordered last in the output permutation @var{p}. No rows/columns are\n\ |
5440 | 469 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\ |
470 @code{stats} and @var{knobs} are printed. The default is @code{@var{knobs} \n\ | |
471 = [10 0]}. Note that @var{knobs} differs from earlier versions of symamd.\n\ | |
5164 | 472 \n\ |
473 @var{stats} is an optional 20-element output vector that provides data\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
474 about the ordering and the validity of the input matrix @var{s}. Ordering\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
475 statistics are in @code{@var{stats} (1:3)}. @code{@var{stats} (1) =\n\ |
5164 | 476 @var{stats} (2)} is the number of dense or empty rows and columns\n\ |
477 ignored by SYMAMD and @code{@var{stats} (3)} is the number of garbage\n\ | |
478 collections performed on the internal data structure used by SYMAMD\n\ | |
479 (roughly of size @code{8.4 * nnz (tril (@var{s}, -1)) + 9 * @var{n}}\n\ | |
480 integers).\n\ | |
481 \n\ | |
482 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
483 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
484 in each column, with a non-negative number of entries in each column (!)\n\ | |
485 and so on. If a matrix is invalid, then SYMAMD may or may not be able\n\ | |
486 to continue. If there are duplicate entries (a row index appears two or\n\ | |
487 more times in the same column) or if the row indices in a column are out\n\ | |
488 of order, then SYMAMD can correct these errors by ignoring the duplicate\n\ | |
489 entries and sorting each column of its internal copy of the matrix S (the\n\ | |
490 input matrix S is not repaired, however). If a matrix is invalid in\n\ | |
491 other ways then SYMAMD cannot continue, an error message is printed, and\n\ | |
492 no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is\n\ | |
493 thus a simple way to check a sparse matrix to see if it's valid.\n\ | |
494 \n\ | |
495 @code{@var{stats} (4:7)} provide information if SYMAMD was able to\n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
496 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
497 if invalid. @code{@var{stats} (5)} is the rightmost column index that\n\ |
5164 | 498 is unsorted or contains duplicate entries, or zero if no such column\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
499 exists. @code{@var{stats} (6)} is the last seen duplicate or out-of-order\n\ |
5164 | 500 row index in the column index given by @code{@var{stats} (5)}, or zero\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
501 if no such row index exists. @code{@var{stats} (7)} is the number of\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
502 duplicate or out-of-order row indices. @code{@var{stats} (8:20)} is\n\ |
5164 | 503 always zero in the current version of SYMAMD (reserved for future use).\n\ |
504 \n\ | |
505 The ordering is followed by a column elimination tree post-ordering.\n\ | |
506 \n\ | |
507 \n\ | |
508 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ | |
10840 | 509 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ |
5164 | 510 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
511 Ng, Oak Ridge National Laboratory. (see\n\ |
5164 | 512 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
5642 | 513 @seealso{colperm, colamd}\n\ |
514 @end deftypefn") | |
5164 | 515 { |
516 octave_value_list retval; | |
5451 | 517 |
518 #ifdef HAVE_COLAMD | |
519 | |
5164 | 520 int nargin = args.length (); |
521 int spumoni = 0; | |
522 | |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
523 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 524 print_usage (); |
5164 | 525 else |
526 { | |
527 // Get knobs | |
528 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); | |
5440 | 529 COLAMD_NAME (_set_defaults) (knobs); |
5164 | 530 |
531 // Check for user-passed knobs | |
532 if (nargin == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
533 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
534 NDArray User_knobs = args(1).array_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
535 int nel_User_knobs = User_knobs.length (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
536 |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
537 if (nel_User_knobs > 0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
538 knobs [COLAMD_DENSE_ROW] = User_knobs (COLAMD_DENSE_ROW); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
539 if (nel_User_knobs > 1) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
540 spumoni = static_cast<int> (User_knobs (1)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
541 } |
5164 | 542 |
543 // print knob settings if spumoni is set | |
544 if (spumoni > 0) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
545 octave_stdout << "symamd: dense row/col fraction: " |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
546 << knobs [COLAMD_DENSE_ROW] << std::endl; |
5164 | 547 |
5440 | 548 octave_idx_type n_row, n_col, nnz; |
549 octave_idx_type *ridx, *cidx; | |
5164 | 550 SparseMatrix sm; |
551 SparseComplexMatrix scm; | |
552 | |
5631 | 553 if (args(0).is_sparse_type ()) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
554 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
555 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
556 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
557 scm = args(0).sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
558 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
559 n_col = scm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
560 nnz = scm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
561 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
562 cidx = scm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
563 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
564 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
565 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
566 sm = args(0).sparse_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
567 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
568 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
569 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
570 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
571 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
572 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
573 } |
5164 | 574 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
575 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
576 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
577 sm = SparseMatrix (real (args(0).complex_matrix_value ())); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
578 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
579 sm = SparseMatrix (args(0).matrix_value ()); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
580 |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
581 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
582 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
583 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
584 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
585 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
586 } |
5164 | 587 |
588 if (n_row != n_col) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
589 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
590 error ("symamd: matrix must be square"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
591 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
592 } |
5164 | 593 |
594 // Allocate workspace for symamd | |
5440 | 595 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1); |
596 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); | |
597 if (!SYMAMD_NAME () (n_col, ridx, cidx, perm, knobs, stats, &calloc, &free)) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
598 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
599 SYMAMD_NAME (_report) (stats) ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
600 error ("symamd: internal error!") ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
601 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
602 } |
5164 | 603 |
604 // column elimination tree post-ordering | |
5440 | 605 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); |
5164 | 606 symetree (ridx, cidx, etree, perm, n_col); |
607 | |
608 // Calculate the tree post-ordering | |
5440 | 609 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1); |
7924 | 610 tree_postorder (n_col, etree, post); |
5164 | 611 |
612 // return the permutation vector | |
613 NDArray out_perm (dim_vector (1, n_col)); | |
5440 | 614 for (octave_idx_type i = 0; i < n_col; i++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
615 out_perm(i) = perm [post [i]] + 1; |
5164 | 616 |
7924 | 617 retval(0) = out_perm; |
5164 | 618 |
619 // print stats if spumoni > 0 | |
620 if (spumoni > 0) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
621 SYMAMD_NAME (_report) (stats) ; |
5164 | 622 |
623 // Return the stats vector | |
624 if (nargout == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
625 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
626 NDArray out_stats (dim_vector (1, COLAMD_STATS)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
627 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
628 out_stats (i) = stats [i] ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
629 retval(1) = out_stats; |
5164 | 630 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
631 // fix stats (5) and (6), for 1-based information on |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
632 // jumbled matrix. note that this correction doesn't |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
633 // occur if symamd returns FALSE |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
634 out_stats (COLAMD_INFO1) ++ ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
635 out_stats (COLAMD_INFO2) ++ ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
636 } |
5164 | 637 } |
638 | |
5451 | 639 #else |
640 | |
641 error ("symamd: not available in this version of Octave"); | |
642 | |
643 #endif | |
644 | |
5164 | 645 return retval; |
646 } | |
647 | |
648 DEFUN_DLD (etree, args, nargout, | |
649 "-*- texinfo -*-\n\ | |
10840 | 650 @deftypefn {Loadable Function} {@var{p} =} etree (@var{s})\n\ |
5164 | 651 @deftypefnx {Loadable Function} {@var{p} =} etree (@var{s}, @var{typ})\n\ |
652 @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{s}, @var{typ})\n\ | |
653 \n\ | |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
654 Returns the elimination tree for the matrix @var{s}. By default @var{s}\n\ |
5164 | 655 is assumed to be symmetric and the symmetric elimination tree is\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
656 returned. The argument @var{typ} controls whether a symmetric or\n\ |
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
657 column elimination tree is returned. Valid values of @var{typ} are\n\ |
5164 | 658 'sym' or 'col', for symmetric or column elimination tree respectively\n\ |
659 \n\ | |
660 Called with a second argument, @dfn{etree} also returns the postorder\n\ | |
661 permutations on the tree.\n\ | |
662 @end deftypefn") | |
663 { | |
664 octave_value_list retval; | |
5297 | 665 |
5164 | 666 int nargin = args.length (); |
667 | |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
668 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 669 print_usage (); |
5164 | 670 else |
671 { | |
5440 | 672 octave_idx_type n_row, n_col, nnz; |
673 octave_idx_type *ridx, *cidx; | |
5164 | 674 bool is_sym = true; |
675 SparseMatrix sm; | |
676 SparseComplexMatrix scm; | |
677 | |
5631 | 678 if (args(0).is_sparse_type ()) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
679 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
680 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
681 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
682 scm = args(0).sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
683 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
684 n_col = scm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
685 nnz = scm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
686 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
687 cidx = scm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
688 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
689 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
690 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
691 sm = args(0).sparse_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
692 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
693 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
694 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
695 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
696 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
697 } |
5164 | 698 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
699 } |
5164 | 700 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
701 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
702 error ("etree: must be called with a sparse matrix"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
703 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
704 } |
5164 | 705 |
706 if (nargin == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
707 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
708 if (args(1).is_string ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
709 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
710 std::string str = args(1).string_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
711 if (str.find ("C") == 0 || str.find ("c") == 0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
712 is_sym = false; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
713 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
714 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
715 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
716 error ("etree: second argument must be a string"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
717 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
718 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
719 } |
7924 | 720 |
5164 | 721 // column elimination tree post-ordering (reuse variables) |
5440 | 722 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); |
5164 | 723 |
724 if (is_sym) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
725 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
726 if (n_row != n_col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
727 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
728 error ("etree: matrix is marked as symmetric, but not square"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
729 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
730 } |
7924 | 731 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
732 symetree (ridx, cidx, etree, 0, n_col); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
733 } |
5164 | 734 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
735 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
736 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
737 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col); |
5164 | 738 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
739 for (octave_idx_type i = 0; i < n_col; i++) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
740 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
741 colbeg[i] = cidx[i]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
742 colend[i] = cidx[i+1]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
743 } |
5164 | 744 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
745 coletree (ridx, colbeg, colend, etree, n_row, n_col); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
746 } |
5164 | 747 |
748 NDArray tree (dim_vector (1, n_col)); | |
5440 | 749 for (octave_idx_type i = 0; i < n_col; i++) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
750 // We flag a root with n_col while Matlab does it with zero |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
751 // Convert for matlab compatiable output |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
752 if (etree[i] == n_col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
753 tree(i) = 0; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
754 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
755 tree(i) = etree[i] + 1; |
5164 | 756 |
7924 | 757 retval(0) = tree; |
5164 | 758 |
759 if (nargout == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
760 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
761 // Calculate the tree post-ordering |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
762 OCTAVE_LOCAL_BUFFER (octave_idx_type, post, n_col + 1); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
763 tree_postorder (n_col, etree, post); |
5164 | 764 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
765 NDArray postorder (dim_vector (1, n_col)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
766 for (octave_idx_type i = 0; i < n_col; i++) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
767 postorder(i) = post[i] + 1; |
5164 | 768 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
769 retval(1) = postorder; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
770 } |
5164 | 771 } |
772 | |
773 return retval; | |
774 } |