Press "Enter" to skip to content

Month: August 2011

Graphics and LaTeX

Latex balloon

One of the most frequent question by beginners in \(\LaTeX\) is

How to produce and to include graphics in my \(\LaTeX\) file?

You may read this e-book. If you have already your graphic in EPS, PDF, PNG, or JPEG format, you may use the graphicx package and its \includegraphic command. You may also produce graphics directly in \(\LaTeX\), or using a package like PGF/TikZ (see the examples gallery). There is also PDFTricks which is the counterpart of PSTricks. You may also use an external program such as  Metapost, Inkscape, the venerable Xfig or the more recent and neat Ipe. I use TikZ and Ipe. By the way, if you need to include selected pages from PDF files inside your \(\LaTeX\) document compiled with pdflatex, you may use the excellent pdfmerge package. Finally, if you use GNU/Linux, you may use for instance Emacs, TeXwork, LaTeXila, LyX, Texmaker, or Kile to edit your \(\LaTeX\) files. I use Emacs or vim (old habits…). You may also try by curiosity TeXmacs.

1 Comment

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.

Leave a Comment



Les crises  qui secouent depuis ses origines le capitalisme ambiant sont très excitantes intellectuellement. Elles soulignent la cupidité individuelle des humains et leur incapacité à répartir les richesses entre eux de manière équitable. Malgré tout, il ne faut peut être pas ranger toutes les montagnes de richesses dans le même sac. Certains milliardaires comme Warren Buffet ou Bill Gates sont parfois grassement philanthropes. En revanche, les grandes sociétés multinationales qui ne sont pas possédées par des milliardaires le sont rarement, ou de manière relativement limitée pour soigner leur image. Elles sont en effet dirigées par des gestionnaires – très (trop ?) bien payés – dont l’unique mission est d’augmenter les profits d’une nuée d’actionnaires ou de sociétaires [Toute personne qui consomme ou possède un compte en banque y participe indirectement]. Cette dilution d’humanité et de responsabilité mériterait d’être encadrée par des lois. Mais qui donc peut promouvoir des lois planétaires ?

Last Updated on 2014-06-17


Two basic probabilistic proofs

Johan Jensen (mathematician)

I enjoy basic beautiful mathematical proofs. I see them like small jewels, that I collect from time to time. In this spirit, this post proposes probabilistic proofs of a couple of basic results.

Jensen inequality. The Jensen inequality states that if \( {X} \) is an integrable random variable on \( {\mathbb{R}^n} \) and \( {\varphi:\mathbb{R}^n\rightarrow\mathbb{R}} \) a convex function such that \( {\varphi(X)} \) is integrable, then

\[ \varphi(\mathbb{E}(X))\leq \mathbb{E}(\varphi(X)). \]

To prove it, we start by using the convexity of \( {\varphi} \), which gives, for every integer \( {n\geq1} \) and every sequence \( {x_1,\ldots,x_n} \) in \( {\mathbb{R}^n} \),

\[ \varphi\left(\frac{x_1+\cdots+x_n}{n}\right) \leq \frac{\varphi(x_1)+\cdots+\varphi(x_n)}{n}. \]

Now, we use the integrability of \( {X} \) and \( {\varphi(X)} \): we take \( {x_1,x_2,\ldots} \) random independent and distributed as \( {X} \), we use the strong law of large numbers for both sides, the fact that \( {\varphi} \) is continuous for the left hand side, and the fact that if \( {\mathbb{P}(A)=\mathbb{P}(B)=1} \) then \( {A\cap B\neq\varnothing} \). I also appreciate the proof based on the equality for affine functions, the variational expression of a convex function as the envelope of its tangent hyperplanes, together with the fact that the supremum of expectations is less than or equal to the expectation of the supremum.

Schur-Hadamard product and cone of positive matrices. The Schur-Hadamard product of two square matrices \( {A,B\in\mathcal{M}_n(\mathbb{R})} \) is the matrix \( {A\circ B\in\mathcal{M}_n(\mathbb{R})} \) defined by

\[ (A\circ B)_{ij}:=A_{ij}B_{ij} \]

for evey \( {1\leq i,j\leq n} \). This entrywise product is denoted .* in Matlab/Octave/Freemat/Scilab.

Obviously, the Schur-Hadamard product preserves the cone of symmetric matrices. It is however not obvious that if \( {A} \) and \( {B} \) are symmetric positive semidefinite (i.e. non negative spectrum) then \( {A\circ B} \) is also symmetric positive semidefinite.

To prove this remarkable statement, let us recall that the set of symmetric positive semidefinite matrices coincides with the set of covariance matrices of random vectors (and even of Gaussian random vectors). Next, let us consider two independent centered random vectors \( {X} \) and \( {Y} \) of \( {\mathbb{R}^n} \) with respective covariance matrices \( {A} \) and \( {B} \). Now, the random vector \( {Z=X\circ Y} \) of \( {\mathbb{R}^n} \) defined by \( {Z_i:=X_iY_i} \) for every \( {1\leq i\leq n} \) has covariance matrix \( {A\circ B} \), which is thus necessarily symmetric positive semidefinite! Any simpler proof?

Last Updated on 2014-06-17

Syntax · Style · .