Mercurial > octave-antonio
annotate libinterp/dldfcn/colamd.cc @ 20163:075a5e2e1ba5 stable
doc: Update more docstrings to have one sentence summary as first line.
Reviewed build-aux, libinterp/dldfcn, libinterp/octave-value,
libinterp/parse-tree directories.
* build-aux/mk-opts.pl, libinterp/dldfcn/__magick_read__.cc,
libinterp/dldfcn/amd.cc, libinterp/dldfcn/audiodevinfo.cc,
libinterp/dldfcn/audioread.cc, libinterp/dldfcn/ccolamd.cc,
libinterp/dldfcn/chol.cc, libinterp/dldfcn/colamd.cc,
libinterp/dldfcn/convhulln.cc, libinterp/dldfcn/dmperm.cc,
libinterp/dldfcn/fftw.cc, libinterp/dldfcn/qr.cc, libinterp/dldfcn/symbfact.cc,
libinterp/dldfcn/symrcm.cc, libinterp/octave-value/ov-base.cc,
libinterp/octave-value/ov-bool-mat.cc, libinterp/octave-value/ov-cell.cc,
libinterp/octave-value/ov-class.cc, libinterp/octave-value/ov-fcn-handle.cc,
libinterp/octave-value/ov-fcn-inline.cc, libinterp/octave-value/ov-java.cc,
libinterp/octave-value/ov-null-mat.cc, libinterp/octave-value/ov-oncleanup.cc,
libinterp/octave-value/ov-range.cc, libinterp/octave-value/ov-struct.cc,
libinterp/octave-value/ov-typeinfo.cc, libinterp/octave-value/ov-usr-fcn.cc,
libinterp/octave-value/ov.cc, libinterp/parse-tree/lex.ll,
libinterp/parse-tree/oct-parse.in.yy, libinterp/parse-tree/pt-binop.cc,
libinterp/parse-tree/pt-eval.cc, libinterp/parse-tree/pt-mat.cc:
doc: Update more docstrings to have one sentence summary as first line.
author | Rik <rik@octave.org> |
---|---|
date | Sun, 03 May 2015 21:52:42 -0700 |
parents | 4197fc428c7d |
children |
rev | line source |
---|---|
5164 | 1 /* |
2 | |
19697
4197fc428c7d
maint: Update copyright notices for 2015.
John W. Eaton <jwe@octave.org>
parents:
19040
diff
changeset
|
3 Copyright (C) 2004-2015 David Bateman |
11523 | 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 |
16313
6aafe87a3144
use int64_t for idx type if --enable-64
John W. Eaton <jwe@octave.org>
parents:
15195
diff
changeset
|
47 #ifdef USE_64_BIT_IDX_T |
5440 | 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 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
55 // The symmetric column elimination tree code take from the Davis LDL code. |
5164 | 56 // Copyright given elsewhere in this file. |
7924 | 57 static void |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
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++) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
66 Pinv[P[k]] = k ; |
5164 | 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) | |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
71 Parent[k] = n ; // parent of k is not yet known |
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
72 Flag[k] = k ; // mark node k as visited |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
73 octave_idx_type kk = (P) ? P[k] // kth original, or permuted, column |
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
74 : (k) ; |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
75 octave_idx_type p2 = cidx[kk+1] ; |
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
76 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
|
77 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
78 // A (i,k) is nonzero (original or permuted A) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
79 octave_idx_type i = (Pinv) ? (Pinv[ridx[p]]) : (ridx[p]) ; |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
80 if (i < k) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
81 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
82 // follow path from i to root of etree, stop at flagged node |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
83 for ( ; Flag[i] != k ; i = Parent[i]) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
84 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
85 // find parent of i if not yet determined |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
86 if (Parent[i] == n) |
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
87 Parent[i] = k ; |
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
88 Flag[i] = k ; // mark i as visited |
10154
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 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
91 } |
5164 | 92 } |
93 } | |
94 | |
95 // The elimination tree post-ordering code below is taken from SuperLU | |
7924 | 96 static inline octave_idx_type |
97 make_set (octave_idx_type i, octave_idx_type *pp) | |
5164 | 98 { |
99 pp[i] = i; | |
100 return i; | |
101 } | |
102 | |
7924 | 103 static inline octave_idx_type |
104 link (octave_idx_type s, octave_idx_type t, octave_idx_type *pp) | |
5164 | 105 { |
106 pp[s] = t; | |
107 return t; | |
108 } | |
109 | |
7924 | 110 static inline octave_idx_type |
111 find (octave_idx_type i, octave_idx_type *pp) | |
5164 | 112 { |
5440 | 113 register octave_idx_type p, gp; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
114 |
5164 | 115 p = pp[i]; |
116 gp = pp[p]; | |
7924 | 117 |
118 while (gp != p) | |
119 { | |
120 pp[i] = gp; | |
121 i = gp; | |
122 p = pp[i]; | |
123 gp = pp[p]; | |
124 } | |
125 | |
126 return p; | |
5164 | 127 } |
128 | |
7924 | 129 static octave_idx_type |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
130 etdfs (octave_idx_type v, octave_idx_type *first_kid, |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
131 octave_idx_type *next_kid, octave_idx_type *post, |
7924 | 132 octave_idx_type postnum) |
5164 | 133 { |
7924 | 134 for (octave_idx_type w = first_kid[v]; w != -1; w = next_kid[w]) |
5164 | 135 postnum = etdfs (w, first_kid, next_kid, post, postnum); |
7924 | 136 |
5164 | 137 post[postnum++] = v; |
138 | |
139 return postnum; | |
140 } | |
141 | |
7924 | 142 static void |
143 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
|
144 octave_idx_type *post) |
5164 | 145 { |
146 // Allocate storage for working arrays and results | |
5440 | 147 OCTAVE_LOCAL_BUFFER (octave_idx_type, first_kid, n+1); |
148 OCTAVE_LOCAL_BUFFER (octave_idx_type, next_kid, n+1); | |
5164 | 149 |
150 // Set up structure describing children | |
7924 | 151 for (octave_idx_type v = 0; v <= n; first_kid[v++] = -1) |
152 /* do nothing */; | |
153 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
154 for (octave_idx_type v = n-1; v >= 0; v--) |
5164 | 155 { |
5440 | 156 octave_idx_type dad = parent[v]; |
5164 | 157 next_kid[v] = first_kid[dad]; |
158 first_kid[dad] = v; | |
159 } | |
160 | |
161 // Depth-first search from dummy root vertex #n | |
162 etdfs (n, first_kid, next_kid, post, 0); | |
163 } | |
164 | |
7924 | 165 static void |
166 coletree (const octave_idx_type *ridx, const octave_idx_type *colbeg, | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
167 octave_idx_type *colend, octave_idx_type *parent, |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
168 octave_idx_type nr, octave_idx_type nc) |
5164 | 169 { |
5440 | 170 OCTAVE_LOCAL_BUFFER (octave_idx_type, root, nc); |
171 OCTAVE_LOCAL_BUFFER (octave_idx_type, pp, nc); | |
172 OCTAVE_LOCAL_BUFFER (octave_idx_type, firstcol, nr); | |
5164 | 173 |
174 // Compute firstcol[row] = first nonzero column in row | |
7924 | 175 for (octave_idx_type row = 0; row < nr; firstcol[row++] = nc) |
176 /* do nothing */; | |
177 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
178 for (octave_idx_type col = 0; col < nc; col++) |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
179 for (octave_idx_type p = colbeg[col]; p < colend[col]; p++) |
5164 | 180 { |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
181 octave_idx_type row = ridx[p]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
182 if (firstcol[row] > col) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
183 firstcol[row] = col; |
5164 | 184 } |
185 | |
186 // Compute etree by Liu's algorithm for symmetric matrices, | |
187 // except use (firstcol[r],c) in place of an edge (r,c) of A. | |
188 // Thus each row clique in A'*A is replaced by a star | |
189 // centered at its first vertex, which has the same fill. | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
190 for (octave_idx_type col = 0; col < nc; col++) |
5164 | 191 { |
5440 | 192 octave_idx_type cset = make_set (col, pp); |
5164 | 193 root[cset] = col; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
194 parent[col] = nc; |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
195 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
|
196 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
197 octave_idx_type row = firstcol[ridx[p]]; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
198 if (row >= col) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
199 continue; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
200 octave_idx_type rset = find (row, pp); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
201 octave_idx_type rroot = root[rset]; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
202 if (rroot != col) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
203 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
204 parent[rroot] = col; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
205 cset = link (cset, rset, pp); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
206 root[cset] = col; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
207 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
208 } |
5164 | 209 } |
210 } | |
211 | |
212 DEFUN_DLD (colamd, args, nargout, | |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
213 "-*- texinfo -*-\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
214 @deftypefn {Loadable Function} {@var{p} =} colamd (@var{S})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
215 @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{S}, @var{knobs})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
216 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
217 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S}, @var{knobs})\n\ |
5164 | 218 \n\ |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
219 Compute the column approximate minimum degree permutation.\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
220 \n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
221 @code{@var{p} = colamd (@var{S})} returns the column approximate minimum\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
222 degree permutation vector for the sparse matrix @var{S}. For a\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
223 non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
224 sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
225 @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
226 than that of @code{@var{S}' * @var{S}}.\n\ |
5164 | 227 \n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
228 @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
|
229 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
|
230 entries are ignored. Columns with more than\n\ |
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
231 @code{max (16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to\n\ |
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
232 ordering, and ordered last in the output permutation @var{p}. Only\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
233 completely dense rows or columns are removed if @code{@var{knobs}(1)} and\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
234 @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is\n\ |
10846
a4f482e66b65
Grammarcheck more of the documentation.
Rik <octave@nomad.inbox5.com>
parents:
10840
diff
changeset
|
235 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
|
236 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\ |
12575
d0b799dafede
Grammarcheck files for 3.4.1 release.
Rik <octave@nomad.inbox5.com>
parents:
11586
diff
changeset
|
237 versions of colamd.\n\ |
5164 | 238 \n\ |
239 @var{stats} is an optional 20-element output vector that provides data\n\ | |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
240 about the ordering and the validity of the input matrix @var{S}. Ordering\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
241 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
242 @code{@var{stats}(2)} are the number of dense or empty rows and columns\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
243 ignored by @sc{colamd} and @code{@var{stats}(3)} is the number of garbage\n\ |
10840 | 244 collections performed on the internal data structure used by @sc{colamd}\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
245 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\ |
5164 | 246 integers).\n\ |
247 \n\ | |
248 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
249 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
250 in each column, with a non-negative number of entries in each column (!)\n\ | |
10840 | 251 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\ |
5164 | 252 to continue. If there are duplicate entries (a row index appears two or\n\ |
253 more times in the same column) or if the row indices in a column are out\n\ | |
10840 | 254 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\ |
5164 | 255 entries and sorting each column of its internal copy of the matrix\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
256 @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
|
257 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
|
258 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\ |
10840 | 259 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\ |
5164 | 260 valid.\n\ |
261 \n\ | |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
262 @code{@var{stats}(4:7)} provide information if @sc{colamd} was able to\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
263 continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
264 invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\ |
5164 | 265 unsorted or contains duplicate entries, or zero if no such column exists.\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
266 @code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
267 index in the column index given by @code{@var{stats}(5)}, or zero if no\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
268 such row index exists. @code{@var{stats}(7)} is the number of duplicate\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
269 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\ |
10840 | 270 the current version of @sc{colamd} (reserved for future use).\n\ |
5164 | 271 \n\ |
272 The ordering is followed by a column elimination tree post-ordering.\n\ | |
273 \n\ | |
19040
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
274 The authors of the code itself are @nospell{Stefan I. Larimore} and\n\ |
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
275 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},\n\ |
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
276 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see\n\ |
5164 | 277 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
278 @seealso{colperm, symamd, ccolamd}\n\ |
5642 | 279 @end deftypefn") |
5164 | 280 { |
281 octave_value_list retval; | |
5451 | 282 |
283 #ifdef HAVE_COLAMD | |
284 | |
5164 | 285 int nargin = args.length (); |
286 int spumoni = 0; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
287 |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
288 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 289 print_usage (); |
5164 | 290 else |
291 { | |
292 // Get knobs | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
293 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); |
5440 | 294 COLAMD_NAME (_set_defaults) (knobs); |
5164 | 295 |
296 // Check for user-passed knobs | |
297 if (nargin == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
298 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
299 NDArray User_knobs = args(1).array_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
300 int nel_User_knobs = User_knobs.length (); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
301 |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
302 if (nel_User_knobs > 0) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
303 knobs[COLAMD_DENSE_ROW] = User_knobs(0); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
304 if (nel_User_knobs > 1) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
305 knobs[COLAMD_DENSE_COL] = User_knobs(1) ; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
306 if (nel_User_knobs > 2) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
307 spumoni = static_cast<int> (User_knobs(2)); |
5440 | 308 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
309 // print knob settings if spumoni is set |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
310 if (spumoni) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
311 { |
5440 | 312 |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
313 octave_stdout << "\ncolamd version " << COLAMD_MAIN_VERSION |
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
314 << "." << COLAMD_SUB_VERSION |
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
315 << ", " << COLAMD_DATE << ":\n"; |
5164 | 316 |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
317 if (knobs[COLAMD_DENSE_ROW] >= 0) |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
318 octave_stdout << "knobs(1): " << User_knobs (0) |
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
319 << ", rows with > max (16," |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
320 << knobs[COLAMD_DENSE_ROW] << "*sqrt (size(A,2)))" |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
321 << " entries removed\n"; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
322 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
323 octave_stdout << "knobs(1): " << User_knobs (0) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
324 << ", only completely dense rows removed\n"; |
5440 | 325 |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
326 if (knobs[COLAMD_DENSE_COL] >= 0) |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
327 octave_stdout << "knobs(2): " << User_knobs (1) |
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
328 << ", cols with > max (16," |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
329 << knobs[COLAMD_DENSE_COL] << "*sqrt (size(A)))" |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
330 << " entries removed\n"; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
331 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
332 octave_stdout << "knobs(2): " << User_knobs (1) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
333 << ", only completely dense columns removed\n"; |
5440 | 334 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
335 octave_stdout << "knobs(3): " << User_knobs (2) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
336 << ", statistics and knobs printed\n"; |
5440 | 337 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
338 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
339 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
340 |
5440 | 341 octave_idx_type n_row, n_col, nnz; |
342 octave_idx_type *ridx, *cidx; | |
5164 | 343 SparseComplexMatrix scm; |
344 SparseMatrix sm; | |
345 | |
5631 | 346 if (args(0).is_sparse_type ()) |
10154
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 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
349 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
350 scm = args(0). sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
351 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
352 n_col = scm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
353 nnz = scm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
354 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
355 cidx = scm.xcidx (); |
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 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
358 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
359 sm = args(0).sparse_matrix_value (); |
5164 | 360 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
361 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
362 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
363 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
364 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
365 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
366 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
367 } |
5164 | 368 else |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
369 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
370 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
371 sm = SparseMatrix (real (args(0).complex_matrix_value ())); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
372 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
373 sm = SparseMatrix (args(0).matrix_value ()); |
5164 | 374 |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
375 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
376 n_col = sm.cols (); |
10527
b4d2080b6df7
Replace nzmax by nnz as needed
David Bateman <dbateman@free.fr>
parents:
10282
diff
changeset
|
377 nnz = sm.nnz (); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
378 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
379 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
380 } |
5164 | 381 |
382 // Allocate workspace for colamd | |
5440 | 383 OCTAVE_LOCAL_BUFFER (octave_idx_type, p, n_col+1); |
384 for (octave_idx_type i = 0; i < n_col+1; i++) | |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
385 p[i] = cidx[i]; |
5164 | 386 |
5440 | 387 octave_idx_type Alen = COLAMD_NAME (_recommended) (nnz, n_row, n_col); |
388 OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen); | |
389 for (octave_idx_type i = 0; i < nnz; i++) | |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
390 A[i] = ridx[i]; |
5164 | 391 |
392 // Order the columns (destroys A) | |
5440 | 393 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); |
394 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
|
395 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
396 COLAMD_NAME (_report) (stats) ; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
397 error ("colamd: internal error!"); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
398 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
399 } |
5164 | 400 |
401 // column elimination tree post-ordering (reuse variables) | |
5440 | 402 OCTAVE_LOCAL_BUFFER (octave_idx_type, colbeg, n_col + 1); |
403 OCTAVE_LOCAL_BUFFER (octave_idx_type, colend, n_col + 1); | |
404 OCTAVE_LOCAL_BUFFER (octave_idx_type, etree, n_col + 1); | |
5164 | 405 |
5440 | 406 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
|
407 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
408 colbeg[i] = cidx[p[i]]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
409 colend[i] = cidx[p[i]+1]; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
410 } |
5164 | 411 |
412 coletree (ridx, colbeg, colend, etree, n_row, n_col); | |
413 | |
414 // Calculate the tree post-ordering | |
7924 | 415 tree_postorder (n_col, etree, colbeg); |
5164 | 416 |
417 // return the permutation vector | |
418 NDArray out_perm (dim_vector (1, n_col)); | |
5440 | 419 for (octave_idx_type i = 0; i < n_col; i++) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
420 out_perm(i) = p[colbeg[i]] + 1; |
5164 | 421 |
7924 | 422 retval(0) = out_perm; |
5164 | 423 |
424 // print stats if spumoni > 0 | |
425 if (spumoni > 0) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
426 COLAMD_NAME (_report) (stats) ; |
5164 | 427 |
428 // Return the stats vector | |
429 if (nargout == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
430 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
431 NDArray out_stats (dim_vector (1, COLAMD_STATS)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
432 for (octave_idx_type i = 0 ; i < COLAMD_STATS ; i++) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
433 out_stats(i) = stats[i] ; |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
434 retval(1) = out_stats; |
5164 | 435 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
436 // fix stats (5) and (6), for 1-based information on |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
437 // jumbled matrix. note that this correction doesn't |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
438 // occur if symamd returns FALSE |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
439 out_stats (COLAMD_INFO1) ++ ; |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
440 out_stats (COLAMD_INFO2) ++ ; |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
441 } |
5164 | 442 } |
443 | |
5451 | 444 #else |
445 | |
446 error ("colamd: not available in this version of Octave"); | |
447 | |
448 #endif | |
449 | |
5164 | 450 return retval; |
451 } | |
452 | |
453 DEFUN_DLD (symamd, args, nargout, | |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
454 "-*- texinfo -*-\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
455 @deftypefn {Loadable Function} {@var{p} =} symamd (@var{S})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
456 @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{S}, @var{knobs})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
457 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
458 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S}, @var{knobs})\n\ |
5164 | 459 \n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
460 For a symmetric positive definite matrix @var{S}, returns the permutation\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
461 vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a\n\ |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
462 sparser Cholesky@tie{}factor than @var{S}.\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
463 \n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
464 Sometimes @code{symamd} works well for symmetric indefinite matrices too. \n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
465 The matrix @var{S} is assumed to be symmetric; only the strictly lower\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
466 triangular part is referenced. @var{S} must be square.\n\ |
5164 | 467 \n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
468 @var{knobs} is an optional one- to two-element input vector. If @var{S} is\n\ |
5440 | 469 n-by-n, then rows and columns with more than\n\ |
14854
5ae9f0f77635
maint: Use Octave coding conventions for coddling parenthis is DLD-FUNCTIONS directory
Rik <octave@nomad.inbox5.com>
parents:
14361
diff
changeset
|
470 @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
|
471 and ordered last in the output permutation @var{p}. No rows/columns are\n\ |
5440 | 472 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\ |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
473 @code{stats} and @var{knobs} are printed. The default is\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
474 @code{@var{knobs} = [10 0]}. Note that @var{knobs} differs from earlier\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
475 versions of @code{symamd}.\n\ |
5164 | 476 \n\ |
477 @var{stats} is an optional 20-element output vector that provides data\n\ | |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
478 about the ordering and the validity of the input matrix @var{S}. Ordering\n\ |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
479 statistics are in @code{@var{stats}(1:3)}.\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
480 @code{@var{stats}(1) = @var{stats}(2)} is the number of dense or empty rows\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
481 and columns ignored by SYMAMD and @code{@var{stats}(3)} is the number of\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
482 garbage collections performed on the internal data structure used by SYMAMD\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
483 (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}\n\ |
5164 | 484 integers).\n\ |
485 \n\ | |
486 Octave built-in functions are intended to generate valid sparse matrices,\n\ | |
487 with no duplicate entries, with ascending row indices of the nonzeros\n\ | |
488 in each column, with a non-negative number of entries in each column (!)\n\ | |
489 and so on. If a matrix is invalid, then SYMAMD may or may not be able\n\ | |
490 to continue. If there are duplicate entries (a row index appears two or\n\ | |
491 more times in the same column) or if the row indices in a column are out\n\ | |
492 of order, then SYMAMD can correct these errors by ignoring the duplicate\n\ | |
493 entries and sorting each column of its internal copy of the matrix S (the\n\ | |
494 input matrix S is not repaired, however). If a matrix is invalid in\n\ | |
495 other ways then SYMAMD cannot continue, an error message is printed, and\n\ | |
496 no output arguments (@var{p} or @var{stats}) are returned. SYMAMD is\n\ | |
497 thus a simple way to check a sparse matrix to see if it's valid.\n\ | |
498 \n\ | |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
499 @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
|
500 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
501 if invalid. @code{@var{stats}(5)} is the rightmost column index that\n\ |
5164 | 502 is unsorted or contains duplicate entries, or zero if no such column\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
503 exists. @code{@var{stats}(6)} is the last seen duplicate or out-of-order\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
504 row index in the column index given by @code{@var{stats}(5)}, or zero\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
505 if no such row index exists. @code{@var{stats}(7)} is the number of\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
506 duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is\n\ |
5164 | 507 always zero in the current version of SYMAMD (reserved for future use).\n\ |
508 \n\ | |
509 The ordering is followed by a column elimination tree post-ordering.\n\ | |
510 \n\ | |
19040
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
511 The authors of the code itself are @nospell{Stefan I. Larimore} and\n\ |
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
512 @nospell{Timothy A. Davis @email{davis@@cise.ufl.edu}}, University of Florida. The algorithm was developed in collaboration with @nospell{John Gilbert},\n\ |
0850b5212619
doc: Add @nospell macro around proper names in documentation.
Rik <rik@octave.org>
parents:
17787
diff
changeset
|
513 Xerox PARC, and @nospell{Esmond Ng}, Oak Ridge National Laboratory. (see\n\ |
5164 | 514 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ |
5642 | 515 @seealso{colperm, colamd}\n\ |
516 @end deftypefn") | |
5164 | 517 { |
518 octave_value_list retval; | |
5451 | 519 |
520 #ifdef HAVE_COLAMD | |
521 | |
5164 | 522 int nargin = args.length (); |
523 int spumoni = 0; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
524 |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
525 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 526 print_usage (); |
5164 | 527 else |
528 { | |
529 // Get knobs | |
530 OCTAVE_LOCAL_BUFFER (double, knobs, COLAMD_KNOBS); | |
5440 | 531 COLAMD_NAME (_set_defaults) (knobs); |
5164 | 532 |
533 // Check for user-passed knobs | |
534 if (nargin == 2) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
535 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
536 NDArray User_knobs = args(1).array_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
537 int nel_User_knobs = User_knobs.length (); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
538 |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
539 if (nel_User_knobs > 0) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
540 knobs[COLAMD_DENSE_ROW] = User_knobs(COLAMD_DENSE_ROW); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
541 if (nel_User_knobs > 1) |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
542 spumoni = static_cast<int> (User_knobs (1)); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
543 } |
5164 | 544 |
545 // print knob settings if spumoni is set | |
546 if (spumoni > 0) | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
547 octave_stdout << "symamd: dense row/col fraction: " |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
548 << knobs[COLAMD_DENSE_ROW] << std::endl; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
549 |
13219
cf5ebc0e47e4
fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents:
12642
diff
changeset
|
550 octave_idx_type n_row, n_col; |
5440 | 551 octave_idx_type *ridx, *cidx; |
5164 | 552 SparseMatrix sm; |
553 SparseComplexMatrix scm; | |
554 | |
5631 | 555 if (args(0).is_sparse_type ()) |
10154
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 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
558 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
559 scm = args(0).sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
560 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
561 n_col = scm.cols (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
562 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
563 cidx = scm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
564 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
565 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
566 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
567 sm = args(0).sparse_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
568 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
569 n_col = sm.cols (); |
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 ()); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
580 |
10154
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 (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
583 ridx = sm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
584 cidx = sm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
585 } |
5164 | 586 |
587 if (n_row != n_col) | |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
588 { |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
589 error ("symamd: matrix S must be square"); |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
590 return retval; |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
591 } |
5164 | 592 |
593 // Allocate workspace for symamd | |
5440 | 594 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1); |
595 OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, COLAMD_STATS); | |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
596 if (!SYMAMD_NAME () (n_col, ridx, cidx, perm, |
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
597 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++) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
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++) |
15020
560317fd5977
maint: Cuddle open bracket used for indexing C++ arrays in source code.
Rik <rik@octave.org>
parents:
14854
diff
changeset
|
628 out_stats(i) = stats[i] ; |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
629 retval(1) = out_stats; |
5164 | 630 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
631 // fix stats (5) and (6), for 1-based information on |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
632 // jumbled matrix. note that this correction doesn't |
10154
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
633 // occur if symamd returns FALSE |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
634 out_stats (COLAMD_INFO1) ++ ; |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11553
diff
changeset
|
635 out_stats (COLAMD_INFO2) ++ ; |
10154
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, | |
17787
175b392e91fe
Use GNU style coding conventions for code in libinterp/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
649 "-*- texinfo -*-\n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
650 @deftypefn {Loadable Function} {@var{p} =} etree (@var{S})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
651 @deftypefnx {Loadable Function} {@var{p} =} etree (@var{S}, @var{typ})\n\ |
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
652 @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})\n\ |
5164 | 653 \n\ |
20163
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
654 Return the elimination tree for the matrix @var{S}.\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
655 \n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
656 By default @var{S} is assumed to be symmetric and the symmetric elimination\n\ |
075a5e2e1ba5
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
657 tree is returned. The argument @var{typ} controls whether a symmetric or\n\ |
9064
7c02ec148a3c
Check grammar on all .cc files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
658 column elimination tree is returned. Valid values of @var{typ} are\n\ |
17281
bc924baa2c4e
doc: Add new @qcode macro for code samples which are quoted.
Rik <rik@octave.org>
parents:
16313
diff
changeset
|
659 @qcode{\"sym\"} or @qcode{\"col\"}, for symmetric or column elimination tree\n\ |
bc924baa2c4e
doc: Add new @qcode macro for code samples which are quoted.
Rik <rik@octave.org>
parents:
16313
diff
changeset
|
660 respectively.\n\ |
5164 | 661 \n\ |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
662 Called with a second argument, @code{etree} also returns the postorder\n\ |
5164 | 663 permutations on the tree.\n\ |
664 @end deftypefn") | |
665 { | |
666 octave_value_list retval; | |
5297 | 667 |
5164 | 668 int nargin = args.length (); |
669 | |
10282
c9780d8e228c
fix invalid checks in amd functions
Jaroslav Hajek <highegg@gmail.com>
parents:
10155
diff
changeset
|
670 if (nargout > 2 || nargin < 1 || nargin > 2) |
5823 | 671 print_usage (); |
5164 | 672 else |
673 { | |
13219
cf5ebc0e47e4
fix warnings for unused but set variables and shadowed variables
John W. Eaton <jwe@octave.org>
parents:
12642
diff
changeset
|
674 octave_idx_type n_row, n_col; |
5440 | 675 octave_idx_type *ridx, *cidx; |
5164 | 676 bool is_sym = true; |
677 SparseMatrix sm; | |
678 SparseComplexMatrix scm; | |
679 | |
5631 | 680 if (args(0).is_sparse_type ()) |
10154
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 if (args(0).is_complex_type ()) |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
683 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
684 scm = args(0).sparse_complex_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
685 n_row = scm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
686 n_col = scm.cols (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
687 ridx = scm.xridx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
688 cidx = scm.xcidx (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
689 } |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
690 else |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
691 { |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
692 sm = args(0).sparse_matrix_value (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
693 n_row = sm.rows (); |
40dfc0c99116
DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents:
9064
diff
changeset
|
694 n_col = sm.cols (); |
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 { |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
702 error ("etree: S must be a sparse matrix"); |
10154
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 { |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
716 error ("etree: TYP must be a string"); |
10154
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 { |
11553
01f703952eff
Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
728 error ("etree: S is marked as symmetric, but is not square"); |
10154
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 } |