User stephen canon - MathOverflow

Answer by Stephen Canon for What is the constant of the Coppersmith-Winograd matrix multiplication algorithm

2009-10-21T22:20:42Z

In your second question, I think you mean "naive matrix multiplication", not "Gaussian elimination".

Henry Cohn et al had a cute paper that relates fast matrix multiply algorithms to certain groups. It doesn't do much for answering your question (unless you want to go and prove the conjectured results =), but it's a fun read.

Also, to back up harrison, I don't think that anyone really believes that there's an $O(n^2)$ algorithm. A fair number of people believe that there is likely to be an algorithm which is $O(n^{2+\epsilon})$ for any $\epsilon > 0$. An $O(n^2 \log n)$ algorithm would fit the bill.

edit: You can get a back-of-the-envelope feeling for a lower bound on the exponent of Coppersmith-Winograd based on the fact that people don't use it, even for n on the order of 10,000; naive matrix multiplication requires $2n^3 + O(n^2)$ flops, and Coppersmith-Winograd requires $Cn^{2.376} + O(n^2)$. Setting the expressions equal and solving for $C$ gives that the two algorithms would have equal performance for n = 10,000 (ignoring memory access patterns, implementation efficiency, and all sorts of other things) if the constant were about 627. In reality, it's likely much larger.

Answer by Stephen Canon for Why is the gradient normal?

2009-10-22T23:48:47Z

I like this intuition:

The bundle of tangent vectors to the surface at a point live in the tangent plane at that point. The tangent[s] to the level set at that point are exactly the vectors in the tangent plane whose "vertical" component is zero. The vector[s] pointing in the direction of greatest increase are those with the largest relative "vertical" components. Plane geometry (in the tangent plane) shows that these must to be perpendicular.

Answer by Stephen Canon for Is x^y a recursive algorythm

2009-10-21T19:58:05Z

There is no pow function in the C language for integers. There is a pow defined in the standard header <math.h>, but it operates on floating-point data, not integers.

FWIW, the actual implementation of the floating-point pow function varies from platform to platform, but it does not typically use any sort of recursion. The implementation is often, but not always, based on the definition $x^y = \exp(y\log x)$ (though not necessarily using the base-e logarithm or exponential; 2 is a common choice).

When people implement integer exponentiation carefully, they usually use a repeated-squaring algorithm, which requires $O(log n)$ multiplications to raise x to the nth power (the complexity of each multiplication is a separate issue if you're not working with fixed-size integers). Knuth has an interesting discussion of integer exponentiation -- in particular, there is no known algorithm other than brute-force search that finds the optimal sequence of multiplications for raising an input to a known power.

Also, why is this question tagged linear-algebra?

Comment by Stephen Canon

2009-11-06T18:16:43Z

Fifthed. I haven't heard any other pronunciation in the US.