Simplified best time bounds, rectangular matrix multiplication
- From: spin@xxxxxxxxxxxxxxxxxxx (Jeremy Spinrad)
- Date: 15 Jun 2005 14:38:57 GMT
I am using rectangular matrix multiplication to solve some problems. The
statement that I have, in Huang and Pan's paper Fast Rectangular Matrix
Multiplication and Applications, is quite complex. Given the dimensions, I can
figure out a time bound, but only by plugging into a somewhat complex formula. I
hate to go into this when simply using the result in a paper; is there a
simplified statement of the best known time bounds anywhere? An approximation
would be good enough for my purposes. To be more precise, I am doing
(n x n^{1.425}) (n^{1.425} x n) matrix multiplication, and since this is not
quite a bottleneck step of the algorithm simply have to say that the running time
is O(n^{2.79}).
Again, I know that it is, but I don't know how to show it simply, without giving
the complex bounds for (n x n) (n x n^ {r > 1}) bounds given in the Huang and Pan
paper.
Jerry Spinrad
.
- Prev by Date: Re: are Real Numbers evil?
- Next by Date: Re: are Real Numbers evil?
- Previous by thread: my web nightmare.
- Next by thread: shortest path with constraints that some nodes can not be on the same pth
- Index(es):