User stephen canon - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T15:51:30Z http://mathoverflow.net/feeds/user/598 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm/1749#1749 Answer by Stephen Canon for What is the constant of the Coppersmith-Winograd matrix multiplication algorithm Stephen Canon 2009-10-21T22:20:42Z 2010-03-05T23:13:32Z <p>In your second question, I think you mean "naive matrix multiplication", not "Gaussian elimination".</p> <p>Henry Cohn et al had <a href="http://arxiv.org/pdf/math.GR/0307321.pdf" rel="nofollow">a cute paper</a> 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.</p> <p>Also, to back up <strong>harrison</strong>, 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.</p> <p><strong>edit:</strong> 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.</p> http://mathoverflow.net/questions/1977/why-is-the-gradient-normal/1979#1979 Answer by Stephen Canon for Why is the gradient normal? Stephen Canon 2009-10-22T23:48:47Z 2009-10-22T23:48:47Z <p>I like this intuition:</p> <p>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.</p> http://mathoverflow.net/questions/1710/is-xy-a-recursive-algorythm/1711#1711 Answer by Stephen Canon for Is x^y a recursive algorythm Stephen Canon 2009-10-21T19:58:05Z 2009-10-21T20:03:30Z <p>There is no <code>pow</code> function in the C language for integers. There is a <code>pow</code> defined in the standard header <code>&lt;math.h&gt;</code>, but it operates on floating-point data, not integers.</p> <p>FWIW, the actual implementation of the floating-point <code>pow</code> function varies from platform to platform, but it does not typically use any sort of recursion. The implementation is <em>often</em>, 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).</p> <p>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.</p> <p>Also, why is this question tagged <code>linear-algebra</code>?</p> http://mathoverflow.net/questions/4381/pronunciation-dijkstra/4385#4385 Comment by Stephen Canon Stephen Canon 2009-11-06T18:16:43Z 2009-11-06T18:16:43Z Fifthed. I haven't heard any other pronunciation in the US.