1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
function [p, cparent, cmember] = nesdis (A, mode, opts) %#ok
%NESDIS nested dissection ordering via CHOLMOD's nested dissection.
%
% Example:
% p = nesdis(A) returns p such chol(A(p,p)) is typically
% sparser than chol(A). Uses tril(A) and assumes
% A is symmetric.
% p = nesdis(A,'sym') the same as p=nesdis(A).
% p = nesdis(A,'col') returns p so that chol(A(:,p)'*A(:,p)) is
% typically sparser than chol(A'*A).
% p = nesdis(A,'row') returns p so that chol(A(p,:)*A(p,:)') is
% typically sparser than chol(A'*A).
%
% A must be square for p=nesdis(A) or nesdis(A,'sym').
%
% With three output arguments, [p cp cmember] = nesdis(...), the
% separator tree and node-to-component mapping is returned. cmember(i)=c
% means that node i is in component c, where c is in the range of 1 to
% the number of components. length(cp) is the number of components
% found. cp is the separator tree; cp(c) is the parent of component c,
% or 0 if c is a root. There can be anywhere from 1 to n components,
% where n is dimension of A, A*A', or A'*A. cmember is a vector of
% length n.
%
% An optional 3rd input argument, nesdis (A,mode,opts), modifies the
% default parameters. opts(1) specifies the smallest subgraph that
% should not be partitioned (default is 200). opts(2) is 0 by default;
% if nonzero, connected components (formed after the node separator is
% removed) are partitioned independently. The default value tends to
% lead to a more balanced separator tree, cp. opts(3) defines when a
% separator is kept; it is kept if the separator size is < opts(3) times
% the number of nodes in the graph being cut (valid range is 0 to 1,
% default is 1).
%
% opts(4) specifies graph is to be ordered after it is dissected. For
% the 'sym' case: 0: natural ordering, 1: CAMD, 2: CSYMAMD. For other
% cases: 0: natural ordering, nonzero: CCOLAMD. The default is 1, to use
% CAMD for the symmetric case and CCOLAMD for the other cases.
%
% If opts is shorter than length 4, defaults are used for entries that
% are not present.
%
% NESDIS uses METIS' node separator algorithm to recursively partition
% the graph. This gives a set of constraints (cmember) that is then
% passed to CCOLAMD, CSYMAMD, or CAMD, constrained minimum degree
% ordering algorithms. NESDIS typically takes slightly more time than
% METIS (METIS_NodeND), but tends to produce better orderings.
%
% Requires METIS, authored by George Karypis, Univ. of Minnesota. This
% MATLAB interface, via CHOLMOD, is by Tim Davis.
%
% See also metis, bisect, amd.
% Copyright 2006-2023, Timothy A. Davis, All Rights Reserved.
% SPDX-License-Identifier: GPL-2.0+
error ('nesdis mexFunction not found') ;
|
