dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / sketch / linear.lucb
## Dense linear algebra for the solver, on row-major `f64` arrays: a
## Cholesky factorization and solve for its normal equations, and a
## Householder QR with column pivoting for rank, null spaces and dependent
## rows (freedom.lucb). Sketch components are small (tens to a few hundred
## unknowns), where dense is fast and simple.
## Factor the `n` by `n` symmetric matrix `a` in place into L Lᵀ (L in the
## lower triangle). False when it is not positive definite to `tolerance`
## (a pivot at or below it, relative to the largest diagonal entry).
pub func cholesky(a: f64[], n: usize, tolerance: f64) -> bool:
var largest = 0.0
for i in 0..<n:
largest = math.max(largest, math.abs(a[i * n + i]))
let floor = tolerance * math.max(largest, nonzero)
for j in 0..<n:
var d = a[j * n + j]
for k in 0..<j:
d -= a[j * n + k] * a[j * n + k]
if not (d > floor): return false
let root = math.sqrt(d)
a[j * n + j] = root
for i in (j + 1)..<n:
var s = a[i * n + j]
for k in 0..<j:
s -= a[i * n + k] * a[j * n + k]
a[i * n + j] = s / root
return true
## Solve L Lᵀ x = b in place in `b`, with `l` from `cholesky`.
pub func cholesky_solve(l: const f64[], n: usize, b: f64[]):
for i in 0..<n:
var s = b[i]
for k in 0..<i:
s -= l[i * n + k] * b[k]
b[i] = s / l[i * n + i]
var i = n
while i > 0:
i -= 1
var s = b[i]
for k in (i + 1)..<n:
s -= l[k * n + i] * b[k]
b[i] = s / l[i * n + i]
## A Householder QR with column pivoting of the `rows` by `columns` matrix
## `a` (row-major, overwritten by R in its upper triangle): A P = Q R.
## `q` gets Q (`rows` by `rows`), `order` the columns' order P (the
## independent first) and the result is the rank: the pivots above
## `tolerance` times the first.
pub func pivoted_qr(a: f64[], rows: usize, columns: usize, q: f64[], order: i64[], tolerance: f64) -> usize:
for i in 0..<rows:
for j in 0..<rows:
q[i * rows + j] = 1.0 if i == j else 0.0
for j in 0..<columns:
order[j] = (i64)j
let steps = rows if rows < columns else columns
var rank: usize = 0
var first = 0.0
for step in 0..<steps:
# The remaining column of largest norm comes next.
var best = step
var best_norm = -1.0
for j in step..<columns:
var s = 0.0
for i in step..<rows:
s += a[i * columns + j] * a[i * columns + j]
if s > best_norm:
best_norm = s
best = j
if best != step:
for i in 0..<rows:
let t = a[i * columns + step]
a[i * columns + step] = a[i * columns + best]
a[i * columns + best] = t
let o = order[step]
order[step] = order[best]
order[best] = o
let norm = math.sqrt(math.max(best_norm, 0.0))
if step == 0: first = norm
if norm <= tolerance * math.max(first, nonzero): break
rank += 1
# The reflector v = x + sign(x0)|x| e0 on rows step..
let x0 = a[step * columns + step]
let alpha = -norm if x0 >= 0.0 else norm
var vnorm = 0.0
a[step * columns + step] = x0 - alpha
for i in step..<rows:
vnorm += a[i * columns + step] * a[i * columns + step]
if vnorm > 0.0:
# Apply H = I - 2 v vᵀ / vᵀv to the later columns and to Q.
for j in (step + 1)..<columns:
var s = 0.0
for i in step..<rows:
s += a[i * columns + step] * a[i * columns + j]
let f = 2.0 * s / vnorm
for i in step..<rows:
a[i * columns + j] -= f * a[i * columns + step]
for k in 0..<rows:
var s = 0.0
for i in step..<rows:
s += q[k * rows + i] * a[i * columns + step]
let f = 2.0 * s / vnorm
for i in step..<rows:
q[k * rows + i] -= f * a[i * columns + step]
a[step * columns + step] = alpha
for i in (step + 1)..<rows:
a[i * columns + step] = 0.0
return rank
## Solve the `n` by `n` system `a` for right-hand sides `x` and `y` in
## place (Gaussian elimination with partial pivoting); false when singular.
func solve_two(a: f64[], n: usize, x: f64[], y: f64[]) -> bool:
for column in 0..<n:
var best = column
for line in column + 1..<n:
if math.abs(a[line * n + column]) > math.abs(a[best * n + column]): best = line
if math.abs(a[best * n + column]) < 1e-14: return false
if best != column:
for k in 0..<n:
let swap = a[column * n + k]
a[column * n + k] = a[best * n + k]
a[best * n + k] = swap
let sx = x[column]
x[column] = x[best]
x[best] = sx
let sy = y[column]
y[column] = y[best]
y[best] = sy
for line in column + 1..<n:
let factor = a[line * n + column] / a[column * n + column]
if factor == 0.0: continue
for k in column..<n: a[line * n + k] -= factor * a[column * n + k]
x[line] -= factor * x[column]
y[line] -= factor * y[column]
var line = n
while line > 0:
line -= 1
var sx = x[line]
var sy = y[line]
for k in line + 1..<n:
sx -= a[line * n + k] * x[k]
sy -= a[line * n + k] * y[k]
x[line] = sx / a[line * n + line]
y[line] = sy / a[line * n + line]
return true