Re: [eigen] request for help: 4x4 matrix inverse

[Benoît Jacob <jacob@xxxxxxxxxxxxxxx>]

OK, I got it:

for i \in \{ 1,2,3 \} let N_i be the following 2x2 matrix:

(M_{00} M_{01})
(M_{i0} M_{i1})

(note that N_1 is just P).

for M to be invertible, it is necessary (not sufficient) that its two first 
columns are linearly independent. For which it is necessary that either N_1 
or N_2 or N_3 is invertible.

Hence we get away with, in the worst case, one row permutation (which can be 
abstracted and doesn't have to be actually performed on the matrix) and two 
extra 2x2 invertibility checks (those for N_1 and N_2, in case they are both 
non-invertible and one has to use N_3).

Cheers,
Benoit

On Tuesday 15 April 2008 15:28:16 Benoît Jacob wrote:
> > I don't do divs as well (reciprocal approximation and Newton-Raphson
> > instead, much faster than div),
>
> I confess I didn't know about these concepts!
>
> > no branching, but i haven't
> > benchmarked it yet. The nice thing about this method is that
> > calculating the determinant is more than half-way to getting the
> > inverse, as most quantities are already calculated.
>
> Indeed, it looks optimal for a determinant+inverse computation. Well, both
> are always closely related, but in your approach one gets both faster than
> with brute-force.
>
> We just need to figure out what to do when detP=0...
>
> I have a rough idea: since we may permute rows and cols, it is enough that
> there exist integers i,j,k,l between 0 and 3 such that the following 2x2
> submatrix of M,
> ( M_{ik} M_{il} )
> ( K_{jk} M_{jl} )
> is invertible.
>
> Such i,j,k,l sure exist whenever M is invertible, so we just need to find
> them. Speed is not even important here since in 98% of cases we'll have
> detP!=0 anyway, so this doesn't impact the "mean complexity" very much.
>
> Cheers,
>
> Benoit

Attachment: signature.asc
Description: This is a digitally signed message part.