Skip to content

Instantly share code, notes, and snippets.

@inspirit
Created October 24, 2012 13:15
Show Gist options
  • Save inspirit/3945994 to your computer and use it in GitHub Desktop.
Save inspirit/3945994 to your computer and use it in GitHub Desktop.
Cholesky solver using simple math only
function cholesky_solve(A:Vector.<Number>, size:int, b:Vector.<Number>):Boolean
{
var col:int, row:int, col2:int;
var val:Number;
for (col = 0; col < size; ++col)
{
var inv_diag:Number = 1;
var cs:int = (col * size);
var rs:int = cs;
for (row = col; row < size; ++row)
{
val = A[(rs+col)];
for (col2 = 0; col2 < col; ++col2)
{
val -= A[(col2*size+col)] * A[(rs+col2)];
}
if (row == col)
{
// this is the diagonal element so don't divide
A[(rs+col)] = val;
if(val == 0){
return false;
}
inv_diag = 1.0 / val;
} else {
// cache the value without division in the upper half
A[(cs+row)] = val;
A[(rs+col)] = val * inv_diag;
}
rs = (rs + size);
}
}
// first backsub through L
var i:int, j:int;
for (i = 0; i < size; ++i)
{
val = b[i];
for (j = 0; j < i; ++j)
{
val -= A[(i*size+j)] * b[j];
}
b[i] = val;
}
// backsub through diagonal
for (i = 0; i < size; ++i)
{
b[i] /= A[(i*size+i)];
}
// backsub through L Transpose
i = (size-1);
for (; i >= 0; --i)
{
val = b[i];
j = (i + 1);
for (; j < size; ++j)
{
val -= A[(j*size+i)] * b[j];
}
b[i] = val;
}
return true;
}
@headupinclouds
Copy link

This is a great contribution. I measure this is 3x faster than OpenCV sepFilter2D on an iPhone 5s and 2x faster than using Apple's vImageConvolve_PlanarF used for separable convolution.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment