Matan Ziv-Av <ma...@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 | p...@goldshmidt.org _______________________________________________ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
