Matrix inversion tool

[Shachar Shemesh]

On 10/08/15 17:32, Matan Ziv-Av wrote:
>
> At the end of this message is a python program with simple
> implementations of both algorithms (Gauss eliminiation and recursive).
> Run them for sizes 10 to 16 consecuitively to see how the difference
> between exponential and polynomial is very significant in this case.
1. Ask for help finding tools on mailing list
2. Get Oleg to question the viability of the suggested solution
3. Matan writes the tool you need for you
4. ????
5. Profit


> The optimizations you suggested are possible (for both algorithms),
> but they are all just scaling the time needed. Even if you speed up by
> a factor of 10^9, the recursive algorithm will just not work.
I have not delved too deeply into the "det" calculation, but wouldn't
caching of sub-results cause an actual decrease in the complexity of the
run?

I've had a program I wrote once (for solving Nonograms
(https://en.wikipedia.org/wiki/Nonogram)) where adding caching of
intermediate results caused an complexity reduction. A riddle previously
solved in ~40 minutes was, after introducing caching, solved in 150
millisconds!!!

I even considered doing a Haifux lecture titled "Complexity; why
programmers ignore it, and why it still matters".

Shachar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.huji.ac.il/pipermail/linux-il/attachments/20150810/2427b634/attachment.html>