Libres pensées d'un mathématicien ordinaire

The success of computers is largely due to the existence of efficient algorithms for solving numerical and combinatorial problems. These algorithms are used billion of times per second. Many users (even among scientists) do not know them. One may find a list of algorithms on Wikipedia. Depending on your tastes, you may distinguish some favorite ones, for their simplicity, elegance, or versatility. Here are some few of my favorite algorithms and paradigms:

• Gram-Schmidt algorithm, QR algorithm, LU algorithms
• Gauss elimination, Euclidean algorithm and Gröbner bases
• Simplex algorithm, Hungarian algorithm, linear programming, semi-definite programming
• Gradient descent, binary search, Newton algorithm
• Robbins-Monro and Kiefer-Wolfowitz stochastic approximation
• Expectation-Maximization, Matching pursuit, Classification And Regression Tree
• Fast Fourier Transform algorithm, Fast Wavelet Transform algorithm, Kalman filter
• Euler algorithms, finite elements algorithms, finite volume algorithms
• Quick sort, Dijkstra algorithm, Message-Digest algorithm, Secure Hash Algorithm
• Huffman coding, Lempel-Ziv-Welch coding
• Hamming coding, Reed-Muller coding, Gallager coding
• Rivest-Shamir-Adleman algorithm, Digital Signature Algorithm
• Knuth-Morris-Pratt, Rabin-Karp, and string matching algorithms
• Miller-Rabin algorithm, Schonhage-Strassen algorithm
• Fisher-Yates-Knuth shuffle, Mersenne twister, Marsaglia ziggurat
• Metropolis-Hastings, Propp-Wilson coupling from the past, simulated annealing

• Monte-Carlo methods
• Dynamic programing paradigm
• Genetic algorithms paradigm
• Branch and bound paradigm
• Greedy algorithms paradigm
• Divide and conquer paradigm

Ironically, the most used algorithms (if we measure say in Megawatt) concern coding, compression, cryptography, linked with what is often identified as “pure mathematics” (finite fields algebra, discrete linear algebra, discrete harmonic analysis). This does not mean that numerical algorithms, identified as “applied mathematics”, are not used! To me, what matters is the depth and beauty of concepts and the efficiency and versatility of implementations.

• Iterative and non-iterative
• Exact and approximate
• Stochastic and deterministic
• Integer and numerical
• Euclid and Archimedes

Je dispense depuis deux années un cours d’initiation aux probabilités pour la préparation à l’agrégation interne de mathématiques, à l’Université Paris-Est Marne-la-Vallée. Comme souvent, j’ai pris le temps d’écrire des notes de cours, d’environ 80 pages, que je distribue à mes étudiants, et que tout le monde peut télécharger sur ma page personnelle sous forme électronique (pratique pour chercher). Ces notes n’ont rien de révolutionnaire dans leur contenu, mais expriment ma manière de voir les choses, dans le cadre du programme de l’agrégation interne (qui mériterait du reste une sérieuse refonte pour les probabilités).

Comme le soulignent mes agrégatifs, ces notes seraient beaucoup plus utiles si elles étaient transformées en livre, car seuls les livres sont autorisés par le jury le jour de l’oral du concours. La méthode traditionnelle pour transformer des notes de cours en livre consiste à contacter un éditeur, qui, bien souvent, interdira la diffusion électronique gratuite pour sauvegarder son profit. Mais pourquoi diable m’encombrer d’une telle contrainte ?

Une solution originale m’a été suggérée par courriel par un collègue distant : demander à titre personnel un numéro ISBN à l’AFNIL (gratuit). Ce service est l’analogue de celui des noms de domaines pour Internet. C’est désormais chose faite. Mes notes de cours possèdent un ISBN et constituent donc un livre électronique. Ce livre électronique est librement accessible sur ma page personnelle. Il est donc en principe utilisable le jour de l’oral par tous les candidats aux concours à partir de la session 2013 (la session 2012 est semble-t-il trop proche).

Les lecteurs qui apprécient ce livre électronique peuvent manifester leur gratitude en faisant un don directement à l’auteur via PayPal. Ce sont eux qui choisissent le montant, tandis que pour un livre classique, le prix est fixe et l’essentiel revient à l’éditeur. Cette rémunération directe de l’auteur est dans le même esprit que la rémunération directe des agriculteurs et des artistes. Elle court-circuite les marchands, qui ne produisent rien. Mais les lecteurs peuvent également choisir d’utiliser ce livre électronique sans payer, car le savoir doit rester librement accessible. Cette auto-édition et auto-diffusion est dans l’esprit de ce que prône Richard M. Stallman. Vive la révolution numérique !

The next week will be very busy for me. I have to give no more than three talks in three different places. The first talk will present the beautiful and now classical Azuma-Hoeffding concentration inequality. You may take a look at the notes prepared for this talk, in French. Late update : you may also take a look at the notes of my third and last talk (in English).

This short post is devoted to an intriguing random walk on the unitary group. Namely, let us fix an integer \( {d\geq1} \) and pick some \( {d\times d} \) unitary matrix \( {U_0} \) from the unitary group \( {\mathbb{U}} \). From the spectral theorem, there exists a unitary matrix \( {U_1} \) in \( {\mathbb{U}} \) such that \( {U_1U_0U_1^*} \) is diagonal with diagonal elements in the unit circle of \( {\mathbb{C}} \). This unitary diagonalization is not unique, and we may pick \( {U_1} \) at random uniformly among the possibilities. This can be written as \( {U_1=f(U_0,\varepsilon_1)} \) where \( {\varepsilon_1} \) is a random variable. Now, we define the sequence \( {{(U_n)}_{n\geq0}} \) by

\[ U_{n+1}=f(U_n,\varepsilon_{n+1}) \]

where \( {{(\varepsilon_n)}_{n\geq1}} \) is an auxiliary i.i.d. sequence, chosen independent of \( {U_0} \) which may be taken at random. This defines a random walk, or a Markov chain if one prefers, on the unitary group \( {\mathbb{U}} \). What do we know about this chain? I have never met this chain before.

Let us say that \( {Q\in\mathbb{U}} \) is a complex permutation matrix when there exists a permutation \( {\sigma} \) of \( {\{1,\ldots,d\}} \) and phases \( {\varphi_1,\ldots,\varphi_d} \) (i.e. complex numbers of unit module) such that

\[ Q_{i,j}=\varphi_i\mathbf{1}_{j=\sigma(i)} \]

for every \( {1\leq i,j\leq d} \). This is equivalent to say that there exists a diagonal matrix \( {D\in\mathbb{U}} \) and a permutation matrix \( {P} \) such that \( {Q=DP} \). Note that \( {Q=DP=PP^{-1}DP=PD’} \) where \( {D’} \) is like \( {D} \). The set of complex permutation matrices is a sub-group of \( {\mathbb{U}} \). If \( {M} \) is a \( {d\times d} \) matrix and \( {Q} \) is a complex permutation matrix, then \( {QM} \) is obtained from \( {M} \) by permuting the rows and multiplying them by a phase (one for each).

Let us say that two elements \( {U} \) and \( {V} \) of \( {\mathbb{U}} \) are equivalent, and we denote \( {U\equiv V} \), when \( {V=QU} \) for some complex permutation matrix \( {Q} \). Conditional on \( {U_n} \), the law of \( {U_{n+1}} \) is uniform over an equivalent class for \( {\equiv} \). The class of \( {I_d} \) includes the commutative subgroup of \( {\mathbb{U}} \) formed by diagonal elements. This class is an irreducible communication class of the chain. In contrast, if \( {U_0} \) is a permutation matrix not equal to the identity then \( {U_1} \) belongs to the class of a sort of bloc circulant Vandermonde matrix given by the roots of unity associated to the cycles decomposition of the permutation. On the other hand, the Haar probability measure on \( {\mathbb{U}} \) is invariant for the chain. How about the spectral decomposition of the chain and its trend to the equilibrium? The convergence seems to be very fast on simulations.

Note that one may start the chain from the eigenvectors matrix of an arbitrary \( {d\times d} \) random matrix \( {X} \) using the unitary Schur decomposition.