Press "Enter" to skip to content

A couple of fast algorithms

Closeup of the London Science Museum's difference engine.

This post is devoted to a couple of simple fast algorithms.

The Horner algorithm. The naive way to evaluate at point \( {z} \) the polynomial

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

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:

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

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

The Strassen algorithm. 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:

\[ \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} \]

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

\[ \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} \]

and then

\[ \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} \]

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. It was published in 1969 in a famous paper of 3 pages called Gaussian elimination is not optimal. It has some similarities with the fast Fourier transform. Volker Strassen (1936 – ) is a German mathematician who is also well known, among other things, for

He has also a nice paper on the existence of probability measures with given marginals. I have a great admiration for his achievements!

I have learnt the Horner scheme in my youth, at school in Algeria, and the Strassen algorithm ten years ago from Terry J. Lyons during a postdoc in the Oxford mathematical institute. Of course one can mix the two for the evaluation of a matrix polynomial.

Be First to Comment

    Leave a Reply

    Your email address will not be published. Required fields are marked *