{"id":2223,"date":"2011-08-27T00:01:10","date_gmt":"2011-08-26T22:01:10","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=2223"},"modified":"2011-08-27T12:55:22","modified_gmt":"2011-08-27T10:55:22","slug":"a-couple-of-fast-algorithms","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2011\/08\/27\/a-couple-of-fast-algorithms\/","title":{"rendered":"A couple of fast algorithms"},"content":{"rendered":"

<\/a>\"Closeup<\/a><\/p>\n

This post is devoted to a couple of simple fast algorithms.<\/p>\n

The Horner algorithm.<\/strong> The naive way to evaluate at point \\( {z} \\) the polynomial<\/p>\n

\\[ P(z):=a_nz^n+\\cdots+a_1z+a_0 \\]<\/p>\n

is to compute separately \\( {a_nz^n,\\ldots,a_1z,a_0} \\) and to sum up the results. The complexity of this evaluation algorithm is \\( {O(n^2)} \\). It could be more clever to compute recursively the sequence \\( {1,z,z^2,\\ldots,z^n} \\). This idea is behind a very simple \\( {O(n)} \\) algorithm called the Horner algorithm<\/em>:<\/p>\n

\\[ P(z)=a_0+z(a_1+\\cdots+z(a_{n-1}+za_n)\\cdots). \\]<\/p>\n

The Horner scheme<\/a> can be used for the division of polynomials and for roots finding. It runs nowadays in microprocessors and in numerical softwares. William George Horner<\/a> (1786 - 1837) was a British mathematician. His algorithm was actually already known at least by the Chinese mathematician Zhu Shijie<\/a> and also by the Italian mathematician Paolo Ruffini<\/a>.<\/p>\n

The Strassen algorithm.<\/strong> The naive way to compute the multiplication \\( {C:=AB} \\) of a couple of \\( {2\\times 2} \\) matrices \\( {A} \\) and \\( {B} \\) consists in the following computations:<\/p>\n

\\[ \\begin{array}{rcl} C_{11}&=&A_{11}B_{11}+A_{12}B_{21}\\\\ C_{12}&=&A_{11}B_{12}+A_{12}B_{22}\\\\ C_{21}&=&A_{21}B_{11}+A_{22}B_{21}\\\\ C_{22}&=&A_{21}B_{12}+A_{22}B_{22}. \\end{array} \\]<\/p>\n

This requires \\( {8} \\) multiplications (we neglect the cost of additions). Surprisingly, Mister Volker Strassen suggest to use the following curious alternative scheme:<\/p>\n

\\[ \\begin{array}{rcl} D_1&=&(A_{11}+A_{22})(B_{11}+B_{22})\\\\ D_2&=&(A_{21}+A_{22})B_{11}\\\\ D_3&=&A_{11}(B_{12}-B_{22})\\\\ D_4&=&A_{22}(B_{21}-B_{11})\\\\ D_5&=&(A_{11}+A_{12})B_{22}\\\\ D_6&=&(A_{21}-A_{11})(B_{11}+B_{12})\\\\ D_7&=&(A_{12}-A_{22})(B_{21}+B_{22}) \\end{array} \\]<\/p>\n

and then<\/p>\n

\\[ \\begin{array}{rcl} C_{11}&=&D_1+D_4-D_5+D_7\\\\ C_{12}&=&D_3+D_5\\\\ C_{21}&=&D_2+D_4\\\\ C_{22}&=&D_1-D_2+D_3+D_6. \\end{array} \\]<\/p>\n

This algorithm involves only \\( {7} \\) multiplications instead of \\( {8} \\). This simple fact, used form \\( {n\\times n} \\) matrices when \\( {n} \\) is a power of \\( {2} \\) (via multiplication by blocks), allows to reduce the complexity of the multiplication of a couple of \\( {n\\times n} \\) matrices from \\( {O(n^3)} \\) to \\( {O(n^{2.8})} \\). It is known as the Strassen algorithm<\/a>. It was published in 1969 in a famous paper of 3 pages called Gaussian elimination is not optimal<\/a>. It has some similarities with the fast Fourier transform<\/a>. Volker Strassen<\/a> (1936 - ) is a German mathematician who is also well known, among other things, for<\/p>\n