csEreach.js (1960B)
1 "use strict"; 2 3 Object.defineProperty(exports, "__esModule", { 4 value: true 5 }); 6 exports.csEreach = csEreach; 7 8 var _csMark = require("./csMark.js"); 9 10 var _csMarked = require("./csMarked.js"); 11 12 /** 13 * Find nonzero pattern of Cholesky L(k,1:k-1) using etree and triu(A(:,k)) 14 * 15 * @param {Matrix} a The A matrix 16 * @param {Number} k The kth column in A 17 * @param {Array} parent The parent vector from the symbolic analysis result 18 * @param {Array} w The nonzero pattern xi[top] .. xi[n - 1], an array of size = 2 * n 19 * The first n entries is the nonzero pattern, the last n entries is the stack 20 * 21 * @return {Number} The index for the nonzero pattern 22 * 23 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 24 */ 25 function csEreach(a, k, parent, w) { 26 // a arrays 27 var aindex = a._index; 28 var aptr = a._ptr; 29 var asize = a._size; // columns 30 31 var n = asize[1]; // initialize top 32 33 var top = n; // vars 34 35 var p, p0, p1, len; // mark node k as visited 36 37 (0, _csMark.csMark)(w, k); // loop values & index for column k 38 39 for (p0 = aptr[k], p1 = aptr[k + 1], p = p0; p < p1; p++) { 40 // A(i,k) is nonzero 41 var i = aindex[p]; // only use upper triangular part of A 42 43 if (i > k) { 44 continue; 45 } // traverse up etree 46 47 48 for (len = 0; !(0, _csMarked.csMarked)(w, i); i = parent[i]) { 49 // L(k,i) is nonzero, last n entries in w 50 w[n + len++] = i; // mark i as visited 51 52 (0, _csMark.csMark)(w, i); 53 } 54 55 while (len > 0) { 56 // decrement top & len 57 --top; 58 --len; // push path onto stack, last n entries in w 59 60 w[n + top] = w[n + len]; 61 } 62 } // unmark all nodes 63 64 65 for (p = top; p < n; p++) { 66 // use stack value, last n entries in w 67 (0, _csMark.csMark)(w, w[n + p]); 68 } // unmark node k 69 70 71 (0, _csMark.csMark)(w, k); // s[top..n-1] contains pattern of L(k,:) 72 73 return top; 74 }