[boost] GSoC uBLAS algorithms for derterminants, inversion and decomposition

Subject: [boost] GSoC uBLAS algorithms for derterminants, inversion and decomposition
From: Ganesh Prasad (sir.gnsp_at_[hidden])
Date: 2013-04-28 08:54:02

As inversion involves steps that use the determinant of the matrix, it's
better to develop an algorithm that evaluates the determinant of the matrix
faster than the conventional recursive way. I think extending the rule of
Sarrus does the trick. So far we have used rule of sarrus as a light weight
formula for evaluating determinants of 2x2 and 3x3 matrices.

But extending it in the following way makes it applicable for higher order
matrices too. And this algorithm has a time complexity O(2*n^2) for nxn
matrices.

// a is a n x n matrix
Det_a=0
Sum1=0
Sum2=0
For count=0 to n-1 do
   For i=1 to n do
      J=i+count
      Val=(j>n)?n:0
      j-=val
      product*=a[i][j]
   sum1+=product
For count=0 to n-1 do
   For i=1 to n do
      J=n-count-(i+1)
      Val=(j<1)?n:0
      J+=val
      product*=a[i][j]
   sum2+=product
det_a=sum1-sum2

return det_a

I want to use this algorithm in my GSoC project to evaluate determinants,
and based on this implementation I'll develop algorithms for inversion and
decomposition. But I think if we can make some changes to this algorithm,
this may run faster. As you can see, this thing traverses the matrix twice.
If we can achieve the goal in only one traversal calculating sum1 and sum2
simultaneously, then it'd be a bit faster, but here I lack ideas. So please
provide me with some help in this regard.

~Ganesh Prasad