1 | import { csReach } from './csReach'
|
2 | import { factory } from '../../../utils/factory'
|
3 |
|
4 | const name = 'csSpsolve'
|
5 | const dependencies = [
|
6 | 'divideScalar',
|
7 | 'multiply',
|
8 | 'subtract'
|
9 | ]
|
10 |
|
11 | export const createCsSpsolve = /* #__PURE__ */ factory(name, dependencies, ({ divideScalar, multiply, subtract }) => {
|
12 | /**
|
13 | * The function csSpsolve() computes the solution to G * x = bk, where bk is the
|
14 | * kth column of B. When lo is true, the function assumes G = L is lower triangular with the
|
15 | * diagonal entry as the first entry in each column. When lo is true, the function assumes G = U
|
16 | * is upper triangular with the diagonal entry as the last entry in each column.
|
17 | *
|
18 | * @param {Matrix} g The G matrix
|
19 | * @param {Matrix} b The B matrix
|
20 | * @param {Number} k The kth column in B
|
21 | * @param {Array} xi The nonzero pattern xi[top] .. xi[n - 1], an array of size = 2 * n
|
22 | * The first n entries is the nonzero pattern, the last n entries is the stack
|
23 | * @param {Array} x The soluton to the linear system G * x = b
|
24 | * @param {Array} pinv The inverse row permutation vector, must be null for L * x = b
|
25 | * @param {boolean} lo The lower (true) upper triangular (false) flag
|
26 | *
|
27 | * @return {Number} The index for the nonzero pattern
|
28 | *
|
29 | * Reference: http://faculty.cse.tamu.edu/davis/publications.html
|
30 | */
|
31 | return function csSpsolve (g, b, k, xi, x, pinv, lo) {
|
32 | // g arrays
|
33 | const gvalues = g._values
|
34 | const gindex = g._index
|
35 | const gptr = g._ptr
|
36 | const gsize = g._size
|
37 | // columns
|
38 | const n = gsize[1]
|
39 | // b arrays
|
40 | const bvalues = b._values
|
41 | const bindex = b._index
|
42 | const bptr = b._ptr
|
43 | // vars
|
44 | let p, p0, p1, q
|
45 | // xi[top..n-1] = csReach(B(:,k))
|
46 | const top = csReach(g, b, k, xi, pinv)
|
47 | // clear x
|
48 | for (p = top; p < n; p++) { x[xi[p]] = 0 }
|
49 | // scatter b
|
50 | for (p0 = bptr[k], p1 = bptr[k + 1], p = p0; p < p1; p++) { x[bindex[p]] = bvalues[p] }
|
51 | // loop columns
|
52 | for (let px = top; px < n; px++) {
|
53 | // x array index for px
|
54 | const j = xi[px]
|
55 | // apply permutation vector (U x = b), j maps to column J of G
|
56 | const J = pinv ? pinv[j] : j
|
57 | // check column J is empty
|
58 | if (J < 0) { continue }
|
59 | // column value indeces in G, p0 <= p < p1
|
60 | p0 = gptr[J]
|
61 | p1 = gptr[J + 1]
|
62 | // x(j) /= G(j,j)
|
63 | x[j] = divideScalar(x[j], gvalues[lo ? p0 : (p1 - 1)])
|
64 | // first entry L(j,j)
|
65 | p = lo ? (p0 + 1) : p0
|
66 | q = lo ? (p1) : (p1 - 1)
|
67 | // loop
|
68 | for (; p < q; p++) {
|
69 | // row
|
70 | const i = gindex[p]
|
71 | // x(i) -= G(i,j) * x(j)
|
72 | x[i] = subtract(x[i], multiply(gvalues[p], x[j]))
|
73 | }
|
74 | }
|
75 | // return top of stack
|
76 | return top
|
77 | }
|
78 | })
|