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

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
> > 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.

 Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/