Commits

committed 93d846c

added high performance version of lowDegreeNodes

• Participants
• Parent commits b030f2c
• Branches default

File src/lamg/amg/setup.py

`         while (stageNum < self.options.eliminationMaxStages):`
`             niter += 1`
`             # % Compute Z and F sets`
`-            (z, f, c) = hyper.lowDegreeNodes(A, degree, self.options.eliminationMaxDegree)`
`+            (z, f, c) = hyper.lowDegreeNodes_matlab(A, degree, self.options.eliminationMaxDegree)`
`             nf = lab.numel(f)`
`             nc = lab.numel(c)`
`             if lab.isempty(c) or (nf <= (self.options.minEliminationFraction * n)) \`
`             `
`             # % Compute coarse operator = Schur complement`
`             Acc = A[ix_(c, c)]`
`-            A = Acc + A[ix_(c, f)] * P`
`+            Acf = A[ix_(c, f)]`
`+            # FIXME: Acc, Acf and P should have the same square shape! `
`+            # example shapes: Acf (57, 193) , Acc (57, 57), P (250, 193)`
`+            A = Acc + Acf * P`
`             n = lab.size(A, 1)`
`             if (n > 1) and (not lab.isempty(lab.find(lab.negate(lab.diag(A), 1)))):`
`                 raise Exception("Zero diagonal element in eliminated operator. Could be due to very small edge weights in original matrix.")`

File src/lamg/hyper.py

`     raise NotImplementedError("TODO")`
` `
` `
`+def lowDegreeNodes(A, d=None, maxDegree=None):`
`+    """`
`+        %LOWDEGREENODES Identify low degree graph nodes to be eliminated in a`
`+    %singly connected graph.`
`+    %   [F,C,STATUS]=LOWDEGREENODES(A,D,MAXDEGREE) returns the indices of an`
`+    %   independent set of (<=MAXDEGREE)-degree nodes (F), and the rest of the`
`+    %   nodes (C), in a symmetric adjacency matrix A. All F nodes are`
`+    %   independent of each other, i.e., A(F,F) is diagonal. D is a vector of`
`+    %   node degrees; if empty, it is internally set to SUM(SPONES(A)).`
`+    %`
`+    %   Note: A can also be a graph Laplacian (in which case A's diagonal is`
`+    %   ignored), or only the sparsity pattern of the adjacency matrix (weights`
`+    %   are not used).`
`+    %`
`+    %   [F,C,STATUS]=LOWDEGREENODES(A) is equivalent to [F,C,STATUS]=LOWDEGREENODES(A,3).`
`+    %`
`+    %   See also: CoarseningStrategyLowImpact, amd.`
`+    """`
`+    `
`+    # % Status flag array coding schema. Must match elimination.h`
`+    LOW_DEGREE = 1`
`+    HIGH_DEGREE = 2`
`+    `
`+    # % Initializations`
`+    if (maxDegree is None):`
`+        maxDegree = 3`
`+    `
`+    if (d is None):`
`+        d = lab.sum(A != 0, 1) # % Could be improved a little by MEX`
`+    `
`+    candidate = lab.find(d <= maxDegree)`
`+    status = HIGH_DEGREE * lab.ones(lab.size(A, 1), 1)`
`+    status[candidate] = 0   # % Reset all relevant nodes to "not visited"`
`+    `
`+    # % Call MEX function for the computationally-intensive step of marking nodes`
`+    status = lowdegreesweep(status, A, candidate)`
`+    `
`+    # % Format flag array as output`
`+    f = lab.find(status == LOW_DEGREE)`
`+    c = lab.find(status != LOW_DEGREE)`
`+    `
`+    # % Never allow the elimination of all nodes. Leave at least one node in c.`
`+    `
`+    if lab.isempty(c):`
`+        c = f[0]`
`+        f = f[1:]`
`+        `
`+    return (f, c, status)`
`+    `
`+    `
` `
`-def lowDegreeNodes(A, d=None, maxDegree=None):`
`+`
`+`
`+def lowDegreeNodes_matlab(A, d=None, maxDegree=None):`
`     """`
`         %LOWDEGREENODES Identify low degree graph nodes to be eliminated (pure`
`     %MATLAB implementation).`