[ODE] Choleski factorization

[Russ Smith]

hi,

it sounds like you're getting close to the "principal pivoting"
algorithm for LCP solving. the PP algorithm works like this:

	solve the LCP problem:  A*x=b+w, x>=0, w>=0, x'*w=0
	where A is n*n, x and w are n*1

	S = a set of indexes, initially empty

	while(1) {
	  // form a 'principle submatrix' and solve for x(S)
	  x = 0
	  x(S) = inv(A(S,S)) * b(S);

	  // compute the residual
  	  w = 0
      	  w(!S) = A(!S,S)*x(S)-b(!S);

	  // find the first violated index and switch it
	  if any elements of x are < 0 then
	    remove index of first x element that is < 0 from S
	  else if any elements of w are < 0 then
	    add index of first w element that is < 0 to S
	  else return		// we're done
	}

in this notation, !S is the set of indexes that are not in S. this
algorithm will converge for all positive definite matrices A and has
'expected' polynomial running time.

> My question is, is a Cholesky Factorization also a factorization for
> all of its sub-matrices?

if you have the factorization A=L*L', then you also have the
factorizations A(1:n,1:n)=L(1:n,1:n)*L(1:n,1:n)' for all n (in matlab
notation). other submatrix factorizations can be gotten incrementally,
see the ODE source for an incremantal factorization updater.

russ.

-- 
Russell Smith
http://www.q12.org