Re: iterative vs. direct methods for linear systems

Gordon Sande <g.sande@xxxxxxxxxxxxxxxx> writes:

There is a 2005 paper by Cohn, Kleinberg, Szegedy and Umans
(Group-theoretic algorithms for matrix multiplication) wherein they give
a minimal lower boundary of O(n^2), but this is a very academic result.

Since the answer is of size n^2 it does not seem to other than a trivial
statement that is often stated to remind foks that there will not be
either linear or n log ( n ) algorithms.

Obviously ;-)

Although they propose a construction scheme which has the possibility of
lowering the complexity exponent to 2, it's not really useful in
practice for more or less the same reasons Strassen's or
Coppersmith-Winograd's method is unsuitable.


Sebastian
.

Loading