Mercurial > octave-nkf

comparison src/DLD-FUNCTIONS/colamd.cc @ 11553:01f703952eff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Improve docstrings for functions in DLD-FUNCTIONS directory. Use same variable names in error() strings and in documentation.
author Rik <octave@nomad.inbox5.com>
date Sun, 16 Jan 2011 22:13:23 -0800
parents fd0a3ac60b0e
children 12df7854fa7c
comparison
equal deleted inserted replaced
11552:6b6e9051ecb8 11553:01f703952eff
208 } 208 }
209 } 209 }
210 210
211 DEFUN_DLD (colamd, args, nargout, 211 DEFUN_DLD (colamd, args, nargout,
212 "-*- texinfo -*-\n\ 212 "-*- texinfo -*-\n\
213 @deftypefn {Loadable Function} {@var{p} =} colamd (@var{s})\n\ 213 @deftypefn {Loadable Function} {@var{p} =} colamd (@var{S})\n\
214 @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{s}, @var{knobs})\n\ 214 @deftypefnx {Loadable Function} {@var{p} =} colamd (@var{S}, @var{knobs})\n\
215 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{s})\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\ 216 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} colamd (@var{S}, @var{knobs})\n\
217 \n\ 217 \n\
218 Column approximate minimum degree permutation.\n\ 218 Column approximate minimum degree permutation.\n\
219 @code{@var{p} = colamd (@var{s})} returns the column approximate minimum\n\ 219 @code{@var{p} = colamd (@var{S})} returns the column approximate minimum\n\
220 degree permutation vector for the sparse matrix @var{s}. For a\n\ 220 degree permutation vector for the sparse matrix @var{S}. For a\n\
221 non-symmetric matrix @var{s}, @code{@var{s} (:,@var{p})} tends to have\n\ 221 non-symmetric matrix @var{S}, @code{@var{S}(:,@var{p})} tends to have\n\
222 sparser LU factors than @var{s}. The Cholesky factorization of\n\ 222 sparser LU@tie{}factors than @var{S}. The Cholesky@tie{}factorization of\n\
223 @code{@var{s}(:,@var{p})' * @var{s} (:,@var{p})} also tends to be sparser\n\ 223 @code{@var{S}(:,@var{p})' * @var{S}(:,@var{p})} also tends to be sparser\n\
224 than that of @code{@var{s}' * @var{s}}.\n\ 224 than that of @code{@var{S}' * @var{S}}.\n\
225 \n\ 225 \n\
226 @var{knobs} is an optional one- to three-element input vector. If @var{s} is\n\ 226 @var{knobs} is an optional one- to three-element input vector. If @var{S} is\n\
227 m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\ 227 m-by-n, then rows with more than @code{max(16,@var{knobs}(1)*sqrt(n))}\n\
228 entries are ignored. Columns with more than\n\ 228 entries are ignored. Columns with more than\n\
229 @code{max(16,knobs(2)*sqrt(min(m,n)))} entries are removed prior to\n\ 229 @code{max(16,@var{knobs}(2)*sqrt(min(m,n)))} entries are removed prior to\n\
230 ordering, and ordered last in the output permutation @var{p}. Only\n\ 230 ordering, and ordered last in the output permutation @var{p}. Only\n\
231 completely dense rows or columns are removed if @code{@var{knobs} (1)} and\n\ 231 completely dense rows or columns are removed if @code{@var{knobs}(1)} and\n\
232 @code{@var{knobs} (2)} are < 0, respectively. If @code{@var{knobs} (3)} is\n\ 232 @code{@var{knobs}(2)} are < 0, respectively. If @code{@var{knobs}(3)} is\n\
233 nonzero, @var{stats} and @var{knobs} are printed. The default is\n\ 233 nonzero, @var{stats} and @var{knobs} are printed. The default is\n\
234 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\ 234 @code{@var{knobs} = [10 10 0]}. Note that @var{knobs} differs from earlier\n\
235 versions of colamd\n\ 235 versions of colamd\n\
236 \n\ 236 \n\
237 @var{stats} is an optional 20-element output vector that provides data\n\ 237 @var{stats} is an optional 20-element output vector that provides data\n\
238 about the ordering and the validity of the input matrix @var{s}. Ordering\n\ 238 about the ordering and the validity of the input matrix @var{S}. Ordering\n\
239 statistics are in @code{@var{stats} (1:3)}. @code{@var{stats} (1)} and\n\ 239 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1)} and\n\
240 @code{@var{stats} (2)} are the number of dense or empty rows and columns\n\ 240 @code{@var{stats}(2)} are the number of dense or empty rows and columns\n\
241 ignored by @sc{colamd} and @code{@var{stats} (3)} is the number of garbage\n\ 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\ 242 collections performed on the internal data structure used by @sc{colamd}\n\
243 (roughly of size @code{2.2 * nnz(@var{s}) + 4 * @var{m} + 7 * @var{n}}\n\ 243 (roughly of size @code{2.2 * nnz(@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\
244 integers).\n\ 244 integers).\n\
245 \n\ 245 \n\
246 Octave built-in functions are intended to generate valid sparse matrices,\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\ 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\ 248 in each column, with a non-negative number of entries in each column (!)\n\
249 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\ 249 and so on. If a matrix is invalid, then @sc{colamd} may or may not be able\n\
250 to continue. If there are duplicate entries (a row index appears two or\n\ 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\ 251 more times in the same column) or if the row indices in a column are out\n\
252 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\ 252 of order, then @sc{colamd} can correct these errors by ignoring the duplicate\n\
253 entries and sorting each column of its internal copy of the matrix\n\ 253 entries and sorting each column of its internal copy of the matrix\n\
254 @var{s} (the input matrix @var{s} is not repaired, however). If a matrix\n\ 254 @var{S} (the input matrix @var{S} is not repaired, however). If a matrix\n\
255 is invalid in other ways then @sc{colamd} cannot continue, an error message\n\ 255 is invalid in other ways then @sc{colamd} cannot continue, an error message\n\
256 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\ 256 is printed, and no output arguments (@var{p} or @var{stats}) are returned.\n\
257 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\ 257 @sc{colamd} is thus a simple way to check a sparse matrix to see if it's\n\
258 valid.\n\ 258 valid.\n\
259 \n\ 259 \n\
260 @code{@var{stats} (4:7)} provide information if COLAMD was able to\n\ 260 @code{@var{stats}(4:7)} provide information if COLAMD was able to\n\
261 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1 if\n\ 261 continue. The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\
262 invalid. @code{@var{stats} (5)} is the rightmost column index that is\n\ 262 invalid. @code{@var{stats}(5)} is the rightmost column index that is\n\
263 unsorted or contains duplicate entries, or zero if no such column exists.\n\ 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\ 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\ 265 index in the column index given by @code{@var{stats}(5)}, or zero if no\n\
266 such row index exists. @code{@var{stats} (7)} is the number of duplicate\n\ 266 such row index exists. @code{@var{stats}(7)} is the number of duplicate\n\
267 or out-of-order row indices. @code{@var{stats} (8:20)} is always zero in\n\ 267 or out-of-order row indices. @code{@var{stats}(8:20)} is always zero in\n\
268 the current version of @sc{colamd} (reserved for future use).\n\ 268 the current version of @sc{colamd} (reserved for future use).\n\
269 \n\ 269 \n\
270 The ordering is followed by a column elimination tree post-ordering.\n\ 270 The ordering is followed by a column elimination tree post-ordering.\n\
271 \n\ 271 \n\
272 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ 272 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\
273 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ 273 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\
274 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ 274 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\
275 Ng, Oak Ridge National Laboratory. (see\n\ 275 Ng, Oak Ridge National Laboratory. (see\n\
276 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\ 276 @url{http://www.cise.ufl.edu/research/sparse/colamd})\n\
277 @seealso{colperm, symamd}\n\ 277 @seealso{colperm, symamd, ccolamd}\n\
278 @end deftypefn") 278 @end deftypefn")
279 { 279 {
280 octave_value_list retval; 280 octave_value_list retval;
281 281
282 #ifdef HAVE_COLAMD 282 #ifdef HAVE_COLAMD
448 return retval; 448 return retval;
449 } 449 }
450 450
451 DEFUN_DLD (symamd, args, nargout, 451 DEFUN_DLD (symamd, args, nargout,
452 "-*- texinfo -*-\n\ 452 "-*- texinfo -*-\n\
453 @deftypefn {Loadable Function} {@var{p} =} symamd (@var{s})\n\ 453 @deftypefn {Loadable Function} {@var{p} =} symamd (@var{S})\n\
454 @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{s}, @var{knobs})\n\ 454 @deftypefnx {Loadable Function} {@var{p} =} symamd (@var{S}, @var{knobs})\n\
455 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{s})\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\ 456 @deftypefnx {Loadable Function} {[@var{p}, @var{stats}] =} symamd (@var{S}, @var{knobs})\n\
457 \n\ 457 \n\
458 For a symmetric positive definite matrix @var{s}, returns the permutation\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\ 459 vector p such that @code{@var{S}(@var{p}, @var{p})} tends to have a\n\
460 sparser Cholesky factor than @var{s}. Sometimes SYMAMD works well for\n\ 460 sparser Cholesky@tie{}factor than @var{S}. Sometimes @code{symamd} works\n\
461 symmetric indefinite matrices too. The matrix @var{s} is assumed to be\n\ 461 well for symmetric indefinite matrices too. The matrix @var{S} is assumed\n\
462 symmetric; only the strictly lower triangular part is referenced. @var{s}\n\ 462 to be symmetric; only the strictly lower triangular part is referenced. \n\
463 must be square.\n\ 463 @var{S} must be square.\n\
464 \n\ 464 \n\
465 @var{knobs} is an optional one- to two-element input vector. If @var{s} is\n\ 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\ 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\ 467 @code{max(16,@var{knobs}(1)*sqrt(n))} entries are removed prior to ordering,\n\
468 and ordered last in the output permutation @var{p}. No rows/columns are\n\ 468 and ordered last in the output permutation @var{p}. No rows/columns are\n\
469 removed if @code{@var{knobs}(1) < 0}. If @code{@var{knobs} (2)} is nonzero,\n\ 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\ 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\ 471 = [10 0]}. Note that @var{knobs} differs from earlier versions of symamd.\n\
472 \n\ 472 \n\
473 @var{stats} is an optional 20-element output vector that provides data\n\ 473 @var{stats} is an optional 20-element output vector that provides data\n\
474 about the ordering and the validity of the input matrix @var{s}. Ordering\n\ 474 about the ordering and the validity of the input matrix @var{S}. Ordering\n\
475 statistics are in @code{@var{stats} (1:3)}. @code{@var{stats} (1) =\n\ 475 statistics are in @code{@var{stats}(1:3)}. @code{@var{stats}(1) =\n\
476 @var{stats} (2)} is the number of dense or empty rows and columns\n\ 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\ 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\ 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\ 479 (roughly of size @code{8.4 * nnz (tril (@var{S}, -1)) + 9 * @var{n}}\n\
480 integers).\n\ 480 integers).\n\
481 \n\ 481 \n\
482 Octave built-in functions are intended to generate valid sparse matrices,\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\ 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\ 484 in each column, with a non-negative number of entries in each column (!)\n\
490 input matrix S is not repaired, however). If a matrix is invalid in\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\ 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\ 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\ 493 thus a simple way to check a sparse matrix to see if it's valid.\n\
494 \n\ 494 \n\
495 @code{@var{stats} (4:7)} provide information if SYMAMD was able to\n\ 495 @code{@var{stats}(4:7)} provide information if SYMAMD was able to\n\
496 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\ 496 continue. The matrix is OK if @code{@var{stats} (4)} is zero, or 1\n\
497 if invalid. @code{@var{stats} (5)} is the rightmost column index that\n\ 497 if invalid. @code{@var{stats}(5)} is the rightmost column index that\n\
498 is unsorted or contains duplicate entries, or zero if no such column\n\ 498 is unsorted or contains duplicate entries, or zero if no such column\n\
499 exists. @code{@var{stats} (6)} is the last seen duplicate or out-of-order\n\ 499 exists. @code{@var{stats}(6)} is the last seen duplicate or out-of-order\n\
500 row index in the column index given by @code{@var{stats} (5)}, or zero\n\ 500 row index in the column index given by @code{@var{stats}(5)}, or zero\n\
501 if no such row index exists. @code{@var{stats} (7)} is the number of\n\ 501 if no such row index exists. @code{@var{stats}(7)} is the number of\n\
502 duplicate or out-of-order row indices. @code{@var{stats} (8:20)} is\n\ 502 duplicate or out-of-order row indices. @code{@var{stats}(8:20)} is\n\
503 always zero in the current version of SYMAMD (reserved for future use).\n\ 503 always zero in the current version of SYMAMD (reserved for future use).\n\
504 \n\ 504 \n\
505 The ordering is followed by a column elimination tree post-ordering.\n\ 505 The ordering is followed by a column elimination tree post-ordering.\n\
506 \n\
507 \n\ 506 \n\
508 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\ 507 The authors of the code itself are Stefan I. Larimore and Timothy A.\n\
509 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\ 508 Davis @email{davis@@cise.ufl.edu}, University of Florida. The algorithm was\n\
510 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\ 509 developed in collaboration with John Gilbert, Xerox PARC, and Esmond\n\
511 Ng, Oak Ridge National Laboratory. (see\n\ 510 Ng, Oak Ridge National Laboratory. (see\n\
585 cidx = sm.xcidx (); 584 cidx = sm.xcidx ();
586 } 585 }
587 586
588 if (n_row != n_col) 587 if (n_row != n_col)
589 { 588 {
590 error ("symamd: matrix must be square"); 589 error ("symamd: matrix S must be square");
591 return retval; 590 return retval;
592 } 591 }
593 592
594 // Allocate workspace for symamd 593 // Allocate workspace for symamd
595 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1); 594 OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1);
645 return retval; 644 return retval;
646 } 645 }
647 646
648 DEFUN_DLD (etree, args, nargout, 647 DEFUN_DLD (etree, args, nargout,
649 "-*- texinfo -*-\n\ 648 "-*- texinfo -*-\n\
650 @deftypefn {Loadable Function} {@var{p} =} etree (@var{s})\n\ 649 @deftypefn {Loadable Function} {@var{p} =} etree (@var{S})\n\
651 @deftypefnx {Loadable Function} {@var{p} =} etree (@var{s}, @var{typ})\n\ 650 @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\ 651 @deftypefnx {Loadable Function} {[@var{p}, @var{q}] =} etree (@var{S}, @var{typ})\n\
653 \n\ 652 \n\
654 Returns the elimination tree for the matrix @var{s}. By default @var{s}\n\ 653 Returns the elimination tree for the matrix @var{S}. By default @var{S}\n\
655 is assumed to be symmetric and the symmetric elimination tree is\n\ 654 is assumed to be symmetric and the symmetric elimination tree is\n\
656 returned. The argument @var{typ} controls whether a symmetric or\n\ 655 returned. The argument @var{typ} controls whether a symmetric or\n\
657 column elimination tree is returned. Valid values of @var{typ} are\n\ 656 column elimination tree is returned. Valid values of @var{typ} are\n\
658 'sym' or 'col', for symmetric or column elimination tree respectively\n\ 657 'sym' or 'col', for symmetric or column elimination tree respectively\n\
659 \n\ 658 \n\
660 Called with a second argument, @dfn{etree} also returns the postorder\n\ 659 Called with a second argument, @code{etree} also returns the postorder\n\
661 permutations on the tree.\n\ 660 permutations on the tree.\n\
662 @end deftypefn") 661 @end deftypefn")
663 { 662 {
664 octave_value_list retval; 663 octave_value_list retval;
665 664
697 } 696 }
698 697
699 } 698 }
700 else 699 else
701 { 700 {
702 error ("etree: must be called with a sparse matrix"); 701 error ("etree: S must be a sparse matrix");
703 return retval; 702 return retval;
704 } 703 }
705 704
706 if (nargin == 2) 705 if (nargin == 2)
707 { 706 {
711 if (str.find ("C") == 0 || str.find ("c") == 0) 710 if (str.find ("C") == 0 || str.find ("c") == 0)
712 is_sym = false; 711 is_sym = false;
713 } 712 }
714 else 713 else
715 { 714 {
716 error ("etree: second argument must be a string"); 715 error ("etree: TYP must be a string");
717 return retval; 716 return retval;
718 } 717 }
719 } 718 }
720 719
721 // column elimination tree post-ordering (reuse variables) 720 // column elimination tree post-ordering (reuse variables)
723 722
724 if (is_sym) 723 if (is_sym)
725 { 724 {
726 if (n_row != n_col) 725 if (n_row != n_col)
727 { 726 {
728 error ("etree: matrix is marked as symmetric, but not square"); 727 error ("etree: S is marked as symmetric, but is not square");
729 return retval; 728 return retval;
730 } 729 }
731 730
732 symetree (ridx, cidx, etree, 0, n_col); 731 symetree (ridx, cidx, etree, 0, n_col);
733 } 732 }