Matrix inversion tool

[Oleg Goldshmidt]

Matan Ziv-Av <matan at svgalib.org> writes:

> The last line is wrong.

You are right.

> The naive algorithm, taught to any engineering or science student in
> the first linear algebra course, is Gauss elimination (also known as
> LU decomposition in this context). It runs in O(n^3) steps.
>
> Note that this algorithm is used very similarly for both inverting a
> matrix and calculating the determinant. So even if we replace step [5]
> in your suggestion, with Gaussian elimination, we still get O(n^5),
> when our code actually has all necessary components for running in
> O(n^3) instead.

A general comment. Asymptotic complexity has its uses but is very rarely
relevant in practice. One would probaly need a serious literature search
just to find out on what scale asymptotic complexity becomes relevant
for a given type of problem, and I will not be surprised if such a
search gives no generic result, or no practically useful result. In
practice, people keep solving problems that would require Hubble times
asymptotically.

There was no scale (or speed) requirement mentioned in the OP. Later,
Shachar mentioned 273x273 as a target. [He also said it was likely to be
sparse, so I wouldn't get stuck on O() estimates.] I admit I have not
done much matrix manipulation for quite a while, but 273x273 seems quite
large for a regular computer. It is not clear to me (I'll appreciate a
comment just for curiousity's sake as well as for education) that a
straightforward algorithm will be practical. Maybe one needs to think of
a highly paralellized algo on such scales. A CUDA (GPGPU, MIC, whatever)
computer may help, may or may not require custom implementation, and may
or may not make any differences in asymptotic complexity go away on the
300x300 scale.

On top of that, it is not clear to me how much the fact that + is XOR
and * is AND over Z2 may help (with or withut CUDA or similar).

-- 
Oleg Goldshmidt | pub at goldshmidt.org